Arrays And Strings

Two Pointers

Move left and right pointers inward on a sorted array to find a pair sum with linear time and constant auxiliary space.

PatternO(n) time / O(1) space

target: 10sum: -

Index 0L

Index 1

Index 2

Index 3

Index 4

Index 5R

Time

O(n)

Space

O(1)

Step Note

Sort the values, then place one pointer at each end.

SampleDetails

function twoPointerPairSum(values: number[], target: number) {
  const array = [...values].sort((a, b) => a - b)
  let left = 0
  let right = array.length - 1
  while (left < right) {
    const sum = array[left] + array[right]
    if (sum === target) return [left, right]
    if (sum < target) {
      left++
    } else {
      right--
    }
  }
  return null
}