Pairs Below a Budget
Problem
A shop lists item prices, and a price can even be negative after a refund. Count the pairs of two different items whose prices add up to strictly less than a budget. Two items at different positions form a separate pair even if their prices are equal.
Examples
Input: prices = [4, -2, 0, 3, 1], budget = 3
Output: 5
Why: (4, -2), (-2, 0), (-2, 3), (-2, 1) and (0, 1) all add up to less than 3Input: prices = [2, 2, 2], budget = 5
Output: 3
Why: each of the three ways to pick two of the 2s adds up to 4Input: prices = [5], budget = 100
Output: 0
Why: edge case, one item cannot form a pairHints
0 / 3
Two nested loops check every pair and are easy to get right. They are also quadratic, so a list ten times longer takes a hundred times as long.
The order of the prices does not change the answer, so you are free to sort them first. In a sorted list, if the smallest and the largest remaining prices fit, what does that tell you about the prices in between?
Sort, then put one pointer at each end. If the two prices fit under the budget, the left price pairs with every price up to the right pointer, so add that count and move left inwards. Otherwise the right price is too big for anything still available, so move right inwards.
Solution
Sorting lets one comparison settle many pairs at once. When the smallest remaining price plus the largest remaining price is under the budget, every price between them also fits with the smallest one, so all of those pairs are counted and the smallest is retired. When the sum is too big, the largest price cannot fit with anything left and is retired instead. Each step retires one price, so the scan after sorting is linear. Time is O(n log n) for the sort, and space is O(n) for the sorted copy.
def pairs_below(prices, budget):
p = sorted(prices)
left, right, count = 0, len(p) - 1, 0
while left < right:
if p[left] + p[right] < budget:
count += right - left # p[left] fits with every price up to right
left += 1
else:
right -= 1 # p[right] fits with nothing left
return count
print(pairs_below([4, -2, 0, 3, 1], 3)) # -> 5
print(pairs_below([2, 2, 2], 5)) # -> 3
print(pairs_below([5], 100)) # -> 0Stuck on the idea rather than the code? O(n²) and Nested Loops covers it.