PrevNext
Not Frequent
 0/10

Two Pointers

Authors: Darren Yao, Qi Wang

Contributor: Aadit Ambadkar

Iterating two monotonic pointers across an array to search for a pair of indices satisfying some condition in linear time.

StatusSourceProblem NameDifficultyTags
CSESEasy
CSESEasy

Resources

Resources
CPH

solutions to the problems above

IUSACO

above + mention of max subarray sum

CF

video explanation of two pointers

Two Pointers

The two pointers method iterates two pointers across an array, to track the start and end of an interval. It can also be used to track two values in an array as shown in CPH's 2SUM solution.

Focus Problem – read through this problem before continuing!

View Internal Solution

Solution - Books

We want to find the longest contiguous segment of books that can be read within tt minutes.

To accomplish this, we can define left\texttt{left} and right\texttt{right} to represent the beginning and end of the segment. Both will start at the beginning of the array. These numbers can be thought of as pointers, hence the name "two pointers."

For every value of left\texttt{left} in increasing order, let's increase right\texttt{right} until the total time for the segment is maximized while being less than or equal to tt.

ans\texttt{ans} will store the maximum value of rightleft+1\texttt{right} - \texttt{left}+1 (segment size) that we have encountered so far.

After incrementing left\texttt{left} by one, the time used decreases, hence the right pointer never has to move leftwards. Thus:

Since both pointers will move at most NN times, the overall time complexity is O(N)\mathcal{O}(N).

As an example, consider the first case in the sample inputs:

Left Pointer
arr[i]\texttt{arr}[i] 3 1 2 1
Right Pointer

We can move the right pointer to index 11:

Left Pointer
arr[i]\texttt{arr}[i] 3 1 2 1
Right Pointer

The sum of the values in this range is 44, and there are 22 values. So, the current maximum segment length is ans=2\texttt{ans}=2. By incrementing the left pointer by 11, we can subtract 33 from the sum of values to get 11. The array then looks like:

Left Pointer
arr[i]\texttt{arr}[i] 3 1 2 1
Right Pointer

Now, we can move the right pointer to the end. This makes the sum of values 1+2+1=41+2+1=4 and the length of the segment equal to 33. So, ans\texttt{ans} is now 33.

Left Pointer
arr[i]\texttt{arr}[i] 3 1 2 1
Right Pointer

Since the right pointer has reached the end of the array, we are done at this point. This leaves us with ans=3\texttt{ans}=3.

Pro Tip

You can visualize these pointers as maintaining a sliding window of books for this problem.

Implementation

C++

Code Snippet: C++ Short Template (Click to expand)
int main() {
setIO();
int n, t, ans = 0;
cin >> n >> t;
vi books(n);
for (int i = 0; i < n; i++){
cin >> books[i];
}

Java

import java.util.*;
import java.io.*;
public class Books {
public static void main(String[] args) {
Kattio io = new Kattio();
int n = io.nextInt();
int t = io.nextInt();
int[] books = new int[n];

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show Tags2P, Sorting
SilverEasy
Show Tags2P, Sorting
CFEasy
Show Tags2P
CFEasy
Show Tags2P
SilverNormal
Show Tags2P, Sorting
SilverNormal
Show Tags2P, Sorting
CFNormal
Show Tags2P

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext