I'm struggling to find an algorithm for this problem that runs in O(n) worst case time.

Let's say you have an array, of n elements, with the value of the elements being either 1 or 0. I need to calculate the number of sub-arrays where there exists more 1's inside the sub-array than there are 0's outside the sub-array.

what i tried to do:

i tried to first make a prefix-sum array of the input array, this is so that when given a sub-array, we grab the start and end indexes of the sub array, look at the corresponding values in the prefix array -> we can find out the number of 1s in the sub-array in O(n) time.

for example:

input array = [1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1]

prefix sum array = [0, 1, 1, 1, 2, 3, 3, 4, 4, 4, 5, 6, 6, 7]

example sub array = [1,0,0,1]

start index = 0, end index = 3

prefix[3 1] - prefix[0] = 2 - 0 = 2 (two 1s inside the sub

array)

I am not sure where to go from here. Help would be much appreciated.

CodePudding user response：

It is a very strange constraint, but after making the following observation it becomes easy:

Enlarging the sub-array always improves its value. We define the value v = i - o, whith i being the ones inside the sub-array and o the number of zeros outside the sub-array. Now another way to formulate the problem is: count all sub-arrays with a value greater than zero. Here is why the value always improves when enlarging the array:

• adding a 0 to the sub-array: v = i - (o - 1) = i - o 1 this is one greater compared to i - o.
• adding a 1 to the sub-array: v = (i 1) - o = i - o 1 this is one greater compared to i - o.

So we can see that enlarging the sub-array not only increases its value, enlarging the sub-array by n elements increases the score exactly by n. Also decreasing the size of the sub-array by n decreases its value by n. This leads to the conclusion that we can calculate a minimum size for the sub-array and then use that number and the array size to get the number of sub-arrays fullfilling the condition.

So here is an O(n) algorithm:

1. Count the number of 0s in the array => z
2. if z = n return 0
3. The size making the value 0 is: m = z (by counting the zeros we look at it like having a sub-array of size 0, so the number of ones inside is 0 and the number of zeros outside is z, this gives a value v = 0 - z = -z, so if we increase the size by z we get a value of 0)
4. So finally we can start at index 0 with a sub-array, here we can count all sub-arrays of sizes m < size < n, so the number of sub-arrays for index 0 is n - m, at index 1 it is n - m - 1 and at index i it is n - m - i (as long as the therm is > 0). Because we know the term will reach zero because the minimum size for the sub-array is 1 we can get the following formula: count = (n - m) * (n - m 1) / 2

And condensed: count the number of 0s z and return (n - z) * (n - z 1) / 2

Which is the same as counting the number of 1s i and return i * (i 1) / 2 (because n - z = i)

CodePudding user response：

maraca's answer is good but here is another way to look at it.

Let n be the number of elements in the input array, and i the number of ones in the input array.

Let the value of a sub-array be the number of ones inside minus the number of zeroes outside. A sub-array counts if its value is greater than 0.

The value of the sub-array of size n is i, so if i is greater than 0, that sub-array counts.

If the value of all sub-arrays of size n-(t-1) is j, then the value of all sub-arrays of size n-t is j-t. This is because any sub-array of size n-t can be obtained by excluding an element from a sub-array of size n-(t-1), and whatever that element is, it decreases the value of the sub-array by exactly 1: it's either 1 more zero outside, or 1 less one inside.

By induction, this means the value of all sub-arrays of size n-t is i-t. It also means a sub-array of value i-t has size n-t.

Only sub-arrays of value i-t where t < i count, so only sub-arrays of size n-t where t < i count. There are n-(s-1) sub-arrays of size s (1 of size n, 2 of size n-1, ..., n of size 1), so there are n-(n-t-1) = t 1 sub-arrays of size n-t. And the sum of t 1 from t = 0 to t = i-1 equals i*(i 1)/2, also known as the i-th triangular number.