TypeScript · Lesson 7
Algorithms
Binary search, sliding windows, two pointers, memoization, grouping and Dijkstra, written as reusable, precisely typed generic functions.
In short
- Name the pattern and its complexity before you code
- Lower bound: half-open range, one invariant
- Sliding window: grow right, move left forward, O(n)
- Tuple type parameters keep wrapped signatures
- Dijkstra: pop closest, skip stale, relax edges
Interview algorithms are a small set of patterns. Once you recognize the pattern, the code
is short. In TypeScript the extra skill is giving each helper a signature that keeps type
information, so groupBy(users, u => u.role) returns something better than any.
Pattern map
| Pattern | Recognize it when… | Typical complexity |
|---|---|---|
| Binary search / lower bound | sorted input, "first position where…", monotonic predicate | O(log n) |
| Sliding window | contiguous subarray/substring, "longest/shortest window with…" | O(n) |
| Two pointers | sorted input, pairs, merging two sorted sequences | O(n) or O(n + m) |
| Sort + sweep | intervals, meetings, overlaps | O(n log n) |
| Memoization | the same sub-call repeats (overlapping subproblems) | states × cost per state |
| Hashing / grouping | "count/group/dedupe by…" | O(n) |
| Dijkstra | shortest path, non-negative weights | O((V + E) log V) |
Binary search without off-by-one bugs
Use the half-open form [lo, hi) and one invariant: everything left of lo is "too small",
everything at or right of hi is "big enough".
function lowerBound<T, K>(items: readonly T[], target: K, compare: (item: T, target: K) => number): number {
let lo = 0;
let hi = items.length; // hi is exclusive
while (lo < hi) {
const mid = (lo + hi) >>> 1; // unsigned shift = floor((lo + hi) / 2)
if (compare(items[mid], target) < 0) lo = mid + 1;
else hi = mid;
}
return lo; // first index whose item is >= target, or items.length
}
The comparator takes two different types, T (the element) and K (the search key), so you
can search users sorted by age with a plain number: lowerBound(users, 30, (u, age) => u.age - age).
Sliding window
Keep a window [left, right] that always satisfies the constraint. Extend right one step at a
time. When the constraint breaks, move left forward until it holds again. Each index enters and
leaves the window once, so the total is O(n), not O(n²).
const lastSeen = new Map<T, number>();
let left = 0;
for (let right = 0; right < items.length; right++) {
const prev = lastSeen.get(items[right]);
if (prev !== undefined && prev >= left) left = prev + 1; // never move left backwards
lastSeen.set(items[right], right);
// window [left, right] has no duplicates here
}
Two pointers and intervals
With two sorted sequences, walk both with an index each and always advance the one that "ends first". Interval problems almost always start by sorting by start (on a copy!) and then sweeping left to right, merging into the last output interval when they overlap.
Higher-order functions with precise types
Capture the whole parameter list as a tuple type so wrappers keep the original signature:
function logged<Args extends unknown[], R>(fn: (...args: Args) => R): (...args: Args) => R {
return (...args) => {
console.log('calling with', args);
return fn(...args);
};
}
const add = logged((a: number, b: number) => a + b); // (a: number, b: number) => number
The same trick powers memoize, debounce, retry and middleware. Type guards make filtering
precise: a predicate (x): x is string => typeof x === 'string' lets partition return
[string[], number[]] instead of two (string | number)[].
Dijkstra in one paragraph
Keep dist (best known distance) and a min-priority queue of (distance, node). Pop the closest
node. If its popped distance is stale (bigger than dist), skip it. Otherwise relax each outgoing
edge: if dist[u] + w < dist[v], update dist[v], remember prev[v] = u and push v. With
non-negative weights, a node's distance is final when it's popped. JavaScript has no built-in
heap, so you write a ~30-line binary heap (see Data Structures).
Gotchas
Array.prototype.sortsorts in place and compares as strings by default:[10, 9, 1].sort()→[1, 10, 9]. Always pass a comparator and copy first ([...xs].sort(...)orxs.toSorted(...)in ES2023).(lo + hi) / 2needsMath.floor.>>> 1does it in one step for array-sized numbers.- Plain objects as dictionaries inherit keys like
constructorand__proto__. UseMaporObject.create(null). - Memo caches that use truthiness (
if (cache.get(k))) re-compute falsy results. Usehas. - Recursion that's fine for n = 1,000 can blow the stack at n = 100,000.
- Dijkstra breaks with negative edges (use Bellman-Ford). BFS is enough when all weights are equal.
In interviews / in real codebases
Side note
- Say the pattern out loud ("sorted input + first position → lower bound"), state the complexity, then code. Interviewers grade the reasoning as much as the code.
- Test the edges explicitly: empty input, one element, all equal, target smaller/larger than everything, duplicates.
- In production code, prefer well-typed small utilities (
groupBy,partition,memoize) overany-typed lodash calls. The precise signatures catch real bugs at compile time. - These patterns reappear in system design: binary search over sorted SSTables, sliding-window rate limiters, interval merging for calendar/booking systems, Dijkstra in routing and maps.
Practise this lesson
In the app: a short video, 7 exercises checked by real tests and a 12-question concept check. Free with a GitHub account.
Open in the app