Count Pairs Under Budget
MediumTwo Pointers
Problem
A gift shop lists item prices in prices (in no particular order). A customer wants to buy exactly two different items and spend at most budget.
Return the number of index pairs i < j with prices[i] + prices[j] ≤ budget.
Example 1
- Input:
- prices = [7, 2, 5, 1, 9], budget = 8
- Output:
- 4
The affordable pairs are (2, 5), (2, 1), (7, 1) and (5, 1).
Example 2
- Input:
- prices = [3, 3, 3], budget = 6
- Output:
- 3
Every pair of the three items costs exactly 6.
Constraints
- 1 ≤ prices.length ≤ 10^5
- -10^4 ≤ prices[i] ≤ 10^4 (negative values are discounts)
- -2·10^4 ≤ budget ≤ 2·10^4
Hint
Show the first hint
The pair count does not depend on the original order, so you are free to sort.
Walkthrough
How to approach it
01Clarify before coding
- Is it 'at most' or 'strictly less than'? At most: a sum equal to budget counts.
- Are pairs counted by index or by value? By index, so equal prices at different positions are separate pairs.
- Can the count be large? Up to about 5·10^9 for n = 10^5; Python integers and JS doubles handle it exactly.
02Brute force
Check all pairs i < j and count those within budget.
Cost: O(n²) time: 5·10^9 checks for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.