aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-05 19:26:24 -0700
committerJack Sangdahl <[email protected]>2025-03-05 19:26:24 -0700
commit38751b396e4922973ee2db29ff9eb2a22793c0bb (patch)
tree1d3ae44218e4e22b45b5333b092410ee52dba4b0
parent63f2810c6d4c7081be8ac26b6a70f9323b4ddcd1 (diff)
downloadleetcode-38751b396e4922973ee2db29ff9eb2a22793c0bb.tar.gz
leetcode-38751b396e4922973ee2db29ff9eb2a22793c0bb.zip
2965. find missing and repeated values
-rw-r--r--find_missing_repeated_val.c55
-rw-r--r--find_missing_repeated_val.py35
2 files changed, 90 insertions, 0 deletions
diff --git a/find_missing_repeated_val.c b/find_missing_repeated_val.c
new file mode 100644
index 0000000..0514a74
--- /dev/null
+++ b/find_missing_repeated_val.c
@@ -0,0 +1,55 @@
+// 2965. Find Missing and Repeated Values
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed 2d integer matrix 'grid' of size 'n * n' with
+ * values in the range '[1, n^2]'. each integer appears exactly once except 'a'
+ * which appears twice and 'b' which is missing. the task is to find the
+ * repeating and missing numbers 'a' and 'b'. return a 0-indexed integer array
+ * 'ans' of size '2' where 'ans[0]' equals to 'a' and 'ans[1]' equals 'b'.
+ */
+
+int *findMissingAndRepeatedValues(int **grid, int gridSize, int *gridColSize,
+ int *returnSize) {
+ int n = gridSize, repeated = 0, missing = 0;
+ int *cnt = (int *)calloc((n * n + 1), sizeof(int));
+ for (int i = 0; i < n; ++i)
+ for (int j = 0; j < gridColSize[i]; ++j) {
+ int num = grid[i][j];
+ cnt[num]++;
+ if (cnt[num] == 2)
+ repeated = num;
+ }
+ for (int i = 1; i <= n * n; ++i)
+ if (!cnt[i]) {
+ missing = i;
+ break;
+ }
+ int *ans = (int *)malloc(2 * sizeof(int));
+ ans[0] = repeated;
+ ans[1] = missing;
+ *returnSize = 2;
+ return ans;
+}
+
+int main() {
+ int g1i[2][2] = {{1, 3}, {2, 2}},
+ g2i[3][3] = {{9, 1, 7}, {8, 9, 2}, {3, 4, 6}};
+ struct two_d_arr g1, g2;
+ two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+ two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+ int rs1, *fmarv1 = findMissingAndRepeatedValues(g1.arr, g1.row_size,
+ g1.col_size, &rs1);
+ int rs2, *fmarv2 = findMissingAndRepeatedValues(g2.arr, g2.row_size,
+ g2.col_size, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", fmarv1[i]); // expect: 2 4
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", fmarv2[i]); // expect: 9 5
+ printf("\n");
+ free(fmarv1);
+ free(fmarv2);
+ two_d_arr_free(&g1);
+ two_d_arr_free(&g2);
+}
diff --git a/find_missing_repeated_val.py b/find_missing_repeated_val.py
new file mode 100644
index 0000000..d8a90ae
--- /dev/null
+++ b/find_missing_repeated_val.py
@@ -0,0 +1,35 @@
+# 2965. Find Missing and Repeated Values
+
+"""
+you are given a 0-indexed 2d integer matrix 'grid' of size 'n n' with
+values in the range '[1, n^2]'. each integer appears exactly once except 'a'
+which appears twice and 'b' which is missing. the task is to find the
+repeating and missing numbers 'a' and 'b'. return a 0-indexed integer array
+'ans' of size '2' where 'ans[0]' equals to 'a' and 'ans[1]' equals 'b'.
+"""
+
+
+class Solution(object):
+ def findMissingAndRepeatedValues(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: List[int]
+ """
+ repeated, missing, n = 0, 0, len(grid)
+ cnt = [0] * (n * n + 1)
+ for i in grid:
+ for j in i:
+ cnt[j] += 1
+ if cnt[j] == 2:
+ repeated = j
+ for i in range(1, n * n + 1):
+ if cnt[i] == 0:
+ missing = i
+ break
+ return [repeated, missing]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findMissingAndRepeatedValues(grid=[[1, 3], [2, 2]]))
+ print(obj.findMissingAndRepeatedValues(grid=[[9, 1, 7], [8, 9, 2], [3, 4, 6]]))