Codility AbsDistinct: Why is this solution not O(n)? This is part of a series of algorithmic lessons and tests by Codility.

For copyright reasons, I cannot reproduce the question, which asks to compute the number of distinct absolute values in a given sorted array.

The question requires a response in \$O(n)\$ time complexity. My response (below) was detected as \$O(n*log(n))\$ by Codility, but I have no idea why. It looks to me like we're only going to go over each item of the array once. Am I wrong or is this \$O(n)\$?

public int solution(int[] A) {
    // write your code in Java SE 8
    int result = 0;
    int start = 0;
    int end = A.length - 1;

    while (start &lt;= end) {
        result++;
        int startValue = Math.abs(A[start]);
        int endValue = Math.abs(A[end]);
        int currentValueFound = Math.max(startValue, endValue);
        while (start &lt;= end &amp;&amp; Math.abs(A[start]) == currentValueFound) {
            start++;
        }
        while (start &lt;= end &amp;&amp; Math.abs(A[end]) == currentValueFound) {
            end--;
        }
    }
    return result;
}


In addition, if anyone has an idea what could have triggered the error in the arth_overflow test, I am interested.
I don't see any reason why your solution would not be O(N).

However, it would fail if the array contained Integer.MIN_VALUE, since its absolute value won't fit within an int.