Three-Slip Settlement Batches
Count triples of distinct array indices with sums in an inclusive range
A theater box office has a tray of unprocessed settlement slips. Each slip records a signed adjustment: a positive amount is a charge, a negative amount is a refund, and zero means no balance change.
You are given the adjustments in amounts and an inclusive settlement band from lower to upper. A candidate batch consists of exactly three different slips. The batch is acceptable when the sum of its adjustments lies within the settlement band.
Return the number of acceptable candidate batches.
Slips are distinguished by their positions in amounts, even when their adjustments are equal. The order of the three slips within a batch does not matter. Count all candidate batches independently; a slip may appear in multiple candidates. If there are fewer than three slips, return zero.
Examples
Example 1
Input: amounts = [-4,1,3,6], lower = 0, upper = 5 Output: 3
The triples with adjustments (-4, 1, 3), (-4, 1, 6), and (-4, 3, 6) fall within the settlement band. The triple (1, 3, 6) exceeds its upper limit.
Example 2
Input: amounts = [2,2,2,2], lower = 6, upper = 6 Output: 4
Every choice of three slips has total adjustment 6. Although all adjustments are equal, different choices of slip positions are different candidate batches.
Example 3
Input: amounts = [-3,8], lower = -10, upper = 10 Output: 0
There are not enough slips to form a batch of exactly three.
Constraints
- 0 <= amounts.length <= 2200
- -1000000 <= amounts[i] <= 1000000
- -3000000 <= lower <= upper <= 3000000
- All input values are integers.
The intended solution takes O(n^2) time and O(n) auxiliary space when sorting a copy. The maximum answer is 1,772,247,400, which is exactly representable by a JavaScript Number.
Hints
Show hint 1Hint 1
Can you express the answer using the number of triples with sum at most a chosen threshold?
Show hint 2Hint 2
After sorting and fixing the first slip, use two pointers for the remaining two. When a pair is small enough, how many choices can you count at once?
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you change the counting routine to count batches containing exactly four slips?
- If slips with equal adjustments were indistinguishable, how would you avoid counting the same adjustment multiset more than once?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem