279. Partition Around a Value
Core1000 ms256 MBSolved by 0%
Given n integers and a pivot value p, print three numbers separated by
spaces: how many values are less than p, how many equal it, and how many are
greater.
That three-way split is the partition step at the heart of quicksort, and counting it first is the easiest way to understand what quicksort is doing before writing the version that rearranges the array in place.
The pivot need not appear in the array at all, in which case the middle count is 0.
Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ p ≤ 1000000000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and p.
The second line contains n integers.
Output
Print three integers separated by spaces: the counts less than, equal to, and greater than p.
Input5 3
3 1 4 1 5
Output2 1 2
Notehas values on both sides and one equal
Input1 1
1
Output0 1 0
Noteis a single element equal to the pivot
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.