Find Kth Largest XOR Coordinate Value

LeetCode Find Kth Largest XOR Coordinate Value (Problem 1738) gives you an m x n matrix of non-negative integers and an integer k. For every coordinate (i, j), you compute the XOR of all elements in the rectangle from (0, 0) to (i, j). Then you return the kth largest value among all those XOR results.

The brute force approach would recompute the rectangle XOR from scratch for every coordinate. That is way too slow. The trick is to recognize that XOR supports the same 2D prefix technique you already know from prefix sums.

Why this problem matters

This problem connects two ideas that show up constantly in interviews: 2D prefix computation and bit manipulation. If you have solved 2D prefix sum problems, you already know the inclusion-exclusion pattern for rectangles. The insight here is that XOR works the same way, because XOR is its own inverse (a ^ a = 0). That self-inverse property means the inclusion-exclusion formula transfers directly.

Understanding this connection means you can apply the 2D prefix framework to any associative, commutative operation that has an inverse. Addition has subtraction, XOR has XOR. Once you see that parallel, an entire class of problems opens up.

The "kth largest" part of the problem is a secondary skill. You just need to collect all the prefix values and find the kth largest efficiently. Sorting works fine here given the constraints.

The key insight

XOR has the same inclusion-exclusion property as addition for 2D prefix computation. If you define prefix[i][j] as the XOR of all elements in the rectangle from (0, 0) to (i-1, j-1) (using 1-indexed prefix with a zero-padded border), the recurrence is:

prefix[i][j] = prefix[i-1][j] ^ prefix[i][j-1] ^ prefix[i-1][j-1] ^ matrix[i-1][j-1]

Why does the prefix[i-1][j-1] term get XORed back in rather than subtracted? Because XOR is its own inverse. In the addition version, you subtract the overlap to avoid double-counting. With XOR, XORing the overlap a second time cancels it out, which is exactly the same effect. The formula looks almost identical to the 2D prefix sum formula, just with ^ replacing + and -.

Once you have all m * n prefix values, collecting the kth largest is a matter of sorting them in descending order and picking index k - 1.

The solution

def kth_largest_value(matrix: list[list[int]], k: int) -> int:
    m, n = len(matrix), len(matrix[0])
    prefix = [[0] * (n + 1) for _ in range(m + 1)]
    values = []

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            prefix[i][j] = (
                prefix[i - 1][j]
                ^ prefix[i][j - 1]
                ^ prefix[i - 1][j - 1]
                ^ matrix[i - 1][j - 1]
            )
            values.append(prefix[i][j])

    values.sort(reverse=True)
    return values[k - 1]

The prefix grid is (m+1) x (n+1) so that the zero-padded row and column eliminate boundary checks. For each cell (i, j), we apply the inclusion-exclusion XOR formula using the three neighbors (above, left, and diagonal) plus the original matrix value. Every computed prefix value gets appended to a flat list.

After the double loop, we sort the list in descending order and return the element at position k - 1. That gives us the kth largest value directly.

Visual walkthrough

Let's trace through the algorithm with a 2x3 matrix: [[5, 2, 1], [6, 3, 4]] and k = 3.

The first step sets up the zero-padded border. Step 2 shows the inclusion-exclusion formula in action for one cell. Step 3 fills in the complete prefix grid. Finally, step 4 sorts all the values and picks the 3rd largest, which is 6.

Complexity analysis

Time: Building the prefix grid takes O(m * n) since each cell requires constant work. Sorting the m * n values costs O(m * n * log(m * n)). The sort dominates.

Space: The prefix grid uses O(m * n) extra space, and the values list also holds O(m * n) entries. You could skip the values list by doing a partial sort (heap of size k), but the asymptotic space stays O(m * n) because of the prefix grid itself.

The building blocks

1. 2D prefix XOR with inclusion-exclusion

The core pattern builds a prefix table where each entry represents the XOR of a top-left rectangle. The recurrence uses three previously computed neighbors:

# Build the 2D prefix XOR table
prefix = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    for j in range(1, n + 1):
        prefix[i][j] = (
            prefix[i - 1][j]       # rectangle above
            ^ prefix[i][j - 1]     # rectangle to the left
            ^ prefix[i - 1][j - 1] # overlap (cancel it)
            ^ matrix[i - 1][j - 1] # new element
        )

This is the same structure as 2D prefix sums. The only difference is that XOR replaces addition and subtraction. Because a ^ a = 0, XORing the overlap region a second time removes it, just like subtraction would for sums.

2. Kth largest from a collection

Once you have all the prefix values in a flat list, finding the kth largest is a classic selection problem. The simplest approach is to sort:

values.sort(reverse=True)
answer = values[k - 1]

If you want O(m * n) expected time instead of O(m * n * log(m * n)), you can use quickselect. For this problem, sorting is fast enough given the constraints (m * n is at most 10^6).

Edge cases

• 1x1 matrix: There is only one coordinate value, matrix[0][0]. With k = 1, the answer is that single value.
• Single row or single column: The 2D prefix reduces to a 1D prefix XOR. The formula still works because the zero-padded border handles missing dimensions.
• All zeros: Every prefix value is 0. The kth largest is 0 for any valid k.
• k equals m * n: You want the smallest prefix value. Sorting still handles this correctly.
• Large values with high bits: XOR operates bitwise, so values up to 10^6 (about 20 bits) work without overflow concerns in Python.
• Duplicate prefix values: Multiple coordinates can produce the same XOR result. Duplicates count separately when ranking, so the 2nd largest might equal the 1st largest.

From understanding to recall

The 2D prefix XOR formula is easy to understand once you see the connection to prefix sums. But understanding and recalling under time pressure are different skills. In an interview, you need the formula prefix[i][j] = top ^ left ^ diagonal ^ current to come to mind instantly, along with the reasoning for why the diagonal term cancels the overlap.

Spaced repetition bridges that gap. You work through the derivation today, revisit it in a few days, and then again a week later. Each retrieval strengthens the memory until the pattern becomes automatic. When you see "2D XOR" in a problem statement, the inclusion-exclusion formula should surface immediately.

Related posts

• XOR Queries of a Subarray - 1D prefix XOR for subarray queries, the simpler version of this technique
• Maximum XOR of Two Numbers in an Array - XOR optimization using tries, another angle on bit manipulation
• Kth Largest Element in an Array - The selection problem in isolation, good practice for the second half of this problem

The jump from 1D prefix XOR to 2D prefix XOR is a great example of how interview patterns compose. You take a technique you already know (prefix computation), combine it with a property of the operation (XOR is self-inverse), and apply it in a higher dimension. CodeBricks breaks these connections into small building blocks and schedules reviews so each insight sticks permanently.