27. Applied Patterns

What you'll learn

• 1Use two pointers on sorted arrays
• 2Use sliding window on subarrays/substrings
• 3Use bitmask for subset enumeration and DP
• 4Use prefix sum for O(1) range queries

Overview

These four idioms come up over and over. Knowing them lets you skip the O(n²) phase entirely and jump straight to the optimal solution.

Core Concepts

1. Two pointers

# Find pair with target sum in a SORTED array — O(n)
def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target: return (lo, hi)
        elif s < target: lo += 1
        else: hi -= 1
    return None

Use cases: sorted arrays, palindrome check, merging, partitioning.

2. Sliding window

# Longest substring with at most K distinct characters — O(n)
from collections import Counter
def longest_at_most_k(s, k):
    count = Counter()
    left = 0
    best = 0
    for right, c in enumerate(s):
        count[c] += 1
        while len(count) > k:
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

Two flavors: fixed-size window (e.g. max sum of K consecutive) and variable-size (until condition violated).

3. Bitmask

# Enumerate all subsets of [0, n) — O(2^n)
for mask in range(1 << n):
    subset = [i for i in range(n) if mask & (1 << i)]
    process(subset)

# Common bit operations
mask | (1 << i)        # turn on bit i
mask & ~(1 << i)       # turn off bit i
mask ^ (1 << i)        # flip bit i
(mask >> i) & 1        # read bit i
bin(mask).count('1')   # popcount

Bitmask DP: dp[mask] = best answer when the visited set is `mask`. Used for TSP and many small-N graph problems.

4. Prefix sum

# 1D — O(1) range sum after O(n) preprocessing
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i+1] = prefix[i] + a[i]

# Sum of a[l..r] inclusive
range_sum = prefix[r+1] - prefix[l]

# 2D — O(1) submatrix sum after O(n*m) preprocessing
prefix = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(m):
        prefix[i+1][j+1] = grid[i][j] + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]

# Sum of submatrix (r1..r2, c1..c2) inclusive
result = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]

When to Use Each

Examples

Example 1 — src/01_two_pointers.py

Two-sum on sorted array + 'subarray sum = K'.

Example 2 — src/02_sliding_window.py

Maximum sum of K consecutive elements + longest substring without repeating.

Example 3 — src/03_bitmask.py

Subset sum enumeration + bitmask DP for TSP (BOJ 2098).

Example 4 — src/04_prefix_sum.py

1D and 2D prefix sums for fast range queries.

Common Mistakes

1. Two-pointer on unsorted array — sort first or use a hash.
2. Sliding window where the constraint isn't monotonic — won't work cleanly.
3. Bitmask on N > 22 — 2²² = 4M subsets, getting slow.
4. Off-by-one in prefix sum: range_sum = prefix[r+1] - prefix[l] (note +1 and l, not l+1).

Recap

• Two pointers: sorted arrays, O(n).
• Sliding window: subarrays with monotonic invariant.
• Bitmask: small-N subset / state DP.
• Prefix sum: O(1) range queries after O(n) preprocessing.

Try It

1. BOJ 2003 (Subarray sum 2) — two pointers.
2. BOJ 11003 (Find minimum) — sliding-window deque.
3. BOJ 2098 (TSP) — bitmask DP.
4. BOJ 11659 (Range sum query 4) — 1D prefix sum.