Find Kth Largest XOR Coordinate Value — LeetCode 1738 Python Solution

The problem

You are given a 2D matrix of size m x n, consisting of non-negative integers. You are also given an integer k.

Example

Input

matrix = [[5,2],[1,6]], k = 1

Output

7

Explanation

The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.

Python solution

class Solution:
    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        ans = []
        for i in range(m):
            for j in range(n):
                s[i + 1][j + 1] = s[i + 1][j] ^ s[i][j + 1] ^ s[i][j] ^ matrix[i][j]
                ans.append(s[i + 1][j + 1])
        return nlargest(k, ans)[-1]

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1738. Find Kth Largest XOR Coordinate Value is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems