Applied Patterns

"""Unit 27 — Practical Patterns: Two Pointer
Topic: Two Pointer Patterns
Time: O(n) per pattern
Space: O(1) ~ O(n)

Description:
    1. Two pointers in opposite directions: Sum of two numbers in a sorted array
    2. Two pointers in the same direction: Minimum subarray with sum at least target
    3. Remove duplicates: Keep only unique elements in a sorted array"""


# ──────────────────────────────────────────────
#1. Two-Pointer in Opposite Directions — Sum of Two Numbers
# ──────────────────────────────────────────────

def two_sum_sorted(arr: list[int], target: int) -> list[tuple[int, int]]:
    """Return all (i, j) pairs with sum equal to target in a sorted array (i < j).

    Time: O(n)
    Space: O(size of result)"""
    result: list[tuple[int, int]] = []
    lo, hi = 0, len(arr) - 1

    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            result.append((arr[lo], arr[hi]))
            lo += 1
            hi -= 1
            #Skip Duplicates
            while lo < hi and arr[lo] == arr[lo - 1]:
                lo += 1
            while lo < hi and arr[hi] == arr[hi + 1]:
                hi -= 1
        elif s < target:
            lo += 1
        else:
            hi -= 1

    return result


# ──────────────────────────────────────────────
#2. Two-Pointer in Same Direction — Minimum Subarray Sum
# ──────────────────────────────────────────────

def min_subarray_len(arr: list[int], target: int) -> int:
    """Return the length of the shortest contiguous subarray with sum at least target. Return 0 if none exists.

    Time: O(n) — lo and hi each move at most n times
    Space: O(1)"""
    n = len(arr)
    lo = 0
    total = 0
    min_len = n + 1

    for hi in range(n):
        total += arr[hi]

        #Condition Met → Move lo as far right as possible
        while total >= target:
            min_len = min(min_len, hi - lo + 1)
            total -= arr[lo]
            lo += 1

    return min_len if min_len <= n else 0


# ──────────────────────────────────────────────
#3. Two-Pointer — Remove Duplicates in Sorted Array (in-place)
# ──────────────────────────────────────────────

def remove_duplicates(arr: list[int]) -> int:
    """Remove duplicates from a sorted array and return the number of unique elements.
    Result is stored in arr[:result_len].

    Time: O(n)
    Space: O(1)"""
    if not arr:
        return 0

    write = 1   #Next Position to Use

    for read in range(1, len(arr)):
        if arr[read] != arr[write - 1]:
            arr[write] = arr[read]
            write += 1

    return write


# ──────────────────────────────────────────────
#4. Two-Pointer — Count of Subarrays with Sum == Target
# ──────────────────────────────────────────────

def count_subarray_sum(arr: list[int], target: int) -> int:
    """Return the count of contiguous subarrays whose sum is exactly target (positive array).

    Time: O(n)
    Space: O(1)

    Note: Only valid for arrays without negative numbers.
          If negatives exist, use a hashmap (prefix sum)."""
    lo = total = count = 0
    for hi in range(len(arr)):
        total += arr[hi]
        while total > target and lo <= hi:
            total -= arr[lo]
            lo += 1
        if total == target:
            count += 1
    return count


