Given K sorted lists of integers, KSortedArray[] of size N each. The task is to find the smallest range that includes at least one element from each of the K lists. If more than one such range's are found, return the first such range found.
Example 1:
Input:
N = 5, K = 3
KSortedArray[][] = {{1 3 5 7 9},
                    {0 2 4 6 8},
                    {2 3 5 7 11}}
Output: 1 2
Explanation: K = 3
A:[1 3 5 7 9]
B:[0 2 4 6 8]
C:[2 3 5 7 11]
Smallest range is formed by number 1
present in first list and 2 is present
in both 2nd and 3rd list.
Example 2:
Input:
N = 4, K = 3
KSortedArray[][] = {{1 2 3 4},
                    {5 6 7 8},
                    {9 10 11 12}}
Output: 4 9
Your Task : 
Complete the function findSmallestRange() that receives array , array size n and k as parameters and returns the output range (as a pair in cpp and array of size 2 in java and python)
Expected Time Complexity : O(n * k *log k)
Expected Auxilliary Space  : O(k)
Constraints:
1 <= K,N <= 500
0 <= a[ i ] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def smallestRange(self, KSortedArray, n, k):
        # code here
        # print the smallest range in a new line

Solutions:
from heapq import *

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		a = KSortedArray
		dibba = []
		(start, end) = (0, 0)
		mini = 99999999999
		maxi = -99999999999
		for i in range(k):
			mini = min(a[i][0], mini)
			maxi = max(a[i][0], maxi)
			heappush(dibba, (a[i][0], i, 0))
		(start, end) = (mini, maxi)
		while len(dibba) >= k:
			top = heappop(dibba)
			mini = top[0]
			if maxi - mini < end - start:
				start = mini
				end = maxi
			if top[2] + 1 < n:
				heappush(dibba, (a[top[1]][top[2] + 1], top[1], top[2] + 1))
				maxi = max(maxi, a[top[1]][top[2] + 1])
		return [start, end]


import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, K):
		K = len(KSortedArray)
		minHeap = []
		currentMax = float('-inf')
		for i in range(K):
			element = KSortedArray[i][0]
			heapq.heappush(minHeap, (element, i, 0))
			currentMax = max(currentMax, element)
		rangeStart = float('-inf')
		rangeEnd = float('inf')
		while True:
			(minElement, listIndex, elementIndex) = heapq.heappop(minHeap)
			if currentMax - minElement < rangeEnd - rangeStart:
				rangeStart = minElement
				rangeEnd = currentMax
			elementIndex += 1
			if elementIndex >= len(KSortedArray[listIndex]):
				break
			element = KSortedArray[listIndex][elementIndex]
			heapq.heappush(minHeap, (element, listIndex, elementIndex))
			currentMax = max(currentMax, element)
		return (rangeStart, rangeEnd)


import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		myl = []
		rangeMax = float('-inf')
		for i in range(k):
			myl.append((KSortedArray[i][0], i, 0))
			if KSortedArray[i][0] > rangeMax:
				rangeMax = KSortedArray[i][0]
		heapq.heapify(myl)
		diff = float('inf')
		inner = 0
		outer = 0
		while inner < n:
			curr = heapq.heappop(myl)
			rangeMin = curr[0]
			currsum = rangeMax - rangeMin
			if currsum < diff:
				diff = currsum
				res = [rangeMin, rangeMax]
			if diff == 0:
				break
			outer = curr[1]
			inner = curr[2] + 1
			if inner < n:
				heapq.heappush(myl, (KSortedArray[outer][inner], outer, inner))
				if KSortedArray[outer][inner] > rangeMax:
					rangeMax = KSortedArray[outer][inner]
			else:
				break
		return res


import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		heap = []
		maxvalue = 0
		for i in range(k):
			heapq.heappush(heap, [KSortedArray[i][0], i, 0])
			maxvalue = max(maxvalue, KSortedArray[i][0])
		heapq.heapify(heap)
		answer = [heap[0][0], maxvalue]
		while True:
			(_, row, col) = heapq.heappop(heap)
			if col == len(KSortedArray[row]) - 1:
				break
			next_num = KSortedArray[row][col + 1]
			maxvalue = max(maxvalue, next_num)
			heapq.heappush(heap, [next_num, row, col + 1])
			if maxvalue - heap[0][0] < answer[1] - answer[0]:
				answer = [heap[0][0], maxvalue]
		return answer


