1738. Find Kth Largest XOR Coordinate Value
Array Divide and Conquer Bit Manipulation Sorting Heap (Priority Queue) Matrix Prefix Sum Quickselect
Read the full problem statement on LeetCode.
Difficulty: medium Acceptance: 63% Topics: Array, Divide and Conquer, Bit Manipulation, Sorting, Heap (Priority Queue), Matrix, Prefix Sum, Quickselect
View full problem on LeetCode Reading material
Reference solution (spoiler · python)
# Time: O(m * n) on average
# Space: O(m * n)
import random
class Solution(object):
def kthLargestValue(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
def nth_element(nums, n, compare=lambda a, b: a < b):
def tri_partition(nums, left, right, target, compare):
mid = left
while mid <= right:
if nums[mid] == target:
mid += 1
elif compare(nums[mid], target):
nums[left], nums[mid] = nums[mid], nums[left]
left += 1
mid += 1
else:
nums[mid], nums[right] = nums[right], nums[mid]
right -= 1
return left, right
left, right = 0, len(nums)-1
while left <= right:
pivot_idx = random.randint(left, right)
pivot_left, pivot_right = tri_partition(nums, left, right, nums[pivot_idx], compare)
if pivot_left <= n <= pivot_right:
return
elif pivot_left > n:
right = pivot_left-1
else: # pivot_right < n.
left = pivot_right+1
vals = []
for r in xrange(len(matrix)):
curr = 0
for c in xrange(len(matrix[0])):
curr = curr^matrix[r][c]
if r == 0:
matrix[r][c] = curr
else:
matrix[r][c] = curr^matrix[r-1][c]
vals.append(matrix[r][c])
nth_element(vals, k-1, compare=lambda a, b: a > b)
return vals[k-1]
Solution from kamyu104/LeetCode-Solutions · MIT