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)