Two-Pointer Technique

This technique refers to using two pointers that start at opposite ends of an array and gradually move towards each other.

In this page, we'll cover:

A simple problem that illustrates the motivation behind the two-pointer technique.
The types of problem for which you should consider using this technique.
A list of problems (with animated solutions!) for you to try that build upon the concepts covered here.

Problem: Two Sum

DESCRIPTION

Given a sorted array of integers nums, determine if there exists a pair of numbers that sum to a given target.

Example: Input: nums = [1,3,4,6,8,10,13], target = 13 Output: True (3 + 10 = 13)

Input: nums = [1,3,4,6,8,10,13], target = 6 Output: False

The naive approach to this problem uses two-pointers i and j in a nested for-loop to consider each pair in the input array, for a total of O(n²) pairs considered.


def isPairSum(nums, target):
  for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
      if nums[i] + nums[j] == target:
        return True
  return False

two sum naive

0 / 11

However, if we put a bit more thought into how we initialize our pointers and how we move them, we can eliminate the number of pairs we consider down to O(n). Understanding why we are able to eliminate pairs is key to understanding the two-pointer technique.

Naive (left) vs. Two-Pointer Technique (right)

Eliminating Pairs

The two-pointer technique leverages the fact that the input array is sorted.

Let's use it to solve the Two Sum problem when nums = [1, 3, 4, 6, 8, 10, 13] and target = 13.

Goal: find this pair of numbers that sum to 13

We start by initializing two pointers at opposite ends of the array, which represent the pair of numbers we are currently considering.

This pair has a sum (14) that is greater than our target (13). And because our array is sorted, all other pairs ending at our right pointer (13) also have sums greater than our target, as they all involve numbers greater than 1, the value at our left pointer.

So, to move onto the next pair we move our right pointer back, which elimininates those unecessary pairs from our search.

Move right pointer back.

Now, since our sum is less than our target, we know that all other pairs involving our left pointer also have sums less than our target. So, we move our left pointer forward to eliminate those unnecessary pairs and arrive at the next pair to consider.

This continues until either our pointers meet (in which case we did not find a successful pair) or until we find a pair that sums to our target, like we did here.

Solution


def twoSum(nums, target):
  left, right = 0, len(nums) - 1
      
  while left < right:
    current_sum = nums[left] + nums[right]
    if current_sum == target:
        return True

    if current_sum < target:
        left += 1
    else:
        right -= 1
      
  return False

two sum algorithm

0 / 7

Summary

The two-pointer technique leverages the fact that the input array is sorted to eliminate the number of pairs we consider from O(n²)down to O(n).
The two-pointers start at opposite ends of the array, and represent the pair of numbers we are currently considering.
We repeatedly compare the sum of the current pair to the target, and move a pointer in a way that eliminates unnecessary pairs from our search.

When Do I Use This?

Consider using the two-pointer technique for questions that involve searching for a pair (or more) of items in an array that meet a certain criteria.

Examples:

Finding a pair of items that sum to a given target in an array.
Finding a triplet of items that sum to 0 in a given array.
Finding the maximum amount of water that can be held between two array items representing wall heights.

Practice Problems

Try applying the concepts related to eliminating unnecessary pairs to the following problems:

Question	Difficulty
Container With Most Water	Medium
3-Sum	Medium
Triangle Numbers	Medium

Bonus: Additional Problems

These problems also use two pointers in an array, but instead, each pointer represents a logical "region" of the array.

Question	Difficulty
Move Zeroes	Easy
Sort Colors	Medium
Trapping Rain Water	Hard

Next: Container With Most Water

Your account is free and you can post anonymously if you choose.

Sort By

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Container With Most Water