"""
p28 — Trapping Rain Water (LeetCode 42).

Four implementations:
    trap_prefix_max     — O(N) time, O(N) space (Solution A)
    trap_two_pointer    — O(N) time, O(1) space (Solution B)
    trap_stack          — O(N) time, O(N) space, monotonic decreasing (Solution C)
    trap_brute          — O(N^2) per-column scan, ORACLE

Run: python3 solution.py
"""
from __future__ import annotations
import random
from typing import List


# --------------------------------------------------------------------------------------
# Solution A — Prefix-suffix max arrays. O(N) time, O(N) space.
# --------------------------------------------------------------------------------------
def trap_prefix_max(height: List[int]) -> int:
    n = len(height)
    if n < 3:
        return 0
    # INVARIANT: max_left[i] = max(height[0..i]), inclusive.
    max_left = [0] * n
    max_left[0] = height[0]
    for i in range(1, n):
        max_left[i] = max(max_left[i - 1], height[i])
    # INVARIANT: max_right[i] = max(height[i..n-1]), inclusive.
    max_right = [0] * n
    max_right[n - 1] = height[n - 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):
        # Water above column i is bounded by the shorter of the two walls.
        level = min(max_left[i], max_right[i])
        total += max(0, level - height[i])  # clamp; redundant given max_left/right ≥ h[i]
    return total


# --------------------------------------------------------------------------------------
# Solution B — Two pointers. O(N) time, O(1) extra space.
# --------------------------------------------------------------------------------------
def trap_two_pointer(height: List[int]) -> int:
    n = len(height)
    if n < 3:
        return 0
    lo, hi = 0, n - 1
    left_max, right_max = 0, 0
    total = 0
    # INVARIANT: left_max = max(height[0..lo]); right_max = max(height[hi..n-1]).
    # INVARIANT: when h[lo] < h[hi], right_max >= h[hi] > h[lo] dominates, so
    #            water at lo is governed by left_max alone.
    while lo < hi:
        if height[lo] < height[hi]:
            left_max = max(left_max, height[lo])
            total += left_max - height[lo]  # ≥ 0 since left_max ≥ h[lo]
            lo += 1
        else:
            right_max = max(right_max, height[hi])
            total += right_max - height[hi]
            hi -= 1
    return total


# --------------------------------------------------------------------------------------
# Solution C — Monotonic decreasing stack. O(N) time, O(N) space.
# Processes water in horizontal strips.
# --------------------------------------------------------------------------------------
def trap_stack(height: List[int]) -> int:
    n = len(height)
    if n < 3:
        return 0
    stack: List[int] = []  # indices of bars with strictly-decreasing-or-equal heights
    total = 0
    for i, h in enumerate(height):
        # While the current bar is taller than the top, the top is a "trough bottom":
        # it has a right wall (i) and, after pop, a left wall (new top).
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break  # no left wall; water spills
            left = stack[-1]
            width = i - left - 1
            strip_h = min(height[left], h) - height[bottom]
            total += width * strip_h
        stack.append(i)
    return total


# --------------------------------------------------------------------------------------
# Brute-force oracle — O(N^2) per-column scan. Used to validate.
# --------------------------------------------------------------------------------------
def trap_brute(height: List[int]) -> int:
    n = len(height)
    total = 0
    for i in range(n):
        max_l = max(height[: i + 1])
        max_r = max(height[i:])
        total += max(0, min(max_l, max_r) - height[i])
    return total


# --------------------------------------------------------------------------------------
# Tests
# --------------------------------------------------------------------------------------
def edge_cases() -> None:
    cases = [
        ([], 0),
        ([5], 0),
        ([3, 0], 0),
        ([0, 3], 0),
        ([3, 3, 3], 0),                            # all equal — no water
        ([1, 2, 3, 4, 5], 0),                      # monotone increasing
        ([5, 4, 3, 2, 1], 0),                      # monotone decreasing
        ([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], 6), # LC canonical
        ([4, 2, 0, 3, 2, 5], 9),                   # LC alt
        ([3, 0, 2, 0, 4], 7),                      # V shapes with plateaus
        ([5, 0, 5], 5),                            # simple bucket
        ([2, 0, 2], 2),                            # tiny bucket
        ([0, 0, 0, 0], 0),                         # all zeros
        ([1, 0, 1, 0, 1], 2),                      # W-shape
    ]
    for arr, expected in cases:
        for name, fn in [
            ("prefix_max", trap_prefix_max),
            ("two_pointer", trap_two_pointer),
            ("stack", trap_stack),
            ("brute", trap_brute),
        ]:
            got = fn(list(arr))
            assert got == expected, f"{name}({arr}) → {got}, expected {expected}"
    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(300):
        n = rng.randint(0, 25)
        height = [rng.randint(0, 8) for _ in range(n)]
        a = trap_prefix_max(list(height))
        b = trap_two_pointer(list(height))
        c = trap_stack(list(height))
        d = trap_brute(list(height))
        assert a == b == c == d, f"DISAGREE on {height}: prefix={a} two={b} stack={c} brute={d}"
    print("stress_test: 300 random arrays — all four implementations agree.")


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