def main() -> None:
    #── 1. Sum of Two Numbers ──
    print("=" * 55)
    print("1. Sum of Two Numbers (Sorted Array, Two-Pointer in Opposite Directions)")
    print("=" * 55)
    arr1 = [-2, -1, 0, 1, 2, 3, 4, 5]
    target1 = 4
    pairs = two_sum_sorted(arr1, target1)
    print(f"Array: {arr1}")
    print(f"  target: {target1}")
    print(f"Result: {pairs}")

    #── 2. Minimum Subarray ──
    print()
    print("=" * 55)
    print("2. Minimum Subarray Length with Sum ≥ Target (Two-Pointer in Same Direction)")
    print("=" * 55)
    cases = [
        ([2, 3, 1, 2, 4, 3], 7),
        ([1, 4, 4], 4),
        ([1, 1, 1, 1], 10),
    ]
    for arr2, tgt in cases:
        result = min_subarray_len(arr2, tgt)
        print(f"arr={arr2}, target={tgt} → Minimum Length: {result}")

    #── 3. Remove Duplicates ──
    print()
    print("=" * 55)
    print("3. Remove Duplicates in Sorted Array (in-place)")
    print("=" * 55)
    arr3 = [1, 1, 2, 2, 3, 4, 4, 5]
    print(f"Original: {arr3}")
    k = remove_duplicates(arr3)
    print(f"After Removal ({k} elements): {arr3[:k]}")

    #── 4. Count of Subarrays with Sum == Target ──
    print()
    print("=" * 55)
    print("4. Number of Subarrays with Sum == Target (Positive Array)")
    print("=" * 55)
    arr4 = [1, 2, 3, 2, 1, 4]
    target4 = 6
    cnt = count_subarray_sum(arr4, target4)
    print(f"Array: {arr4}, Target: {target4}")
    print(f"Number of Subarrays with Sum {target4}: {cnt}")

    #── Complexity Summary ──
    print()
    print("=" * 55)
    print("Two-Pointer Complexity Summary")
    print("=" * 55)
    print("Opposite Directions: O(n), Requires Sorted Array")
    print("Same Direction: O(n), Requires Array with Positive Values")
    print("Remove duplicates: O(n), in-place O(1) space")


if __name__ == "__main__":
    main()

"""Unit 27 — Practical Patterns: Sliding Window
Topic : Sliding Window — Fixed/Variable + Deque Min/Max
Time  : O(n)
Space : O(k) or O(n)

Explanation:
    1. Fixed-size window: Maximum sum of a length k interval
    2. Variable-size window: Minimal interval with a sum at least target (positive)
    3. O(n) window minimum with deque: Baekjoon 11003 style
    4. Maximum number of unique characters in variable-size window (string)"""

from collections import deque


# ──────────────────────────────────────────────
#1. Fixed-size window — Maximum sum
# ──────────────────────────────────────────────

def max_sum_fixed_window(arr: list[int], k: int) -> int:
    """Return the maximum sum of a contiguous subarray of length k.

    Time : O(n)
    Space: O(1)"""
    if len(arr) < k:
        return 0

    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]   #Add on the right, remove on the left
        max_sum = max(max_sum, window_sum)

    return max_sum


# ──────────────────────────────────────────────
#2. Variable-size window — Minimum subarray with sum ≥ target
# ──────────────────────────────────────────────

def min_window_sum(arr: list[int], target: int) -> int:
    """Return the length of the shortest subarray whose sum is at least target (positive array).

    Time : O(n)
    Space: O(1)"""
    n = len(arr)
    lo = total = 0
    min_len = n + 1

    for hi in range(n):
        total += arr[hi]
        while total >= target:
            min_len = min(min_len, hi - lo + 1)
            total -= arr[lo]
            lo += 1

    return min_len if min_len <= n else 0


# ──────────────────────────────────────────────
#3. Deque sliding window — Minimum of range O(n)
# ──────────────────────────────────────────────

def sliding_window_minimum(arr: list[int], k: int) -> list[int]:
    """Return a list of minimum values in sliding windows of size k.

    Principle: Monotonic increasing deque — the front of the deque is the index of the current window's minimum.
    Remove indices from the back that are larger than the new element (unnecessary).

    Time : O(n)  — each element enters and leaves the deque once
    Space: O(k)"""
    result: list[int] = []
    dq: deque[int] = deque()   #Store index

    for i, val in enumerate(arr):
        #Remove elements from the back of the deque that are greater than or equal to the current value (keep monotonic increase)
        while dq and arr[dq[-1]] >= val:
            dq.pop()
        dq.append(i)

        #Remove index that went out of the window
        if dq[0] <= i - k:
            dq.popleft()

        #Save result once the window is complete
        if i >= k - 1:
            result.append(arr[dq[0]])

    return result


