Two Pointers

The two pointers technique helps us solve problems by performing actions on the values located at the pointers or deriving new information based on them.

Overview

A variable that references a specific position or item in a linear data structure is called a pointer. The two pointers technique helps us solve problems by performing actions on the values located at the pointers or deriving new information based on them.

Pointer

A variable that references a specific position or item in a linear data structure, e.g. an index of an array or string, or a specific node in a linked list.

The Technique

The basic foundation of the two pointers technique is as follows:

Define Pointers

Specify the variable names and values they reference in the data structure.

Perform an Action

Do something that gets you closer to the goal at hand. For example, swap values at the two pointers, calculate a value, etc.

Move Pointers

Move one or both pointers. Pointers may move independently, in opposite directions, and/or at different "speeds".

Check a Condition

Perform a conditional check to determine if the steps should end or return to Step 2.

With this foundation, we typically employ the technique in two different ways:

Contrary Motion - the two pointers move toward one another
Similar Motion - the two pointers move in the same direction

Contrary Motion

In contrary motion, pointers move toward one another. This implies that our pointers start at opposite ends of the data structure. For this reason, we commonly name

a variable left that points to the first item in the data structure and
a variable right that points to the last item

Left and Right Pointers

const nums = [1,2,3,4,5]
let left = s
let right = s.length - 1

Example

Let's say we wanted to reverse our nums array. To accomplish this, we can devise a two pointers-based algorithm with contrary motion pointers.

Pseudocode to Reverse an Array

1. Set a left pointer at the first index, and a right pointer at the last index of the array
2. swap the values at the pointers (i.e. swap `nums[left]` and `nums[right]`)
3. move both pointers
    - move `left` by incrementing it by 1
    - move `right` by decrementing it by 1
4. check whether there are still values to swap
    - if `left` < `right` then there are still values to swap
    - if `left` === `right` then we should stop because
        - the pointers reference the same value and there's nothing left to swap
        - occurs for arrays of odd length
    - if `left` > `right` we should stop because
        - these values have already been swapped;
        - occurs for arrays of even length

The pointer movement described by our pseudocode would look something like this.

Pointer Movement

    [ 1 2 3 4 5 ]
      L       R     <- our left and right pointers
      

    [ 5 2 3 4 1 ]   <- swapped positions of 5 and 1
        L   R       <- moved pointers inward
       

    [ 5 4 3 2 1 ]
          L         <- the pointers are at the same position, reversal done
          R         <-

Here's a sample implementation:

Reverse an Array

function reverseArray(nums) {
    // 1. set pointers
    let left = 0
    let right = nums.length - 1
 
    while(left < right){ // 4. check if swapping is still necessary
 
        // 2. swap values
        let temp = nums[left]
        nums[left] = nums[right]
        nums[right] = temp
 
        // 3. move pointers
        left++
        right--
    }
 
    return nums
};

Two Pointers

Overview

The Technique

Contrary Motion

Example

Similar Motion

On this page