CODEWITHSUNDEEP
algorithmpseudocode
ymmayg
ymmayg

Reputation: 9

How to make a better algorithm given this code?

i have this algo and i want to know if it's possible to make it better(less complexity):

 for i = 3 to A.length 
  for j = 2 to i − 1
    for k = 1 to j − 1
      if |A[i] − A[j]| = = |A[j] − A[k]| or |A[i] − A[k]| = = |A[j] − A[k]|
           return true
 return false

The complexity has to be O(n^3), and the sentence after "or" is just A[i]=A[j]

I am not sure that could exist a better algorithm...

Upvotes: 1

Views: 70

Answers (2)

Vedang Mehta
Vedang Mehta

Reputation: 2254

You can sort the array beforehand and use binary-search to bring down the time complexity from O(N^3) to O(N^2 logN).

Pseudo code -

sort(A)

for i = 1 to A.length - 2
    for j = i + 1 to A.length - 1
        //search for an element A[k] such that A[k]-A[j] == A[j]-A[i]
        if binary_search(A, 2 * A[j] - A[i], j + 1, A.length)
            return True
return False

binary_search(A, x, i, j) returns true if x is present in A between indices i and j.

Unlike the other solution involving hashing, you won't need any additional space.

Upvotes: 1

גלעד ברקן
גלעד ברקן

Reputation: 23945

You could reduce to O(n^2) time (but increase space complexity) by hashing the counts of differences.

Upvotes: 1

Related Questions