diff options
author | Jack Sangdahl <[email protected]> | 2025-03-04 13:14:39 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-04 13:14:39 -0700 |
commit | d84519d4d115251af42c780c825447d1a7559868 (patch) | |
tree | 2183e892c3f789fd8ed4ae9ba0af183d059bb591 /find_kth_large_xor_coord.c | |
parent | 8f19a94ccd34fb82b658bf1206f0b0ffdf70b1b2 (diff) | |
download | leetcode-d84519d4d115251af42c780c825447d1a7559868.tar.gz leetcode-d84519d4d115251af42c780c825447d1a7559868.zip |
1738. find kth largest xor coordinate value
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); +} |