"""
p10 — Contains Duplicate
=========================
LeetCode 217 · Easy · Topics: Array, Hash Table, Sorting

Sections:
  1. BRUTE FORCE — O(N^2)
  2. HASHSET — O(N) avg time, O(N) space, EARLY EXIT (production)
  3. SORT + ADJACENT — O(N log N) time, O(1) extra space (mutates a copy)
  4. ONE-LINER — len(set(nums)) != len(nums) — for comparison
  5. STRESS TEST — all four agree across 1000 random arrays
  6. EDGE CASES
"""

import random
from typing import List


# ----------------------------------------------------------------------
# 1. BRUTE FORCE — O(N^2)
# ----------------------------------------------------------------------
def contains_duplicate_brute(nums: List[int]) -> bool:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return True
    return False


# ----------------------------------------------------------------------
# 2. HASHSET — production answer with EXPLICIT EARLY EXIT
# ----------------------------------------------------------------------
def contains_duplicate(nums: List[int]) -> bool:
    # INVARIANT: at the top of iteration i, seen = {nums[0..i-1]} as a set.
    # If nums[i] is already in seen, some earlier index has the same value.
    # Early-exit on first hit — for duplicate-near-start inputs, this is ~O(2).
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False


# ----------------------------------------------------------------------
# 3. SORT + ADJACENT — memory-efficient when mutation OK
# ----------------------------------------------------------------------
def contains_duplicate_sort(nums: List[int]) -> bool:
    # Copy to avoid mutating caller's list. If mutation is permitted, sort in place.
    arr = sorted(nums)
    for i in range(1, len(arr)):
        if arr[i] == arr[i - 1]:
            return True
    return False


# ----------------------------------------------------------------------
# 4. ONE-LINER — Pythonic but NO EARLY EXIT
# ----------------------------------------------------------------------
def contains_duplicate_oneliner(nums: List[int]) -> bool:
    return len(set(nums)) != len(nums)


# ----------------------------------------------------------------------
# 5. STRESS TEST
# ----------------------------------------------------------------------
def stress_test(iterations: int = 1000, max_n: int = 50) -> None:
    rng = random.Random(42)
    for it in range(iterations):
        n = rng.randint(0, max_n)
        # Vary value range to control duplicate density
        if rng.random() < 0.3:
            # narrow range — lots of duplicates
            nums = [rng.randint(0, max(1, n // 4)) for _ in range(n)]
        else:
            # wide range — likely all distinct
            nums = [rng.randint(-10_000, 10_000) for _ in range(n)]
        a = contains_duplicate_brute(nums)
        b = contains_duplicate(nums)
        c = contains_duplicate_sort(nums)
        d = contains_duplicate_oneliner(nums)
        assert a == b == c == d, (
            f"disagreement on {nums}: brute={a} hashset={b} sort={c} oneliner={d}"
        )
    print(f"stress_test PASSED — {iterations} iterations (4 algorithms agree)")


# ----------------------------------------------------------------------
# 6. EDGE CASES
# ----------------------------------------------------------------------
def edge_cases() -> None:
    cases = [
        ([], False, "empty"),
        ([7], False, "single element"),
        ([1, 2], False, "two distinct"),
        ([1, 1], True, "two equal — earliest possible duplicate"),
        ([1, 2, 3, 4, 5], False, "all distinct"),
        ([1, 1, 1, 1], True, "all equal"),
        ([1, 2, 3, 1], True, "canonical LC example"),
        ([-1, -1, 0], True, "negatives"),
        (list(range(100)) + [50], True, "duplicate buried at end of long array"),
    ]
    for nums, expected, label in cases:
        got = contains_duplicate(nums)
        status = "PASS" if got == expected else "FAIL"
        print(f"  [{status}] {label}: expected={expected} got={got}")


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