1738. Find Kth Largest XOR Coordinate Value

MediumBit ManipulationArrayDivide and ConquerMatrixPrefix SumQuickselectHeap (Priority Queue)

Problem Description

In this problem, we are given a matrix of non-negative integers with m rows and n columns. We need to calculate the value of certain coordinates, with the value being defined as the XOR (exclusive OR) of all the elements of the submatrix defined by the corner (0, 0) and the coordinate (a, b).

To clarify, for each coordinate (a, b), we consider the rectangle from the top-left corner (0, 0) to the coordinate (a, b) and compute the XOR of all the elements within that rectangle.

Our goal is to find the k-th largest such XOR value from all possible coordinates.

Intuition

Arriving at the solution for this problem involves understanding how XOR operates and using properties of XOR to build a dynamic solution. The XOR operation has a key property of reversibility, which means that if a ^ b = c, then a ^ c = b and b ^ c = a.

Knowing this, we can compute the cumulative XOR in a dynamic fashion as we traverse the matrix. For each cell (i, j), we can determine its XOR value based on previously computed values in the matrix: the XOR of the rectangle from (0, 0) to (i, j) is the XOR of the rectangle from (0, 0) to (i-1, j), the rectangle from (0, 0) to (i, j-1), the overlapping rectangle ending at (i-1, j-1) (since it's included twice, it cancels out using the XOR reversibility), and the current cell value matrix[i][j].

Therefore, for any cell (i, j), we can calculate its cumulative XOR as s[i][j] = s[i-1][j] ^ s[i][j-1] ^ s[i-1][j-1] ^ matrix[i][j]. This formula helps us determine the cumulative XOR efficiently. After computing the XOR value for all possible coordinates, we add them to a list.

Once we have the XOR values for all coordinates, we want the k-th largest value. Python's heapq.nlargest() function can be extremely helpful here. It allows us to quickly obtain the k largest elements from a list, and we return the last of these elements, which corresponds to the k-th largest value.

Learn more about Divide and Conquer, Prefix Sum and Heap (Priority Queue) patterns.

Solution Approach

In the given Python code, the solution follows these steps using dynamic programming and a priority queue (heap):

Initialize a 2D list s of size (m+1) x (n+1) with zeros. This list will store the cumulative XOR values where s[i][j] corresponds to the XOR value from the top-left corner (0, 0) to the coordinate (i-1, j-1).
Create an empty list ans which will store the XOR of all coordinates of the given matrix.
Iterate through each cell (i, j) of the given 2D matrix starting from the top-left corner. For each cell, calculate the cumulative XOR using the formula:
```
s[i + 1][j + 1] = s[i + 1][j] ^ s[i][j + 1] ^ s[i][j] ^ matrix[i][j]
```
This formula uses the concept of inclusion-exclusion to avoid double-counting the XOR of any region. Here, s[i + 1][j + 1] includes the value of the cell itself (matrix[i][j]), the XOR of the rectangle above it (s[i + 1][j]), the XOR of the rectangle to the left (s[i][j + 1]), and excludes the XOR of the overlapping rectangle from the top-left to (i-1, j-1) (s[i][j]).
After calculating the cumulative XOR for the cell (i, j), append the result to the ans list.
Once all cells have been processed, we have a complete list of XOR values for all coordinates. Now, we need to find the k-th largest value. The nlargest method from Python's heapq library can efficiently accomplish this by return a list of the k largest elements from ans. Here's the code line that employs it:
```
return nlargest(k, ans)[-1]
```

This code snippets returns the last element from the list returned by nlargest, which is the k-th largest XOR value from the matrix.

The time complexity for computing the cumulative XOR is O(m*n) because we iterate through each cell once, and the time complexity for finding the k-th largest element using nlargest is O(n*log(k)). Hence, the total time complexity of this approach is dominated by the larger of the two, which is typically O(m*n) assuming k is relatively small compared to m*n.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a matrix with m = 2 rows and n = 3 columns, and let's find the 2nd largest XOR value. The matrix looks like this:

matrix = [
  [1, 2, 3],
  [4, 5, 6]
]

Now let's walk through the solution approach:

We initialize a 2D list s with dimensions (m+1) x (n+1), which translates to a 3x4 list filled with zeros. This will be used to store cumulative XOR values:

s = [
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0]
]

