Count pairs below a target
One check can count a whole group of pairs. About 10 minutes.
One check can count many pairs
Same two fingers, new question: how many pairs add up to less than the target?
Suppose the left and right values together are below the target. Everything between them is no bigger than the right value, so the left value paired with any of them is below the target too. That one check just counted a whole batch of pairs: one for every item between the fingers. After that, the left item is done, so move it right.
1 + 9 = 10 is not below 8. 9 pairs with nothing, so right moves left.
Too big? The right item has to go
If the sum isn't below the target, the right item is too big even with the smallest item left. It can't be part of any pair you still need, so move the right finger left and count nothing.
Every step moves a finger, so the walk ends quickly. One thing to watch: with a million items there can be about 500 billion pairs, more than a normal whole number holds in some languages. Use a 64-bit number for the count.
left, right, count = 0, len(nums) - 1, 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left
left += 1
else:
right -= 1
return count1 + 6 = 7 is below the target of 8. How many pairs does this one check count?
1, 2, 4, 6, 9 · left finger on 1 (box 0), right finger on 6 (box 3)
- A3
- B1
- C4
Show the answer
3. 1 pairs with 2, 4 and 6: every item between the fingers, 3 of them.
Count pairs below a target
You get numbers sorted from smallest to largest, and a target. Count the pairs of positions i < j where nums[i] + nums[j] is strictly less than the target, and return the count.
nums = [1, 2, 4, 6, 9], target = 8 → 4
0 ≤ n ≤ 1,000,000 · sorted ascending · −1,000,000 ≤ each value ≤ 1,000,000 · return a long