Smallest Range

Given k sorted integer arrays, pick k elements (one element from each of sorted arrays), what is the smallest range.

Assumptions:

k >= 2
None of the k arrays is null or empty

Examples:

{ { 1, 4, 6 },

{ 2, 5 },

{ 8, 10, 15} }

pick one element from each of 3 arrays, the smallest range is {5, 8} (pick 6 from the first array, pick 5 from the second array and pick 8 from the third array).

import heapq
class Solution(object):
  def smallestRange(self, arrays):
    heap = []
    max_val = arrays[0][0]
    for i in xrange(len(arrays)):
      heapq.heappush(heap,(arrays[i][0],i,0))
      max_val = max(max_val,arrays[i][0])
    min_range = [-10**5, 10**5]
    while heap:
      min_val, i, j = heapq.heappop(heap)
      if max_val - min_val < min_range[1] - min_range[0] or (max_val - min_val == min_range[1] - min_range[0] and min_val < min_range[0]):
        min_range = [min_val,max_val]
      if  j + 1 < len(arrays[i]):
        max_val = max(max_val,arrays[i][j+1])
        heapq.heappush(heap,(arrays[i][j+1],i,j+1))
      else:
        return min_range