Contents
How to Analyze Arrays & Strings
Use this checklist before coding:
- What kind of interval logic?
- contiguous segment -> sliding window / prefix sum
- pair/triple relation -> two pointers / sort + scan
- Is there monotonic feasibility?
- if answer can be binary-searched (min/max feasible value), use binary search on answer
- Need exact substring matching?
- many text-pattern checks -> KMP / Z / rolling hash
- Target complexity
- most interview-quality solutions should land in
O(n) or O(n log n)
Sliding Window (fixed/variable)
def longest_no_repeat(s: str) -> int:
cnt = [0] * 256
best = 0
l = 0
for r, ch in enumerate(s):
idx = ord(ch)
cnt[idx] += 1
while cnt[idx] > 1:
cnt[ord(s[l])] -= 1
l += 1
best = max(best, r - l + 1)
return best
Two Pointers (sorted arrays/strings)
def two_sum_sorted(a: list[int], target: int) -> bool:
l, r = 0, len(a) - 1
while l < r:
s = a[l] + a[r]
if s == target:
return True
if s < target:
l += 1
else:
r -= 1
return False
Binary Search on Answer (monotonic predicate)
def first_good(lo: int, hi: int, good) -> int:
# Finds smallest x in [lo, hi] with good(x) == True.
while lo < hi:
mid = (lo + hi) // 2
if good(mid):
hi = mid
else:
lo = mid + 1
return lo
Prefix Sum / Difference Array
def prefix_sum(nums: list[int]) -> list[int]:
ps = [0] * (len(nums) + 1)
for i, x in enumerate(nums):
ps[i + 1] = ps[i] + x
return ps
def range_sum(ps: list[int], l: int, r: int) -> int:
# inclusive range [l, r]
return ps[r + 1] - ps[l]
Hash Map Frequencies
from collections import Counter
def freq_map(nums: list[int]) -> dict[int, int]:
return dict(Counter(nums))
def freq_map_manual(nums: list[int]) -> dict[int, int]:
freq = {}
for x in nums:
freq[x] = freq.get(x, 0) + 1
return freq
KMP (Substring Search)
def kmp_pi(s: str) -> list[int]:
n = len(s)
pi = [0] * n
for i in range(1, n):
j = pi[i - 1]
while j > 0 and s[i] != s[j]:
j = pi[j - 1]
if s[i] == s[j]:
j += 1
pi[i] = j
return pi
def kmp_find_all(text: str, pattern: str) -> list[int]:
if not pattern:
return list(range(len(text) + 1))
pi = kmp_pi(pattern)
out = []
j = 0
for i, ch in enumerate(text):
while j > 0 and ch != pattern[j]:
j = pi[j - 1]
if ch == pattern[j]:
j += 1
if j == len(pattern):
out.append(i - len(pattern) + 1)
j = pi[j - 1]
return out
Manacher (Longest Palindromic Substring, O(n))
def manacher(s: str) -> str:
if not s:
return ""
t = "|" + "|".join(s) + "|"
n = len(t)
p = [0] * n
center = right = 0
best_len = best_center = 0
for i in range(n):
mirror = 2 * center - i
if i < right:
p[i] = min(right - i, p[mirror])
while (
i - 1 - p[i] >= 0
and i + 1 + p[i] < n
and t[i - 1 - p[i]] == t[i + 1 + p[i]]
):
p[i] += 1
if i + p[i] > right:
center, right = i, i + p[i]
if p[i] > best_len:
best_len, best_center = p[i], i
start = (best_center - best_len) // 2
return s[start : start + best_len]
Z-Algorithm (Pattern occurrences)
def z_func(s: str) -> list[int]:
n = len(s)
if n == 0:
return []
z = [0] * n
l = r = 0
for i in range(1, n):
if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l = i
r = i + z[i] - 1
return z
String Rolling Hash (Rabin-Karp)
class RH:
B = 911382323
M = 1_000_000_007
def __init__(self, s: str):
n = len(s)
self.p = [1] * (n + 1)
self.h = [0] * (n + 1)
for i, ch in enumerate(s):
self.p[i + 1] = (self.p[i] * self.B) % self.M
self.h[i + 1] = (self.h[i] * self.B + ord(ch)) % self.M
def get(self, l: int, r: int) -> int:
# substring hash for s[l:r]
return (self.h[r] - self.h[l] * self.p[r - l]) % self.M