diff options
Diffstat (limited to 'find_kth_large_xor_coord.c')
-rw-r--r-- | find_kth_large_xor_coord.c | 42 |
1 files changed, 42 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); +} |