2

Input is an array of integers, and a "move" is an operation removing a single element and placing it at the end of the array.

Find the minimum number of moves so the sum of any contiguous subsequence starting at the first element is non-negative

I would like to find the time-complexity optimal solution.

It is guaranteed that it's possible to find a sequence of moves such that after it the sum of every subsequence of the array(from the start of it) is non-negative.

e.g.:

for input: [1,3,-4,1] result is 0, since any subsequence starting at the first element is non-negative. {1}=1,{1,3}=4,{1,3,-4}=0,{1,3,-4,1}=1

for input: [1,3,-5,1] result is 1, since the sum of subsequence {1,3,-5} is negative, so a single move -5 is performed to create [1,3,1,-5]. Then every subsequence sum is non-negative. {1}=1,{1,3}=4,{1,3,1}=5,{1,3,1,-5}=0

for input: [15,-10,-11,1,-7,12]

result is 2, moving -11 and then -10, which will look like that:

[15,-10,1,-7,12,-11] - {15,-10,1,-7}=-1 - negative!

[15,1,-7,12,-11,-10] - {15}=15,{15,1}=16,{15,1,-7}=9,{15,1,-7,12}=21,{15,1,-7,12,-11}=10,{15,1,-7,12,-11,-10}=0

guruguru
  • 21
  • 2
  • Are you sure the word you're looking for is "non-negative"? I don't understand why you say that in `[1,3,1,-5]`, "every subsequence is non-negative". Surely -5 is negative? – Stef Nov 11 '21 at 10:50
  • @Stef Every contiguous sequence that starts at the first element of the array. So `[1], [1,3], [1,3,1], [1,3,1,-5]` – user3386109 Nov 11 '21 at 10:52
  • @user3386109 That still doesn't explain how -5 is non-negative? It's definitely a negative number. – Stef Nov 11 '21 at 10:55
  • @Stef The sum of the sequence is non-negative. The only sequence that includes -5 is `[1,3,1,-5]` which has a sum of 0. – user3386109 Nov 11 '21 at 10:56
  • @user3386109 I see. You should edit the question. The word "sum" is extremely important here, and you didn't include it in the question. – Stef Nov 11 '21 at 10:57
  • edited(the title turned up a bit verbose) and improved the samples – guruguru Nov 11 '21 at 11:42
  • The general idea is to compute the cumulative sum starting from the first element. When you reach an element that makes the sum negative, move the most negative element to the end of the array. For example, given `[15,-10,-11,1,-7,12]` the sums are `sum([15]) = 15`, `sum([15,-10]) = 5`, `sum([15,-10,-11]) = -6`. Since the sum is negative at that point, and -11 is the most negative number, move the -11 to the end. Note that with a large array (30K or more elements, you'll want to use a priority queue to hold the negative numbers that have been seen so far. – user3386109 Nov 11 '21 at 18:20
  • Does [this](https://stackoverflow.com/questions/69675180/minimum-reallocations-required-to-make-all-prefix-sum-0) answer your question? It appears to be an identical problem, and the posted answer will work here. – kcsquared Nov 11 '21 at 20:55
  • @user3386109 so N insertions/deletions to the priority queue(supposing it's implemented using a min-heap or self balancing BST), which means the solution complexity is O(Nlog(N)). Is that optimal? – guruguru Nov 12 '21 at 02:13
  • @kcsquared yeah, but they didn't really properly discuss an optimal solution complexity. I think user3386109 got the working solution, but I'd like to verify that O(Nlog(N)) is optimal. – guruguru Nov 12 '21 at 02:20
  • I would recommend editing the question to ask specifically for optimal complexity, given that a reasonably efficient solution has already been shown. For a start on researching, consider the much easier special case where the array has exactly two positive elements, at each end. This is exactly the problem from [this post](https://stackoverflow.com/questions/5963983/find-the-minimum-number-of-elements-required-so-that-their-sum-equals-or-exceeds). A linear-time solution for that problem exists, but involves recursion with linear-time quickselect. – kcsquared Nov 12 '21 at 04:41
  • 1
    @kcsquared edited as you suggested. The solution there relies on heapifying the entire array which is O(N), but doesn't help me here since I need the heap of the current subarray, e.g. if I'm on index i, I need the heap of [0,i]. This mean N insertions to a heap which is still O(Nlog(N)). – guruguru Nov 12 '21 at 05:42

0 Answers0