Minimum Elements Moved to the Back for Nonnegative Prefixes
Problem statement
You are given an integer array (values may be negative) whose total sum is guaranteed to be nonnegative. You may move elements to the back of the array. What is the minimum number of elements you must move so that every prefix sum of the resulting array is nonnegative?
Constraints:
- 2 <= n <= 10^5
- The total sum of the array is nonnegative.
Examples:
- [3, -4, 2] -> 1 (move -4 to the back: [3, 2, -4] has prefix sums 3, 5, 1).
- [1, 2, 3] -> 0 (all prefix sums are already nonnegative).
- [2, -1, -1, 3, -2] -> 0 (prefix sums 2, 1, 0, 3, 1 are all nonnegative).
Show hint
What do the prefix sums look like if you read the array left to right and ask where things first go wrong?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.