from sys import maxsize
import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		min_heap = []
		maxi = -maxsize
		mini = maxsize
		for i in range(k):
			heapq.heappush(min_heap, (KSortedArray[i][0], i, 0))
			maxi = max(maxi, KSortedArray[i][0])
			mini = min(mini, KSortedArray[i][0])
		(start, end) = (mini, maxi)
		while min_heap:
			(mini, pos, idx) = heapq.heappop(min_heap)
			if maxi - mini < end - start:
				(start, end) = (mini, maxi)
			if idx + 1 < len(KSortedArray[pos]):
				heapq.heappush(min_heap, (KSortedArray[pos][idx + 1], pos, idx + 1))
				maxi = max(maxi, KSortedArray[pos][idx + 1])
			else:
				break
		return (start, end)


from heapq import heappush, heappop

class Solution:

	def smallestRange(self, a, n, k):
		q = []
		mini = 10 ** 9
		maxi = -10 ** 9
		r = 10 ** 9
		(low, high) = (0, 0)
		for i in range(k):
			heappush(q, [a[i][0], [i, 0]])
			mini = min(mini, a[i][0])
			maxi = max(maxi, a[i][0])
		while True:
			temp = heappop(q)
			mn = temp[0]
			if r > maxi - mn:
				r = maxi - mn
				low = mn
				high = maxi
			i = temp[1][0]
			j = temp[1][1]
			if j == n - 1:
				break
			heappush(q, [a[i][j + 1], [i, j + 1]])
			if maxi < a[i][j + 1]:
				maxi = a[i][j + 1]
		return [low, high]


from heapq import *

class Solution:

	def smallestRange(self, grid, n, k):
		h = []
		maxdiff = 100000
		ans = [0, 0]
		m = 0
		for i in range(k):
			heappush(h, [grid[i][0], i, 0])
			m = max(m, grid[i][0])
		while h:
			if maxdiff > m - h[0][0]:
				maxdiff = m - h[0][0]
				ans = [h[0][0], m]
			(_, i, j) = heappop(h)
			j += 1
			if j < n:
				m = max(m, grid[i][j])
				heappush(h, [grid[i][j], i, j])
			else:
				break
		return ans


import heapq as h

class Solution:

	def smallestRange(self, a, n, k):
		heap = []
		start = 0
		end = 0
		j = 0
		mini = 99999999999
		maxi = -99999999999
		for i in range(k):
			mini = min(a[i][0], mini)
			maxi = max(a[i][0], maxi)
			h.heappush(heap, (a[i][0], i, 0))
			j += 1
		(start, end) = (mini, maxi)
		while j >= k:
			top = h.heappop(heap)
			j -= 1
			mini = top[0]
			if maxi - mini < end - start:
				start = mini
				end = maxi
			if top[2] + 1 < n:
				h.heappush(heap, (a[top[1]][top[2] + 1], top[1], top[2] + 1))
				j += 1
				maxi = max(maxi, a[top[1]][top[2] + 1])
		return [start, end]


import heapq

class Solution:

	def smallestRange(self, arr, n, k):
		h = []
		maxval = -100000000.0
		minval = 100000000.0
		start = end = 0
		n = len(arr)
		n2 = len(arr[0])
		for i in range(n):
			heapq.heappush(h, (arr[i][0], i, 1))
			maxval = max(maxval, arr[i][0])
		rang = 100000000.0
		while True:
			top = heapq.heappop(h)
			minval = top[0]
			if rang > maxval - minval + 1:
				rang = maxval - minval + 1
				start = minval
				end = maxval
			if top[2] < n2:
				heapq.heappush(h, (arr[top[1]][top[2]], top[1], top[2] + 1))
				maxval = max(maxval, arr[top[1]][top[2]])
			else:
				break
		return (start, end)


import heapq

