14.13 Two-Pointer Greedy

Many greedy algorithms operate on sorted data and repeatedly make decisions from the extremes of a range.

algorithmsgreedy

14.13 Two-Pointer Greedy

Many greedy algorithms operate on sorted data and repeatedly make decisions from the extremes of a range. Instead of maintaining a complex state or exploring multiple possibilities, the algorithm keeps two indices and moves one of them after each decision.

This pattern is known as the two-pointer technique.

While two pointers are often introduced as an array-processing optimization, they also form the basis of several elegant greedy algorithms. In these problems, the movement of each pointer corresponds directly to a locally optimal decision.

The resulting algorithms are frequently linear-time, easy to implement, and surprisingly powerful.

Problem

You have a sorted collection of elements.

At each step:

  • The most relevant candidates lie near the beginning or end.
  • A local decision determines which candidate should be consumed.
  • Once consumed, that candidate never needs to be revisited.

Examples include:

  • Pairing resources.
  • Matching constraints.
  • Loading boats.
  • Assigning tasks.
  • Scheduling interactions.

The two-pointer technique provides an efficient way to process these decisions.

The Basic Pattern

Given a sorted array:

a[0 ... n-1]

Initialize:

left  = 0
right = n - 1

Then repeatedly:

Inspect a[left]
Inspect a[right]

Make greedy choice

Move one or both pointers

Eventually:

left > right

and the algorithm terminates.

The power comes from proving that discarded elements can never participate in a better solution later.

Example: Rescue Boats

Suppose people must be transported using boats.

Each boat has capacity:

limit

and can carry at most two people.

Given:

weights = [1,2,2,3]
limit   = 3

Goal:

Minimize the number of boats.

First Observations

Sort the weights:

[1,2,2,3]

The heaviest person is:

3

That person cannot share a boat with anyone.

One boat is unavoidable.

This immediately suggests looking at the heaviest remaining person first.

Greedy Insight

Consider the heaviest remaining person.

If that person can share a boat with the lightest remaining person, then doing so is always safe.

Why?

Because any other partner would be heavier and therefore no easier to accommodate.

This yields the greedy rule:

Pair the heaviest person with the lightest feasible person.

Walkthrough

Input:

[1,2,2,3]

Pointers:

left  = 1
right = 3

Inspect:

1 + 3 = 4

Too large.

Person 3 must travel alone.

boats = 1
right--

Remaining:

[1,2,2]

Inspect:

1 + 2 = 3

Fits.

Pair them.

boats = 2
left++
right--

Remaining:

[2]

One final boat.

Answer:

3

Why the Greedy Choice Works

Consider the heaviest remaining person:

H

If:

lightest + H > limit

then no partner is possible.

Every other candidate is heavier than the lightest person.

Therefore:

H

must travel alone.

No future decision can change this fact.

If:

lightest + H <= limit

then pairing them is optimal because it removes the heaviest person while consuming the smallest possible additional weight.

This preserves maximum flexibility.

Go Implementation

func NumRescueBoats(people []int, limit int) int {
	sort.Ints(people)

	left := 0
	right := len(people) - 1
	boats := 0

	for left <= right {
		if people[left]+people[right] <= limit {
			left++
		}

		right--
		boats++
	}

	return boats
}

Complexity Analysis

Sorting:

O(n log n)

Pointer scan:

O(n)

Total:

O(n log n)

Space:

O(1)

excluding sorting overhead.

Example: Assign Cookies

Suppose children require cookie sizes.

Arrays:

children = [1,2,3]
cookies  = [1,1]

A child with greed factor:

g

requires a cookie of size at least:

g

Goal:

Maximize the number of satisfied children.

Greedy Insight

Sort both arrays.

Attempt to satisfy the least demanding child first.

Why?

Because larger cookies can satisfy both small and large demands.

Small cookies have fewer options.

Therefore:

Match the smallest available cookie with the smallest unsatisfied child it can satisfy.

Walkthrough

Sorted:

children = [1,2,3]
cookies  = [1,1]

Pointers:

child  = 0
cookie = 0

Cookie 1 satisfies child 1.

Advance both.

child  = 1
cookie = 1

Cookie 1 cannot satisfy child 2.

Advance cookie.

End.

Result:

1 satisfied child

Go Implementation

func FindContentChildren(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)

	i := 0
	j := 0

	for i < len(g) && j < len(s) {
		if s[j] >= g[i] {
			i++
		}
		j++
	}

	return i
}

Example: Container With Most Water

Given heights:

[1,8,6,2,5,4,8,3,7]

Choose two lines maximizing contained water.

Area:

$$ \text{width} \times \min(h_1,h_2) $$

Brute force:

$$ O(n^2) $$

Two-pointer solution:

$$ O(n) $$

Greedy Observation

Area is limited by the shorter wall.

Suppose:

left_height < right_height

Moving the taller wall inward cannot increase the limiting height.

Only moving the shorter wall can potentially improve the solution.

Therefore:

Always move the shorter pointer.

Algorithm

Evaluate area

Move shorter wall

Repeat

This simple rule reduces quadratic search to linear time.

Common Two-Pointer Greedy Signals

Certain problem characteristics strongly suggest this technique.

Sorted Input

Elements can be ordered meaningfully.

Decisions Near Extremes

Important choices involve smallest, largest, leftmost, or rightmost elements.

Irreversible Elimination

After a decision, some elements can never become useful again.

Pairing Problems

Resources must be matched optimally.

Monotonic Behavior

Moving a pointer reduces the search space without losing optimal solutions.

Proof Pattern

Most two-pointer greedy proofs follow the same structure.

Step 1

Identify an extreme element.

Step 2

Show that at least one pointer position can never participate in a better future solution.

Step 3

Discard that position.

Step 4

Repeat on the reduced problem.

This is essentially an exchange argument expressed geometrically.

Rather than replacing elements, the proof demonstrates that certain candidates can be safely eliminated.

Common Mistakes

Using Unsorted Data

Many two-pointer arguments depend on sorted order.

Without sorting, the proof usually fails.

Moving the Wrong Pointer

The proof typically identifies exactly one safe movement.

Moving the other pointer may destroy optimality.

Revisiting Discarded Elements

Once eliminated, a pointer position should never need reconsideration.

If reconsideration is necessary, the greedy argument is probably incomplete.

Assuming All Two-Pointer Algorithms Are Greedy

Some two-pointer algorithms are merely search optimizations.

The problems in this chapter rely on a genuine greedy choice.

Relationship to Earlier Recipes

Sorting plus greedy:

Sort
Scan
Choose

Priority queue greedy:

Maintain candidates
Choose best candidate

Two-pointer greedy:

Sort
Choose from extremes
Discard safely

All three patterns reduce a large search space through locally justified decisions.

The difference lies in how the candidates are represented.

Takeaway

Two-pointer greedy algorithms exploit sorted structure to make locally optimal decisions from the boundaries of a search space. By proving that one extreme element can never contribute to a better future solution, the algorithm safely discards candidates and shrinks the problem. The result is often a simple linear scan following an initial sort, making two-pointer greedy one of the most practical and frequently used optimization techniques in algorithm design.