LeetCode 1738 - Find Kth Largest XOR Coordinate Value

The problem asks us to compute the XOR coordinate value for each element in a given 2D matrix and then find the kth largest among them.

leetcodemediumarraydivide-and-conquerbit-manipulationsortingheap-(priority-queue)matrixprefix-sumquickselect

LeetCode Problem 1738

Difficulty: 🟡 Medium
Topics: Array, Divide and Conquer, Bit Manipulation, Sorting, Heap (Priority Queue), Matrix, Prefix Sum, Quickselect

Solution

Problem Understanding

The problem asks us to compute the XOR coordinate value for each element in a given 2D matrix and then find the kth largest among them. Specifically, for a coordinate (a, b), the value is defined as the XOR of all elements in the submatrix that starts at (0, 0) and ends at (a, b). XOR is a bitwise operation with properties like commutativity and associativity, which allows us to leverage prefix computations efficiently.

The input is a matrix of non-negative integers with dimensions m x n, and an integer k specifying which largest XOR value to return. The output is the integer that represents the kth largest XOR coordinate value.

Constraints indicate that the matrix can be large (m and n up to 1000), meaning a naive approach that computes XOR for every submatrix individually will be too slow, because it would involve O(m * n * m * n) operations. All values are non-negative integers less than 10^6, so bitwise operations are feasible without overflow concerns. Edge cases include a matrix with a single element, a matrix with all zeros, and the maximum size matrix, all of which must be handled efficiently.

Approaches

The brute-force approach would iterate over each coordinate (a, b) and compute the XOR of the corresponding submatrix starting from (0,0) up to (a,b). While this guarantees correctness, it is extremely slow for large matrices because it involves repeatedly XORing overlapping submatrices, leading to O((m * n)^2) time complexity.

The key observation for an optimal solution is that XOR satisfies the inclusion-exclusion principle. This allows us to compute a prefix XOR matrix where each cell (i, j) stores the XOR of the submatrix (0,0) to (i,j). Using this prefix matrix, the XOR of a coordinate can be computed in O(1) using the formula:

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

This formula accounts for double counting by subtracting the overlapping XOR at (i-1,j-1).

Once all prefix XORs are computed, we can collect them into a list and either sort it to find the kth largest value or use a min-heap of size k to efficiently track the top k values.

Approach Time Complexity Space Complexity Notes
Brute Force O((m*n)^2) O(1) Compute XOR of every submatrix naively, extremely slow
Optimal O(m_n_log(m_n)) or O(m_n*logk) O(m*n) or O(k) Compute prefix XOR, then sort or use min-heap for kth largest

Algorithm Walkthrough

  1. Initialize a 2D array prefix of the same dimensions as matrix to store XOR values up to each coordinate (i, j).
  2. Iterate over each row i and each column j in the matrix.
  3. Compute the prefix XOR using the formula:
prefix[i][j] = matrix[i][j] 
               ^ (prefix[i-1][j] if i > 0 else 0) 
               ^ (prefix[i][j-1] if j > 0 else 0) 
               ^ (prefix[i-1][j-1] if i > 0 and j > 0 else 0)

This computes the XOR of all elements in the rectangle from (0,0) to (i,j) in O(1). 4. Collect all prefix[i][j] values into a list values. 5. Use either Python’s sort and access values[-k] for the kth largest, or use a min-heap of size k to efficiently maintain the largest k values. 6. Return the kth largest value.

Why it works: The prefix XOR invariant guarantees that each prefix[i][j] contains the XOR of all elements from (0,0) to (i,j) efficiently. Collecting all these ensures we have all coordinate values, and sorting or using a heap retrieves the kth largest efficiently.

Python Solution

from typing import List
import heapq

class Solution:
    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        prefix = [[0] * n for _ in range(m)]
        values = []
        
        for i in range(m):
            for j in range(n):
                top = prefix[i-1][j] if i > 0 else 0
                left = prefix[i][j-1] if j > 0 else 0
                top_left = prefix[i-1][j-1] if i > 0 and j > 0 else 0
                prefix[i][j] = matrix[i][j] ^ top ^ left ^ top_left
                values.append(prefix[i][j])
        
        # Using sort to get the kth largest
        values.sort()
        return values[-k]

The code first constructs a prefix XOR matrix to allow O(1) computation of each coordinate value. Each computed value is appended to a list. Sorting this list allows retrieval of the kth largest value. This method is straightforward and leverages Python’s efficient sort.

Go Solution

import "sort"

func kthLargestValue(matrix [][]int, k int) int {
    m, n := len(matrix), len(matrix[0])
    prefix := make([][]int, m)
    values := []int{}
    
    for i := 0; i < m; i++ {
        prefix[i] = make([]int, n)
        for j := 0; j < n; j++ {
            top, left, topLeft := 0, 0, 0
            if i > 0 {
                top = prefix[i-1][j]
            }
            if j > 0 {
                left = prefix[i][j-1]
            }
            if i > 0 && j > 0 {
                topLeft = prefix[i-1][j-1]
            }
            prefix[i][j] = matrix[i][j] ^ top ^ left ^ topLeft
            values = append(values, prefix[i][j])
        }
    }
    
    sort.Ints(values)
    return values[len(values)-k]
}

The Go solution mirrors the Python approach. Slice initialization and boundary checks for index access are explicitly handled, but the overall algorithm remains the same. Sorting the collected values allows straightforward retrieval of the kth largest.

Worked Examples

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

i j top left topLeft prefix[i][j] values
0 0 0 0 0 5 [5]
0 1 0 5 0 7 [5,7]
1 0 5 0 0 4 [5,7,4]
1 1 7 4 5 6 [5,7,4,6]

Sorted values = [4,5,6,7], k=1 largest is 7.

Complexity Analysis

Measure Complexity Explanation
Time O(m_n_log(m*n)) Computing prefix XOR is O(m_n), sorting all values is O(m_n_log(m_n))
Space O(m*n) Prefix matrix stores m_n elements, values list stores m_n elements

Using a min-heap of size k instead of sorting would reduce time complexity to O(m_n_logk) and space to O(k).

Test Cases

# Provided examples
assert Solution().kthLargestValue([[5,2],[1,6]], 1) == 7  # largest
assert Solution().kthLargestValue([[5,2],[1,6]], 2) == 5  # second largest
assert Solution().kthLargestValue([[5,2],[1,6]], 3) == 4  # third largest

# Edge cases
assert Solution().kthLargestValue([[0]], 1) == 0  # single element
assert Solution().kthLargestValue([[1]], 1) == 1  # single element nonzero
assert Solution().kthLargestValue([[1,1],[1,1]], 1) == 1  # all ones
assert Solution().kthLargestValue([[1,1],[1,1]], 4) == 0  # smallest XOR value
Test Why
[[5,2],[1,6]], k=1 Largest XOR value
[[5,2],[1,6]], k=2 Second largest XOR value
[[5,2],[1,6]], k=3 Third largest XOR value
[[0]], k=1 Single element zero
[[1]], k=1