Skip to main content
Talentd

Find Kth Largest XOR Coordinate Value - Solution & Explanation

MediumArrayDivide and ConquerBit ManipulationSorting13 min readAsked at: Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an m x n matrix. For every coordinate (i, j), compute the XOR of all elements in the submatrix from (0,0) to (i,j). This value is called the XOR coordinate value. After computing all m*n values, return the kth largest among them.

The core challenge is efficiently computing XOR values for every submatrix. Recomputing each region from scratch would be expensive, so the key idea is to reuse previously computed results using a prefix sum-style technique with XOR.

Approach 1: Prefix XOR + Min-Heap (O(mn log k) time, O(k) space)

Compute the XOR prefix for each cell using the relation px[i][j] = matrix[i][j] ^ px[i-1][j] ^ px[i][j-1] ^ px[i-1][j-1]. This works similarly to a 2D prefix sum but uses XOR operations. While iterating through the matrix, push each prefix XOR value into a min-heap of size k. If the heap grows beyond k, remove the smallest element. This keeps only the k largest XOR values seen so far, and the heap root becomes the answer.

The insight is that you do not need to store or sort all m*n values. A heap (priority queue) maintains the top k elements efficiently. Each matrix cell is processed once, making the traversal O(mn), while heap updates cost O(log k).

Approach 2: Prefix XOR + Sorting (O(mn log(mn)) time, O(mn) space)

First compute all XOR coordinate values using the same 2D prefix XOR formula. Store every computed value in an array. After processing the entire matrix, sort the array in descending order and return the element at index k-1.

This approach is straightforward and easy to implement. However, sorting all m*n values adds extra overhead compared to maintaining only the top k. For large matrices, O(mn log(mn)) becomes noticeably slower than the heap-based solution. Still, it remains a good option when code simplicity is preferred or when k is close to m*n.

Recommended for interviews: The prefix XOR with min-heap solution is typically expected. Interviewers want to see that you recognize the 2D prefix XOR pattern (a variant of prefix sum) and combine it with a priority queue to maintain the kth largest element efficiently. The sorting approach demonstrates understanding of the prefix XOR computation, but the heap solution shows stronger optimization skills.

Approach 1: Prefix XOR and Min-Heap

We can use prefix XOR to quickly calculate the XOR value of any sub-matrix. The prefix XOR at (i, j) can be defined as the XOR of all elements from (0, 0) to (i, j). With this, the XOR for every coordinate can be derived quickly. To find the kth largest value among these, a min-heap of size k can be used, continually maintaining the largest k values observed so far.

This Python solution uses a min-heap to track the kth largest XOR value. We compute the prefix XOR for each element in the matrix, storing each result in the heap. If the heap exceeds size k, we remove the smallest item. Our final result is the smallest item in this size-k heap, which represents the kth largest XOR value.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(m * n * log k), where m is the number of rows and n is the number of columns.
Space Complexity: O(m * n + k).

Try this approach in the editor →

Approach 2: Prefix XOR and Sorting

An alternative approach is to calculate all possible XOR values using prefix XOR and then sort these values to directly find the kth largest. Although this method might have higher time complexity due to sorting, it is straightforward and utilizes built-in sorting algorithms for reliability.

This C solution calculates all XOR values using a prefix XOR approach, stores these values in an array, and sorts the array to quickly find the kth largest value. The use of qsort simplifies the sorting process.

Code

CJavaScript

C

JavaScript

Complexity

Time Complexity: O(m * n log(m * n)), due to sorting.
Space Complexity: O(m * n) for storing XOR values.

Try this approach in the editor →

Approach 3: Two-dimensional Prefix XOR + Sorting or Quick Selection

We define a two-dimensional prefix XOR array s, where s[i][j] represents the XOR result of the elements in the first i rows and the first j columns of the matrix, i.e.,

$ s[i][j] = \bigoplus_{0 leq x leq i, 0 leq y leq j} matrix[x][y]

And s[i][j] can be calculated from the three elements s[i - 1][j], s[i][j - 1] and s[i - 1][j - 1], i.e.,

s[i][j] = s[i - 1][j] \oplus s[i][j - 1] \oplus s[i - 1][j - 1] \oplus matrix[i - 1][j - 1]

We traverse the matrix, calculate all s[i][j], then sort them, and finally return the kth largest element. If you don't want to use sorting, you can also use the quick selection algorithm, which can optimize the time complexity.

The time complexity is O(m times n times log (m times n)) or O(m times n), and the space complexity is O(m times n). Here, m and n$ are the number of rows and columns of the matrix, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix XOR and Min-Heap

Time Complexity: O(m * n * log k), where m is the number of rows and n is the number of columns.
Space Complexity: O(m * n + k).

Prefix XOR and Sorting

Time Complexity: O(m * n log(m * n)), due to sorting.
Space Complexity: O(m * n) for storing XOR values.

Two-dimensional Prefix XOR + Sorting or Quick Selection—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix XOR + Min-HeapO(mn log k)O(k)Best general solution when k is much smaller than m*n
Prefix XOR + SortingO(mn log(mn))O(mn)Simple implementation when memory is not a concern

Video Solution

Find Kth Largest XOR Coordinate Value | leetcode 1738 | Contest 225 Question 3 • Coding Decoded • 1,173 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Kth Largest XOR Coordinate Value easy or hard?
The problem is rated Medium because it combines multiple concepts: 2D prefix XOR computation and selecting the kth largest value using a heap or sorting. Understanding the prefix XOR relation is the main challenge; once that is clear, the rest of the implementation is straightforward.
Find Kth Largest XOR Coordinate Value Python/Java solution
Python and Java implementations typically compute prefix XOR values while iterating through the matrix and push them into a priority queue of size k. Python uses heapq for the min-heap, while Java uses PriorityQueue. Both implementations achieve O(mn log k) time complexity.
How to solve Find Kth Largest XOR Coordinate Value in O(n)?
The matrix must be processed fully, so the lower bound is O(mn). Using a 2D prefix XOR allows computing each coordinate value in constant time after previous values are known. Maintaining a heap of size k keeps the total complexity at O(mn log k), which is the practical optimal solution.
What is the best approach for Find Kth Largest XOR Coordinate Value?
The most efficient approach uses a 2D prefix XOR combined with a min-heap. Compute the XOR value for each matrix coordinate using the prefix relation, then maintain a heap of size k containing the largest values seen so far. This reduces the complexity to O(mn log k) instead of sorting all m*n values.
Is Find Kth Largest XOR Coordinate Value asked at Google/Amazon/Meta?
This type of problem appears in interviews at companies that test matrix processing and prefix techniques, including Amazon and Google-style coding rounds. It evaluates understanding of prefix XOR, matrix traversal, and heap-based selection problems.
What data structure is used in Find Kth Largest XOR Coordinate Value?
The key structures are a 2D prefix XOR array and a min-heap (priority queue). The prefix array efficiently computes submatrix XOR values, while the heap keeps track of the top k largest results without storing or sorting every value.
What is the time complexity of Find Kth Largest XOR Coordinate Value?
The optimal solution runs in O(mn log k) time, where m and n are the matrix dimensions. Each cell contributes one prefix XOR computation and one heap operation. A simpler approach that stores all values and sorts them takes O(mn log(mn)) time.

Ready to solve this problem?

Practice Find Kth Largest XOR Coordinate Value with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays