Skip to main content
1 of 2
Steven
  • 29.6k
  • 2
  • 28
  • 49

Let $A = \langle a_1, \dots, a_n \rangle$ be the input array. I will only consider the case $n \ge 3$, otherwise the problem is trivial.

The key property is that the order relation between all but one pair of consecutive elements modulo $n$ in $A$ will be "greater than" if $A$ is some circular shift of an increasing array (possibly the trivial shift by $0$), and "less than" if $A$ is some circular shift of a decreasing array. Examining the first and last elements suffices to determine if the shift is trivial or not.

In practice you can determine the type of $A$ in constant time, as follows:

  • Look the majority value $x$ among $\textrm{sign}(a_n-a_1)$, $\textrm{sign}(a_2-a_1)$, and $\textrm{sign}(a_3-a_2)$.

  • If $x = +1$ then $A$ is some circular shift of an increasing array. If $\textrm{sign}(a_n-a_1)=1$, $A$ is of type "ascending", otherwise it is of type "ascending rotated".

  • If $x = -1$ then $A$ is some circular shift of a decreasing array. If $\textrm{sign}(a_n-a_1)=-1$, $A$ is of type "descending", otherwise it is of type "descending rotated".

As for returning the maximum, I will only discuss the case in which $A$ is a circular shift of an increasing array (the complementary case is handled similarly). Notice that, if the maximum element is in some position $a_j$, then all $a_1, \dots, a_j$ are larger than or equal to $a_1$, while all ements $a_{j+1}, \dots, a_n$ are smaller than $a_1$. This allows you to binary search for the last element that is larger than or equal to $a_1$, i.e., $a_j$.

Steven
  • 29.6k
  • 2
  • 28
  • 49