2. Arrays & Strings

Key Insight

Most array problems reduce to one of four patterns: two pointers, sliding window, prefix sums, or in-place manipulation. Recognising the pattern immediately constrains your approach to $O(n)$ or $O(n \log n)$.

Complexity Reference

Operation	Array (list)	Notes
Access by index	$O(1)$
Append	$O(1)$ amortized
Insert/delete at index	$O(n)$
Search (unsorted)	$O(n)$
Slice a[i:j]	$O(j-i)$	Creates a new list

---

2.1 Two Pointers

Use when: sorted array, pair/triplet sum, removing duplicates, palindrome check.

# --- Pair with target sum (sorted array) ---
def two_sum_sorted(arr: list[int], target: int) -> tuple[int, int]:
    l, r = 0, len(arr) - 1
    while l < r:
        s = arr[l] + arr[r]
        if s == target:
            return l, r
        elif s < target:
            l += 1
        else:
            r -= 1
    return -1, -1

# --- Remove duplicates in-place (sorted) ---
def remove_duplicates(arr: list[int]) -> int:
    if not arr:
        return 0
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1  # new length

# --- Three Sum (all unique triplets summing to 0) ---
def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue  # skip duplicate pivot
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == 0:
                res.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l+1]: l += 1
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
            elif s < 0:
                l += 1
            else:
                r -= 1
    return res

---

2.2 Sliding Window

Fixed window: size $k$ is known. Variable window: expand right, shrink left when constraint is violated.

# --- Fixed window: max sum of subarray of size k ---
def max_sum_k(arr: list[int], k: int) -> int:
    window = sum(arr[:k])
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]
        best = max(best, window)
    return best

# --- Variable window: longest subarray with at most k distinct values ---
from collections import defaultdict

def longest_k_distinct(s: str, k: int) -> int:
    freq: dict[str, int] = defaultdict(int)
    l = best = 0
    for r, c in enumerate(s):
        freq[c] += 1
        while len(freq) > k:          # shrink until valid
            freq[s[l]] -= 1
            if freq[s[l]] == 0:
                del freq[s[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

# --- Minimum window substring (contains all chars of t) ---
def min_window(s: str, t: str) -> str:
    need = defaultdict(int)
    for c in t:
        need[c] += 1
    have, required = 0, len(need)
    window: dict[str, int] = defaultdict(int)
    res, res_len = [-1, -1], float("inf")
    l = 0
    for r, c in enumerate(s):
        window[c] += 1
        if c in need and window[c] == need[c]:
            have += 1
        while have == required:
            if (r - l + 1) < res_len:
                res, res_len = [l, r], r - l + 1
            window[s[l]] -= 1
            if s[l] in need and window[s[l]] < need[s[l]]:
                have -= 1
            l += 1
    return s[res[0]:res[1]+1] if res_len != float("inf") else ""

---

2.3 Prefix Sums

Key insight: prefix[i] = prefix[i-1] + arr[i-1]. Range sum [l, r] = prefix[r+1] - prefix[l] in $O(1)$ after $O(n)$ build.

# --- 1D prefix sum ---
def build_prefix(arr: list[int]) -> list[int]:
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + arr[i]
    return prefix

def range_sum(prefix: list[int], l: int, r: int) -> int:
    return prefix[r+1] - prefix[l]  # sum of arr[l..r] inclusive

# --- 2D prefix sum ---
def build_prefix_2d(grid: list[list[int]]) -> list[list[int]]:
    m, n = len(grid), len(grid[0])
    p = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            p[i][j] = grid[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1]
    return p

def query_2d(p, r1, c1, r2, c2) -> int:
    # sum of submatrix (r1,c1) to (r2,c2) inclusive, 0-indexed original grid
    return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]

# --- Subarray sum equals k (count) ---
def subarray_sum_k(nums: list[int], k: int) -> int:
    count = prefix = 0
    seen = defaultdict(int)
    seen[0] = 1
    for x in nums:
        prefix += x
        count += seen[prefix - k]
        seen[prefix] += 1
    return count

---

2.4 Kadane's Algorithm (Maximum Subarray)

def max_subarray(nums: list[int]) -> int:
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

# Variant: return the actual subarray indices
def max_subarray_indices(nums: list[int]) -> tuple[int, int]:
    best = cur = nums[0]
    start = end = best_start = 0
    for i in range(1, len(nums)):
        if nums[i] > cur + nums[i]:
            cur = nums[i]
            start = i
        else:
            cur += nums[i]
        if cur > best:
            best = cur
            best_start = start
            end = i
    return best_start, end

---

2.5 Key CP Patterns

Pattern	Trigger phrase	Template
Two pointers	sorted, pair/triplet sum	l, r = 0, n-1
Sliding window	subarray/substring with constraint	expand r, shrink l
Prefix sum	range query on static array	prefix[r+1] - prefix[l]
Kadane's	max subarray sum	cur = max(x, cur+x)
Dutch flag	3-way partition	3 pointers lo, mid, hi

---