Krdytkyu

This question is related to this one, since it's about the same Codility exercise (Tape Equilibrium instructions): Time complexity of tape equilibirum

Basically, given an integer array, the objective is to split it at a given index into 2 smaller arrays, sum each arrays and find the smallest absolute difference possible between the 2 arrays.

Example:

I have an array A = {3, 1, 2, 4, 3}.

If I split at index 1, left array is {3} and right array is {1, 2, 4, 3}. The absolute difference is |(3) - (1 + 2 + 4 + 3)| = 7.

The smallest possible split is with index 3, where left array is {3, 1, 2} and right array is {4, 3} and the absolute difference is |(3 + 1 + 2) - (4 + 3)| = 1.

I have written the following code:

class Solution {



    private Map<Integer, Integer> lowerSplitSumValue;

    private Map<Integer, Integer> upperSplitSumValue;



    public void loadSplitSumValue(int A) {

        if (lowerSplitSumValue == null) {

            lowerSplitSumValue = new HashMap<Integer, Integer>();

            upperSplitSumValue = new HashMap<Integer, Integer>();

        }



        for (int i = 1 ; i < A.length ; ++i) {

            if (i != 1) {

                lowerSplitSumValue.put(i, lowerSplitSumValue.get(i - 1) + A[i - 1]);

                upperSplitSumValue.put(A.length - i, upperSplitSumValue.get(A.length - i + 1) + A[A.length - i]);

            } else {

                lowerSplitSumValue.put(i, A[0]);

                upperSplitSumValue.put(A.length - i, A[A.length - 1]);

            }

        }

    }



    public int solution(int A) {

        if (A == null || A.length < 1) {

            return 0;

        }



        loadSplitSumValue(A);



        int smallestValue = Math.abs(lowerSplitSumValue.get(1) - upperSplitSumValue.get(1));



        for (int i = 2 ; i < A.length - 1 ; ++i) {

            int newValue = Math.abs(lowerSplitSumValue.get(i) - upperSplitSumValue.get(i));



            if (newValue < smallestValue) {

                smallestValue = newValue;

            }

        }



        return smallestValue;

    }

}

From my understanding, this should be at most $O(N*log(N))$:

• I'm using several for loops, but none of them are nested, so their complexity is $O(N)$.


• Each for loops are accessing a Map, which to my understanding have a general complexity of $O(log(N))$.

However, when I submit this code on Codility, the compiler says only 33% of the performance tests passed, and the complexity is $O(N*N)$, which is way higher than what I expected...

Why does Codility consider my algorithm to be $O(N*N)$? Java Maps aren't supposed to be that slow...