# 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.

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ||||

CSES | Easy |

## 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 $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:

Left Pointer | ||||

$\texttt{arr}[i]$ | 3 | 1 | 2 | 1 |

Right Pointer |

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

Left Pointer | ||||

$\texttt{arr}[i]$ | 3 | 1 | 2 | 1 |

Right Pointer |

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:

Left Pointer | ||||

$\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=4$ and the length of the segment equal to $3$. So, $\texttt{ans}$ is now $3$.

Left Pointer | ||||

$\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 $\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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show Tags2P, Sorting | |||

Silver | Easy | ## Show Tags2P, Sorting | |||

CF | Easy | ## Show Tags2P | |||

CF | Easy | ## Show Tags2P | |||

Silver | Normal | ## Show Tags2P, Sorting | |||

Silver | Normal | ## Show Tags2P, Sorting | |||

CF | Normal | ## 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!