TypeScript · Lesson 7

Algorithms

Binary search, sliding windows, two pointers, memoization, grouping and Dijkstra, written as reusable, precisely typed generic functions.

4 min read

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

PatternRecognize it when…Typical complexity
Binary search / lower boundsorted input, "first position where…", monotonic predicateO(log n)
Sliding windowcontiguous subarray/substring, "longest/shortest window with…"O(n)
Two pointerssorted input, pairs, merging two sorted sequencesO(n) or O(n + m)
Sort + sweepintervals, meetings, overlapsO(n log n)
Memoizationthe same sub-call repeats (overlapping subproblems)states × cost per state
Hashing / grouping"count/group/dedupe by…"O(n)
Dijkstrashortest path, non-negative weightsO((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".

▶ Try
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²).

▶ Try
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:

▶ Try
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.sort sorts in place and compares as strings by default: [10, 9, 1].sort() → [1, 10, 9]. Always pass a comparator and copy first ([...xs].sort(...) or xs.toSorted(...) in ES2023).
  • (lo + hi) / 2 needs Math.floor. >>> 1 does it in one step for array-sized numbers.
  • Plain objects as dictionaries inherit keys like constructor and __proto__. Use Map or Object.create(null).
  • Memo caches that use truthiness (if (cache.get(k))) re-compute falsy results. Use has.
  • 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) over any-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