Specials

When To Use

Use this for two-pointer problems that have a problem-specific invariant and do not fit a broad reusable template cleanly.

Problems

Trapping Rain Water

Problem: compute total water trapped between bars.

Pattern: opposite ends with running best boundaries.

Key idea: if height[l] < height[r], the water at l is decided by left_max; there is already a right wall tall enough to close it.

Applied pseudocode:

l = 0
r = n - 1
left_max = 0
right_max = 0
ans = 0
 
while l < r:
    if height[l] < height[r]:
        left_max = max(left_max, height[l])
        ans += left_max - height[l]
        l++
    else:
        right_max = max(right_max, height[r])
        ans += right_max - height[r]
        r--

Maximum Score of a Good Subarray

Problem: find the max score min(nums[l..r]) * (r - l + 1) where the subarray must contain index k.

Pattern: expand outward from k, always choosing the better next boundary.

Key idea: for a fixed current minimum, a wider window is better, so expand toward the side with the larger next value to keep the minimum as high as possible.

Applied pseudocode:

l = k
r = k
cur_min = nums[k]
ans = nums[k]
 
while l > 0 or r < n - 1:
    if l == 0:
        r++
    else if r == n - 1:
        l--
    else if nums[l - 1] < nums[r + 1]:
        r++
    else:
        l--
 
    cur_min = min(cur_min, nums[l], nums[r])
    ans = max(ans, cur_min * (r - l + 1))