The Concept
The concept
Why Patterns, Not Problems
The human brain can't memorize 2,000 solutions. But it can memorize 4-5 patterns and learn to recognize which one applies. This is how strong competitive programmers and interviewers think — they don't recall a specific problem, they identify the structural property of the input and map it to a technique.
For arrays and strings, the key structural properties are:
- Is the data sorted? → Two pointers can exploit ordering to eliminate brute-force pairs
- Is there a contiguous sub-range with a constraint? → Sliding window maintains a valid window while expanding/contracting
- Are there repeated range-sum queries? → Prefix sums precompute cumulative sums for O(1) range queries
- Are you looking up complements or frequencies? → Hash maps trade space for O(1) lookups
Every array/string interview problem you encounter will be a combination of these. The skill is not knowing 200 problems — it's recognizing which pattern matches the problem in front of you within 30 seconds of reading it.
The patterns
1. Two Pointers — O(n), O(1)
Use when: sorted array or string, finding pairs, or collapsing a brute-force O(n²) loop.
You're given a sorted array and need to find if any two numbers sum to a target. The brute-force is O(n²) with nested loops. How do you optimize to O(n)?
Two pointers exploits the sorted property. Start with lo=0, hi=n-1. If arr[lo]+arr[hi] < target, increasing lo increases the sum. If > target, decreasing hi decreases it. Each step eliminates one element, so it's O(n) with O(1) space — better than the hash map approach which needs O(n) space.
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
return [lo, hi]
elif s < target:
lo += 1
else:
hi -= 1
return []
# Interview signal: "I'm using two pointers because the array is sorted,
# so I can eliminate halves with each step — O(n) time, O(1) space."
Variant: fast/slow pointers — detecting a cycle in a linked list, finding the middle.
2. Sliding Window — O(n), O(k)
Use when: "longest/shortest subarray/substring satisfying a condition."
def max_sum_subarray_k(nums: list[int], k: int) -> int:
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # slide: add right, drop left
best = max(best, window)
return best
# Variable window (expand right / shrink left until valid):
def longest_no_repeat(s: str) -> int:
seen: dict[str, int] = {}
best = lo = 0
for hi, c in enumerate(s):
if c in seen and seen[c] >= lo:
lo = seen[c] + 1 # shrink: move left past the repeat
seen[c] = hi
best = max(best, hi - lo + 1)
return best
The key move: expand the right edge freely; shrink the left only when the window breaks the constraint.
3. Prefix Sums — O(n) preprocessing, O(1) range queries
Use when: "sum of elements from i to j" asked many times, or "subarray with sum = k."
def subarray_sum_equals_k(nums: list[int], k: int) -> int:
count = 0
prefix = 0
seen = {0: 1} # empty prefix has sum 0
for n in nums:
prefix += n
count += seen.get(prefix - k, 0) # seen[prefix - k] means we found a subarray
seen[prefix] = seen.get(prefix, 0) + 1
return count
# O(n) time, O(n) space — the hash map is the secret ingredient
4. Hash Map — O(n), O(n)
Use when: "check existence / count / group by value" without sorting.
def two_sum(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {}
for i, n in enumerate(nums):
comp = target - n
if comp in seen:
return [seen[comp], i]
seen[n] = i
return []
# "I store each number as I go; for each new number I ask 'is its complement
# already in the map?' — one pass, O(n)."
Interview discipline
Before coding, say the pattern aloud:
"This is a sliding-window problem — fixed window size, I'll slide and update in O(n)."
"I'll use a hash map to trade O(n) space for O(n) time instead of a nested loop."
Then: write a two-line example, code it, state the complexity. Interviewers grade the process, not just the answer.
Try the variable sliding-window pattern yourself — tweak the input string and watch how the window expands and shrinks:
def longest_no_repeat(s: str) -> tuple[int, str]:
"""Longest substring without repeating characters. Returns (length, substring)."""
seen: dict[str, int] = {}
best_len = lo = 0
best_start = 0
for hi, c in enumerate(s):
if c in seen and seen[c] >= lo:
lo = seen[c] + 1 # shrink: move left past the repeat
seen[c] = hi
if hi - lo + 1 > best_len:
best_len = hi - lo + 1
best_start = lo
return best_len, s[best_start:best_start + best_len]
# Try it: change the string and see the window pattern react
for text in ["abcabcbb", "bbbbb", "pwwkew", "dvdf"]:
length, window = longest_no_repeat(text)
print(f"{text!r:12} -> longest={length}, substring={window!r}")
Worked Example: 3Sum (Medium)
"Find all unique triplets in an array that sum to 0."
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort() # O(n log n) — sorting enables two pointers
result = []
for i in range(len(nums) - 2):
# Skip duplicates: if nums[i] == nums[i-1], we already found all
# triplets starting with this value
if i > 0 and nums[i] == nums[i - 1]:
continue
# Two pointers for the remaining two elements
lo, hi = i + 1, len(nums) - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total == 0:
result.append([nums[i], nums[lo], nums[hi]])
# Skip inner duplicates too
while lo < hi and nums[lo] == nums[lo + 1]: lo += 1
while lo < hi and nums[hi] == nums[hi - 1]: hi -= 1
lo += 1
hi -= 1
elif total < 0:
lo += 1
else:
hi -= 1
return result
# Pattern: sort + two pointers (not hash map — hash map can't deduplicate easily)
# Time: O(n²) — outer loop O(n) × inner two pointers O(n)
# Space: O(1) excluding output
Why is two pointers better than a hash set for 3Sum?
With a hash set, you'd need to store pairs and deduplicate triplets afterward — messy and error-prone. Two pointers on a sorted array naturally skips duplicates by advancing past equal values. The sort is O(n log n) but the two-pointer scan is O(n) per outer iteration, giving O(n²) total — same as the hash set approach but cleaner code and O(1) extra space.
Pattern Selection Guide
Problem says... → Use this pattern
"pair that sums to target" (sorted) → Two pointers
"pair that sums to target" (unsorted) → Hash map
"longest/shortest substring with X" → Sliding window (variable)
"max sum of subarray of size k" → Sliding window (fixed)
"subarray sum equals k" → Prefix sum + hash map
"count of pairs/groups with property" → Hash map (frequency)
"three elements with property" → Sort + two pointers (extend pair)
"rotate/shift array" → Reverse trick (in-place)
"merge two sorted arrays" → Two pointers
"find duplicate in array" → Fast/slow pointers or hash set
Complexity Comparison
Pattern Time Space When to prefer
──────────────────────────────────────────────────────────
Two pointers O(n) O(1) Sorted input, pair finding
Sliding window O(n) O(k) Subarray/substring constraints
Prefix sum O(n) prep O(n) Repeated range queries
Hash map O(n) O(n) Unsorted, existence checks, counting
Sort + TP O(n log n) O(1) 3Sum, closest pair, unsorted + dedup