Two Pointers

Resources

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.

Solution - Books

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

To accomplish this, we can define $\texttt{left}$ and $\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 $\texttt{left}$ in increasing order, let's increase $\texttt{right}$ until the total time for the segment is maximized while being less than or equal to $t$.

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

After incrementing $\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 $N$ times, the overall time complexity is $\mathcal{O}(N)$.

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

We can move the right pointer to index $1$:

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

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

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

Here's an animation of the above example:

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
 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]; }

	int left = 0, right = 0, cur = 0;

Copy
import java.io.*;
import java.util.*;

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];

Copy
n = int(input())
t = int(input())

books = [int(input()) for _ in range(n)]

right = 0
left = 0
cur = 0
ans = 0

Problems

Quiz