We create an empty list ans to store the XOR values of all coordinates of the given matrix.

We iterate through each cell (i, j) of the matrix. On the first iteration (i, j) = (0, 0), we calculate the cumulative XOR as follows:

s[1][1] = s[1][0] ^ s[0][1] ^ s[0][0] ^ matrix[0][0]
s[1][1] = 0 ^ 0 ^ 0 ^ 1
s[1][1] = 1

We append the result to the ans list, which now looks like: ans = [1].

We continue the process for the rest of the cells. After processing all cells, the s matrix is filled with cumulative XOR values up to each cell (i, j):
```
s = [
  [0, 0, 0, 0],
  [0, 1, 3, 0],
  [0, 5, 7, 6]
]
```
And the ans list filled with the XOR values of each coordinate is: ans = [1, 3, 0, 5, 7, 6].
Finally, to find the 2nd largest value, we use the nlargest method from Python's heapq library and return the second item of the list:
```
return nlargest(2, ans)[-1]
```

When we apply the final step, nlargest yields the list [7, 6] (since 7 and 6 are the two largest numbers from the list ans), and we return the last element, which is 6. Thus, the 2nd largest XOR value is 6.

Solution Implementation

1from heapq import nlargest  # We'll use nlargest function from the heapq module
2
3class Solution:
4    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
5        # Calculate the number of rows and columns
6        num_rows, num_columns = len(matrix), len(matrix[0])
7      
8        # Initialize a 2D list for storing exclusive or (XOR) prefix sums
9        prefix_xor = [[0] * (num_columns + 1) for _ in range(num_rows + 1)]
10        # This list will hold all the XOR values in the matrix
11        xor_values = []
12      
13        # Compute the XOR value for each cell and store it in prefix_xor
14        for row in range(num_rows):
15            for col in range(num_columns):
16                # XOR of the current value with its prefix sums
17                prefix_xor[row + 1][col + 1] = (
18                    prefix_xor[row + 1][col] ^ 
19                    prefix_xor[row][col + 1] ^ 
20                    prefix_xor[row][col] ^ 
21                    matrix[row][col]
22                )
23                # Add the result to the list of XOR values
24                xor_values.append(prefix_xor[row + 1][col + 1])
25      
26        # Get the kth largest XOR value by using the nlargest function
27        # and returning the last element in the resulting list
28        return nlargest(k, xor_values)[-1]
29

1class Solution {
2    public int kthLargestValue(int[][] matrix, int k) {
3      
4        // Obtain the dimensions of the input matrix
5        int rows = matrix.length, cols = matrix[0].length;
6      
7        // Initialize the prefix XOR matrix with one extra row and column
8        int[][] prefixXor = new int[rows + 1][cols + 1];
9      
10        // This list will store all the unique XOR values from the matrix
11        List<Integer> xorValues = new ArrayList<>();
12      
13        // Calculating prefix XOR matrix and storing XOR values of submatrices
14        for (int i = 0; i < rows; ++i) {
15            for (int j = 0; j < cols; ++j) {
16              
17                // Calculate the prefix XOR value for the current submatrix
18                prefixXor[i + 1][j + 1] = prefixXor[i][j + 1] ^ prefixXor[i + 1][j] ^ prefixXor[i][j] ^ matrix[i][j];
19              
20                // Add the current XOR value to the list
21                xorValues.add(prefixXor[i + 1][j + 1]);
22            }
23        }
24      
25        // Sort the XOR values in ascending order
26        Collections.sort(xorValues);
27      
28        // Return the kth largest value by indexing from the end of the sorted list
29        return xorValues.get(xorValues.size() - k);
30    }
31}
32

