"""
p01 — Two Sum
=============
LeetCode 1 · Easy · Topics: Array, Hash Table
Companies: Amazon, Google, Meta, Apple, Microsoft, Bloomberg

The file is structured in 4 sections:
  1. BRUTE FORCE (correctness oracle for stress test)
  2. OPTIMAL (one-pass hashmap)
  3. STRESS TEST (brute vs optimal on random inputs)
  4. EDGE CASE runner
"""

import random
from typing import List


# ----------------------------------------------------------------------
# 1. BRUTE FORCE — O(N^2) time, O(1) space
# ----------------------------------------------------------------------
def two_sum_brute(nums: List[int], target: int) -> List[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []  # per problem, never reached, but explicit fallback aids debugging


# ----------------------------------------------------------------------
# 2. OPTIMAL — O(N) time, O(N) space (one-pass hashmap)
# ----------------------------------------------------------------------
def two_sum(nums: List[int], target: int) -> List[int]:
    # INVARIANT: at iteration i, `seen` holds {value: latest_index} for nums[0..i-1].
    # The complement check happens BEFORE insertion — this is what makes [3,3] work:
    # at i=1, seen={3:0}, complement=3 is found at index 0 → return [0, 1].
    # Reversing (insert then check) would self-match the current index.
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        complement = target - x
        j = seen.get(complement)  # one hash lookup, not two
        if j is not None:
            return [j, i]
        seen[x] = i
    return []


# ----------------------------------------------------------------------
# 3. STRESS TEST — random inputs, brute vs optimal must agree on validity
# ----------------------------------------------------------------------
def stress_test(iterations: int = 1000, max_n: int = 30, value_range: int = 50) -> None:
    """
    Compares brute and optimal on random inputs.
    Both return any valid pair; we assert both pairs SUM to target
    (not that they're identical, since multiple valid pairs may exist).
    """
    rng = random.Random(42)  # deterministic for reproducible failures
    for it in range(iterations):
        n = rng.randint(2, max_n)
        nums = [rng.randint(-value_range, value_range) for _ in range(n)]
        # ensure at least one valid pair: pick two distinct indices, set target
        i, j = rng.sample(range(n), 2)
        target = nums[i] + nums[j]

        a = two_sum_brute(nums, target)
        b = two_sum(nums, target)

        assert len(a) == 2, f"brute failed: nums={nums}, target={target}"
        assert len(b) == 2, f"optimal failed: nums={nums}, target={target}"
        assert nums[a[0]] + nums[a[1]] == target, f"brute wrong sum: {a} on {nums}"
        assert nums[b[0]] + nums[b[1]] == target, f"optimal wrong sum: {b} on {nums}"
        assert b[0] != b[1], f"optimal returned same index twice: {b} on {nums}"
    print(f"stress_test PASSED — {iterations} iterations")


# ----------------------------------------------------------------------
# 4. EDGE CASES — explicit, named cases that catch common bugs
# ----------------------------------------------------------------------
def edge_cases() -> None:
    cases = [
        ([2, 7, 11, 15], 9, "canonical"),
        ([3, 3], 6, "same-value duplicates — the [3,3] trap"),
        ([-3, 4, 3, 90], 0, "negative values"),
        ([0, 4, 3, 0], 0, "two zeros summing to zero"),
        ([-1, -2, -3, -4], -7, "all negatives"),
        ([1_000_000_000, 1_000_000_000], 2_000_000_000, "large values, no overflow in Python"),
    ]
    for nums, target, label in cases:
        result = two_sum(nums, target)
        ok = len(result) == 2 and nums[result[0]] + nums[result[1]] == target and result[0] != result[1]
        status = "PASS" if ok else "FAIL"
        print(f"  [{status}] {label}: nums={nums}, target={target} → {result}")


if __name__ == "__main__":
    print("=== Edge cases ===")
    edge_cases()
    print("\n=== Stress test ===")
    stress_test()