Given a list of integers nums and an integer threshold, rearrange nums in place so that every value >= threshold comes first, in its original relative order, followed by all values < threshold (in any order). Return the number of values >= threshold.
Tests call (k := push_small_back(a := [...], t), a[:k], sorted(a[k:]))[1:], so the front part must be in order and the back part is compared after sorting.
Examples
Input: nums = [5, 1, 8, 2, 9], threshold = 3
Output: 3, nums starts with [5, 8, 9] and ends with {1, 2}
Input: nums = [1, 1, 1], threshold = 2
Output: 0
Constraints
0 <= len(nums) <= 10**5- Target: O(n) time, O(1) extra space.
Goals
- Compact the elements that satisfy a predicate to the front in one pass
- Return a boundary index that describes the new layout