class Solution:

	def smallestRange(self, numbers, n, k):
		minheap = []
		maxx = -float('inf')
		for i in range(k):
			heapq.heappush(minheap, (numbers[i][0], i, 0))
			maxx = max(numbers[i][0], maxx)
		heapq.heapify(minheap)
		diff = maxx - minheap[0][0]
		ans = [minheap[0][0], maxx]
		while True:
			(mini, r, c) = heapq.heappop(minheap)
			if diff > maxx - mini:
				diff = maxx - mini
				ans = [mini, maxx]
			if c + 1 >= len(numbers[r]):
				break
			num = numbers[r][c + 1]
			maxx = max(maxx, num)
			heapq.heappush(minheap, (num, r, c + 1))
		return ans


from collections import defaultdict

class Solution:

	def smallestRange(self, arr, k, n):
		lis = []
		for i in range(n):
			for item in arr[i]:
				lis.append([item, i])
		lis.sort()
		ind = 0
		(left, right) = (0, 0)
		cnt = 0
		mnrange = 1000000000.0
		d = defaultdict(int)
		l = len(lis)
		for i in range(l):
			(curnum, curindex) = lis[i]
			if d[curindex] == 0:
				cnt += 1
			d[curindex] += 1
			while cnt == n:
				(num, index) = lis[ind]
				if curnum - num < mnrange:
					(left, right) = (num, curnum)
					mnrange = curnum - num
				d[index] -= 1
				if d[index] == 0:
					cnt -= 1
				ind += 1
		return [left, right]


import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		a = KSortedArray
		heap = []
		maxx = -99999999999
		for i in range(k):
			heapq.heappush(heap, (a[i][0], i, 0))
			maxx = max(a[i][0], maxx)
		heapq.heapify(heap)
		diff = maxx - heap[0][0]
		ans = [heap[0][0], maxx]
		while True:
			(mini, r, c) = heapq.heappop(heap)
			if diff > maxx - mini:
				diff = maxx - mini
				ans = [mini, maxx]
			if c + 1 >= n:
				break
			num = a[r][c + 1]
			maxx = max(maxx, num)
			heapq.heappush(heap, (num, r, c + 1))
		return ans


from heapq import *

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		a = KSortedArray
		heap = []
		s = 0
		e = 0
		mi = 9999999999
		mx = -9999999999
		for i in range(k):
			mx = max(mx, a[i][0])
			mi = min(mi, a[i][0])
			heappush(heap, (a[i][0], i, 0))
		(s, e) = (mi, mx)
		while len(heap) >= k:
			top = heappop(heap)
			mi = top[0]
			if mx - mi < e - s:
				s = mi
				e = mx
			if top[2] + 1 < n:
				heappush(heap, (a[top[1]][top[2] + 1], top[1], top[2] + 1))
				mx = max(mx, a[top[1]][top[2] + 1])
		return [s, e]


import sys
import heapq

class Solution:

	def smallestRangeBF(self, KSortedArray, n, k):
		all_elems = [x for arr in KSortedArray for x in arr]
		ranges = [(a, b) if a < b else (b, a) for a in all_elems for b in all_elems]
		ranges.sort(key=lambda x: x[0])
		diff = sys.maxsize
		last_range = []
		for r in ranges:
			d = r[1] - r[0] + 1
			if d < diff:
				count = 0
				for i in range(k):
					is_exist = False
					for j in range(n):
						if r[0] <= KSortedArray[i][j] <= r[1]:
							is_exist = True
							break
					count = count + 1 if is_exist else count
				if count == k:
					last_range = r if d < diff else last_range
					diff = d
		return last_range

	def smallestRange(self, KSortedArray, n, k):
		mini = sys.maxsize
		maxi = -1
		min_heap = []
		for i in range(k):
			data = KSortedArray[i][0]
			heapq.heappush(min_heap, (data, i, 0))
			mini = min(mini, data)
			maxi = max(maxi, data)
		(start, end) = (mini, maxi)
		while len(min_heap):
			temp = heapq.heappop(min_heap)
			mini = temp[0]
			if maxi - mini < end - start:
				(start, end) = (mini, maxi)
			(i, j) = (temp[1], temp[2])
			if j + 1 < len(KSortedArray[i]):
				data = KSortedArray[i][j + 1]
				maxi = max(maxi, data)
				heapq.heappush(min_heap, (data, i, j + 1))
			else:
				break
		return (start, end)


import heapq as hq

