aboutsummaryrefslogtreecommitdiff
path: root/smallest_range_convering_elem_k.py
diff options
context:
space:
mode:
Diffstat (limited to 'smallest_range_convering_elem_k.py')
-rw-r--r--smallest_range_convering_elem_k.py37
1 files changed, 37 insertions, 0 deletions
diff --git a/smallest_range_convering_elem_k.py b/smallest_range_convering_elem_k.py
new file mode 100644
index 0000000..35b0e77
--- /dev/null
+++ b/smallest_range_convering_elem_k.py
@@ -0,0 +1,37 @@
+# 632. Smallest Range Covering Elements from K Lists
+import heapq
+
+"""
+you have 'k' lists of sorted integers in non decreasing order. find the
+smallest range that includes at least one number from each of the 'k' lists.
+we define the range '[a, b]' is smaller than the range '[c, d]' if 'b - a < d
+- c' or 'a < c' if 'b - a == d - c'
+"""
+
+
+class Solution(object):
+ def smallestRange(self, nums):
+ """
+ :type nums: List[List[int]]
+ :rtype: List[int]
+ """
+ pq = [(row[0], i, 0) for i, row in enumerate(nums)]
+ ans = -1e9, 1e9
+ right = max(row[0] for row in nums)
+ while pq:
+ left, i, j = heapq.heappop(pq)
+ if right - left < ans[1] - ans[0]:
+ ans = left, right
+ if j + 1 == len(nums[i]):
+ return ans
+ v = nums[i][j + 1]
+ right = max(right, v)
+ heapq.heappush(pq, (v, i, j + 1))
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.smallestRange(nums=[[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]])
+ )
+ print(obj.smallestRange(nums=[[1, 2, 3], [1, 2, 3], [1, 2, 3]]))