0
$\begingroup$

I have an array A with n elements. I am trying to write an efficient algorithm to find the index of elements that matches condition A[j-1]>=A[j]<=A[j+1].

Example:

A = [12,11,9,7,5,54,67,87,23,54,20,22]

Should return 4 because subarray [7,5,54] matches the condition where A[4] = 5.

Below is the solution I tried. It has run time O(n). I am looking if there is any other better solution?

 def sol_1():
      for j in range(1,n):
        if A[j-1]>=A[j] and A[j]<=A[j+1]:
          return j
      return False
$\endgroup$
5
  • $\begingroup$ what about the indexes $1$ and $n$. What is the satisfying conditions for them? $\endgroup$ Sep 19, 2021 at 9:15
  • $\begingroup$ Do you have any reason to suspect there might be a "better" solution? And what do you mean with "better"? $\endgroup$
    – no comment
    Sep 19, 2021 at 10:28
  • $\begingroup$ You say "Should return 4" but then you actually only return True or None. Which one is it? $\endgroup$
    – no comment
    Sep 19, 2021 at 10:31
  • 1
    $\begingroup$ Before efficiency, I suggest you first make it correct. For example for n = 3 A = [1,2,1] your code crashes. $\endgroup$
    – no comment
    Sep 19, 2021 at 10:35
  • $\begingroup$ Should return 4 What about 10, 8? $\endgroup$
    – greybeard
    Sep 20, 2021 at 7:42

1 Answer 1

2
$\begingroup$

You can not do better than $n-2$ in the worst case. You can show this using an adversarial argument.

Suppose the array is $A = [1,2,3,\dotsc,n]$. There is no index in the array that satisfies that $A[i-1] \geq A[i] \leq A[i+1]$. Therefore, the answer is trivially no. For the sake of contradiction assume that there is an algorithm that solves the problem in less than $n-2$ operations. It means there is an index of the array that is not accessed by the algorithm. Suppose this index is $t$ and $1<t<n$. Since the algorithm has not seen this index yet, the adversary can decrease $A[t]$ value by $1$, i.e., $A[t] = t-1$. Now, index $t$ satisfies that $A[t-1] \geq A[t] \leq A[t+1]$; thus proving the algorithm wrong.

Therefore, any correct algorithm must access at least $n-2$ entries of the array. Therefore, the lower bound on the running time is $\Omega(n)$.

$\endgroup$
4
  • $\begingroup$ Thank you for the answer. I have been trying if it can be solved in a better way using the divide and conquer approach. Do you have any thoughts on that? $\endgroup$ Sep 25, 2021 at 2:54
  • $\begingroup$ What do you mean by better? Less time complexity? $\endgroup$ Sep 25, 2021 at 3:52
  • $\begingroup$ Yes, anything less than O(n). $\endgroup$ Sep 25, 2021 at 15:06
  • 1
    $\begingroup$ @five_star_021 That is what I proved. It is not possible to do better in the worst case. $\endgroup$ Sep 25, 2021 at 15:11

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.