aboutsummaryrefslogtreecommitdiff
path: root/find_kth_large_xor_coord.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-04 13:14:39 -0700
committerJack Sangdahl <[email protected]>2025-03-04 13:14:39 -0700
commitd84519d4d115251af42c780c825447d1a7559868 (patch)
tree2183e892c3f789fd8ed4ae9ba0af183d059bb591 /find_kth_large_xor_coord.py
parent8f19a94ccd34fb82b658bf1206f0b0ffdf70b1b2 (diff)
downloadleetcode-d84519d4d115251af42c780c825447d1a7559868.tar.gz
leetcode-d84519d4d115251af42c780c825447d1a7559868.zip
1738. find kth largest xor coordinate value
Diffstat (limited to 'find_kth_large_xor_coord.py')
-rw-r--r--find_kth_large_xor_coord.py41
1 files changed, 41 insertions, 0 deletions
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))