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_boundlower_bound/upper_boundupper_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.
gcdgcd/lcmlcm, 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.StringIOio.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 <= hiwhile 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

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_boundlower_bound` and `upper_boundupper_bound`

Boundary-finding template: exclusive hihi, while lo < hiwhile lo < hi. lower_boundlower_bound finds the first index with arr[i] >= targetarr[i] >= target; upper_boundupper_bound finds the first index with arr[i] > targetarr[i] > target. In production code, reach for bisect.bisect_leftbisect.bisect_left / bisect.bisect_rightbisect.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))

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)feasible(x) predicate (False, False, ..., False, True, ..., TrueFalse, False, ..., False, True, ..., True) and get back the smallest xx 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

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 limitlimit, 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))

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 % ma**b % m in $O(\log b)$ ; Fermat’s little theorem turns the same routine into a modular inverse for prime mm. Python’s built-in pow(a, b, m)pow(a, b, m) already does the exponentiation in C — use it directly in real solutions, and reach for power_modpower_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)

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)(a, b) to their GCD in $O(\log(\min(a, b)))$ . In real code, use math.gcdmath.gcd / math.lcmmath.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))

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]fail[i]) is the longest proper prefix of pattern[0..i]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"))

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]z[i] is the length of the longest substring starting at ii that matches a prefix of the string. Glue pattern + "#" + textpattern + "#" + text and look for z[i] == len(pattern)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"))

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.StringIOio.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.stdinsys.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()

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()

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.

Recap

Binary search has three shapes — exact match (lo <= hilo <= hi), boundary-finding (lo < hilo < hi, lower_boundlower_bound/upper_boundupper_bound), and binary-search-on-the-answer (same lo < hilo < hi shape, a feasible()feasible() predicate instead of an array comparison).
Sieve of Eratosthenes: $O(n \log \log n)$ for every prime up to nn.
Fast modular exponentiation ( $O(\log b)$ ) and the Fermat modular inverse built on top of it — or just call pow(a, b, m)pow(a, b, m) directly.
GCD/LCM via Euclid, or math.gcdmath.gcd/math.lcmmath.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()sys.stdin.buffer.read().split() plus a single sys.stdout.writesys.stdout.write beats input()input()/print()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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee