Two Pointers

This page briefly introduces the two-pointer technique.

Introduction

Two pointers are a simple and flexible technique. Used on its own, the technique easily solves certain problems; combined with other algorithms, it has many more applications.

As the name suggests, two pointers use two pointers at the same time. In sequences and linked lists they point to positions, while in trees and graphs they point to vertices. The pointers maintain or collect information by moving in the same direction or toward each other.

We now look at several concrete ways to use two pointers.

Maintaining interval information

Without combining it with another data structure, the simplest way to use two pointers for interval information is to maintain a quantity with suitable monotonicity, for which adding or removing one element is easy to handle, such as the sum of positive numbers or the product of positive integers.

Example 1

Example 1: LeetCode 713. Subarray Product Less Than K

Given an array of length $n$ of positive integers, denoted by $\mathit{nums}$, and an integer $k$, find the number of contiguous subarrays whose product is less than $k$.

Here $1 \leq n \leq 3 \times 10^4, 1 \leq nums[i] \leq 1000, 0 \leq k \leq 10^6$.

Procedure

Let the two pointers be $l,r$, and let $\mathit{tmp}$ record the product of all numbers in $[l,r]$. Initially $l,r$ are both at the left end. Move $r$ to the right until $\mathit{tmp}\geq k$ for the first time, then hold $r$ fixed and move $l$ right until $\mathit{tmp}\lt k$. For each $r$, $l$ is the leftmost boundary to which the interval can extend. Because products of positive integers are monotone, the number of valid intervals ending at $r$ is $r-l+1$.

Implementation

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
  long long ji = 1ll, ans = 0;
  int l = 0;
  for (int i = 0; i < nums.size(); ++i) {
    ji *= nums[i];
    while (l <= i && ji >= k) ji /= nums[l++];
    ans += i - l + 1;
  }
  return ans;
}

Two pointers can also be combined with other data structures, such as difference arrays, monotone queues, segment trees, and chairman trees. Mo's algorithm also incorporates the two-pointer technique: after sorting queries offline, it generally uses two pointers to record the current interval and updates its information as the pointers move step by step.

Example 2

Next is an example that uses two pointers on a tree together with tree difference arrays.

Example 2: Luogu P3066 Running Away From the Barn G

Given a rooted tree with $n$ vertices and weighted edges, numbered from 1 to $n$ with vertex 1 as the root, and a parameter $t$, for every vertex $u$ find how many vertices in the subtree of $u$ are at distance not greater than $t$ from $u$. The constraints are $1\leq n \leq 2\times 10^5,1 \leq t \leq 10^{18},1 \leq p_i \lt i,1 \leq w_i \leq 10^{12}$.

Procedure

Run a DFS from the root. Use a stack to record the tree chain from the root to the current vertex. Let pointer $u$ denote the current vertex, and let pointer $p$ denote the shallowest vertex among those whose distance from $u$ is not greater than $t$. Record the distance to the root and determine $p$ by binary search each time. At this point, $u$ contributes to every vertex on the path from $p$ to $u$, which can be recorded with tree differences. Do not move $p$ by brute force, or the time complexity may degrade to $O(n^2)$.

Exercises

LeetCode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Subsequence matching

Example 3: LeetCode 524. Longest Word in Dictionary through Deleting

Given a string $s$ and a string array $\mathit{dictionary}$, find and return the longest string in the dictionary that can be obtained by deleting some characters from $s$.

Procedure

This type of problem matches strings $s$ and $t$ to determine whether $t$ is a subsequence of $s$. Put pointer $i$ at the beginning of $s$ and pointer $j$ at the beginning of $t$. If $s[i]=t[j]$, the $j$-th character of $t$ has found its first match in $s$, so both $i$ and $j$ can be incremented. Otherwise the $j$-th character of $t$ has not been matched, so increment only $i$ and continue searching in the remainder of $s$. Finally, if $j$ has reached the position just past the end, the whole string has been matched and $t$ is a subsequence of $s$; otherwise it is not.

Implementation