# ──────────────────────────────────────────────
#4. Variable window — Maximum length substring with at most k unique characters
# ──────────────────────────────────────────────

def max_len_at_most_k_distinct(s: str, k: int) -> int:
    """Return the length of the longest substring with at most k distinct characters.

    Time : O(n)
    Space: O(k)  (maximum k character types)"""
    freq: dict[str, int] = {}
    lo = max_len = 0

    for hi, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1

        while len(freq) > k:
            left_ch = s[lo]
            freq[left_ch] -= 1
            if freq[left_ch] == 0:
                del freq[left_ch]
            lo += 1

        max_len = max(max_len, hi - lo + 1)

    return max_len


def main() -> None:
    #── 1. Maximum sum with fixed window ──
    print("=" * 55)
    print("1. Maximum sum with fixed-size window")
    print("=" * 55)
    arr1 = [2, 1, 5, 1, 3, 2]
    k1 = 3
    result1 = max_sum_fixed_window(arr1, k1)
    print(f"Array: {arr1}, k={k1}")
    print(f"Maximum sum: {result1}  (5+1+3=9 or 2+1+5=8 → {result1})")

    #Check sum of all windows
    print("Sum per window:", [sum(arr1[i:i+k1]) for i in range(len(arr1)-k1+1)])

    #── 2. Minimum subarray with variable window ──
    print()
    print("=" * 55)
    print("2. Minimum subarray with sum ≥ target")
    print("=" * 55)
    cases2 = [
        ([2, 3, 1, 2, 4, 3], 7),
        ([1, 4, 4], 4),
    ]
    for arr2, tgt in cases2:
        r = min_window_sum(arr2, tgt)
        print(f"  arr={arr2}, target={tgt} → {r}")

    #── 3. Sliding window minimum (deque) ──
    print()
    print("=" * 55)
    print("3. Sliding window minimum (deque, O(n))")
    print("=" * 55)
    arr3 = [1, 3, -1, -3, 5, 3, 6, 7]
    k3 = 3
    mins = sliding_window_minimum(arr3, k3)
    print(f"Array: {arr3}")
    print(f"k={k3} Window minimums: {mins}")
    print(f"Expected:          [-1, -3, -3, -3, 3, 3]")

    #── 4. Longest substring with at most k unique characters ──
    print()
    print("=" * 55)
    print("4. Longest substring with ≤ k unique characters")
    print("=" * 55)
    test_cases = [("eceba", 2), ("aa", 1), ("aabacbebebe", 3)]
    for s, k in test_cases:
        r = max_len_at_most_k_distinct(s, k)
        print(f"  s={s!r}, k={k} → {r}")

    #── Complexity Summary ──
    print()
    print("=" * 55)
    print("Sliding window complexity summary")
    print("=" * 55)
    print("Fixed window sum/average : O(n),  O(1)")
    print("Variable window sum       : O(n),  O(1)")
    print("Deque minimum             : O(n),  O(k)")
    print("Variable window hashmap: O(n), O(k)")


if __name__ == "__main__":
    main()

"""Unit 27 — Practical Pattern: Bitmask
Topic: Bitmask — Subset Enumeration, Visited State DP, TSP
Time: Subset Enumeration O(2ⁿ), TSP O(2ⁿ * n²)
Space: O(2ⁿ * n)

Description:
    1. Basics of bit operations (ON/OFF/CHECK/COUNT)
    2. Subset enumeration O(2ⁿ)
    3. Visited state DP — representing visited sets with bitmask
    4. TSP (Traveling Salesman Problem) bitmask DP"""

import sys

INF = sys.maxsize


# ──────────────────────────────────────────────
#1. Bit Operation Utility
# ──────────────────────────────────────────────

def bit_on(mask: int, i: int) -> int:
    """Set the i-th bit to 1. Time O(1)."""
    return mask | (1 << i)


