snippetjavaMinor

How to tweak Tape Equilibrium assignment on Codility to be of complexity O(N)?

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

equilibriumcodilityassignmenttweaktapehowcomplexity

Problem

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 -> (i >= -1000 && i = 2 && A.length  differences = new ArrayList();
            if (A.length  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;
    }
}

Solution

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) -> o1.compareTo(o2)); can be just Collections.sort(differences);

You are using A.length




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

Consider what this code is actually doing:

for (int j = 0; j  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 -> (i >= -1000 && i = 2 && input.length <= 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 < input.length - 1; j++) {
        int value = input[j];
        sum -= value;
        sum2 += value;
        int diff = Math.abs(sum - sum2);
        if (diff < lowestDiff) {
            lowestDiff = diff;
        } else {
            return lowestDiff; // diff will not get any lower
        }
    }
    return lowestDiff;
}

Code Snippets

for (int j = 0; j < 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) -> o1.compareTo(o2));

public static int solution(int[] input) {
    boolean eachIntegerIsWithinValidRange = IntStream.of(input).allMatch(i -> (i >= -1000 && i <= 1000));
    boolean numberOfElementsIsWithinDesignatedBounds = input.length >= 2 && input.length <= 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 < input.length - 1; j++) {
        int value = input[j];
        sum -= value;
        sum2 += value;
        int diff = Math.abs(sum - sum2);
        if (diff < lowestDiff) {
            lowestDiff = diff;
        } else {
            return lowestDiff; // diff will not get any lower
        }
    }
    return lowestDiff;
}

Context

StackExchange Code Review Q#107148, answer score: 7

Revisions (0)

No revisions yet.