diff options
-rw-r--r-- | find_kth_large_xor_coord.c | 42 | ||||
-rw-r--r-- | find_kth_large_xor_coord.py | 41 |
2 files changed, 83 insertions, 0 deletions
diff --git a/find_kth_large_xor_coord.c b/find_kth_large_xor_coord.c new file mode 100644 index 0000000..2611be1 --- /dev/null +++ b/find_kth_large_xor_coord.c @@ -0,0 +1,42 @@ +// 1738. Find Kth Largest XOR Coordinate Value +#include "leetcode.h" + +/* + * you are given a 2d 'matrix' of size 'm x n' consisting of non-negative + * integers. you are also given an integer 'k'. the value of coordinate '(a, b)' + * of the matrix is the xor of all 'matrix[i][j]' where '0 <= i <= a < m' and + * '0 <= j <= b < n' (0-indexed). find the k'th largest value (1-indexed) of all + * the coordinates of 'matrix'. + */ + +int cmp(const void *a, const void *b) { return *(int *)a > *(int *)b; } + +int kthLargestValue(int **matrix, int matrixSize, int *matrixColSize, int k) { + int map[matrixSize * (*matrixColSize)], idx = 0; + for (int i = 0; i < matrixSize; i++) + for (int j = 0; j < *matrixColSize; j++) { + if (j > 0) + matrix[i][j] ^= matrix[i][j - 1]; + if (i > 0) + matrix[i][j] ^= matrix[i - 1][j]; + if (i > 0 && j > 0) + matrix[i][j] ^= matrix[i - 1][j - 1]; + map[idx++] = matrix[i][j]; + } + qsort(map, idx, sizeof(int), cmp); + return map[idx - k]; +} + +int main() { + int matrix_input[2][2] = {{5, 2}, {1, 6}}; + struct two_d_arr matrix; + two_d_arr_init(&matrix, ARRAY_SIZE(matrix_input), ARRAY_SIZE(matrix_input[0]), + matrix_input); + printf("%d\n", kthLargestValue(matrix.arr, matrix.row_size, matrix.col_size, + 1)); // expect: 7 + printf("%d\n", kthLargestValue(matrix.arr, matrix.row_size, matrix.col_size, + 2)); // expect: 5 + printf("%d\n", kthLargestValue(matrix.arr, matrix.row_size, matrix.col_size, + 3)); // expect: 4 + two_d_arr_free(&matrix); +} diff --git a/find_kth_large_xor_coord.py b/find_kth_large_xor_coord.py new file mode 100644 index 0000000..feb19a8 --- /dev/null +++ b/find_kth_large_xor_coord.py @@ -0,0 +1,41 @@ +# 1738. Find Kth Largest XOR Coordinate Value +import heapq + +""" +you are given a 2d 'matrix' of size 'm x n' consisting of non-negative +integers. you are also given an integer 'k'. the value of coordinate '(a, b)' +of the matrix is the xor of all 'matrix[i][j]' where '0 <= i <= a < m' and +'0 <= j <= b < n' (0-indexed). find the k'th largest value (1-indexed) of all +the coordinates of 'matrix'. +""" + + +class Solution(object): + def kthLargestValue(self, matrix, k): + """ + :type matrix: List[List[int]] + :type k: int + :rtype: int + """ + m, n = len(matrix), len(matrix[0]) + pq = [] + for i in range(m): + for j in range(n): + if i > 0: + matrix[i][j] ^= matrix[i - 1][j] + if j > 0: + matrix[i][j] ^= matrix[i][j - 1] + if i > 0 and j > 0: + matrix[i][j] ^= matrix[i - 1][j - 1] + if len(pq) < k: + heapq.heappush(pq, matrix[i][j]) + else: + heapq.heappushpop(pq, matrix[i][j]) + return pq[0] + + +if __name__ == "__main__": + obj = Solution() + print(obj.kthLargestValue(matrix=[[5, 2], [1, 6]], k=1)) + print(obj.kthLargestValue(matrix=[[5, 2], [1, 6]], k=2)) + print(obj.kthLargestValue(matrix=[[5, 2], [1, 6]], k=3)) |