class Solution:

	def smallestRange(self, a, n, k):
		heap = []
		start = 0
		end = 0
		mini = float('inf')
		maxi = float('-inf')
		for i in range(k):
			mini = min(a[i][0], mini)
			maxi = max(a[i][0], maxi)
			hq.heappush(heap, (a[i][0], i, 0))
		(start, end) = (mini, maxi)
		while len(heap) >= k:
			(ele, row, col) = hq.heappop(heap)
			mini = ele
			if maxi - mini < end - start:
				start = mini
				end = maxi
			if col + 1 < n:
				hq.heappush(heap, (a[row][col + 1], row, col + 1))
				maxi = max(maxi, a[row][col + 1])
		return [start, end]


from heapq import *

class Solution:

	def smallestRange(self, a, n, k):
		heap = []
		start = 0
		end = 0
		mini = float('inf')
		maxi = -float('inf')
		for i in range(k):
			mini = min(a[i][0], mini)
			maxi = max(a[i][0], maxi)
			heappush(heap, (a[i][0], i, 0))
		(start, end) = (mini, maxi)
		while len(heap) >= k:
			top = heappop(heap)
			mini = top[0]
			if maxi - mini < end - start:
				start = mini
				end = maxi
			if top[2] + 1 < n:
				heappush(heap, (a[top[1]][top[2] + 1], top[1], top[2] + 1))
				maxi = max(maxi, a[top[1]][top[2] + 1])
		return [start, end]


class Solution:

	def smallestRange(self, KSortedArray, n, k):
		from heapq import heappush, heappop
		arr = KSortedArray
		min_heap = []
		maxi = 0
		for i in range(k):
			heappush(min_heap, (arr[i][0], i, 0))
			maxi = max(maxi, arr[i][0])
		mini = min_heap[0][0]
		j = 0
		ans = [mini, maxi]
		dis = maxi - mini
		while min_heap:
			(x, i, j) = heappop(min_heap)
			j += 1
			if j < n:
				heappush(min_heap, (arr[i][j], i, j))
				maxi = max(maxi, arr[i][j])
			else:
				break
			mini = min_heap[0][0]
			if maxi - mini < dis:
				dis = maxi - mini
				ans = [mini, maxi]
		return ans


from heapq import heappush, heappop

class Solution:

	def smallestRange(self, a, n, k):
		min_diff = float('inf')
		res = []
		heap = []
		max_val = float('-inf')
		for i in range(k):
			heappush(heap, (a[i][0], 0, i))
			max_val = max(max_val, a[i][0])
		while heap:
			(min_val, index, arr_index) = heappop(heap)
			if min_diff > max_val - min_val:
				min_diff = max_val - min_val
				res = [min_val, max_val]
			if index == n - 1:
				break
			heappush(heap, (a[arr_index][index + 1], index + 1, arr_index))
			max_val = max(max_val, a[arr_index][index + 1])
		return res


import heapq

class Solution:

	def smallestRange(self, a, n, k):
		mini = float('inf')
		maxi = float('-inf')
		h = []
		heapq.heapify(h)
		for i in range(k):
			ele = a[i][0]
			mini = min(mini, ele)
			maxi = max(maxi, ele)
			heapq.heappush(h, [ele, i, 0])
		start = mini
		end = maxi
		while len(h) != 0:
			temp = heapq.heappop(h)
			mini = temp[0]
			if maxi - mini < end - start:
				start = mini
				end = maxi
			if temp[2] + 1 < n:
				maxi = max(maxi, a[temp[1]][temp[2] + 1])
				heapq.heappush(h, [a[temp[1]][temp[2] + 1], temp[1], temp[2] + 1])
			else:
				break
		return [start, end]


import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		min_range = float('inf')
		max_range = float('-inf')
		range_start = 0
		range_end = 0
		min_heap = []
		for i in range(k):
			heapq.heappush(min_heap, (KSortedArray[i][0], i, 0))
			max_range = max(max_range, KSortedArray[i][0])
		while len(min_heap) == k:
			(curr_min, list_index, element_index) = heapq.heappop(min_heap)
			if max_range - curr_min < min_range:
				min_range = max_range - curr_min
				range_start = curr_min
				range_end = max_range
			if element_index + 1 < n:
				heapq.heappush(min_heap, (KSortedArray[list_index][element_index + 1], list_index, element_index + 1))
				max_range = max(max_range, KSortedArray[list_index][element_index + 1])
		return [range_start, range_end]


