Space
Open
From Fieldwork
Scales
Archive
It’s like a tournament bracket:
Divide the players into two brackets.
Sort the players within their own brackets (Recursion).
Compare players from Bracket A against Bracket B to find reverse pairs (The Counting Step). We can do this fast because they are sorted!
Merge the brackets into one big ranked list (The Sorting Step) so the next level up can repeat the process.
This is pretty nuanced. There's a logical leap here, and though the code's simple, the divide and conquer strategy warrants close investigation.
Sorting preserves relative order between two halves because... we're sorting the two halves. Not the whole thing.
class Solution:
def reversePairs(self, nums: list[int]) -> int:
def merge_sort(start, end):
if start >= end:
return 0
mid = (start + end) // 2
count = merge_sort(start, mid) + merge_sort(mid + 1, end)
# --- Counting Step ---
# Use two pointers to count reverse pairs between the two sorted halves
j = mid + 1
for i in range(start, mid + 1):
while j <= end and nums[i] > 2 * nums[j]:
j += 1
count += (j - (mid + 1))
# --- Standard Merge Step ---
nums[start:end+1] = sorted(nums[start:end+1])
return count
return merge_sort(0, len(nums) - 1)Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode