In this algorithm, you keep track of two pointers to items in an array, and iterate one or the other as needed. This works with sorted lists.

When To Use#

This algorithm is used when you have a sorted list and you need to operate on pairs, triplets, or more. This is a good first choice when you need to find two numbers in an array that satisy some condition.

Examples# 

def isPairSum(A, N, X):
    # represents first pointer
    i = 0
    # represents second pointer
    j = N - 1
    while(i < j):
        # If we find a pair
        if (A[i] + A[j] == X):
            return True
        # If sum of elements at current
        # pointers is less, we move towards
        # higher values by doing i += 1
        elif(A[i] + A[j] < X):
            i += 1
        # If sum of elements at current
        # pointers is more, we move towards
        # lower values by doing j -= 1
        else:
            j -= 1
    return 0
## array declaration
arr = [2, 3, 5, 8, 9, 10, 11]
## value to search
val = 17
print(isPairSum(arr, len(arr), val))

Pasted image 20220713213825.png

Problems Featuring this Solution#

  • Squaring a sorted array (easy)
  • Triplets that sum to zero (medium)
  • Comparing strings that contain backspaces (medium)

Sources#

14 Patterns to Ace Coding Interview #2: 2 Pointer 727. Remove Duplicates From Sorted Array