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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Kth Largest XOR Coordinate Value

Difficulty: Medium

Problem Description

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.

Key Insights

  • The value at each coordinate (a, b) is computed using the XOR operation over a submatrix defined by the top-left corner (0, 0) to (a, b).
  • We can derive the XOR values for each coordinate using a prefix XOR approach.
  • The problem can be reduced to finding the kth largest element among the calculated XOR values, which can be efficiently done using sorting or a min-heap.

Space and Time Complexity

Time Complexity: O(m * n log(m * n)), where m is the number of rows and n is the number of columns (due to sorting). Space Complexity: O(m * n), for storing the XOR values.

Solution

To solve the problem, we need to calculate the XOR values for each coordinate in the matrix efficiently. We can use a prefix XOR array to store the cumulative XOR up to each index. Once we have the XOR values, we can store them in a list, sort the list, and return the kth largest value.

  1. Initialize a 2D list to store the XOR values.
  2. Use nested loops to calculate the XOR for each coordinate using the prefix XOR logic.
  3. Store all the XOR values in a single list.
  4. Sort the list of XOR values in descending order.
  5. Return the kth largest value from the sorted list.

Code Solutions

def kthLargestValue(matrix, k):
    m, n = len(matrix), len(matrix[0])
    xor_matrix = [[0] * n for _ in range(m)]
    
    for i in range(m):
        for j in range(n):
            xor_matrix[i][j] = matrix[i][j] ^ (xor_matrix[i - 1][j] if i > 0 else 0) ^ (xor_matrix[i][j - 1] if j > 0 else 0) ^ (xor_matrix[i - 1][j - 1] if i > 0 and j > 0 else 0)
    
    # Collect all XOR values
    xor_values = []
    for i in range(m):
        for j in range(n):
            xor_values.append(xor_matrix[i][j])
    
    # Sort and find the kth largest
    xor_values.sort(reverse=True)
    return xor_values[k - 1]
← Back to All Questions