We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Kth Largest XOR Coordinate Value

Number: 1860

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an m x n matrix of non-negative integers, compute the XOR of the rectangle from the top-left corner (0, 0) to every coordinate (i, j) (inclusive). Return the kth largest XOR value among all coordinates.

Key Insights

  • Build a prefix XOR matrix that stores the XOR of all elements from (0,0) to (i,j) using the relationship:
    • prefix[i][j] = prefix[i-1][j] XOR prefix[i][j-1] XOR prefix[i-1][j-1] XOR matrix[i][j]
  • The computed prefix XOR at (i,j) represents the XOR of the submatrix from (0,0) to (i,j).
  • Once all XOR values are computed, select the kth largest value.
  • Instead of sorting the entire list, a min-heap of size k could be used for more efficient selection especially when k is small compared to m*n.

Space and Time Complexity

Time Complexity: O(m * n + mn * log(k)) in worst-case using a min-heap; or O(m * n * log(mn)) if sorting all values. Space Complexity: O(m * n) to store the XOR values (or O(m*n) for the prefix table if done separately).

Solution

The algorithm involves two main steps:

  1. Compute a prefix XOR table where each cell (i, j) is calculated based on the XOR results from above and left.
  2. Collect all XOR values and select the kth largest using either sorting (by descending order) or a min-heap of size k. Data Structures used include:
  • 2D list/array for storing prefix results.
  • List or heap to store and select the kth largest value. The prefix XOR trick reduces redundant recalculation of XORs, and the selection process uses a heap (or sorting technique) to efficiently retrieve the kth largest value.

Code Solutions

# Python solution with detailed comments
import heapq

def kthLargestValue(matrix, k):
    # Get dimensions of the matrix
    m, n = len(matrix), len(matrix[0])
    # Initialize prefix xor matrix with extra row and col for easier boundary handling
    prefix = [[0] * (n + 1) for _ in range(m + 1)]
    
    # List to collect all XOR coordinate values
    values = []  
    
    # Build prefix matrix and compute XOR values for each coordinate (i,j)
    for i in range(m):
        for j in range(n):
            # Compute the prefix xor using inclusion-exclusion principle
            prefix[i+1][j+1] = prefix[i][j+1] ^ prefix[i+1][j] ^ prefix[i][j] ^ matrix[i][j]
            # Append current XOR value to values list
            values.append(prefix[i+1][j+1])
    
    # Option 1: Sort the list in descending order and pick kth element (1-indexed)
    values.sort(reverse=True)
    return values[k-1]

# Example usage:
matrix1 = [[5,2],[1,6]]
k1 = 1
print(kthLargestValue(matrix1, k1))  # Output: 7
← Back to All Questions