1class Solution {
2public:
3    int kthLargestValue(vector<vector<int>>& matrix, int k) {
4        // Get the number of rows and columns in the matrix
5        int rows = matrix.size(), cols = matrix[0].size();
6        // Create a 2D vector to store the xor values
7        vector<vector<int>> prefixXor(rows + 1, vector<int>(cols + 1));
8        // Vector to store the xor of all elements in the matrix
9        vector<int> xorValues;
10      
11        // Calculate the prefix xor values for each cell in the matrix
12        for (int i = 0; i < rows; ++i) {
13            for (int j = 0; j < cols; ++j) {
14                // Compute the xor value for the current cell by using the previously calculated values
15                prefixXor[i + 1][j + 1] = prefixXor[i + 1][j] ^ prefixXor[i][j + 1] ^ prefixXor[i][j] ^ matrix[i][j];
16                // Add the computed xor value to the list of xor values
17                xorValues.push_back(prefixXor[i + 1][j + 1]);
18            }
19        }
20      
21        // Sort the xor values in ascending order
22        sort(xorValues.begin(), xorValues.end());
23        // The kth largest value is at index (size - k) after sorting
24        return xorValues[xorValues.size() - k];
25    }
26};
27

1function kthLargestValue(matrix: number[][], k: number): number {
2    // Get the number of rows and columns in the matrix
3    const rows = matrix.length;
4    const cols = matrix[0].length;
5
6    // Create a 2D array to store the prefix XOR values for each cell
7    const prefixXor: number[][] = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0));
8    // Array to store the XOR of all elements in the matrix
9    const xorValues: number[] = [];
10
11    // Calculate the prefix XOR values for each cell in the matrix
12    for (let i = 0; i < rows; i++) {
13        for (let j = 0; j < cols; j++) {
14            // Compute the XOR value for the current cell using the previously calculated values
15            prefixXor[i + 1][j + 1] =
16                prefixXor[i + 1][j] ^ prefixXor[i][j + 1] ^ prefixXor[i][j] ^ matrix[i][j];
17            // Add the computed XOR value to the list of XOR values
18            xorValues.push(prefixXor[i + 1][j + 1]);
19        }
20    }
21
22    // Sort the XOR values in ascending order
23    xorValues.sort((a, b) => a - b);
24    // The k-th largest value is at the index of (total number of values - k) after sorting
25    return xorValues[xorValues.length - k];
26}
27

Time and Space Complexity

Time Complexity

The time complexity of the given code can be evaluated by looking at each operation performed:

Initialization of the Prefix XOR Matrix (s):
- The code initializes an auxiliary matrix s with dimensions m + 1 by n + 1.
Calculation of Prefix XOR values:
- There are two nested loops that iterate over each cell of the matrix which runs m * n times.
- Within the inner loop, there is a calculation that takes constant time, which performs the XOR operations to fill in the s matrix. This is done for each of the m * n cells.
- After calculating the XOR for a cell, the result is appended to the ans list. This operation takes constant time.

So we can express this part of the time complexity as O(m * n).

Finding the kth largest value with heapq.nlargest method:
- The function nlargest(k, ans) is used to find the kth largest element and operates on the ans list of size m * n.
- The nlargest function has a time complexity of O(N * log(k)) where N is the number of elements in the list and k is the argument to nlargest. Hence, in our case, it becomes O(m * n * log(k)).

So when combined, the overall time complexity is O(m * n) from the nested loops plus O(m * n * log(k)) from finding the kth largest value. Since O(m * n) is subsumed by O(m * n * log(k)), the overall time complexity simplifies to:

O(m * n * log(k))

Space Complexity

For space complexity analysis, we consider the additional space used by the algorithm excluding input and output storage:

Space for the s Matrix:
- The code creates an auxiliary matrix s of size (m + 1) * (n + 1), which takes O((m + 1) * (n + 1)) or simplifying it O(m * n) space.
Space for the List ans:
- A list ans is used to store XOR results which will have at most m * n elements.
- Hence the space taken by ans is O(m * n).

So combining these, the space complexity of the algorithm is the sum of the space needed for s and ans, which is O(m * n) + O(m * n), which simplifies to:

O(m * n)

Both time and space complexities are proposed considering the list List and integer int types are imported from Python’s typing module as is customary in type-hinted Python code.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don't know