Find magnitude pole of an array Please review this code, considering I put emphasis on constraining space complexity at the expense of execution speed (accepting additional branching).


Can you see cases that prove the algorithm incorrect?
Could you improve its execution speed without increasing space complexity?
Could you make it more readable?


Method signature from Codility (i.e. strange capitalised parameter name).

Definition of "magnitude pole": available online (e.g. https://stackoverflow.com/questions/15397637/interview-find-magnitude-pole-in-an-array)

import java.util.Arrays;
public class MagnitudePole {
  public int solution(int[] A) {
    final int notFound = -1;
    final int minimumArrayLength = 2;
    if (A.length &lt; minimumArrayLength) {
      return notFound;
    }
    int magnitudePole = 0;
    boolean isPoleValid = true;
    int highestSeen = A[magnitudePole];
    for (int i = 1; i &lt; A.length; i++) {
      final int currentValue = A[i];
      if (currentValue &lt; A[magnitudePole]) {
        isPoleValid = false;
      } else if (currentValue &gt; A[magnitudePole]) {
        if (currentValue &gt; highestSeen &amp;&amp; !isPoleValid) {
          isPoleValid = true;
          magnitudePole = i;
        }
      } else {
        if (currentValue &lt; highestSeen) {
          isPoleValid = false;
        } else {
          isPoleValid = true;
          magnitudePole = i;
        }
      }
      highestSeen = Math.max(currentValue, highestSeen);
    }
    return isPoleValid ? magnitudePole : notFound;
  }
}
Style

final int notFound = -1;
final int minimumArrayLength = 2;


These two fields can be better placed as private static final fields, instead of inside the method. On a related note, you may also want to consider turning this into an "utility class" and have the method as static too:

public class MagnitudePole {

    private static final int notFound = -1;
    private static final int minimumArrayLength = 2;

    private MagnitudePole() {
        // empty
    }

    // using an arguably better-sounding name... MagnitudePole.solveFor(int[])
    public static int solveFor(int[] A) {
        // ...
    }
}


For the currentValue &gt; A[magnitudePole] else-if condition, you can join that with the inner if:

There's a bug here all right... The else should only be done on the original outer condition, so if the inner ifconditions fail it shouldn't reach there. Slightly edited the code block so as not to invalidate the comments on this part. :)

if (currentValue &lt; A[magnitudePole]) {
    isPoleValid = false;
} else if (currentValue &gt; A[magnitudePole] &amp;&amp; currentValue &gt; highestSeen &amp;&amp; !isPoleValid) {
    isPoleValid = true;
    magnitudePole = i;
} else {
    /* this should only be reached when
        currentValue &lt;= A[magnitudePole],
        bug in preceding else-if! */
}


Finally, in the else part, you can also re-order the conditions around as such:

} else {
    isPoleValid = currentValue &gt;= highestSeen;
    if (isPoleValid) {
      magnitudePole = i;
    }
}


Logic + unit testing

You perform a check for the array to contain at least two elements, which means single-element arrays are conveniently bypassed. Do you actually want to consider them as magnitude poles, since all the LHS and RHS elements ("none", or \$\emptyset\$) are equal to it? :)

I will also suggest writing unit tests as a means of documenting what are the expected outputs for various inputs - valid, invalid, and edge cases in all. The slight benefit is that you can safely optimize your logic later on, and have a safety mechanism to ensure the modifications still work per expectation.