S023 · Arrays & Strings — Indexing, Slicing, Two-Pointer

"""arrays_strings.py — the two-pointer + sliding-window canon.
 
Run:  python arrays_strings.py
"""
from __future__ import annotations
 
 
# ------------------------------------------------------------------
# 1) Reverse in place — the classic opposite-ends two-pointer
# ------------------------------------------------------------------
def reverse_in_place(a: list) -> list:
    """Reverse the list in-place, O(n) time, O(1) extra memory."""
    left, right = 0, len(a) - 1
    while left < right:
        a[left], a[right] = a[right], a[left]
        left += 1
        right -= 1
    return a
 
 
# ------------------------------------------------------------------
# 2) Two-sum on a sorted array — opposite-ends with a condition
# ------------------------------------------------------------------
def two_sum_sorted(a: list[int], target: int) -> tuple[int, int] | None:
    """Return (i, j) with i<j and a[i]+a[j]==target, else None. O(n)."""
    left, right = 0, len(a) - 1
    while left < right:
        s = a[left] + a[right]
        if s == target:
            return left, right
        if s < target:
            left += 1        # need a bigger sum → move left up
        else:
            right -= 1       # need a smaller sum → move right down
    return None
 
 
# ------------------------------------------------------------------
# 3) Remove duplicates from a sorted array — same-start two-pointer
# ------------------------------------------------------------------
def remove_duplicates(a: list[int]) -> int:
    """Compact the list in place so the first k elements are unique. Return k. O(n)."""
    if not a:
        return 0
    slow = 0
    for fast in range(1, len(a)):
        if a[fast] != a[slow]:
            slow += 1
            a[slow] = a[fast]
    return slow + 1
 
 
# ------------------------------------------------------------------
# 4) Valid palindrome (ignoring non-alphanumerics + case)
# ------------------------------------------------------------------
def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True
 
 
# ------------------------------------------------------------------
# 5) Longest substring without repeating characters — sliding window
# ------------------------------------------------------------------
def longest_unique_substring(s: str) -> int:
    """Return length of the longest substring with all distinct chars. O(n)."""
    seen: dict[str, int] = {}   # char -> most recent index
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1     # jump left past the previous occurrence
        seen[ch] = right
        best = max(best, right - left + 1)
    return best
 
 
# ------------------------------------------------------------------
# 6) Minimum-size subarray with sum >= target — classic sliding window
# ------------------------------------------------------------------
def min_subarray_len(target: int, nums: list[int]) -> int:
    left = 0
    total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
 
 
# ------------------------------------------------------------------
# 7) Anti-pattern demo — string concat in a loop is O(n²)
# ------------------------------------------------------------------
def slow_join(pieces: list[str]) -> str:
    out = ""
    for p in pieces:
        out += p              # each concat copies the whole prefix — O(n²) total
    return out
 
 
def fast_join(pieces: list[str]) -> str:
    return "".join(pieces)    # O(n) — builds once with the exact final length
 
 
# ------------------------------------------------------------------
# Runner
# ------------------------------------------------------------------
if __name__ == "__main__":
    print("reverse:", reverse_in_place([1, 2, 3, 4, 5]))
    print("two_sum_sorted:", two_sum_sorted([1, 3, 4, 7, 11, 15], 18))
    a = [1, 1, 2, 2, 3, 4, 4, 5]
    k = remove_duplicates(a)
    print(f"remove_duplicates: k={k}  compacted={a[:k]}")
    print("palindrome 'A man, a plan, a canal: Panama':", is_palindrome("A man, a plan, a canal: Panama"))
    print("longest_unique 'abcabcbb':", longest_unique_substring("abcabcbb"))
    print("min_subarray_len target=7 nums=[2,3,1,2,4,3]:", min_subarray_len(7, [2, 3, 1, 2, 4, 3]))
 
    # Prove the concat anti-pattern
    import time
    pieces = ["x"] * 200_000
    t = time.perf_counter(); slow_join(pieces);  print(f"slow_join  200k: {time.perf_counter()-t:.3f}s")
    t = time.perf_counter(); fast_join(pieces);  print(f"fast_join  200k: {time.perf_counter()-t:.3f}s")