✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-222

Two-Pointer Technique

The Two-Pointer Technique uses two indices to traverse a data structure efficiently, often reducing nested-loop solutions to linear-time algorithms.

Explanation

Overview

The Two-Pointer Technique is an algorithmic approach in which two pointers move through an array, string, linked list, or other sequence according to specific conditions. The pointers may move toward each other, in the same direction, or at different speeds.

How it works

Identify the sequence and the condition that must be checked.; Choose suitable starting positions for the two pointers.; Compare the values or positions referenced by the pointers.; Move one or both pointers according to the problem's rules.; Continue until the required condition is satisfied or the pointers meet or cross.

Key concepts

Pointer positions; Opposite-direction traversal; Same-direction traversal; Sorted sequences; Boundary movement; Invariant maintenance

Time complexity

operation: Single traversal with two pointers; complexity: O(n); operation: Nested pointer movement; complexity: Often O(n) when each pointer moves only forward or backward a limited number of times

Space complexity

Usually O(1) auxiliary space when pointers are used directly without additional collections.

Example

array: 1; 2; target: 14; problem: Find two numbers whose sum equals 14.; steps: Start with left = 0 and right = 5.; 1 + 10 = 11, which is smaller than 14, so move left forward.; result: 4; 10

Applications

Two Sum in sorted arrays; Palindrome checking; Removing duplicates; Merging sorted arrays; Partitioning sequences; Container With Most Water

Example or application

Array

  • 1

  • 2

  • 4

  • 6

  • 8

  • 10

Target

14

Problem

Find two numbers whose sum equals 14.

Steps

  • Start with left = 0 and right = 5.

  • 1 + 10 = 11, which is smaller than 14, so move left forward.

  • 2 + 10 = 12, which is smaller than 14, so move left forward.

  • 4 + 10 = 14, so the required pair is found.

Result

  • 4

  • 10

Definition

The Two-Pointer Technique is an algorithmic approach in which two pointers move through an array, string, linked list, or other sequence according to specific conditions. The pointers may move toward each other, in the same direction, or at different speeds.

Common Patterns

PatternDescriptionTypical Uses

Opposite-direction pointers

One pointer starts at the beginning and another at the end. They move toward each other until the required condition is satisfied.

  • Finding pairs with a target sum in a sorted array

  • Checking whether a string is a palindrome

  • Reversing an array

  • Finding container-area solutions

Same-direction pointers

Both pointers move forward, often at different rates or with one maintaining a boundary.

  • Removing duplicates from sorted arrays

  • Partitioning arrays

  • Merging sorted sequences

  • Maintaining a valid range

Fast and slow pointers

One pointer moves faster than the other. Their relative movement can reveal cycles or specific positions in linked lists.

  • Cycle detection

  • Finding the middle of a linked list

  • Finding cycle entry points

How It Works

  • Identify the sequence and the condition that must be checked.

  • Choose suitable starting positions for the two pointers.

  • Compare the values or positions referenced by the pointers.

  • Move one or both pointers according to the problem's rules.

  • Continue until the required condition is satisfied or the pointers meet or cross.

Implementation

Language

Pseudocode

Code

  • function twoSumSorted(array, target):

  • left = 0

  • right = length(array) - 1

  • while left < right:

  • currentSum = array[left] + array[right]

  • if currentSum == target:

  • return [left, right]

  • else if currentSum < target:

  • left += 1

  • else:

  • right -= 1

  • return notFound

Time Complexity

OperationComplexity

Single traversal with two pointers

O(n)

Nested pointer movement

Often O(n) when each pointer moves only forward or backward a limited number of times

Space Complexity

Usually O(1) auxiliary space when pointers are used directly without additional collections.

Key Concepts

  • Pointer positions

  • Opposite-direction traversal

  • Same-direction traversal

  • Sorted sequences

  • Boundary movement

  • Invariant maintenance

Advantages

  • Can reduce time complexity compared with nested loops.

  • Often requires very little additional memory.

  • Works well with sorted arrays and strings.

  • Provides a clear way to maintain and process sequence boundaries.

Limitations

  • Some approaches require sorted input.

  • Pointer movement rules must be justified by the problem's properties.

  • Incorrect boundary conditions can cause missed elements or infinite loops.

  • Not every pair-search or range problem can be solved using two pointers.

Applications

  • Two Sum in sorted arrays

  • Palindrome checking

  • Removing duplicates

  • Merging sorted arrays

  • Partitioning sequences

  • Container With Most Water

  • Sliding-window algorithms

Related Topics

  • Sliding Window Technique

  • Fast and Slow Pointer Technique

  • Array Algorithms

  • String Algorithms

  • Binary Search

Practice Questions

QuestionAnswer

What is the main idea of the Two-Pointer Technique?

Use two indices to traverse a sequence according to a problem-specific movement rule.

Why is a sorted array useful for the opposite-direction pattern?

The ordering helps determine which pointer should move based on the current comparison.

What is the typical time complexity of a basic two-pointer traversal?

O(n), when each pointer moves through the sequence only a limited number of times.

Does every two-pointer algorithm require sorted input?

No. Some patterns work with unsorted sequences when their movement rules do not depend on sorted order.

Learning Objectives

  • Explain the central idea and purpose of two-pointer technique.

  • Identify the assumptions, inputs, and conditions relevant to two-pointer technique.

  • Evaluate an application of two-pointer technique for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Specialized Algorithms and Computational Topics

Suggest a correction or source · More in Algorithms & Data Structures