def bit_off(mask: int, i: int) -> int:
    """Set the i-th bit to 0. Time O(1)."""
    return mask & ~(1 << i)


def bit_check(mask: int, i: int) -> bool:
    """Check if the i-th bit is 1. Time O(1)."""
    return bool(mask >> i & 1)


def bit_count(mask: int) -> int:
    """Number of 1 bits (popcount). Time O(1) (using built-in bin)."""
    return bin(mask).count("1")


def lowest_bit(mask: int) -> int:
    """Keep only the lowest 1 bit. Time O(1)."""
    return mask & (-mask)


# ──────────────────────────────────────────────
#2. Subset Enumeration
# ──────────────────────────────────────────────

def enumerate_subsets(items: list) -> list[list]:
    """Returns all subsets of items (including the empty set).

    Time: O(2ⁿ * n)
    Space: O(2ⁿ * n)"""
    n = len(items)
    result = []
    for mask in range(1 << n):
        subset = [items[i] for i in range(n) if bit_check(mask, i)]
        result.append(subset)
    return result


def enumerate_subsets_of_mask(mask: int) -> list[int]:
    """Enumerate all submasks of the given mask.
    (including empty one)

    Time: O(2^k)  k = popcount(mask)"""
    sub = mask
    result = []
    while sub:
        result.append(sub)
        sub = (sub - 1) & mask
    result.append(0)  #Empty Set
    return result


# ──────────────────────────────────────────────
#3. Visit State DP — Represent visited set with bitmask
# ──────────────────────────────────────────────

def min_cost_visit_all(
    dist: list[list[int]],
    start: int,
) -> int:
    """Minimum cost to visit all nodes exactly once and return to start.
    (small TSP)

    dp[mask][v] = minimum cost when visiting the set mask and currently at position v.

    Time: O(2ⁿ * n²)
    Space: O(2ⁿ * n)"""
    n = len(dist)
    full = (1 << n) - 1
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1 << start][start] = 0

    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            if not bit_check(mask, u):
                continue
            for v in range(n):
                if bit_check(mask, v):
                    continue   #Already visited
                if dist[u][v] == INF:
                    continue
                new_mask = bit_on(mask, v)
                cost = dp[mask][u] + dist[u][v]
                if cost < dp[new_mask][v]:
                    dp[new_mask][v] = cost

    #Return to start after visiting all nodes
    best = INF
    for v in range(n):
        if v == start:
            continue
        if dp[full][v] != INF and dist[v][start] != INF:
            best = min(best, dp[full][v] + dist[v][start])

    return best


def main() -> None:
    #── 1. Bit Operation Basics ──
    print("=" * 55)
    print("1. Bit Operation Basics")
    print("=" * 55)
    mask = 0b1010   #Turn on bits 1 and 3
    print(f"Initial mask: {bin(mask)} ({mask})")
    print(f"Turn on bit 0: {bin(bit_on(mask, 0))}")
    print(f"Turn off bit 1: {bin(bit_off(mask, 1))}")
    print(f"Check bit 3: {bit_check(mask, 3)}")
    print(f"Number of bits: {bit_count(mask)}")
    print(f"Lowest bit: {bin(lowest_bit(mask))}")

    #── 2. Subset Enumeration ──
    print()
    print("=" * 55)
    print("2. Subset Enumeration (n=3)")
    print("=" * 55)
    items = ["A", "B", "C"]
    subsets = enumerate_subsets(items)
    for i, s in enumerate(subsets):
        print(f"mask={bin(i):>5}: {s if s else 'Empty Set'}")

    print()
    print(f"Total {len(subsets)} (2^{len(items)})")

    #── 2b. Sub-masks of a specific mask ──
    print()
    print("=" * 55)
    print("2b. Enumerate sub-masks of mask=0b1011")
    print("=" * 55)
    m = 0b1011
    subs = enumerate_subsets_of_mask(m)
    print(f"mask={bin(m)}: number of sub-masks {len(subs)}")
    for s in subs:
        print(f"    {bin(s)}")

    #── 3. TSP (4 cities) ──
    print()
    print("=" * 55)
    print("3. TSP — Minimum tour cost for 4 cities (bitmask DP)")
    print("=" * 55)
    dist_matrix = [
        [0,   10,  15,  20],
        [10,  0,   35,  25],
        [15,  35,  0,   30],
        [20,  25,  30,  0 ],
    ]
    print("Distance matrix:")
    for i, row in enumerate(dist_matrix):
        print(f"    {row}")

    min_cost = min_cost_visit_all(dist_matrix, start=0)
    print(f"Minimum tour cost: {min_cost}")
    print("  (0→1→3→2→0: 10+25+30+15=80)")

    #── Complexity Summary ──
    print()
    print("=" * 55)
    print("Bitmask Complexity Summary")
    print("=" * 55)
    print("Bit operations      : O(1)")
    print("Subset enumeration : O(2ⁿ * n)")
    print("Submask enumeration : O(2^k), k=popcount")
    print("  TSP DP          : O(2ⁿ * n²)")
    for n_val in [10, 15, 20]:
        ops = (2 ** n_val) * n_val ** 2
        print(f"    n={n_val}: {ops:>12,}  "
              f"{'OK' if ops <= 1e8 else 'TLE risk'}")


if __name__ == "__main__":
    main()

"""Chapter 27 — Practical Patterns: Range Sum (Prefix Sum)
Topic: 1D and 2D Prefix Sum with O(1) Range Query
Time: O(n) preprocessing, O(1) query
Space: O(n) or O(nm)

Explanation:
    1. 1D range sum: prefix[i+1] = prefix[i] + arr[i]
       query(l, r) = prefix[r+1] - prefix[l]
    2. 2D range sum: inclusion-exclusion principle
       ps[i][j] = arr + ps_above + ps_left - ps_top_left_diagonal
       query(r1,c1,r2,c2) = ps[r2+1][c2+1] - ps[r1][c2+1]
                            - ps[r2+1][c1] + ps[r1][c1]
    3. Difference Array: O(1) batch update on a range"""


# ──────────────────────────────────────────────
#1. 1D Range Sum
# ──────────────────────────────────────────────

class PrefixSum1D:
    """1D array range sum query.

    Time: O(n) initialization, O(1) query
    Space: O(n)"""

    def __init__(self, arr: list[int]) -> None:
        n = len(arr)
        self.prefix = [0] * (n + 1)
        for i in range(n):
            self.prefix[i + 1] = self.prefix[i] + arr[i]

    def query(self, l: int, r: int) -> int:
        """Returns the sum of the [l, r] range (0-indexed, inclusive).

        Time: O(1)"""
        return self.prefix[r + 1] - self.prefix[l]

    def range_count_ge(self, l: int, r: int, threshold: int) -> int:
        """[l, r] Count of elements greater than or equal to threshold (sum-based application rather than cumulative frequency)."""
        #Example of simple sum application — in practice, sorting + binary search is needed
        raise NotImplementedError


# ──────────────────────────────────────────────
#2. 2D Range Sum
# ──────────────────────────────────────────────

