Algorithm Templates

Every phase so far built these algorithms up from first principles. This page strips the explanation back down to the part you actually reuse under contest time pressure: a correct, self-contained template for each one, ready to paste and adapt. Every block below runs standalone — no external input required — so you can drop it straight into this page’s editor and see it work before you ever paste it into a real submission.

What you’ll learn

The exact-match, lower_bound/upper_bound, and binary-search-on-the- answer templates side by side.
The Sieve of Eratosthenes, ready to cap at any limit.
Fast modular exponentiation and the Fermat modular inverse that rides on top of it.
gcd/lcm, plus the stdlib versions that replace them in real code.
KMP’s failure function and search, and the Z-algorithm — both linear- time pattern-matching templates.
A fast-I/O boilerplate built on io.StringIO, so the same skeleton works in the browser here and on a real judge’s stdin.

Binary search: exact match

Search a sorted array for an exact value. Inclusive bounds, while lo <= hi, the loop ends the moment the space is empty.

binary_search_exact.py

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2   # overflow-free habit
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
 
 
arr = [1, 3, 4, 7, 9, 11, 13, 18, 21, 25]
print(binary_search(arr, 13))   # expect 6
print(binary_search(arr, 6))    # expect -1

`lower_bound` and `upper_bound`

Boundary-finding template: exclusive hi, while lo < hi. lower_bound finds the first index with arr[i] >= target; upper_bound finds the first index with arr[i] > target. In production code, reach for bisect.bisect_left / bisect.bisect_right instead of hand-rolling these — they’re the same algorithm, already written in C.

lower_upper_bound.py

def lower_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
 
def upper_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
 
import bisect
 
arr = [1, 3, 3, 3, 5, 7, 9]
print("lower_bound(3):", lower_bound(arr, 3), "| bisect_left:", bisect.bisect_left(arr, 3))
print("upper_bound(3):", upper_bound(arr, 3), "| bisect_right:", bisect.bisect_right(arr, 3))

Binary search on the answer

A generic feasibility-check template: search a range of candidate answers instead of an array. Pass any monotonic feasible(x) predicate (False, False, ..., False, True, ..., True) and get back the smallest x for which it holds.

binary_search_on_answer.py

def binary_search_on_answer(lo, hi, feasible):
    """Smallest x in [lo, hi] with feasible(x) True.
    Requires feasible to be monotonic over the range."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid           # mid works -- try to go smaller
        else:
            lo = mid + 1        # mid doesn't work -- need bigger
    return lo
 
 
# Demo: smallest x such that x * x >= 50
answer = binary_search_on_answer(0, 50, lambda x: x * x >= 50)
print("smallest x with x*x >= 50:", answer)   # expect 8

Sieve of Eratosthenes

Every prime up to limit, found by crossing off multiples starting at each prime’s square (smaller multiples are already crossed off by a smaller prime).

sieve.py

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime[i]:
            for multiple in range(i * i, limit + 1, i):
                is_prime[multiple] = False
    return [i for i, prime in enumerate(is_prime) if prime]
 
 
primes = sieve_of_eratosthenes(50)
print("primes up to 50:", primes)
print("count:", len(primes))

Fast modular exponentiation and modular inverse

Binary exponentiation computes a**b % m in $O(\log b)$ ; Fermat’s little theorem turns the same routine into a modular inverse for prime m. Python’s built-in pow(a, b, m) already does the exponentiation in C — use it directly in real solutions, and reach for power_mod only to understand the mechanism.

mod_pow_and_inverse.py

MOD = 1_000_000_007
 
 
def power_mod(base, exp, mod=MOD):
    result = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp >>= 1
    return result
 
 
def mod_inverse(a, mod=MOD):
    return power_mod(a, mod - 2, mod)   # valid ONLY when mod is prime
 
 
print("3^13 mod 7:", power_mod(3, 13, 7), "| pow() built-in:", pow(3, 13, 7))
 
inv = mod_inverse(123456)
print("check: a * inv mod p == 1 ->", (123456 * inv) % MOD == 1)

GCD and LCM

Euclid’s algorithm shrinks (a, b) to their GCD in $O(\log(\min(a, b)))$ . In real code, use math.gcd / math.lcm instead of hand-rolling these — shown side by side below to confirm they match.

gcd_lcm.py

import math
 
 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
 
def lcm(a, b):
    return a * b // gcd(a, b)
 
 
print("gcd(48, 18):", gcd(48, 18), "| math.gcd:", math.gcd(48, 18))
print("lcm(4, 6):", lcm(4, 6), "| math.lcm:", math.lcm(4, 6))

KMP: prefix function and search

The failure function (fail[i]) is the longest proper prefix of pattern[0..i] that’s also a suffix of it — exactly how far to fall back on a mismatch, so the text pointer never moves backward. $O(n + m)$ .

kmp_template.py

def build_failure(pattern):
    m = len(pattern)
    fail = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = fail[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        fail[i] = k
    return fail
 
 
def kmp_search(text, pattern):
    if not pattern:
        return []
    fail = build_failure(pattern)
    matches = []
    k = 0
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = fail[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            matches.append(i - k + 1)
            k = fail[k - 1]
    return matches
 
 
text = "ababcababcabc"
print("failure function:", build_failure("ababc"))
print("matches of 'abc':", kmp_search(text, "abc"))

Z-algorithm

z[i] is the length of the longest substring starting at i that matches a prefix of the string. Glue pattern + "#" + text and look for z[i] == len(pattern) to turn the Z-array into a pattern search. Also $O(n + m)$ .

z_algorithm_template.py

def z_array(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    l, r = 0, 0
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z
 
 
def z_search(text, pattern):
    combined = pattern + "#" + text
    z = z_array(combined)
    m = len(pattern)
    return [i - m - 1 for i in range(m + 1, len(combined)) if z[i] == m]
 
 
print("Z-array of 'aabxaab':", z_array("aabxaab"))
print("matches of 'ab':", z_search("abcabcabab", "ab"))

Fast I/O boilerplate

The skeleton to paste at the top of almost any real judge solution. io.StringIO fakes stdin here so the template runs standalone in the browser; on a real judge you’d delete that one line and let the judge’s actual stdin feed sys.stdin.

fast_io_template.py

import sys
import io
 
# --- fake stdin so this demo runs standalone; delete this line on a real judge ---
sys.stdin = io.StringIO("5\n4 2 9 1 7\n")
 
 
def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    n = int(next(it))
    arr = [int(next(it)) for _ in range(n)]
 
    out = []
    out.append(str(sum(arr)))
    out.append(str(max(arr)))
    sys.stdout.write("\n".join(out) + "\n")
 
 
main()

Complexity

Every template on this page, with the bound worth quoting and the one input that makes it degrade:

Template	Time	Space	Degrades when
Binary search (exact)	$O(\log n)$	$O(1)$	the array is not sorted — silently wrong, not slow
`lower_bound` / `upper_bound`	$O(\log n)$	$O(1)$	—
Binary search on the answer	$O(n \log R)$	$O(1)$	the predicate is not monotone; $R$ is the value range, not `n`
Sieve of Eratosthenes	$O(n \log\log n)$	$O(n)$	`n` beyond ~ $10^7$ — memory, not time
Modular exponentiation	$O(\log b)$	$O(1)$	—
Modular inverse (Fermat)	$O(\log p)$	$O(1)$	the modulus is not prime — wrong answer, no error
GCD (Euclid)	$O(\log \min(a,b))$	$O(1)$	—
KMP prefix + search	$O(n + m)$	$O(m)$	—
Z-algorithm	$O(n)$	$O(n)$	—
Fast I/O	$O(1)$ per token	$O(\text{input})$ if read all at once	—

Two things worth reading off that table:

Only two entries can be wrong rather than slow — binary search on unsorted input, and Fermat’s inverse with a composite modulus. Both fail silently, which makes them worth more attention than the ones that merely time out.
“Binary search on the answer” has $R$ in its bound, not $n$ . $\log R$ where $R$ is the numeric range of the answer — so a range up to $10^{18}$ is 60 iterations, and the n factor comes from the feasibility check inside each one. Quoting it as $O(\log n)$ is the usual slip.

Pitfalls

Copying a binary search without checking the invariant. lo <= hi with hi = mid - 1 finds an exact match; lo < hi with hi = mid finds a boundary. Mixing the two halves gives an off-by-one or an infinite loop, and the templates here are deliberately written as two separate functions for that reason.
Using lower_bound when you meant upper_bound. They differ only in < versus <=, and both return a plausible index. Decide from the question — “first element ≥ x” versus “first element > x” — not from which one you remember.
Fermat’s inverse on a composite modulus. pow(a, m - 2, m) is an inverse only when m is prime. Otherwise it returns a number with no error and everything downstream is wrong.
Sieving to answer one primality question. $O(n \log\log n)$ setup for a question trial division answers in $O(\sqrt n)$ .
sys.stdin.readline keeping the trailing newline. int() tolerates it, .strip() is needed for strings, and comparing an unstripped line to a literal fails for no visible reason.
Non-monotone predicates in binary search on the answer. The check must be “false … false true … true” over the whole range. If a mid value can be feasible while a larger one is not, the search is meaningless — verify monotonicity before writing it.
Off-by-one in the KMP prefix function. pi[0] is always 0 and the loop starts at i = 1; starting at 0 compares the string with itself and reports a full-length border.
Reaching for a template before reading the constraints. These are tools, not answers — the Master Complexity Cheatsheet is what tells you which one the input size permits.

Interview follow-ups

They ask	What they’re checking	The answer
“Write binary search”	Whether you know which one they mean	Ask: exact match, or first/last position satisfying a predicate? They are different templates — `lo <= hi` with `hi = mid - 1` for the former, `lo < hi` with `hi = mid` for the latter
“Why `lo + (hi - lo) // 2` rather than `(lo + hi) // 2`?”	Language awareness	In C++/Java the sum can overflow a 32-bit int; in Python it cannot. Knowing it is a portability habit rather than a Python necessity is the better answer
“How do you know binary search on the answer applies?”	The precondition	The feasibility predicate must be monotone in the answer: once true, true for everything larger. State that check explicitly before writing the loop
“Primes up to $10^6$ , then primes up to $10^{12}$ ”	Matching the tool to the size	Sieve for $10^6$ . At $10^{12}$ the array cannot be allocated — trial division to $\sqrt n$ per query, or Miller–Rabin
“Why is KMP $O(n + m)$ and not $O(nm)$ ?”	The amortised argument	Because the text pointer never moves backwards and each mismatch strictly decreases the border length, so the total fallback work is bounded by the total growth
“What is the modulus $10^9+7$ for?”	Understanding the constraint	It is prime (so Fermat’s inverse works) and small enough that the product of two residues fits in 64 bits. It exists because the true answer is too large to represent
“Which of these would you memorise?”	Judgement	Binary search’s two forms and modular exponentiation, because they appear constantly and are easy to get subtly wrong. KMP and Z are worth being able to derive rather than recall
“Your template has a bug at `n = 1`”	Edge-case discipline	Walk the smallest inputs before submitting: empty, single element, all-equal, target absent, target at both ends. Most template bugs are boundary bugs

Practice

Drill 1 — binary search on the answer. Complete the branch that keeps searching for a smaller feasible value.

Drill 2 — KMP’s failure fallback. Complete the backtrack that reuses the best-known shorter prefix length on a mismatch.

Drill 3 — fast token read. Complete the one-call read that grabs the entire input as whitespace-separated tokens.

LeetCode problem set

Every problem below is solvable with one of the templates on this page — binary search and its bounds, the sieve, modular exponentiation, or KMP. Use it as a drill: read the problem, name the template, then check.

20 problems

4 easy12 medium4 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

Unsolved onlyImport

28Find the Index of the First Occurrence in a StringeasyLeetCode Top Interview 150
35Search Insert PositioneasyLeetCode Top Interview 150
69Sqrt(x)easyLeetCode Top Interview 150
704Binary SearcheasyNeetCode 150
33Search in Rotated Sorted ArraymediumNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftbloomberg
875Koko Eating BananasmediumNeetCode 150googleamazonbytedance
34Find First and Last Position of Element in Sorted ArraymediumLeetCode Top Interview 150
204Count Primesmedium
264Ugly Number IImedium
279Perfect Squaresmedium
438Find All Anagrams in a Stringmedium
686Repeated String Matchmedium
981Time Based Key-Value StoremediumNeetCode 150
1011Capacity To Ship Packages Within D Daysmedium
1390Four Divisorsmedium
1631Path With Minimum Effortmedium
214Shortest Palindromehard
410Split Array Largest Sumhard
774Minimize Max Distance to Gas Stationpremiumhard
1392Longest Happy Prefixhard

Recall card

Binary search, two forms — exact match: while lo <= hi, hi = mid - 1. Boundary: while lo < hi, hi = mid, answer is lo. Pick by the question asked.
lower_bound = first index with a[i] >= x; upper_bound = first with a[i] > x. One character apart.
Binary search on the answer — needs a monotone predicate; cost is $O(n \log R)$ where $R$ is the value range.
Sieve — inner loop from i*i, outer to $\sqrt n$ ; $O(n \log\log n)$ . One primality test → trial division to $\sqrt n$ instead.
Modular exponentiation — square the base, multiply on set bits; pow(a, b, m) in Python.
Modular inverse — pow(a, p-2, p) only for prime p; otherwise extended Euclid.
GCD — while b: a, b = b, a % b, $O(\log)$ .
KMP — prefix function pi, fall back to pi[k-1], never rewind the text; $O(n+m)$ .
Fast I/O — sys.stdin.readline and .strip(); buffer output and print once.
Only two of these fail silently — unsorted binary search, and Fermat’s inverse on a composite modulus. Everything else just gets slow.

Recap

Binary search has three shapes — exact match (lo <= hi), boundary-finding (lo < hi, lower_bound/upper_bound), and binary-search-on-the-answer (same lo < hi shape, a feasible() predicate instead of an array comparison).
Sieve of Eratosthenes: $O(n \log \log n)$ for every prime up to n.
Fast modular exponentiation ( $O(\log b)$ ) and the Fermat modular inverse built on top of it — or just call pow(a, b, m) directly.
GCD/LCM via Euclid, or math.gcd/math.lcm in real code.
KMP and the Z-algorithm both do linear-time pattern matching by reusing information instead of re-scanning; KMP via the failure function, Z via prefix self-similarity.
Fast I/O: sys.stdin.buffer.read().split() plus a single sys.stdout.write beats input()/print() in a loop at scale.

Next: Master Complexity Cheatsheet — every operation, data structure, and algorithm on this site laid out with its time and space complexity in one place, plus a rule of thumb for reading constraints.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading