Two Pointers: Practice Problems with Solutions

Coding Patterns - Guide to 30 Core Algorithm Patterns

Two Pointers: Opposite and Same Direction with Examples

Welcome to the practice problems for two pointers. If you need a refresher on the code, the code templates have the patterns in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.

Recommended Study Order

The problems are ordered by difficulty, but the progression matters as much as the individual solutions.

Valid Palindrome teaches opposite direction pointers in their purest form. Master this before adding any complexity.
Remove Duplicates from Sorted Array introduces same direction pointers. The roles are asymmetric, one scans and one writes, which is the other core idea of the pattern.
Squares of a Sorted Array keeps the opposite direction setup but changes where the answer is written. This trains you to notice where the result goes, not just where the pointers are.
Two Sum II is the canonical pair-search problem. If you can write this from memory, the opposite direction template is yours.
Container With Most Water adds a greedy decision to the pointer movement. The rule for which pointer moves is the whole problem.
3Sum layers a fixed pivot over the pair search. This is where duplicate handling enters and the complexity jumps to
O(N^2)
.
Trapping Rain Water combines running maximums with opposite direction movement. It is the hardest problem in the set and the classic capstone for this pattern.

The order above is designed to build intuition progressively. The app schedules your reviews so you don’t forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Valid Palindrome

LeetCode 125 | Difficulty: Easy

Brief: Check whether a string reads the same forwards and backwards, ignoring every character that is not a letter or digit.

Why this pattern: A palindrome is decided by comparing the two ends and moving inward. That is the opposite direction variant with no sum involved.

Key Insight: The pointers must skip non-alphanumeric characters before each comparison. The skipping happens on both sides in the same loop iteration, or the pointers get misaligned.

Visual:

    graph LR
    S["'A man, a plan, a canal: Panama'"] --> L["left skips to 'A'"]
    S --> R["right skips to 'a'"]
    L --> C{"lowercase('A') == lowercase('a')?"}
    R --> C
    C -->|"yes"| M["move both pointers inward"]
    C -->|"no"| F["return false"]

Code:

var isPalindrome = function(s) {
    let left = 0, right = s.length - 1;

    while (left < right) {
        // Skip anything that is not a letter or digit.
        // Without this, punctuation and spaces break the comparison.
        while (left < right && !isAlphanumeric(s[left])) left++;
        while (left < right && !isAlphanumeric(s[right])) right--;

        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
        left++;
        right--;
    }
    return true;
};

function isAlphanumeric(c) {
    return /[a-zA-Z0-9]/.test(c);
}

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            # Skip non-alphanumeric characters so the comparison
            # only ever sees letters and digits.
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1

            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1

        return True

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;

        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;

            if (Character.toLowerCase(s.charAt(left)) !=
                Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;

        while (left < right) {
            while (left < right && !isalnum(s[left])) left++;
            while (left < right && !isalnum(s[right])) right--;

            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

func isPalindrome(s string) bool {
    left, right := 0, len(s)-1

    for left < right {
        // Skip anything that is not a letter or digit
        // before comparing, on both sides of the string.
        for left < right && !isAlphanumeric(s[left]) { left++ }
        for left < right && !isAlphanumeric(s[right]) { right-- }

        if toLower(s[left]) != toLower(s[right]) {
            return false
        }
        left++
        right--
    }
    return true
}

func isAlphanumeric(c byte) bool {
    return (c >= 'a' && c <= 'z') ||
        (c >= 'A' && c <= 'Z') ||
        (c >= '0' && c <= '9')
}

func toLower(c byte) byte {
    if c >= 'A' && c <= 'Z' {
        return c + 32
    }
    return c
}

The template is the opposite direction pair search, with the comparison replaced by a character check and the movement extended with skip loops. The skip loops keep the invariant that both pointers always rest on comparable characters. A string that is only punctuation, like " ", never enters the comparison because left < right fails, so it correctly returns true.

2. Remove Duplicates from Sorted Array

LeetCode 26 | Difficulty: Easy

Brief: Remove duplicates in-place from a sorted array and return the new length.

Why this pattern: Same direction pointers. One index scans, the other marks where the next kept value goes. The prefix of the array doubles as the result buffer.

Key Insight: The scan compares against nums[slow], the last kept value, not against nums[fast - 1]. Once the prefix is overwritten, the raw neighbor is not a reliable comparison target.

Visual:

    graph LR
    I["[0,0,1,1,1,2,2,3,3,4]"] --> S["slow=0, fast=1"]
    S --> D{"nums[fast] != nums[slow]?"}
    D -->|"yes"| W["slow++, copy nums[fast] to nums[slow]"]
    D -->|"no"| N["skip"]
    W --> R["fast++"]
    N --> R
    R --> F["return slow + 1 = 5"]

Code:

var removeDuplicates = function(nums) {
    if (nums.length === 0) return 0;

    let slow = 0; // where the next unique value will be written
    for (let fast = 1; fast < nums.length; fast++) {
        // fast found a value the kept prefix does not have yet.
        // Move the write position forward and place it there.
        if (nums[fast] !== nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
};

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0

        slow = 0  # where the next unique value will be written
        for fast in range(1, len(nums)):
            # The scan found a value the kept prefix does not have.
            # Write it at the next position and extend the prefix.
            if nums[fast] != nums[slow]:
                slow += 1
                nums[slow] = nums[fast]
        return slow + 1

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;

        int slow = 0; // where the next unique value will be written
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        return slow + 1;
    }
}

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;

        int slow = 0; // where the next unique value will be written
        for (int fast = 1; fast < nums.size(); fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        return slow + 1;
    }
};

func removeDuplicates(nums []int) int {
    if len(nums) == 0 { return 0 }

    slow := 0 // where the next unique value will be written
    for fast := 1; fast < len(nums); fast++ {
        if nums[fast] != nums[slow] {
            slow++
            nums[slow] = nums[fast]
        }
    }
    return slow + 1
}

def remove_duplicates(nums)
  return 0 if nums.empty?

  slow = 0 # where the next unique value will be written
  (1...nums.length).each do |fast|
    if nums[fast] != nums[slow]
      slow += 1
      nums[slow] = nums[fast]
    end
  end
  slow + 1
end

The write position slow only advances when a new unique value is found, so the kept prefix always contains one copy of each distinct value in order. The returned length is slow + 1, since slow is an index. The empty-input guard is the first line because without it the function returns 1 for an empty array instead of 0.

3. Squares of a Sorted Array

LeetCode 977 | Difficulty: Easy

Brief: Return a new array where every element of a sorted array is squared, in sorted order.

Why this pattern: The input may contain negatives, so the largest square sits at one of the two ends, not in the middle. Opposite direction pointers compare the two ends and fill the result from the back.

Key Insight: Whichever end has the larger absolute value owns the current right-most slot of the result. The comparison decides which pointer advances.

Visual:

    graph LR
    I["[-4,-1,0,3,10]"] --> C{"abs(nums[left]) > abs(nums[right])?"}
    C -->|"yes"| L["square nums[left], fill result from the back"]
    C -->|"no"| R["square nums[right], fill result from the back"]
    L --> F["[0,1,9,16,100]"]
    R --> F

Code:

var sortedSquares = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    let left = 0, right = n - 1;

    // The largest square is at one of the two ends, so fill
    // the output from the back by comparing absolute values.
    for (let i = n - 1; i >= 0; i--) {
        if (Math.abs(nums[left]) > Math.abs(nums[right])) {
            result[i] = nums[left] * nums[left];
            left++;
        } else {
            result[i] = nums[right] * nums[right];
            right--;
        }
    }
    return result;
};

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        left, right = 0, n - 1

        for i in range(n - 1, -1, -1):
            # The largest remaining square always comes from
            # whichever end has the bigger absolute value.
            if abs(nums[left]) > abs(nums[right]):
                result[i] = nums[left] * nums[left]
                left += 1
            else:
                result[i] = nums[right] * nums[right]
                right -= 1

        return result

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0, right = n - 1;

        for (int i = n - 1; i >= 0; i--) {
            if (Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[i] = nums[left] * nums[left];
                left++;
            } else {
                result[i] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
}

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        int left = 0, right = n - 1;

        for (int i = n - 1; i >= 0; i--) {
            if (abs(nums[left]) > abs(nums[right])) {
                result[i] = nums[left] * nums[left];
                left++;
            } else {
                result[i] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
};

func sortedSquares(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    left, right := 0, n-1

    for i := n - 1; i >= 0; i-- {
        // The two ends hold the largest absolute values.
        // Whichever is bigger owns the current back-most slot.
        if abs(nums[left]) > abs(nums[right]) {
            result[i] = nums[left] * nums[left]
            left++
        } else {
            result[i] = nums[right] * nums[right]
            right--
        }
    }
    return result
}

func abs(x int) int {
    if x < 0 { return -x }
    return x
}

The pointer movement is the opposite direction pair search with the comparison swapped for absolute values. The interesting part is the write side. The result is filled from the back because the largest squares are produced first. If you tried to fill from the front, you would need a third pointer or a sort.

Medium Problems

4. Two Sum II - Input Array Is Sorted

LeetCode 167 | Difficulty: Medium

Brief: Given a 1-indexed sorted array, find two numbers that add up to a target and return their indices.

Why this pattern: This is the purest application of the opposite direction template. The sorted input is exactly the guarantee the pattern needs.

Key Insight: The answer uses 1-based indexing, so add 1 to both pointer positions when returning.

Visual:

    graph LR
    A["Array: 2,7,11,15"] --> B["Target: 9"]
    B --> C["left=0, right=3"]
    C --> D["2+15=17 > 9"]
    D --> E["right--"]
    E --> F["2+11=13 > 9"]
    F --> G["right--"]
    G --> H["2+7=9 == 9"]
    H --> I["Return [1,2]"]

Code:

var twoSum = function(numbers, target) {
    let left = 0, right = numbers.length - 1;

    while (left < right) {
        const sum = numbers[left] + numbers[right];
        if (sum === target) {
            return [left + 1, right + 1];
        } else if (sum < target) {
            left++;  // the sum is too small, so the only way up is from the left
        } else {
            right--; // the sum is too large, so shrink from the right
        }
    }
    return [-1, -1];
};

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1

        while left < right:
            total = numbers[left] + numbers[right]
            if total == target:
                return [left + 1, right + 1]
            elif total < target:
                left += 1
            else:
                right -= 1

        return [-1, -1]

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return {left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return {-1, -1};
    }
};

The two tweaks to the base template are the 1-based return values and the problem guaranteeing exactly one solution, so no duplicate handling is needed. Every comparison rules out all remaining pairs containing the moved element, which keeps the loop linear.

5. Container With Most Water

LeetCode 11 | Difficulty: Medium

Brief: Given an array of heights, find the two lines that together with the x-axis form a container holding the most water.

Why this pattern: The widest container starts with both ends, and narrowing the width can only be compensated by a taller wall. The pointer movement rule is the entire solution.

Key Insight: The shorter wall caps the area, so moving the shorter side inward is the only move that can produce a larger container. Moving the taller side can only shrink the width without raising the cap.

Visual:

    graph TD
    A["Start: left=0, right=n-1"] --> B["Area = min(h[left], h[right]) * (right - left)"]
    B --> C{"h[left] < h[right]?"}
    C -->|"yes"| D["left++"]
    C -->|"no"| E["right--"]
    D --> F{"left < right?"}
    E --> F
    F -->|"yes"| B
    F -->|"no"| G["Return max area"]

Code:

var maxArea = function(height) {
    let left = 0, right = height.length - 1;
    let maxArea = 0;

    while (left < right) {
        const area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);

        // The shorter wall caps the area, so moving it inward
        // is the only move that can find a bigger container.
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
};

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0

        while left < right:
            area = min(height[left], height[right]) * (right - left)
            max_area = max(max_area, area)

            # The shorter wall caps the area. Move it inward,
            # which is the only move that can enlarge the container.
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxArea = 0;

        while (left < right) {
            int area = min(height[left], height[right]) * (right - left);
            maxArea = max(maxArea, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
};

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0

    for left < right {
        area := min(height[left], height[right]) * (right - left)
        if area > maxArea { maxArea = area }

        // The shorter wall caps the area, so the only move
        // that can help is advancing the shorter side.
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return maxArea
}

func min(a, b int) int {
    if a < b { return a }
    return b
}

The greedy move is what makes this correct. For any container, the area is capped by its shorter wall. Every container that keeps the shorter wall and moves the taller one inward is narrower and still capped by the same short wall, so none of them can beat the current area. That eliminates a whole group of candidates with one comparison, exactly like the pair search.

6. 3Sum

LeetCode 15 | Difficulty: Medium

Brief: Find all unique triplets in an array that sum to zero.

Why this pattern: Sort the input, fix one element as the pivot, then run the opposite direction pair search on the range to the right of the pivot. The pair search now targets -pivot.

Key Insight: Duplicate values must be skipped in two places, once when advancing the pivot and once after a triplet is found, or the answer contains repeated triplets.

Visual:

    graph LR
    S["[-4,-1,-1,0,1,2]"] --> P["Pivot at index 1: -1"]
    P --> C["left at index 2: -1, right at index 5: 2"]
    C --> A["-1 + -1 + 2 = 0"]
    A --> B["Record [-1,-1,2]"]
    B --> D["Skip duplicate neighbors, advance both pointers"]
    D --> E["Continue until the pair range is exhausted"]

Code:

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];

    for (let i = 0; i < nums.length - 2; i++) {
        // A repeated pivot produces the same triplets again,
        // so skip it to keep the answer free of duplicates.
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                // Skip equal neighbors so the same triplet
                // is never recorded twice.
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
};

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []

        for i in range(len(nums) - 2):
            # A repeated pivot can only reproduce triplets that
            # were already recorded, so skip it.
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, len(nums) - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    # Advance past equal neighbors to avoid
                    # recording the same triplet twice.
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif total < 0:
                    left += 1
                else:
                    right -= 1

        return result

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;

        for (int i = 0; i < (int)nums.size() - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
};

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    result := [][]int{}

    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] { continue }

        left, right := i+1, len(nums)-1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            if sum == 0 {
                result = append(result, []int{nums[i], nums[left], nums[right]})
                // Advance past equal neighbors so the same
                // triplet is never recorded twice.
                for left < right && nums[left] == nums[left+1] { left++ }
                for left < right && nums[right] == nums[right-1] { right-- }
                left++
                right--
            } else if sum < 0 {
                left++
            } else {
                right--
            }
        }
    }
    return result
}

def three_sum(nums)
  nums.sort!
  result = []

  (0...nums.length - 2).each do |i|
    next if i > 0 && nums[i] == nums[i - 1]

    left, right = i + 1, nums.length - 1
    while left < right
      sum = nums[i] + nums[left] + nums[right]
      if sum == 0
        result << [nums[i], nums[left], nums[right]]
        left += 1 while left < right && nums[left] == nums[left + 1]
        right -= 1 while left < right && nums[right] == nums[right - 1]
        left += 1
        right -= 1
      elsif sum < 0
        left += 1
      else
        right -= 1
      end
    end
  end
  result
end

The pivot loop turns the linear template into a quadratic algorithm,

O(N^2)

time and

O(1)

extra space after the sort. The duplicate skipping appears twice. The pivot skip prevents repeating work from equal pivot values, and the neighbor skip after a match prevents recording the same triplet twice from one pivot. Missing either one fails the uniqueness requirement.

Hard Problems

7. Trapping Rain Water

LeetCode 42 | Difficulty: Hard

Brief: Given an array of elevations, compute how much water is trapped after a rain.

Why this pattern: Water above a bar is capped by the shorter of the tallest wall to its left and the tallest wall to its right. Two pointers can track both maximums in one pass with

O(1)

space.

Key Insight: Process the side with the lower current wall. Its water level is already decided by the running maximum on that side, because the wall on the other side is at least as tall.

