How to tweak Tape Equilibrium assignment on Codility to be of complexity O(N)? Why Codility detects my solution for Tape Equilibrium to have complexity of \$O(n^2)\$. How can I make my code better?

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.IntStream;

class Solution {
    public int solution(int[] A) {
        boolean eachIntegerIsWithinValidRange = IntStream.of(A).allMatch(i -&gt; (i &gt;= -1000 &amp;&amp; i &lt;= 1000));
        boolean numberOfElementsIsWithinDesignatedBounds = A.length &gt;= 2 &amp;&amp; A.length &lt;= 100000;

        if (numberOfElementsIsWithinDesignatedBounds &amp;&amp; eachIntegerIsWithinValidRange) {
            List&lt;Integer&gt; differences = new ArrayList&lt;Integer&gt;();
            if (A.length &lt; 3) {
                Arrays.sort(A);
                return A[0];
            }

            for (int j = 0; j &lt; A.length - 1; j++) {
                int[] subArrayOne = Arrays.copyOfRange(A, 0, j + 1);
                int[] subArrayTwo = Arrays.copyOfRange(A, j + 1, A.length);
                int sumOne = IntStream.of(subArrayOne).sum();
                int sumTwo = IntStream.of(subArrayTwo).sum();

                differences.add(Math.abs(sumOne - sumTwo));
            }
            Collections.sort(differences, (o1, o2) -&gt; o1.compareTo(o2));
            return differences.get(0);
        } else if (!eachIntegerIsWithinValidRange) {
            throw new RuntimeException("There is/are integer that is out of designated bound: -1000 to 1000");
        } else if (!numberOfElementsIsWithinDesignatedBounds) {
            throw new RuntimeException("Invalid array size. Allowed number of elements is more than 1 and less than 100,001");
        }
        return 0;
    }
}
General improvements


Your method can be made static
Your variable name A would be better as input
By using "early return" or "early throw", your intendation level can be improved a bit
Collections.sort(differences, (o1, o2) -&gt; o1.compareTo(o2)); can be just Collections.sort(differences);
You are using A.length &lt; 3 as an edge case, I would just consider A.length &lt;= 1 as an edge case, the rest should be possible to be handled by your algorithm.


Why is your approach \$O(n^2)\$?

Consider what this code is actually doing:

for (int j = 0; j &lt; A.length - 1; j++) {
    int[] subArrayOne = Arrays.copyOfRange(A, 0, j + 1);
    int[] subArrayTwo = Arrays.copyOfRange(A, j + 1, A.length);
    int sumOne = IntStream.of(subArrayOne).sum();
    int sumTwo = IntStream.of(subArrayTwo).sum();

    differences.add(Math.abs(sumOne - sumTwo));
}
Collections.sort(differences, (o1, o2) -&gt; o1.compareTo(o2));


For every index in your array it does the following things:


Create an subarray, which is an \$O(n)\$ operation
Calculate the sum of the two newly created arrays, which is an \$O(n)\$ operation


These operations makes your code become \$O(n^2)\$

Additionally, it then afterwards does a Collections.sort operation which is \$O(n * log(n))\$

How to do it faster


Initialize a variable sum to be the sum of your whole array, and a sum2 to be 0
For every index, decrease sum with the current value, and increase sum2 with the current value. Then create a diff for sum and sum2 and see if it is lower than the previous lowest record.


Spoiler alert: Here is what I ended up with.

public static int solution(int[] input) {
    boolean eachIntegerIsWithinValidRange = IntStream.of(input).allMatch(i -&gt; (i &gt;= -1000 &amp;&amp; i &lt;= 1000));
    boolean numberOfElementsIsWithinDesignatedBounds = input.length &gt;= 2 &amp;&amp; input.length &lt;= 100000;

    if (!eachIntegerIsWithinValidRange) {
        throw new RuntimeException("There is/are integer that is out of designated bound: -1000 to 1000");
    }
    if (!numberOfElementsIsWithinDesignatedBounds) {
        throw new RuntimeException("Invalid array size. Allowed number of elements is more than 1 and less than 100,001");
    }
    if (input.length == 0) {
        return 0;
    }

    int sum = IntStream.of(input).sum() - input[0];
    int sum2 = input[0];
    int lowestDiff = Math.abs(sum - sum2);
    for (int j = 1; j &lt; input.length - 1; j++) {
        int value = input[j];
        sum -= value;
        sum2 += value;
        int diff = Math.abs(sum - sum2);
        if (diff &lt; lowestDiff) {
            lowestDiff = diff;
        } else {
            return lowestDiff; // diff will not get any lower
        }
    }
    return lowestDiff;
}