Summit trios
MediumOnline Assessment
Count the ways a guide can split hikers into roped teams of three for a ridge crossing.
Each hiker carries one pack, and packs[i] is the weight in kilograms of hiker i's pack. A team is any set of three different hikers. Two teams are different if they contain different hikers, even when the packs weigh the same. The order of hikers inside a team does not matter, and the order of packs is not sorted in any way.
A team may cross the ridge only if both safety rules hold:
- the heaviest pack and the lightest pack in the team differ by at most
spreadkilograms (so the rope hangs level), and - the three packs weigh at most
capkilograms in total (the rope anchor's rating).
Both limits are inclusive.
Input: packs, the list of pack weights, and the integers spread and cap.
Output: the number of different valid teams. If there are fewer than three hikers, return 0.
A busy base camp can have hundreds of hikers, so trying every possible trio will be too slow.
Example 1
- Input:
- [[4,5,6,9],2,16]
- Output:
- 1
- Explanation
- Only the trio 4, 5, 6 qualifies: its packs differ by 2 and weigh 15 in total. Any trio that includes the 9 kg pack has a difference of at least 3 between its lightest and heaviest pack, which is more than the allowed 2.
Example 2
- Input:
- [[3,3,3,4],1,9]
- Output:
- 1
- Explanation
- The three 3 kg packs form a team: no difference at all, total exactly 9, which is allowed because the cap is inclusive. Each team that uses the 4 kg pack weighs 10 and is over the cap. The answer is 1.
Example 3
- Input:
- [[8,1,5,2,6,3,7],3,15]
- Output:
- 3
- Explanation
- The packs in the order given are 8, 1, 5, 2, 6, 3, 7. Teams within 3 kg of each other and at most 15 kg in total: {1, 2, 3}, {2, 3, 5} and {3, 5, 6}. A trio like {5, 6, 7} is close enough but weighs 18, and {6, 7, 8} weighs 21.
Constraints
0 <= packs.length <= 7001 <= packs[i] <= 1,000,0000 <= spread <= 1,000,0000 <= cap <= 3,000,000