Find Kth Largest XOR Coordinate Value - Practice Coding Problems

Find Kth Largest XOR Coordinate Value - Problem

Array Divide and Conquer Bit Manipulation Sorting Heap (Priority Queue) Matrix Prefix Sum Quickselect Medium

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.

Input & Output

Example 1 — Basic 2x2 Matrix

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

› Output: 7

💡 Note: Coordinate values: (0,0)=5, (0,1)=5⊕2=7, (1,0)=5⊕1=4, (1,1)=5⊕2⊕1⊕6=2. Sorted: [7,5,4,2]. 1st largest is 7.

Example 2 — Same Matrix, Different k

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

› Output: 5

💡 Note: Same coordinate values [7,5,4,2]. 2nd largest is 5.

Example 3 — Single Row Matrix

$ Input: matrix = [[1,0,3,2]], k = 3

› Output: 2

💡 Note: Coordinate values: (0,0)=1, (0,1)=1⊕0=1, (0,2)=1⊕0⊕3=2, (0,3)=1⊕0⊕3⊕2=0. Sorted: [2,1,1,0]. 3rd largest is 1.

Constraints

m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 1000
0 ≤ matrix[i][j] ≤ 10⁶
1 ≤ k ≤ m * n

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D matrix with coordinate-based XOR calculations

Calculate Values

XOR of all elements from (0,0) to each coordinate

Find Kth Largest

Sort coordinate values and return kth largest

Key Takeaway

🎯 Key Insight: Use 2D prefix XOR for O(1) coordinate lookups, then find kth largest efficiently

Asked in

G Google 35 f Facebook 28 M Microsoft 22

The key insight is to use 2D prefix XOR arrays to calculate coordinate values efficiently in O(1) time. The optimal approach builds the prefix array in O(mn) time, then collects and sorts all coordinate values. Time: O(mn log(mn)), Space: O(mn). For small k values, a heap-based approach can be more efficient.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with 2D Prefix XOR	O(mn + mn log(mn))	O(mn)	Build 2D prefix XOR array to calculate coordinate values in O(1) time
Heap-based Selection (QuickSelect Alternative)	O(mn + mn log k)	O(mn + k)	Use min-heap of size k to find kth largest without sorting all values
Brute Force with Direct XOR Calculation	O(m²n² + mn log(mn))	O(mn)	Calculate XOR value for each coordinate from scratch, then sort to find kth largest

Optimized with 2D Prefix XOR — Algorithm Steps

Build 2D prefix XOR array using dynamic programming
For each coordinate, lookup value from prefix array in O(1)
Collect all coordinate values
Sort values and return kth largest

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Prefix Array

Calculate cumulative XOR for each position

Instant Lookup

Get coordinate value in O(1) time

Sort and Return

Sort all values and find kth largest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}

int solution(int matrix[100][100], int m, int n, int k) {
    int prefix[100][100];
    int values[10000];
    int count = 0;
    
    // Build 2D prefix XOR array
    prefix[0][0] = matrix[0][0];
    
    // Fill first row
    for (int j = 1; j < n; j++) {
        prefix[0][j] = prefix[0][j-1] ^ matrix[0][j];
    }
    
    // Fill first column
    for (int i = 1; i < m; i++) {
        prefix[i][0] = prefix[i-1][0] ^ matrix[i][0];
    }
    
    // Fill rest of the array
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            prefix[i][j] = prefix[i-1][j] ^ prefix[i][j-1] ^ prefix[i-1][j-1] ^ matrix[i][j];
        }
    }
    
    // Collect all coordinate values
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            values[count++] = prefix[i][j];
        }
    }
    
    qsort(values, count, sizeof(int), compare);
    return values[k - 1];
}

int main() {
    int matrix[100][100];
    int m = 0, n = 0;
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple matrix parsing
    char *ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            n = 0;
            while (*ptr && *ptr != ']') {
                matrix[m][n++] = strtol(ptr, &ptr, 10);
                if (*ptr == ',') ptr++;
            }
            if (*ptr == ']') ptr++;
            m++;
        } else {
            ptr++;
        }
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(matrix, m, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn + mn log(mn))

O(mn) to build prefix array + O(mn) to collect values + O(mn log(mn)) sorting

⚡ Linearithmic

Space Complexity

O(mn)

2D prefix XOR array and values array both size mn

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

854 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with 2D Prefix XOR — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler