aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--smallest_range_convering_elem_k.c67
-rw-r--r--smallest_range_convering_elem_k.py37
2 files changed, 104 insertions, 0 deletions
diff --git a/smallest_range_convering_elem_k.c b/smallest_range_convering_elem_k.c
new file mode 100644
index 0000000..3cb4a3d
--- /dev/null
+++ b/smallest_range_convering_elem_k.c
@@ -0,0 +1,67 @@
+// 632. Smallest Range Covering Elements from K Lists
+#include "leetcode.h"
+
+/*
+ * 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'
+ */
+
+int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
+
+int *smallestRange(int **nums, int numsSize, int *numsColSize,
+ int *returnSize) {
+ int n = 0, idx = 0;
+ for (int i = 0; i < numsSize; i++)
+ n += numsColSize[i];
+ int *data = (int *)calloc(n, sizeof(int));
+ for (int i = 0; i < numsSize; i++)
+ for (int j = 0; j < numsColSize[i]; j++)
+ data[idx++] = nums[i][j] * 4096 | i;
+ qsort(data, n, sizeof(int), cmp);
+ int *ans = (int *)calloc(2, sizeof(int));
+ int left = 0, right = 0, list_cnt = 0,
+ min_range = (data[n - 1] >> 12) - (data[0] >> 1);
+ ans[0] = data[0] >> 12;
+ ans[1] = data[n - 1] >> 12;
+ idx = 0;
+ memset(numsColSize, 0, numsSize * sizeof(int));
+ while (right < n) {
+ int list_idx = data[right++] & 0xFFF;
+ numsColSize[list_idx]++;
+ if (numsColSize[list_idx] == 1) {
+ list_cnt++;
+ while (list_cnt == numsSize) {
+ int diff = (data[right - 1] >> 12) - (data[left] >> 12);
+ if (diff < min_range) {
+ ans[0] = data[left] >> 12;
+ ans[1] = data[right - 1] >> 12;
+ min_range = diff;
+ }
+ list_idx = data[left++] & 0xFFF;
+ numsColSize[list_idx]--;
+ if (!numsColSize[list_idx])
+ list_cnt--;
+ }
+ }
+ }
+ *returnSize = 2;
+ free(data);
+ return ans;
+}
+
+int main() {
+ int n1[3][5] = {{4, 10, 15, 24, 26}, {0, 9, 12, 20}, {5, 18, 22, 30}},
+ ncs1 = 3, rs1;
+ int n2[3][3] = {{1, 2, 3}, {1, 2, 3}, {1, 2, 3}}, ncs2 = 3, rs2;
+ int *sr1 = smallestRange((int **)n1, ARRAY_SIZE(n1), &ncs1, &rs1);
+ int *sr2 = smallestRange((int **)n2, ARRAY_SIZE(n2), &ncs2, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", sr1[i]); // expect: 20 24
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", sr2[i]); // expect: 1 1
+ printf("\n");
+ free(sr1), free(sr2);
+}
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]]))