from heapq import heappush, heappop

class Solution:

	def smallestRange(self, arr, n, k):
		heap = []
		min_range = float('inf')
		(start, end) = (-1, -1)
		(maxi, mini) = (float('-inf'), float('inf'))
		for i in range(k):
			maxi = max(maxi, arr[i][0])
			mini = min(mini, arr[i][0])
			heappush(heap, (arr[i][0], i, 0))
		min_range = maxi - mini
		(start, end) = (mini, maxi)
		while heap:
			(num, r, c) = heappop(heap)
			if c == n - 1:
				break
			heappush(heap, (arr[r][c + 1], r, c + 1))
			mini = heap[0][0]
			maxi = max(maxi, arr[r][c + 1])
			if maxi - mini < min_range:
				min_range = maxi - mini
				(start, end) = (mini, maxi)
		return (start, end)


import heapq

class Solution:

	def smallestRange(self, arr, n, k):
		q = []
		ans = 10 ** 10
		rg = []
		(mn, mx) = (10 ** 10, -10 ** 10)
		for i in range(k):
			heapq.heappush(q, [arr[i][0], i, 1])
			mx = max(mx, arr[i][0])
		while True:
			temp = heapq.heappop(q)
			mn = temp[0]
			if mx - mn + 1 < ans:
				ans = mx - mn + 1
				rg = [mn, mx]
			if temp[2] < n:
				temp[0] = arr[temp[1]][temp[2]]
				temp[2] += 1
				heapq.heappush(q, temp)
				mx = max(mx, temp[0])
			else:
				break
		return rg


import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		pq = []
		for (i, j) in enumerate(KSortedArray):
			pq.append([j[0], i, 0])
		right = -1
		for i in pq:
			right = max(right, i[0])
		heapq.heapify(pq)
		ans = [-1000000000.0, 1000000000.0]
		while pq:
			(left, array_num, index) = heapq.heappop(pq)
			if right - left < ans[1] - ans[0]:
				ans = [left, right]
			if index + 1 == len(KSortedArray[array_num]):
				return ans
			v = KSortedArray[array_num][index + 1]
			right = max(right, v)
			heapq.heappush(pq, [KSortedArray[array_num][index + 1], array_num, index + 1])


import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		tri = []
		r = ()
		diff = 2e+31
		heapq.heapify(tri)
		ixs = [0] * k
		res = [None] * k
		for i in range(k):
			s = heapq.heappop(KSortedArray[i])
			heapq.heappush(tri, (s, i))
			res[i] = s
		res.sort()
		mx = res[-1]
		while len(tri):
			v = heapq.heappop(tri)
			mn = v[0]
			if mx - mn < diff:
				diff = mx - mn
				r = (mn, mx)
			if ixs[v[1]] < n - 1:
				ixs[v[1]] += 1
				s = heapq.heappop(KSortedArray[v[1]])
				heapq.heappush(tri, (s, v[1]))
				res[v[1]] = s
				if s > mx:
					mx = s
			else:
				break
		return r


import heapq as hq

class Solution:

	def smallestRange(self, A, n, k):
		mnh = []
		mx = float('-inf')
		for (r, a) in enumerate(A):
			mx = max(mx, a[0])
			hq.heappush(mnh, (a[0], r, 0))
		ans = [mnh[0][0], mx]
		while mnh:
			(v, r, c) = hq.heappop(mnh)
			if mx - v < ans[1] - ans[0]:
				ans = [v, mx]
			if c + 1 == n:
				return ans
			mx = max(mx, A[r][c + 1])
			hq.heappush(mnh, (A[r][c + 1], r, c + 1))
		return ans


import heapq

class Solution:

	def smallestRange(self, mat, n, k):
		minheap = []
		maxi = -10 ** 9
		for i in range(k):
			heapq.heappush(minheap, [mat[i][0], i, 0])
			maxi = max(maxi, mat[i][0])
		diff = maxi - minheap[0][0]
		ans = [minheap[0][0], maxi]
		while minheap:
			(val, r, c) = heapq.heappop(minheap)
			if diff > maxi - val:
				diff = maxi - val
				ans = [val, maxi]
			if c + 1 >= n:
				break
			heapq.heappush(minheap, [mat[r][c + 1], r, c + 1])
			maxi = max(maxi, mat[r][c + 1])
		return ans


