2
$\begingroup$

Consider this problem: You are given an array $A$ (of distinct integers) of one out of the following four types:

  • Ascending (e.g., 1,2,4,6);
  • Descending (e.g., 6,4,2,1);
  • Ascending rotated (a non-trivial circular shift of an ascending array, e.g., 4,6,1,2);
  • Descending rotated (a non-trivial circular shift of an descending array, e.g., 4,2,1,6).

The task is to determine the type and the maximum element of $A$.

Since $A$ is "sorted", is there a $O(\log n)$-time approach or is the best possible time complexity $O(n)$, as suggested in the link?

$\endgroup$
  • 3
    $\begingroup$ Please include the question as part of your post. The link could rot in the future. $\endgroup$ – Yuval Filmus Nov 1 '19 at 16:45
  • $\begingroup$ The question has been put on hold seconds before I could post my answer. Am I allowed to edit the question even if I'm not the original poster? $\endgroup$ – Steven Nov 1 '19 at 18:31
  • $\begingroup$ @Steven yes, and edit was very good. $\endgroup$ – Evil Nov 2 '19 at 4:20
  • 1
    $\begingroup$ Let N>= 3 be the array size, n = N/3, m=2N/3, x=position of last element. Read a, b, c from index 0, n and m. a, b, c can be sorted in six different ways, and each corresponds to one of the six cases array sorted in ascending/descending order, and x<n, n<=x<m, and x>= m. The rest is binary search in a sub array of size N/3, so O(log N). $\endgroup$ – gnasher729 Nov 2 '19 at 10:36
  • $\begingroup$ What did you try? Where did you get stuck? Can you recognize any of the four cases? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Nov 3 '19 at 7:31
4
$\begingroup$

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_1-a_n)$, $\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_1-a_n)=-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_1-a_n)=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$.

$\endgroup$
  • 1
    $\begingroup$ No doubt this is a great answer as per me. But, I think we should consider $x$ as majority of $sign(a_1-a_n), sign(a_2-a_1)$ and $sign(a_3 - a_2)$. Because I'm getting wrong answer if I follow above approach with sequence $6,3,4,5$. $\endgroup$ – Vimal Patel Nov 2 '19 at 11:07
  • $\begingroup$ Ughh. You are right! Thanks for spotting that. $\endgroup$ – Steven Nov 2 '19 at 11:13
0
$\begingroup$

if we are given with first two cases i.e Ascending sorted array and descending sorted arrays we can simply find the difference b/w last element of array and first element of array i.e (last element of array - first element of arrays)if difference is positive then it is ascending order and maximum element is the element at last index of array (in ascending sorted arrays ) and vice versa. it takes just 0(1) in that case.

$\endgroup$
  • 1
    $\begingroup$ We don’t know which of the four cases it is, finding which case is part of the problem. $\endgroup$ – gnasher729 Nov 3 '19 at 13:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.