"""
p55 — Trapping Rain Water (LeetCode 42, HARD).

Given height[] (non-negative ints), how many units of water are trapped after rain?

Implementations:
    trap_prefix_arrays  — precompute max_left[], max_right[], sum per column. O(n) time, O(n) space.
    trap_two_pointers   — converging pointers, move the shorter wall. O(n) time, O(1) space.
    trap_stack          — monotonic decreasing stack, horizontal slices. O(n) time, O(n) space.
    trap_brute          — for each i, scan left/right for max. O(n^2) oracle.
"""
from __future__ import annotations
import random
from typing import List


def trap_prefix_arrays(height: List[int]) -> int:
    n = len(height)
    if n < 3:
        return 0
    max_left = [0] * n
    max_right = [0] * n
    max_left[0] = height[0]
    for i in range(1, n):
        max_left[i] = max(max_left[i - 1], height[i])
    max_right[-1] = height[-1]
    for i in range(n - 2, -1, -1):
        max_right[i] = max(max_right[i + 1], height[i])
    total = 0
    for i in range(n):
        total += min(max_left[i], max_right[i]) - height[i]
    return total


def trap_two_pointers(height: List[int]) -> int:
    # INVARIANT: lmax = max(height[0..l]); rmax = max(height[r..n-1]).
    # The pointer with the smaller side-wall is guaranteed bottlenecked by its own side,
    # so water at that column = side_wall - height[that column].
    n = len(height)
    if n < 3:
        return 0
    l, r = 0, n - 1
    lmax = rmax = 0
    total = 0
    while l < r:
        if height[l] < height[r]:
            lmax = max(lmax, height[l])
            total += lmax - height[l]
            l += 1
        else:
            rmax = max(rmax, height[r])
            total += rmax - height[r]
            r -= 1
    return total


def trap_stack(height: List[int]) -> int:
    # INVARIANT: stack holds indices whose heights are NON-STRICTLY decreasing top-down,
    # i.e., each new index is pushed only after popping shorter bars.
    # When a taller bar arrives, the popped bar is the FLOOR of a horizontal water slice;
    # the bar below it on the stack is the LEFT wall; current i is the RIGHT wall.
    stack: List[int] = []
    total = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            width = i - left - 1
            bounded = min(h, height[left]) - height[bottom]
            total += width * bounded
        stack.append(i)
    return total


def trap_brute(height: List[int]) -> int:
    n = len(height)
    total = 0
    for i in range(n):
        ml = max(height[: i + 1])
        mr = max(height[i:])
        total += min(ml, mr) - height[i]
    return total


def edge_cases() -> None:
    # LC canonical
    assert trap_prefix_arrays([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
    assert trap_two_pointers([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
    assert trap_stack([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6

    # LC second canonical
    assert trap_prefix_arrays([4, 2, 0, 3, 2, 5]) == 9
    assert trap_two_pointers([4, 2, 0, 3, 2, 5]) == 9
    assert trap_stack([4, 2, 0, 3, 2, 5]) == 9

    # Single deep valley
    assert trap_two_pointers([3, 0, 2, 0, 4]) == 7

    # Flat top
    assert trap_two_pointers([3, 3, 3]) == 0

    # Monotone decreasing — no right wall
    assert trap_two_pointers([5, 4, 3, 2, 1]) == 0

    # Monotone increasing — no left wall
    assert trap_two_pointers([1, 2, 3, 4, 5]) == 0

    # Single column
    assert trap_two_pointers([7]) == 0

    # Two columns
    assert trap_two_pointers([4, 7]) == 0

    # Empty
    assert trap_two_pointers([]) == 0
    assert trap_prefix_arrays([]) == 0
    assert trap_stack([]) == 0

    # All zeros
    assert trap_two_pointers([0, 0, 0, 0]) == 0

    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(1000):
        n = rng.randint(0, 30)
        height = [rng.randint(0, 10) for _ in range(n)]
        a = trap_prefix_arrays(height)
        b = trap_two_pointers(height)
        c = trap_stack(height)
        d = trap_brute(height) if n > 0 else 0
        assert a == b == c == d, f"trial {trial}: height={height} prefix={a} 2p={b} stack={c} brute={d}"
    print("stress_test: 1000 random trials — prefix, two_pointers, stack, brute all agree.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")