import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		heap = []
		maxi = 0
		rangee = 10000000000
		for i in range(len(KSortedArray)):
			maxi = max(maxi, KSortedArray[i][0])
			heapq.heappush(heap, [KSortedArray[i][0], i, 0])
		while len(heap) >= k:
			(mini, arrayno, idx) = heapq.heappop(heap)
			if maxi - mini < rangee:
				rangee = min(rangee, maxi - mini)
				start = mini
				end = maxi
			if idx + 1 < n:
				heapq.heappush(heap, [KSortedArray[arrayno][idx + 1], arrayno, idx + 1])
				maxi = max(maxi, KSortedArray[arrayno][idx + 1])
		return [start, end]


from heapq import heapify, heappush, heappop

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		heap = [(row[0], i, 0) for (i, row) in enumerate(KSortedArray)]
		heapify(heap)
		right = max((row[0] for row in KSortedArray))
		ans = (-1000000000.0, 1000000000.0)
		while heap:
			(left, i, j) = heappop(heap)
			if right - left < ans[1] - ans[0]:
				ans = (left, right)
			if j + 1 == n:
				return ans
			next = KSortedArray[i][j + 1]
			right = max(right, next)
			heappush(heap, (next, i, j + 1))


import heapq

class Solution:

	def smallestRange(self, kSortedArray, n, k):
		min_heap = []
		curr_min = curr_max = 0
		for i in range(k):
			min_heap.append([kSortedArray[i][0], i, 0])
			curr_max = max(curr_max, kSortedArray[i][0])
		heapq.heapify(min_heap)
		curr_min = min_heap[0][0]
		res_min = curr_min
		res_max = curr_max
		while min_heap:
			(curr_min, r_idx, c_idx) = heapq.heappop(min_heap)
			if curr_max - curr_min < res_max - res_min:
				res_min = curr_min
				res_max = curr_max
			c_idx += 1
			if c_idx < n:
				curr_max = max(curr_max, kSortedArray[r_idx][c_idx])
				heapq.heappush(min_heap, [kSortedArray[r_idx][c_idx], r_idx, c_idx])
			else:
				break
		return [res_min, res_max]


import heapq

class Solution:

	def smallestRange(self, A, n, k):
		pq = [(row[0], i, 0) for (i, row) in enumerate(A)]
		heapq.heapify(pq)
		ans = (-1000000000.0, 1000000000.0)
		right = max((row[0] for row in A))
		while pq:
			(left, i, j) = heapq.heappop(pq)
			if right - left < ans[1] - ans[0]:
				ans = (left, right)
			if j + 1 == len(A[i]):
				return ans
			v = A[i][j + 1]
			right = max(right, v)
			heapq.heappush(pq, (v, i, j + 1))


import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		(start_point, end_point) = (float('-inf'), float('inf'))
		max_value = float('-inf')
		heap = []
		for i in range(k):
			element = KSortedArray[i][0]
			max_value = max(max_value, element)
			heapq.heappush(heap, (element, i, 0))
		while len(KSortedArray) == len(heap):
			(value, arr_pos, col_pos) = heapq.heappop(heap)
			if max_value - value < end_point - start_point:
				start_point = value
				end_point = max_value
			if col_pos + 1 >= len(KSortedArray[arr_pos]):
				break
			num = KSortedArray[arr_pos][col_pos + 1]
			max_value = max(max_value, num)
			heapq.heappush(heap, (num, arr_pos, col_pos + 1))
		return [start_point, end_point]


import heapq

class Solution:

	def smallestRange(self, arr, n, k):
		mini = float('inf')
		maxi = float('-inf')
		heap = []
		for i in range(k):
			heapq.heappush(heap, [arr[i][0], i, 0])
			mini = min(mini, arr[i][0])
			maxi = max(maxi, arr[i][0])
		ans = [mini, maxi]
		rng = maxi - mini
		while heap:
			[mini, i, j] = heapq.heappop(heap)
			if maxi - mini < rng:
				rng = maxi - mini
				ans = [mini, maxi]
			if j + 1 < n:
				maxi = max(maxi, arr[i][j + 1])
				heapq.heappush(heap, [arr[i][j + 1], i, j + 1])
			else:
				break
		return ans


