Pairs under budget: hints, no solution
Medium · Two pointers
A podcast editor has a list of clip lengths in seconds, in no particular order, and wants to know how many two-clip combinations fit into an ad slot. A combination is a pair of positions i < j in the list. It fits when the two lengths add up to strictly less than the slot budget.
Return the number of pairs that fit. Two clips with the same length are different clips, so equal values at different positions form pairs of their own. Return 0 when the list has fewer than two clips or when no pair fits.
Examples
- Input
- clips = [3, 1, 4, 1, 5], budget = 6
- Output
- 5
- Note
- The five fitting pairs are (3,1), (3,1), (1,4), (1,1) and (4,1); sums must be below 6.
- Input
- clips = [1, 1, 1], budget = 2
- Output
- 0
- Note
- The best pair sums to exactly 2, which is not below the budget of 2.
- Input
- clips = [2, 2, 2], budget = 5
- Output
- 3
- Note
- All three pairs of clips sum to 4, under 5.
Constraints
- 0 <= clips.length <= 70000
- 1 <= clips[i] <= 9999
- 1 <= budget <= 20000
Hint 1: a nudge
Does the order of the clips in the list change how many pairs fit? What could you do to the list first?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.