Skip to content

Two Pointers

This page provides a brief introduction to the two-pointer technique.

Introduction

The two-pointer technique is a simple yet flexible skill and idea. Used alone, it can easily solve certain specific problems; combined with other algorithms, it can also serve various purposes.

As the name suggests, two pointers involve using two pointers simultaneously. In sequence or linked list structures, they point to positions; in tree or graph structures, they point to nodes. They maintain or collect information by moving either in the same direction or towards each other.

Next, we will look at several specific applications of the two-pointer technique.

Maintaining Interval Information

When not combined with other data structures, the simplest mode of using two pointers to maintain interval information is to handle information that exhibits certain monotonicity and where adding or removing an element is easy to process, 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 positive integers nums of length \(n\) and an integer \(k\), find the number of contiguous subarrays where the product of all the elements is less than \(k\).

Constraints: \(1 \leq n \leq 3 \times 10^4\), \(1 \leq nums[i] \leq 1000\), \(0 \leq k \leq 10^6\).

Process

Let the two pointers be \(l\) and \(r\), and set a variable \(\mathit{tmp}\) to record the product of all numbers in \([l, r]\). Initially, both \(l\) and \(r\) are at the leftmost position. First, move \(r\) to the right until \(\mathit{tmp} \geq k\) is found for the first time. Then fix \(r\) and move \(l\) to the right until \(\mathit{tmp} < k\). For each \(r\), \(l\) is the left boundary it can extend to. Due to the monotonicity of the product of positive integers, the number of intervals satisfying the condition with \(r\) as the right endpoint is \(r - l + 1\).

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

Using two pointers to maintain interval information can also be combined with other data structures such as difference arrays, monotonic queues, segment trees, persistent segment trees, etc. Additionally, the two-pointer technique is integrated into algorithms like Mo's algorithm. In Mo's algorithm, after offline sorting of queries, two pointers are generally used to record the current interval to be processed, and the interval information is gradually updated as the pointers move step by step.

Example 2

Next, let's look at an example of using two pointers on a tree combined with tree difference:

Example 2 luogu P3066 Running Away From the Barn G

Given a rooted tree with \(n\) nodes, edges have weights. Nodes are numbered from 1 to \(n\), and node 1 is the root. Given a parameter \(t\), for each node \(u\) in the tree, find the number of nodes in the subtree of \(u\) such that the distance from that node to \(u\) is not greater than \(t\). Constraints: \(1 \leq n \leq 2 \times 10^5\), \(1 \leq t \leq 10^{18}\), \(1 \leq p_i < i\), \(1 \leq w_i \leq 10^{12}\).

Process

Traverse the entire tree using dfs starting from the root, using a stack to record the tree path from the root to the current node. Let pointer \(u\) point to the current node, and another pointer \(p\) point to the node with the smallest depth among those whose distance to \(u\) is not greater than \(t\). Record the distance to the root and use binary search to determine \(p\) each time. At this point, \(u\) contributes to all nodes on the path from \(p\) to \(u\), which can be recorded using tree difference.
Note that \(p\) cannot be moved directly by brute force, otherwise 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}\) as a dictionary, find and return the longest string in the dictionary that can be obtained by deleting some characters from \(s\).

Process

This type of problem requires matching string \(s\) with \(t\) to determine if \(t\) is a subsequence of \(s\). To solve this, place one pointer \(i\) at the start of \(s\) and another pointer \(j\) at the start of \(t\). If \(s[i] = t[j]\), it means the \(j\)-th character of \(t\) has found its first match in \(s\), and we can proceed to check the remaining parts. Thus, increment both \(i\) and \(j\) by one. If the equality does not hold, the \(j\)-th character of \(t\) has not been matched yet, so only increment \(i\) by one and continue searching in the later part of \(s\). Finally, if \(j\) has moved beyond the end of \(t\), it means the entire string can be matched, i.e., \(t\) is a subsequence of \(s\); otherwise, it is not.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
}

This method of using two pointers pointing to different objects and gradually comparing them can also be used in some dynamic programming problems.

Utilizing Sequence Ordering

Often, using two pointers on a sequence works correctly because of certain properties of the sequence, most commonly utilizing the ordering of the sequence.

Example 4 leetcode 167. Two Sum II - Input Array Is Sorted

Given an integer array numbers sorted in non-decreasing order, find two numbers such that they add up to a specific target number target.

Process

This problem is also a classic application of two pointers. Although binary search is convenient, it adds an extra \(\log{n}\) factor to the time complexity and the code is less concise.

Next, we introduce the two-pointer approach: Since we need to find two numbers, and they cannot be at the same position, their positions must be one left and one right. Since the sum of the two numbers is fixed, the smaller the smaller number, the larger the larger number. Considering these properties, we can approach them from both sides.

First, assume the answer is at positions 1 and \(n\). If we find \(num[1] + num[n] > \mathit{target}\), it means we need to make one of the elements smaller. Since \(\mathit{num}[1]\) cannot become smaller anymore, we decrement the pointer pointing to \(n\) to make the larger number smaller.

Similarly, if we find \(num[1] + num[n] < \mathit{target}\), it means we need to make one of the elements larger. Since \(\mathit{num}[n]\) cannot become larger anymore, we increment the pointer pointing to 1 to make the smaller number larger.

Generalizing, if we have two pointers at \(l\) and \(r\) respectively, with \(l < r\), and if \(num[l] + num[r] > \mathit{target}\), decrement \(r\); if \(num[l] + num[r] < \mathit{target}\), increment \(l\). Thus, \(l\) continuously moves right, and \(r\) continuously moves left, eventually each approaching an answer.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
}

In merge sort, merging two sorted arrays in \(O(n+m)\) time also utilizes the two-pointer method under the condition of array ordering.

Exercises

leetcode 15. 3Sum

Finding Cycles in a Singly Linked List

Process

There are multiple methods to find cycles in a singly linked list, but the fast-slow two-pointer method is one of the most concise. Next, we introduce this method.

First, both pointers point to the head of the linked list. Let one pointer move one step at a time and the other move two steps at a time. If they meet, it proves there is a cycle; otherwise, there is no cycle. The time complexity is \(O(n)\).

If there is a cycle, how do we find the starting point of the cycle?

Let's derive the formula. Suppose when they meet, the slow pointer has taken \(k\) steps and has walked \(l\) steps on the cycle (when the fast and slow pointers meet on the cycle, the slow pointer must not have completed a full cycle). The fast pointer has taken \(2k\) steps. Let the cycle length be \(C\). Then we have:

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

For the first meeting, \(n\) takes the smallest positive integer 1. That is, \(k = C\). Using this equation, after the two pointers meet, move one pointer to the head of the list and let both move one step at a time. The position where they meet again is the starting point of the cycle.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
pair<bool, vector<int>> findCycle(
    vector<int>
        nxt)  // nxt[i] represents the node pointed to by i in the singly linked list (0-indexed), -1 means pointing to no node
{
  int fast = 0, slow = 0;
  do  // First, check if there is a cycle
  {
    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)  // Then, find the entry point of the cycle
  {
    slow = nxt[slow];
    fast = nxt[fast];
  }
  vector<int> cycle;
  do  // Finally, find the entire cycle
  {
    cycle.push_back(slow);
    slow = nxt[slow];
  } while (slow != fast);
  return make_pair(true, cycle);
}

Time complexity: \(O(n)\).

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用