import heapq

class Solution:

	def smallestRange(self, array, n, k):
		heapQ = [(row[0], i, 0) for (i, row) in enumerate(array)]
		heapq.heapify(heapQ)
		maximum = max((row[0] for row in array))
		result = [-1, 1000000]
		while heapQ:
			(value, i, index) = heapq.heappop(heapQ)
			if maximum - value < result[1] - result[0]:
				result = [value, maximum]
			if index + 1 == n:
				return result
			next_value = array[i][index + 1]
			maximum = max(next_value, maximum)
			heapq.heappush(heapQ, (next_value, i, index + 1))
		return result


import heapq

class heap:

	class minHeap:

		def __init__(self):
			self.myheap = list()

		def pop(self):
			if not self.myheap:
				return -1
			return heapq.heappop(self.myheap)

		def push(self, x):
			heapq.heappush(self.myheap, x)
			return None

		def heapify(self, listt):
			self.myheap.extend(listt)
			heapq.heapify(self.myheap)
			return None

class Solution:

	def smallestRange(self, array, n, k):
		heapQ = heap.minHeap()
		listt = [(row[0], i, 0) for (i, row) in enumerate(array)]
		heapQ.heapify(listt)
		maximum = max((row[0] for row in array))
		result = [-1, 1000000]
		while heap:
			(value, i, index) = heapQ.pop()
			if maximum - value < result[1] - result[0]:
				result = [value, maximum]
			if index + 1 == n:
				return result
			next_value = array[i][index + 1]
			maximum = max(maximum, next_value)
			heapQ.push((next_value, i, index + 1))
		return result


import heapq

class Solution:

	def smallestRange(self, array, n, k):
		heap = [(row[0], i, 0) for (i, row) in enumerate(array)]
		heapq.heapify(heap)
		local_maximum = max((row[0] for row in array))
		inf = 1000000
		result = [-inf, inf]
		while heap:
			(local_minimum, num_list, local_min_index) = heapq.heappop(heap)
			if local_maximum - local_minimum < result[1] - result[0]:
				result = [local_minimum, local_maximum]
			if local_min_index + 1 == len(array[num_list]):
				return result
			next_val = array[num_list][local_min_index + 1]
			local_maximum = max(next_val, local_maximum)
			heapq.heappush(heap, (next_val, num_list, local_min_index + 1))
		return result


class Solution:

	def smallestRange(self, nums, n, k):
		from bisect import bisect
		q = []
		for (i, ele) in enumerate(nums):
			x = bisect(q, [ele[-1], i])
			q.insert(x, [ele[-1], i])
		ans = [q[0][0], q[-1][0]]
		while True:
			ele = q.pop()
			max_ind = ele[1]
			nums[max_ind].pop()
			if len(nums[max_ind]) == 0:
				return ans
			x = bisect(q, [nums[max_ind][-1], max_ind])
			q.insert(x, [nums[max_ind][-1], max_ind])
			max_ele = q[-1][0]
			min_ele = q[0][0]
			if max_ele - min_ele <= ans[1] - ans[0]:
				ans[0] = min_ele
				ans[1] = max_ele


import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		hp = []
		mx = -99999
		mn = 99999
		for i in range(k):
			heapq.heappush(hp, (KSortedArray[i][0], i))
			mx = max(mx, KSortedArray[i][0])
			mn = min(mn, KSortedArray[i][0])
			KSortedArray[i].pop(0)
		mnr = (mn, mx)
		while len(hp) == k:
			el = heapq.heappop(hp)
			if len(KSortedArray[el[1]]) > 0:
				new = KSortedArray[el[1]].pop(0)
				mx = max(mx, new)
				heapq.heappush(hp, (new, el[1]))
				mn = hp[0][0]
				if mnr[1] - mnr[0] > mx - mn:
					mnr = (mn, mx)
		return mnr


import heapq

