1
\$\begingroup\$

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...

\$\endgroup\$
11
  • 2
    \$\begingroup\$ Welcome to Code Review! We generally provide open-ended feedback about all aspects of your code (see "Do I want feedback about any or all facets of the code?" in the help center). The current wording of your question suggests you only want to know why the computational complexity of your code is not what you expect. \$\endgroup\$
    – Graham
    Nov 20 '18 at 13:47
  • 1
    \$\begingroup\$ It isn't O(n*n) but Codility only estimates it by runtime. Is there any reason for using Map<Integer, Integer> instead of just int[] lowerSplitSumValue? You know the array will have same length as int[] A. Using Map in such case brings no benefits, it is only slower. Maybe that is enough to exceed time limits on task. \$\endgroup\$
    – user158037
    Nov 20 '18 at 15:28
  • 1
    \$\begingroup\$ Welcome to Code Review! The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ Nov 21 '18 at 8:17
  • 2
    \$\begingroup\$ "What is the complexity of my algorithm?" sounds like you don't understand your own code. "*Can I reduce the algorithmic complexity?" would sound more like (part of) a review request. You also should attempt to explain (in your own words) the problem you're solving, rather than just relying on a link. \$\endgroup\$ Nov 21 '18 at 8:45
  • 1
    \$\begingroup\$ All I can suggest is simply stating that you and the judge disagree on the complexity (and justify your reasoning), and let the reviewers choose whether to pick up on that. BTW, you should be able to solve this with an algorithm that scales as O(n), with no other containers needed. Think about how the left sum and right sum each change as you move one position along the input. \$\endgroup\$ Nov 21 '18 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.