# Find Kth Largest XOR Coordinate Value
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-kth-largest-xor-coordinate-value)
Canonical: https://scaleengineer.com/dsa/problems/find-kth-largest-xor-coordinate-value
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer), [Sorting](https://scaleengineer.com/algorithms/sorting), [Quickselect](https://scaleengineer.com/algorithms/quickselect)
**Data structures:** Array, Heap (Priority Queue), Matrix
---
## Problem
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 `kth` largest value **(1-indexed)** of all the coordinates of `matrix`.

**Example 1:**

**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.

**Example 2:**

**Input:** matrix = [[5,2],[1,6]], k = 2
**Output:** 5
**Explanation:** The value of coordinate (0,0) is 5 = 5, which is the 2nd largest value.

**Example 3:**

**Input:** matrix = [[5,2],[1,6]], k = 3
**Output:** 4
**Explanation:** The value of coordinate (1,0) is 5 XOR 1 = 4, which is the 3rd largest value.

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= m, n <= 1000`
* `0 <= matrix[i][j] <= 106`
* `1 <= k <= m * n`

# Approaches
## Dynamic Programming with Sorting
This approach first calculates all the coordinate values using a dynamic programming technique and then finds the k-th largest value by sorting all the calculated values.
**Time:** O(m * n * log(m * n)). `O(m * n)` to compute all prefix XOR values. `O(m * n * log(m * n))` to sort the list of `m * n` values. The sorting step dominates the overall time complexity. · **Space:** O(m * n). We need `O(m * n)` space for the `prefixXor` DP table and another `O(m * n)` for the `values` list.
**Pros:** Relatively simple to understand and implement.
**Cons:** The time complexity is high due to sorting all `m * n` elements, which can be inefficient for large matrices.; The space complexity is also high, requiring storage for both the DP table and the list of values.
### Explanation
The core idea is to efficiently compute the value for each coordinate `(r, c)`, which is the XOR sum of all elements in the rectangle from `(0, 0)` to `(r, c)`. This can be viewed as a 2D prefix XOR problem. We can define `dp[r][c]` as the value of coordinate `(r, c)`. The value `dp[r][c]` can be calculated using the values of its neighbors and the element `matrix[r][c]`. The recurrence relation is:
`dp[r][c] = dp[r-1][c] ^ dp[r][c-1] ^ dp[r-1][c-1] ^ matrix[r][c]`.
(Here, `^` denotes the XOR operation).
We can create a DP table of size `(m+1) x (n+1)` to store these prefix XORs. We iterate through the matrix, compute each `dp[i][j]`, and store all `m * n` computed values into a list. After populating the list with all coordinate values, we sort the list in ascending order. The k-th largest element will be at index `list.size() - k`.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] prefixXor = new int[m + 1][n + 1];
        List<Integer> values = new ArrayList<>();

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixXor[i][j] = prefixXor[i - 1][j] ^ prefixXor[i][j - 1] ^ prefixXor[i - 1][j - 1] ^ matrix[i - 1][j - 1];
                values.add(prefixXor[i][j]);
            }
        }

        Collections.sort(values);
        return values.get(values.size() - k);
    }
}
```
### Algorithm
- Initialize an `(m+1) x (n+1)` DP table, `prefixXor`, with all zeros.
- Initialize an empty list, `values`, to store all coordinate values.
- Iterate `i` from 1 to `m` and `j` from 1 to `n`:
  - Calculate `prefixXor[i][j] = prefixXor[i-1][j] ^ prefixXor[i][j-1] ^ prefixXor[i-1][j-1] ^ matrix[i-1][j-1]`.
  - Add `prefixXor[i][j]` to the `values` list.
- Sort the `values` list in ascending order.
- Return the element at index `values.size() - k`.

## Dynamic Programming with a Min-Heap
This approach improves upon the first one by avoiding a full sort. Instead of storing all values and then sorting, we use a min-heap (Priority Queue) of size `k` to keep track of the `k` largest values seen so far.
**Time:** O(m * n * log k). `O(m * n)` to iterate through all coordinates and calculate their values. For each of the `m * n` values, we perform a heap operation (`offer` and possibly `poll`), which takes `O(log k)` time. · **Space:** O(m*n + k). `O(m * n)` for the `prefixXor` DP table and `O(k)` for the min-heap. Note: The DP calculation can be space-optimized to `O(n)`, leading to an overall space complexity of `O(n + k)`.
**Pros:** More time-efficient than full sorting, especially when `k` is much smaller than `m * n`.; Can be implemented with very good space efficiency (`O(n + k)`) by optimizing the DP calculation.
**Cons:** Slightly more complex to implement than the sorting approach.; Time complexity is dependent on `log k`, which can be close to `log(m*n)` if `k` is large.
### Explanation
Similar to the first approach, we calculate the prefix XOR value for each coordinate. We maintain a min-heap of size `k`. As we calculate each coordinate's value, we add it to the heap. If the heap's size exceeds `k`, we remove the smallest element (the root of the min-heap). This ensures the heap always contains the `k` largest values encountered up to that point. After iterating through all coordinates, the root of the heap will be the k-th largest value overall. While the DP calculation can be done with `O(m*n)` space, it can also be optimized to use `O(n)` space, making this approach very memory-efficient.

```java
import java.util.PriorityQueue;

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        // Min-heap to store the k largest values
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        int[][] prefixXor = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixXor[i][j] = prefixXor[i - 1][j] ^ prefixXor[i][j - 1] ^ prefixXor[i - 1][j - 1] ^ matrix[i - 1][j - 1];
                minHeap.offer(prefixXor[i][j]);
                if (minHeap.size() > k) {
                    minHeap.poll();
                }
            }
        }
        
        return minHeap.peek();
    }
}
```
### Algorithm
- Initialize a min-heap, `minHeap`.
- Initialize an `(m+1) x (n+1)` DP table, `prefixXor`, with all zeros.
- Iterate `i` from 1 to `m` and `j` from 1 to `n`:
  - Calculate the current coordinate's value: `currentValue = prefixXor[i-1][j] ^ prefixXor[i][j-1] ^ prefixXor[i-1][j-1] ^ matrix[i-1][j-1]`.
  - Add `currentValue` to `minHeap`.
  - If `minHeap.size() > k`, call `minHeap.poll()`.
- Return `minHeap.peek()`.

## Dynamic Programming with Quickselect
This is the most time-efficient approach on average. It combines the `O(m*n)` dynamic programming calculation of coordinate values with the Quickselect algorithm, which finds the k-th largest element in linear average time.
**Time:** O(m * n) on average. `O(m * n)` to compute all prefix XOR values. `O(m * n)` on average for the Quickselect algorithm. The worst-case is `O((m*n)^2)`, but it's highly unlikely with a randomized pivot. · **Space:** O(m * n). `O(m * n)` for the `prefixXor` DP table and the `values` list. Even with a space-optimized DP calculation, we still need `O(m*n)` space to store all values for the Quickselect algorithm.
**Pros:** Asymptotically the fastest approach on average.
**Cons:** Implementation of Quickselect is more complex than using built-in sorting or a priority queue.; Has a quadratic worst-case time complexity, although this is rare in practice with a good pivot strategy.; Requires `O(m*n)` space to hold all values, which is less memory-efficient than the optimized min-heap approach.
### Explanation
First, we compute all `m * n` coordinate values using the same DP technique as in the previous approaches and store them in a list or an array. Once we have the list of all values, we apply the Quickselect algorithm. Quickselect is a selection algorithm that modifies the Quicksort algorithm to find the k-th smallest (or largest) element in an unsorted list. It works by partitioning the array around a pivot element and recursively searching only in the partition that is expected to contain the k-th element. This avoids sorting the entire array. On average, Quickselect has a time complexity of `O(N)`, where `N` is the number of elements (`m * n` in our case).

```java
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] prefixXor = new int[m + 1][n + 1];
        List<Integer> values = new ArrayList<>();

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixXor[i][j] = prefixXor[i - 1][j] ^ prefixXor[i][j - 1] ^ prefixXor[i - 1][j - 1] ^ matrix[i - 1][j - 1];
                values.add(prefixXor[i][j]);
            }
        }
        
        return quickSelect(values, k);
    }

    private int quickSelect(List<Integer> nums, int k) {
        int left = 0, right = nums.size() - 1;
        // k-th largest is (n-k)-th smallest
        int targetIndex = nums.size() - k;
        Random rand = new Random();

        while (left <= right) {
            int pivotIndex = rand.nextInt(right - left + 1) + left;
            int finalPivotIndex = partition(nums, left, right, pivotIndex);

            if (finalPivotIndex == targetIndex) {
                return nums.get(finalPivotIndex);
            } else if (finalPivotIndex < targetIndex) {
                left = finalPivotIndex + 1;
            } else {
                right = finalPivotIndex - 1;
            }
        }
        return -1; // Should not happen
    }

    private int partition(List<Integer> nums, int left, int right, int pivotIndex) {
        int pivotValue = nums.get(pivotIndex);
        swap(nums, pivotIndex, right); // Move pivot to end
        int storeIndex = left;

        for (int i = left; i < right; i++) {
            if (nums.get(i) < pivotValue) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        swap(nums, storeIndex, right); // Move pivot to its final place
        return storeIndex;
    }

    private void swap(List<Integer> nums, int i, int j) {
        int temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }
}
```
### Algorithm
- Initialize an `(m+1) x (n+1)` DP table, `prefixXor`, with all zeros.
- Initialize an empty list, `values`, to store all coordinate values.
- Iterate `i` from 1 to `m` and `j` from 1 to `n`:
  - Calculate `prefixXor[i][j] = prefixXor[i-1][j] ^ prefixXor[i][j-1] ^ prefixXor[i-1][j-1] ^ matrix[i-1][j-1]`.
  - Add `prefixXor[i][j]` to the `values` list.
- Use the Quickselect algorithm to find the `k`-th largest element in `values`. This is equivalent to finding the `(N - k)`-th smallest element, where `N = m * n`.
- Return the result from Quickselect.

# Solutions
### Java

```java
class Solution { public int kthLargestValue ( int [][] matrix , int k ) { int m = matrix . length , n = matrix [ 0 ]. length ; int [][] s = new int [ m + 1 ][ n + 1 ]; List < Integer > ans = new ArrayList <>(); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { s [ i + 1 ][ j + 1 ] = s [ i + 1 ][ j ] ^ s [ i ][ j + 1 ] ^ s [ i ][ j ] ^ matrix [ i ][ j ]; ans . add ( s [ i + 1 ][ j + 1 ]); } } Collections . sort ( ans ); return ans . get ( ans . size () - k ); } }
```

### CPP

```cpp
class Solution { public: int kthLargestValue ( vector < vector < int >>& matrix , int k ) { int m = matrix . size (), n = matrix [ 0 ]. size (); vector < vector < int >> s ( m + 1 , vector < int > ( n + 1 )); vector < int > ans ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { s [ i + 1 ][ j + 1 ] = s [ i + 1 ][ j ] ^ s [ i ][ j + 1 ] ^ s [ i ][ j ] ^ matrix [ i ][ j ]; ans . push_back ( s [ i + 1 ][ j + 1 ]); } } sort ( ans . begin (), ans . end ()); return ans [ ans . size () - k ]; } };
```

### Python

```python
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 ]
```