Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Two Pointers

Guide 1 of 6 · Path 1 of 6

PreviousNext →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 8
1
L
8
6
2
5
4
8
3
7
R

area = 8

LC11: area = min(hL,hR) * (R-L). Start at both ends.

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtwo-pointers

Container With Most Water

Problem (restated)

You are given height bars on a line. Choose two lines that form a container with the x-axis holding the most water. Return that maximum area.

Intuition

Area = min(h[l],h[r]) * (r-l). Starting at both ends maximizes width; the only way to improve is to move the shorter line inward hoping for a taller height.

Approaches

Two pointers from both ends

Tested only
Time O(n)Space O(1)

Idea. left=0, right=n-1. Track max area. Move the pointer at the shorter height. Stop when left≥right.

Walkthrough. Heights [1,8,6,2,5,4,8,3,7]: start width 8, area min(1,7)*8=8; move left to 8, … eventually best=49.

Trade-offs. Greedy correctness relies on: moving the taller line cannot increase min height and only decreases width.

Solution
export function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1, best = 0;
  while (left < right) {
    const h = Math.min(height[left]!, height[right]!);
    best = Math.max(best, h * (right - left));
    if (height[left]! < height[right]!) left++;
    else right--;
  }
  return best;
}

export function maxArea(height: number[]): number {
  let left = 0, right = height.length - 1, best = 0;
  while (left < right) {
    const h = Math.min(height[left]!, height[right]!);
    best = Math.max(best, h * (right - left));
    if (height[left]! < height[right]!) left++;
    else right--;
  }
  return best;
}

Try all pairs

Tested only
Time O(n²)Space O(1)

Idea. Compute area for every (i,j).

Walkthrough. Nested loops; keep maximum.

Trade-offs. Obvious correctness, fails larger constraints.

Solution
export function maxAreaBrute(height: number[]): number {
  let best = 0;
  for (let i = 0; i < height.length; i++)
    for (let j = i + 1; j < height.length; j++)
      best = Math.max(best, Math.min(height[i]!, height[j]!) * (j - i));
  return best;
}

export function maxAreaBrute(height: number[]): number {
  let best = 0;
  for (let i = 0; i < height.length; i++)
    for (let j = i + 1; j < height.length; j++)
      best = Math.max(best, Math.min(height[i]!, height[j]!) * (j - i));
  return best;
}

Template connection

Opposite-ends two pointers; move the side that limits the height.

Reflection