PhD Admissions Written Test (Basic)

Question

Let A be an array containing n integers. It is required to find 3 indices i, j, k such that i < j < k and either A[i] ≤ A[j] ≤ A[k] or A[i] ≥ A[j] ≥ A[k], if such indices exist. The asymptotic time complexity of the fastest algorithm for this problem, assuming the array is already available, is Θ(_____________).

Answer 1

This can be done in O(1) time

Argument 1:

 Assume all the numbers are distinct. Check the first 3 numbers. Let them be $a_i$, $a_j$ and $a_k$. If they are increasing or decreasing, then we are done.

Else

• $a_j$ is lesser than or greater than $a_i$,
• $a_k$ lies between $a_i$ and $a_j$.

 Now take the 4^th term $a_l$. Whereever $a_l$ lies relative to $a_i$, $a_j$ and $a_k$, the condition will be satisfied. 

Argument 2:

Now assuming the numbers are not distinct, check the first 6 terms. If the condition is not satisfied, then there has to be 3 distinct terms repeated twice reach. If there are 4 or more distinct terms then Argument 1 works.

Now check the 7^th term. If the 7^th terms matches any of the 3 distinct terms prior to it, then 3 terms are equal between the indices [1..6] or [0..5] (whatever your numbering convention). This satisfies the condition. If the 7^th term is not present in the previous indices, then we have 4 distinct terms from [1..7] or [0..6]. Apply argument 1 on these 4 terms. 

Comments

You can always do it by checking atmost any 5 consecutive terms of the array