Visual:

    graph TD
    I["left=0, right=n-1, leftMax=0, rightMax=0"] --> C{"height[left] < height[right]?"}
    C -->|"yes"| L["Process left bar against leftMax"]
    C -->|"no"| R["Process right bar against rightMax"]
    L --> M["left++"]
    R --> N["right--"]
    M --> C
    N --> C

Code:

var trap = function(height) {
    let left = 0, right = height.length - 1;
    let leftMax = 0, rightMax = 0, water = 0;

    while (left < right) {
        // Process the side with the lower wall. Its water level
        // is decided by the highest wall seen so far on that side.
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left]; // no wall to trap against yet
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }
    return water;
};

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max, right_max, water = 0, 0, 0

        while left < right:
            # Work on the side with the lower wall. Its water
            # level depends only on the max seen on that side.
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    water += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    water += right_max - height[right]
                right -= 1

        return water

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, water = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
                right--;
            }
        }
        return water;
    }
}

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0, water = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
                right--;
            }
        }
        return water;
    }
};

func trap(height []int) int {
    left, right := 0, len(height)-1
    leftMax, rightMax, water := 0, 0, 0

    for left < right {
        // Handle the side with the lower wall. Its water level
        // is fixed by the running max on that side alone.
        if height[left] < height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                water += leftMax - height[left]
            }
            left++
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                water += rightMax - height[right]
            }
            right--
        }
    }
    return water
}

def trap(height)
  left, right = 0, height.length - 1
  left_max, right_max, water = 0, 0, 0

  while left < right
    if height[left] < height[right]
      if height[left] >= left_max
        left_max = height[left]
      else
        water += left_max - height[left]
      end
      left += 1
    else
      if height[right] >= right_max
        right_max = height[right]
      else
        water += right_max - height[right]
      end
      right -= 1
    end
  end
  water
end

When the left wall is shorter than the right one, the water above the left bar is capped by leftMax, because the current right bar is already taller than anything on the left. The same argument applies symmetrically, so each bar is processed exactly once and no precomputed arrays are needed. This is the

O(1)

space answer to a problem often solved with extra arrays. The same problem has a monotonic stack solution with a different tradeoff, fully worked through on the stack pattern problems page , which is worth reading to see both approaches side by side.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These seven problems cover both directions of the pattern. Start with the opposite direction mechanics in Valid Palindrome and Two Sum II, pick up same direction rewrites in Remove Duplicates, then layer on greedy movement, pivots, and running maximums. The three-pointer extension of this pattern, Sort Colors , has a full walkthrough on the array manipulation problems page , and the sliding window problems page continues with the related pattern for contiguous subarrays. By the end of this set, you should be able to look at an array problem and know which direction the pointers should face.

Done with these problems? The app has more, plus a spaced repetition system that brings problems back right before you would forget them. Continue your prep .