"""
p52 — Next Greater Element I (LeetCode 496, EASY).

nums1 is a subset of nums2; nums2 has distinct values. For each nums1[i], find the
next strictly-greater value to the right of its occurrence in nums2, else -1.

Implementations:
    next_greater_element_stack — precompute via monotonic stack on nums2. O(n+m).
    next_greater_element_brute — nested loop O(n*m) oracle.
"""
from __future__ import annotations
import random
from typing import Dict, List


def next_greater_element_stack(nums1: List[int], nums2: List[int]) -> List[int]:
    # INVARIANT: stack holds values from nums2 (left-to-right) in STRICTLY DECREASING order.
    # When a larger value v arrives, every smaller value still on the stack gets v as its
    # next greater.
    nxt: Dict[int, int] = {}
    stack: List[int] = []
    for v in nums2:
        while stack and stack[-1] < v:
            nxt[stack.pop()] = v
        stack.append(v)
    for v in stack:
        nxt[v] = -1
    return [nxt[v] for v in nums1]


def next_greater_element_brute(nums1: List[int], nums2: List[int]) -> List[int]:
    pos: Dict[int, int] = {v: i for i, v in enumerate(nums2)}
    out: List[int] = []
    for q in nums1:
        i = pos[q]
        ans = -1
        for j in range(i + 1, len(nums2)):
            if nums2[j] > q:
                ans = nums2[j]
                break
        out.append(ans)
    return out


def edge_cases() -> None:
    # LC canonical
    assert next_greater_element_stack([4, 1, 2], [1, 3, 4, 2]) == [-1, 3, -1]
    assert next_greater_element_stack([2, 4], [1, 2, 3, 4]) == [3, -1]

    # Subset == full
    assert next_greater_element_stack([1, 3, 4, 2], [1, 3, 4, 2]) == [3, 4, -1, -1]

    # Single
    assert next_greater_element_stack([1], [1]) == [-1]

    # Strictly increasing nums2 — every non-last value has the next as its NGE
    assert next_greater_element_stack([1, 3], [1, 2, 3, 4]) == [2, 4]

    # Strictly decreasing — all -1 except none gets one
    assert next_greater_element_stack([4, 3, 2, 1], [4, 3, 2, 1]) == [-1, -1, -1, -1]

    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(1000):
        m = rng.randint(1, 20)
        # Distinct values: sample from large range, then permute
        nums2 = rng.sample(range(1, 200), m)
        # nums1 is a random non-empty subset of nums2
        k = rng.randint(1, m)
        nums1 = rng.sample(nums2, k)
        a = next_greater_element_stack(nums1, nums2)
        b = next_greater_element_brute(nums1, nums2)
        assert a == b, f"trial {trial}: nums1={nums1} nums2={nums2} a={a} b={b}"
    print("stress_test: 1000 random trials — stack and brute agree.")


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