class Key:

	def __init__(self, data, row, column):
		self.data = data
		self.row = row
		self.column = column

	def __lt__(self, other):
		return self.data < other.data

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		a = KSortedArray
		heap = []
		heapq.heapify(heap)
		start = 0
		end = 0
		mini = float('inf')
		maxi = float('-inf')
		for i in range(k):
			mini = min(a[i][0], mini)
			maxi = max(a[i][0], maxi)
			heapq.heappush(heap, (a[i][0], i, 0))
		(start, end) = (mini, maxi)
		while len(heap) >= k:
			top = heapq.heappop(heap)
			mini = top[0]
			if maxi - mini < end - start:
				start = mini
				end = maxi
			if top[2] + 1 < n:
				heapq.heappush(heap, (a[top[1]][top[2] + 1], top[1], top[2] + 1))
				maxi = max(maxi, a[top[1]][top[2] + 1])
		return [start, end]


from heapq import *

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		heap = [(row[0], i, 0) for (i, row) in enumerate(KSortedArray)]
		heapify(heap)
		end = max((row[0] for row in KSortedArray))
		ans = (heap[0][0], end)
		while len(heap) == k:
			(start, i, j) = heappop(heap)
			if end - start + 1 < ans[1] - ans[0] + 1:
				ans = (start, end)
			if j + 1 < n:
				heappush(heap, (KSortedArray[i][j + 1], i, j + 1))
				end = max(end, KSortedArray[i][j + 1])
		return ans


from heapq import *

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		store = []
		mini = 898989898
		maxi = -98984654654
		start = end = 0
		for i in range(k):
			mini = min(mini, KSortedArray[i][0])
			maxi = max(maxi, KSortedArray[i][0])
			heappush(store, (KSortedArray[i][0], i, 0))
		start = mini
		end = maxi
		while len(store) >= k:
			top = heappop(store)
			mini = top[0]
			if maxi - mini < end - start:
				start = mini
				end = maxi
			if top[2] + 1 < n:
				heappush(store, (KSortedArray[top[1]][top[2] + 1], top[1], top[2] + 1))
				maxi = max(maxi, KSortedArray[top[1]][top[2] + 1])
		return [start, end]


from heapq import heappush, heappop

class Solution:

	def smallestRange(self, a, n, k):
		h = []
		maxTillNow = -1
		for i in range(k):
			heappush(h, (a[i][0], i, 0))
			maxTillNow = max(maxTillNow, a[i][0])
		slot = [0, 0]
		slotL = 1 << 31
		while h:
			(value, i, j) = heappop(h)
			if maxTillNow - value < slotL:
				slotL = maxTillNow - value
				(slot[0], slot[1]) = (value, maxTillNow)
			if j + 1 < n:
				heappush(h, (a[i][j + 1], i, j + 1))
				maxTillNow = max(maxTillNow, a[i][j + 1])
			else:
				break
		return slot


class Solution:

	def smallestRange(self, KSortedArray, n, k):
		range = [-100000, 100000]
		list = sorted([(item, i) for (i, sublist) in enumerate(KSortedArray) for item in sublist])
		(i, j) = (0, 0)
		dict = {}
		groups = 0
		while j < len(list):
			group = list[j][1]
			dict[group] = dict.get(group, 0) + 1
			if dict[group] == 1:
				groups += 1
			while groups == k:
				a = list[i][0]
				b = list[j][0]
				c = range[0]
				d = range[1]
				if b - a < d - c:
					range[0] = a
					range[1] = b
				dict[list[i][1]] -= 1
				if dict[list[i][1]] == 0:
					groups -= 1
				i += 1
			j += 1
		return range


import heapq

class Solution:

	def smallestRange(self, KSortedArray, n, k):
		h = []
		(tmx, tmn) = (0, 100000)
		(mx, mn) = (0, 100000)
		for i in range(k):
			heapq.heappush(h, (KSortedArray[i][0], i))
			mx = max(mx, KSortedArray[i][0])
			mn = min(mn, KSortedArray[i][0])
			KSortedArray[i].remove(KSortedArray[i][0])
		tmx = mx
		tmn = mn
		while h:
			(temp, i) = heapq.heappop(h)
			if len(h) == k - 1:
				tmn = temp
			if tmx - tmn < mx - mn:
				mn = tmn
				mx = tmx
			if len(KSortedArray[i]) != 0:
				heapq.heappush(h, (KSortedArray[i][0], i))
				tmx = max(KSortedArray[i][0], tmx)
				KSortedArray[i].remove(KSortedArray[i][0])
		return (mn, mx)