class PrefixSum2D:
    """2D matrix rectangular range sum query.

    Time: O(nm) initialization, O(1) query
    Space: O(nm)"""

    def __init__(self, grid: list[list[int]]) -> None:
        n = len(grid)
        m = len(grid[0]) if n > 0 else 0
        self.n = n
        self.m = m
        #ps[i][j] = sum of rectangle from (0,0) to (i-1,j-1) (1-indexed)
        self.ps = [[0] * (m + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                self.ps[i][j] = (
                    grid[i - 1][j - 1]
                    + self.ps[i - 1][j]
                    + self.ps[i][j - 1]
                    - self.ps[i - 1][j - 1]
                )

    def query(self, r1: int, c1: int, r2: int, c2: int) -> int:
        """Sum of rectangular section from (r1,c1) to (r2,c2) (0-indexed, both ends included).

        Inclusion-Exclusion Principle:
            Total - remove top - remove left + restore diagonal

        Time: O(1)"""
        return (
            self.ps[r2 + 1][c2 + 1]
            - self.ps[r1][c2 + 1]
            - self.ps[r2 + 1][c1]
            + self.ps[r1][c1]
        )


# ──────────────────────────────────────────────
#3. Difference Array
# ──────────────────────────────────────────────

class DifferenceArray:
    """Batch section update O(1), final array reconstruction O(n).

    Use: When there are many updates adding val to [l, r] sections.

    Time: O(1) update, O(n) build
    Space: O(n)"""

    def __init__(self, n: int) -> None:
        self.diff = [0] * (n + 1)
        self.n = n

    def update(self, l: int, r: int, val: int) -> None:
        """Add val to [l, r] section (0-indexed). Time O(1)."""
        self.diff[l] += val
        if r + 1 <= self.n:
            self.diff[r + 1] -= val

    def build(self) -> list[int]:
        """Return final array. Time O(n)."""
        result = [0] * self.n
        cur = 0
        for i in range(self.n):
            cur += self.diff[i]
            result[i] = cur
        return result


def main() -> None:
    #── 1. 1D Range Sum ──
    print("=" * 55)
    print("1. 1D Range Sum")
    print("=" * 55)
    arr = [3, 1, 4, 1, 5, 9, 2, 6]
    ps1 = PrefixSum1D(arr)
    print(f"Array: {arr}")
    print(f"  prefix: {ps1.prefix}")
    queries = [(0, 3), (2, 5), (0, 7), (3, 3)]
    for l, r in queries:
        ans = ps1.query(l, r)
        brute = sum(arr[l:r+1])
        print(f"query({l},{r}) = {ans}  (direct sum: {brute})")

    #── 2. 2D Range Sum ──
    print()
    print("=" * 55)
    print("2. 2D Range Sum")
    print("=" * 55)
    grid = [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12],
    ]
    ps2 = PrefixSum2D(grid)
    print("Matrix:")
    for row in grid:
        print(f"    {row}")
    print()

    q2d = [
        (0, 0, 1, 1),   # 1+2+5+6=14
        (1, 1, 2, 2),   # 6+7+10+11=34
        (0, 0, 2, 3),   #Total sum = 78
    ]
    for r1, c1, r2, c2 in q2d:
        ans = ps2.query(r1, c1, r2, c2)
        brute = sum(grid[r][c] for r in range(r1, r2+1)
                    for c in range(c1, c2+1))
        print(f"query({r1},{c1},{r2},{c2}) = {ans}  (direct: {brute})")

    #── 3. Difference Array ──
    print()
    print("=" * 55)
    print("3. Difference Array — Range Update")
    print("=" * 55)
    n = 8
    da = DifferenceArray(n)
    updates = [(1, 3, 10), (2, 5, 20), (4, 7, -5)]
    print("Initial: [0] * 8")
    for l, r, v in updates:
        da.update(l, r, v)
        print(f"  update({l},{r},{v:+})")
    result = da.build()
    print(f"Final: {result}")
    print("Direct check:")
    manual = [0] * n
    for l, r, v in updates:
        for i in range(l, r + 1):
            manual[i] += v
    print(f"Expected value: {manual}")
    print(f"Match: {result == manual}")

    #── Complexity Summary ──
    print()
    print("=" * 55)
    print("Summary of Range Sum Complexity")
    print("=" * 55)
    print("1D Preprocessing: O(n),   Query: O(1)")
    print("2D Preprocessing: O(nm),  Query: O(1)")
    print("Difference Array: O(1) update, O(n) reconstruction")
    print("Segment Tree: O(n) preprocessing, O(log n) update+query")


if __name__ == "__main__":
    main()