Resources

Two Pointers

The Two Pointers method iterates two pointers across an array to track indices satisfying some condition. There are two common variations:

1. Two pointers starting at different ends of the array and moving towards each other.
2. Two pointers moving in the same direction at different speeds. This variation is known as the Sliding Window algorithm.

Sum of Two Values

Solution - Sum of Two Values

The "Opposite Ends" method allows us to find the target pair in linear time if the array is sorted. Instead of checking every possible pair (which would take $\mathcal{O}(N^2)$ time), we use the sorted property to narrow down the search space in a single pass.

We want to find two indices $i$ and $j$ such that $a_i + a_j = x$.

We can start by sorting the array. Then, we can initialize a left pointer at the beginning of the array ($l=0$) and a right pointer at the end ($r=N-1$).

While $l < r$:

1. If $a[l] + a[r] == x$, we have found the target sum.
2. If $a[l] + a[r] < x$, the sum is too small. To increase the sum, we increment $l$.
3. If $a[l] + a[r] > x$, the sum is too large. To decrease the sum, we decrement $r$.

Since the array is sorted, moving the left pointer to the right will never decrease the sum, and moving the right pointer to the left will never increase the sum.

Implementation

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

Copy
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main() {
	int n, x;
	cin >> n >> x;

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int x = Integer.parseInt(st.nextToken());

Copy
n, x = map(int, input().split())

nums = [(int(val), i) for i, val in enumerate(input().split())]
nums.sort()

l = 0
r = n - 1
while l < r:
	sum = nums[l][0] + nums[r][0]
	if sum == x:

Sliding Window

The Sliding Window method is a variation of the two pointers technique where two pointers move in the same direction to maintain a specific range or "window" of elements. While standard two pointers often move towards each other, the sliding window technique is used to find a contiguous subarray that satisfies a condition.

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
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N, T;
	cin >> N >> T;
	vector<int> A(N);

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[] A = new int[N];

Copy
N, T = map(int, input().split())
A = list(map(int, input().split()))

r = -1
window_sum = 0  # sum of A[l ... r inclusive]
ans = 0

for l in range(N):
	while r + 1 < N and window_sum + A[r + 1] <= T:
		r += 1
		window_sum += A[r]
	ans = max(ans, r - l + 1)
	window_sum -= A[l]

print(ans)

Problems

Quiz