educative.io

Time complexity of searchPair

Courses
,
#1

Why is the time complexity of searchPair O(N)?

searchPair contains an outer loop, and, potentially two inner while loops.

Inners loop I am referring to are:

        while (left < right && arr[left] == arr[left - 1])
          left++; // skip same element to avoid duplicate triplets
        while (left < right && arr[right] == arr[right + 1])
          right--; // skip same element to avoid duplicate triplets

For a scenario like [-5,2,2,2,2,2,3,3,3,3,3,3], I don’t understand why these inner while loops do not also have a time complexity of O(N)?

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Triplet Sum to Zero (medium) - Grokking the Coding Interview: Patterns for Coding Questions

1 Like
#2

Hi @Adam_Johnston
As the whole array is needed to be traversed that’s why the time complexity of searchPair is O(N) in which the cost of inner and outer loops are included as a whole.
Hope it will help.
Thank you :blush:

1 Like
#3

Hi @Adam_Johnston

As the searchPair function is concerned, there is a nested loop having the same condition in all of the loops while(left < right). So if we calculate the total number of iterations that the searchPair function can have is equal to the size of the array (N) because in each interaction either we increase left or decrease right so after N iterations our function will reach the return point. There are total 3 ways in which N iterations can be done:

  1. left start from zero and end at SizeofArray (means all time left++)
  2. Right start from SizeofArray and end at zero (means all time right–)
  3. Both left++ and right-- occurs so they overlap each other and while(left < right) return false

Note: both of the inner loops are used just to bypass the repeated values, so they are not increasing the number of iterations at all.