Sort, then two pointers
When positions don't matter, sort first and walk inward. About 10 minutes.
When is sorting allowed?
Sorting moves values around, so their positions change. If a question asks for positions, like "the first index where", that is a problem. But if it asks how many pairs there are, or whether a pair exists, only the values matter, and you are free to sort first.
It is like counting how many couples at a party can share a cab: who stands where doesn't matter.
1 + 9 = 10 fits. 1 also fits with 3, 6 and 8: count = 4. Left moves right.
Sorting unlocks two pointers
You met this walk in Arrays. On a sorted list, if the cheapest and the dearest of the two ends fit the budget together, then the cheapest also fits with every value between them, because those are smaller. Count them all at once and move the left end up. If they don't fit, the right end is too dear for anyone, so move the right end down.
prices.sort()
count = 0
lo, hi = 0, len(prices) - 1
while lo < hi:
if prices[lo] + prices[hi] <= budget:
count += hi - lo
lo += 1
else:
hi -= 1
return countWhich of these can you solve by sorting the list first?
- ACount the pairs whose sum is at most 50
- BReturn the positions of two values that add up to 50
- CReturn the first value that repeats, from the left
Show the answer
Count the pairs whose sum is at most 50. Only the values matter, so sorting can't change the answer.
Pairs within a budget
Each value in prices is what one item costs, in no particular order. Count the ways to buy two different items (at two different positions) for a total of at most budget.
prices = [8, 1, 6, 3, 9], budget = 10 → 5
0 ≤ n ≤ 500,000 · 1 ≤ each price ≤ 1,000,000 · 1 ≤ budget ≤ 2,000,000 · the count can be too big for an int