# Python with heapy, O(nlogk)

• This problem is a variant of the merge k sorted arrays. Reference can be found here: merge and shortest range.

``````import heapq
class Solution(object):
def smallestRange(self, nums):
"""
:type nums: List[List[int]]
:rtype: List[int]
"""
q = []  # element in the heap: val, i, j, where val is nums[i][j]
max_val = nums[0][0]
for i in range(len(nums)):
heapq.heappush(q, (nums[i][0], i, 0))
max_val = max(max_val, nums[i][0])  # also remember max of the heap
min_range = [-10 ** 5, 10 ** 5]
while q:
min_val, i, j = heapq.heappop(q)
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]
# push the next value in the ith array if any
if j + 1 < len(nums[i]):
max_val = max(max_val, nums[i][j + 1])
heapq.heappush(q, (nums[i][j + 1], i, j + 1))
else:  # ths ith array is exhausted
return min_range``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.