K-th Largest Corner XOR

Medium

You are given an m × n table grid of non-negative integers and an integer k. The value of cell (a, b) is the XOR of every grid[i][j] in the rectangle stretching from the top-left corner to that cell inclusive, that is, with 0 ≤ i ≤ a and 0 ≤ j ≤ b. The table has exactly m · n such values. Return the k-th largest of them (k = 1 means the maximum; equal values are counted separately).

Example 1

grid=[[3, 4], [6, 1]], k=1 → 7

Cell values: (0,0) → 3, (0,1) → 3⊕4 = 7, (1,0) → 3⊕6 = 5, (1,1) → 3⊕4⊕6⊕1 = 0. The largest is 7.

Example 2

grid=[[3, 4], [6, 1]], k=3 → 3

In descending order the values are 7, 5, 3, 0, so the third one is 3.

Example 3

grid=[[9, 9, 2]], k=2 → 2

Constraints

1 ≤ m, n ≤ 1000
0 ≤ grid[i][j] ≤ 10⁶
1 ≤ k ≤ m · n

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

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

Similar problems

K-th Highest Score Medium Most Common Values Medium Nearest Points to the Base Medium Three Heaviest Diamonds Medium K-th Biggest Long Number Medium

Input

grid=[[3, 4], [6, 1]], k=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 89 tests on the server, hidden ones included.