string findLongestWord(string s, vector<string>& dictionary) {
  sort(dictionary.begin(), dictionary.end());
  int mx = 0, r = 0;
  string ans = "";
  for (int i = dictionary.size() - 1; i >= 0; i--) {
    r = 0;
    for (int j = 0; j < s.length(); ++j) {
      if (s[j] == dictionary[i][r]) r++;
    }
    if (r == dictionary[i].length()) {
      if (r >= mx) {
        mx = r;
        ans = dictionary[i];
      }
    }
  }
  return ans;
}

The method of putting two pointers on different objects and comparing them step by step is also useful in some dynamic-programming problems.

Using the ordering of a sequence

Two pointers often work correctly on a sequence because of one of its properties; the most common is that the sequence is ordered.

Example 4: LeetCode 167. Two Sum II — Input Array Is Sorted

Given an integer array numbers sorted in ascending order, find two numbers whose sum equals the target target.

Procedure

This is a classic application of two pointers. Binary search is also convenient, but it adds a factor of $\log{n}$ to the time complexity and produces less concise code.

To use two pointers, observe that the two numbers must occupy different positions, so one is on the left and the other on the right. Since their sum is fixed, increasing the smaller number requires decreasing the larger number. We can therefore approach the answer from both ends.

Initially suppose the answer is 1 and n. If $num[1]+num[n]\gt \mathit{target}$, one of the numbers must decrease. $\mathit{num}[1]$ cannot decrease any further, so decrement the pointer at $n$ and make the larger number smaller.

Similarly, if $num[1]+num[n]\lt \mathit{target}$, one of the numbers must increase. $\mathit{num}[n]$ cannot increase any further, so increment the pointer at 1 and make the smaller number larger.

In general, if the pointers are at $l,r$ with $l\lt r$, decrement $r$ when $num[l]+num[r]\gt \mathit{target}$, and increment $l$ when $num[l]+num[r]\lt \mathit{target}$. Thus $l$ moves right and $r$ moves left until they approach an answer.

Implementation

vector<int> twoSum(vector<int>& numbers, int target) {
  int r = numbers.size() - 1, l = 0;
  vector<int> ans;
  ans.clear();
  while (l < r) {
    if (numbers[l] + numbers[r] > target)
      r--;
    else if (numbers[l] + numbers[r] == target) {
      ans.push_back(l + 1), ans.push_back(r + 1);
      return ans;
    } else
      l++;
  }
  return ans;
}

Merging two sorted arrays in $O(n+m)$ time during merge sort is another use of two pointers that relies on the arrays remaining ordered.

Exercises

LeetCode 15. 3Sum

Finding a cycle in a singly linked list

Procedure

There are several ways to find a cycle in a singly linked list, but the fast-and-slow two-pointer method is one of the simplest.

Initially both pointers point to the head. Move one pointer one step at a time and the other two steps at a time. If they meet, there is a cycle; otherwise there is none. The time complexity is $O(n)$.

If there is a cycle, how can we find its starting point?

Let us write the equations. Suppose that when the pointers meet, the slow pointer has taken $k$ steps in total and has taken $l$ steps on the cycle (when the pointers meet on the cycle, the slow pointer has not completed a full lap). The fast pointer has taken $2k$ steps. Let the cycle length be $C$. Then

$$\begin{align} & \ 2 k=n \times C+l+(k-l) \\ & \ k=n \times C \\ \end{align}$$

At the first meeting, $n$ is the smallest positive integer 1, so $k=C$. Therefore, after the pointers meet, move one pointer to the head and move both one step at a time. Their next meeting point is the start of the cycle.

Implementation

pair<bool, vector<int>> findCycle(
    vector<int>
        nxt)  // nxt[i] is the node pointed to by i in the singly linked list (0-indexed); -1 means no outgoing edge
{
  int fast = 0, slow = 0;
  do  // first determine whether a cycle exists
  {
    if (nxt[fast] == -1 || nxt[nxt[fast]] == -1) {
      return make_pair(false, vector<int>());  // no cycle
    }
    fast = nxt[nxt[fast]];
    slow = nxt[slow];
  } while (fast != slow);
  slow = 0;
  while (slow != fast)  // find the cycle entry
  {
    slow = nxt[slow];
    fast = nxt[fast];
  }
  vector<int> cycle;
  do  // finally collect the entire cycle
  {
    cycle.push_back(slow);
    slow = nxt[slow];
  } while (slow != fast);
  return make_pair(true, cycle);
}

The time complexity is $O(n)$.