How can we optimize this algorithm from O(N ** 2) to better complexity in order to pass performance test?

The solution aims to calculate the number of pairs of zeros and ones without redundancy

Let’s say that index 0 is with value 0 and index 1 is with value 1 which means that input looks like so: [0, 1]

And this simply means that we now have 1 pair and result should be 1

Another example: With the input [0, 1] in theory we should have 2 pairs [0, 1] and [1, 0] which are considered redundant and it should pick up only one of them so the result here should be 1

Another example: With input of [1, 0], the pairs should only start with indices of zeros not ones which means that [0, 1] is a successful pair but [1, 0] is not, and result in this case should be 0

And if the result exceeds 1000000000, then it should return -1

Currently I have a solution which achieves 100% correctness but in terms of performance it actually fails

The complexity of this solution is O(N ** 2)

The solution is as follows:

        int result = 0;
        int len = a.length;

        for (int i = 0; i < len; i++) {
            int current = a[i];

            if (current != 0) {
                continue;
            }

            for (int inner = i; inner < len; inner++) {
                if (current != a[inner]) {
                    result++;
                }
            }
        }

        return (result > 1000000000) ? -1 : result;

What I want to achieve is to introduce a lower complexity solution in order to pass the performance tests. Can we do something better?

Here are some test cases:

[0, 1, 0, 1, 1] expected result is 5 which are [0, 1], [0, 3], [0, 4], [2, 3], [2, 4]

[0, 1, 1, 1, 1] expected result is 4 which are [0, 1], [0, 2], [0, 3], [0, 4]

[0, 1, 0, 0, 1, 0, 1] expected result is 8 which are [0, 1], [0, 4], [0, 6], [2, 4], [2, 6], [3, 4], [3, 6], [5, 6]

Input samples must be a single array of 0s or 1s

But when input exceeds 10,000 records, then it fails the performance test to execute during a specific period of time ex: 0.6 sec.

>Solution :

You only need O(N) time to solve this problem, since you only need to iterate over the list exactly once.

You go backwards in the list and count how many 1 values you have. At each cell you check if you have a 1 or 0.

• If it is a 1, increase the counter.
• If it is a 0, then this 0 will be paired with all the already found 1s you have counted so far.

So you add the current count number of 1s to a total result in your algorithm. When you reached the end of the list, you are done and return the total result.

Example for your input [0, 1, 0, 0, 1, 0, 1]:

Input: 0100101
        |  | |  count=0, total=0
        |  | ^  count=1, total=0
        |  |^   count=1, total=1 (0+1)
        |  ^    count=2, total=1
        | ^     count=2, total=3 (1+2)
        |^      count=2, total=5 (3+2)
        ^       count=3, total=5
       ^        count=3, total=8 (5+3)

So you have your total number of 8 pairs (1+2+2+3) from your list [0, 1, 0, 0, 1, 0, 1].

(You can also go forward and count how many 0s you have and pair them with the 1s you found, resulting in 1+3+4=8 pairs)