Minimum Elements Moved to the Back for Nonnegative Prefixes

Reported in interviews at Qube Research Technologies

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.

Related free problems