'Minimum operations needed to make array perfect

Given an array of 1s and -1s the task is to make array perfect

If array satisfies below conditions then it is said to be perfect

  1. all possible prefixes should have sum strictly greater than 0 and
  2. all possible suffixes should have sum strictly greater than 0

The task here is to find the minimum operations required to make array perfect. Acceptable Complexity : O(N)

For Example

Consider array [1, -1, 1] there is a prefix [1,-1] whose sum is 0, same for suffix minimum operations needed to make array perfect is 1 that is make -1 into 1.

Consider array [1, 1, -1, 1, 1] No prefix or Suffix has the sum <= 0 so no modifications are needed, output 0

I've tried traversing from left to right and right to left and calculated the sum whenever sum becomes 0 i made that element 1, hope this is not the correct approach. Any idea on how this can be solved in O(N) or less.



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source