CODEWITHSUNDEEP
algorithmsearch
njok
njok

Reputation: 53

O(n) algorithm that returns array indexes if condition is true

I am trying to write an algorithm that takes a linear array, sorted from lowest to highest. It should return the positions of values if arr[i] - arr[j] = 160.

My problem is that the runtime should be O(n).

If I do it with a for loop that goes from highest to lowest array element, and for each element searches for appropriate array element with a binary search, the runtime is still O(n log2 n).

How can I reduce the complexity to O(n)?

Upvotes: 3

Views: 75

Answers (1)

amit
amit

Reputation: 178431

It can be done with two iterators, i,j, such that i > j always, and you increase i if arr[i] - arr[j] > 160, and increase j if arr[i] - arr[j] < 160 (if it equals 160, you abort).

i = 1
j = 0
while (i < n):
   if (arr[i] - arr[j] == 160:
      // found it!
   else if (arr[i] - arr[j] < 160):
      i++
   else:
      j++

Upvotes: 3

Related Questions