Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1738. Find Kth Largest XOR Coordinate Value - Leetcode Solution

Code Implementation

import heapq

class Solution:
    def kthLargestValue(self, matrix, k):
        m, n = len(matrix), len(matrix[0])
        # Build prefix XOR matrix
        pre = [[0] * (n + 1) for _ in range(m + 1)]
        vals = []
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                pre[i][j] = (pre[i-1][j] ^
                             pre[i][j-1] ^
                             pre[i-1][j-1] ^
                             matrix[i-1][j-1])
                vals.append(pre[i][j])
        # Find kth largest
        return heapq.nlargest(k, vals)[-1]
      
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> pre(m + 1, vector<int>(n + 1, 0));
        vector<int> vals;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                pre[i][j] = pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1] ^ matrix[i-1][j-1];
                vals.push_back(pre[i][j]);
            }
        }
        nth_element(vals.begin(), vals.begin() + k - 1, vals.end(), greater<int>());
        return vals[k-1];
    }
};
      
import java.util.*;

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int[][] pre = new int[m + 1][n + 1];
        List<Integer> vals = new ArrayList<>();
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                pre[i][j] = pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1] ^ matrix[i-1][j-1];
                vals.add(pre[i][j]);
            }
        }
        Collections.sort(vals, Collections.reverseOrder());
        return vals.get(k-1);
    }
}
      
var kthLargestValue = function(matrix, k) {
    const m = matrix.length, n = matrix[0].length;
    const pre = Array.from({length: m+1}, () => Array(n+1).fill(0));
    const vals = [];
    for (let i = 1; i <= m; ++i) {
        for (let j = 1; j <= n; ++j) {
            pre[i][j] = pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1] ^ matrix[i-1][j-1];
            vals.push(pre[i][j]);
        }
    }
    vals.sort((a, b) => b - a);
    return vals[k-1];
};

Problem Description

Given a 2D matrix of integers called matrix with dimensions m x n, define the XOR coordinate value at position (a, b) as the cumulative XOR of all elements from the top-left corner (0, 0) to (a, b). Specifically, for each cell (a, b), the value is:

matrix[0][0] ^ ... ^ matrix[0][b] ^ ... ^ matrix[a][0] ^ ... ^ matrix[a][b]

Your task is to compute all such XOR coordinate values for every cell in the matrix, then return the kth largest value among them.
  • Each cell's XOR is over the rectangle from (0,0) to (a,b).
  • Return the kth largest value (not the kth unique value).
  • All matrix elements are used; no element is reused in different coordinate calculations.
  • There is always at least one valid answer.

Thought Process

At first glance, the brute-force approach would be to compute the XOR for every possible rectangle ending at each cell. However, this would be highly inefficient, especially for larger matrices, because it would involve recalculating the same XORs multiple times.

To optimize, we can use the concept of a prefix XOR matrix, similar to prefix sums but using XOR instead of addition. This allows us to compute the XOR of any submatrix in constant time by reusing previously computed results, just as prefix sums allow for fast range sum queries.

Once we have all the XOR coordinate values, we need to find the kth largest. This can be done efficiently using a heap or by sorting the list of values.

Solution Approach

The solution can be broken down into the following steps:
  1. Build a Prefix XOR Matrix:
    • Create a new matrix pre with dimensions (m+1) x (n+1) initialized to zero.
    • For each cell (i, j) in the original matrix, compute:
      pre[i][j] = pre[i-1][j] ^ pre[i][j-1] ^ pre[i-1][j-1] ^ matrix[i-1][j-1]
    • This formula ensures that each pre[i][j] contains the XOR of all elements from (0,0) to (i-1,j-1).
  2. Collect All XOR Coordinate Values:
    • As you compute each pre[i][j], add it to a list or array.
  3. Find the kth Largest Value:
    • Sort the list of values in descending order, or use a heap to efficiently find the kth largest.
    • Return the value at index k-1 (since indices are zero-based).
This approach leverages dynamic programming for efficient calculation and uses standard library tools for selection.

Example Walkthrough

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

Step 1: Build Prefix XOR Matrix
  • pre[1][1] = 5
  • pre[1][2] = 5 ^ 2 = 7
  • pre[2][1] = 5 ^ 1 = 4
  • pre[2][2] = 5 ^ 2 ^ 1 ^ 6 = 5 ^ 2 = 7, 7 ^ 1 = 6, 6 ^ 6 = 0
So, the XOR coordinate values are: [5, 7, 4, 0]

Step 2: Sort and Find kth Largest
  • Sorted descending: [7, 5, 4, 0]
  • k = 2, so answer is 5
Why? Because after sorting, the 2nd largest value is 5.

Time and Space Complexity

  • Brute-Force Approach:
    • Time: O(m2 n2) — For each cell, you would need to compute the XOR over a rectangle, which is very slow.
    • Space: O(1) extra, but inefficient.
  • Optimized Approach (Prefix XOR):
    • Time: O(mn) to compute the prefix XORs, plus O(mn log mn) to sort (or O(mn log k) if using a heap).
    • Space: O(mn) for the prefix matrix and list of values.
The optimized approach is much more efficient and practical for large matrices.

Summary

The key insight in this problem is the use of a prefix XOR matrix, which allows us to compute all rectangle XORs efficiently with dynamic programming. By collecting all these values and selecting the kth largest, we solve the problem efficiently and elegantly. This approach avoids redundant computation and leverages standard data structures for the selection step.