Substitute Algorithm

Problem

A function reaches its result through a convoluted path: nested loops, flags, manual bookkeeping. A simpler approach exists, perhaps a standard library call or a well-known algorithm, but the old code stays because nobody wants to touch it.

Solution

Write the new algorithm in a fresh body and swap it in, keeping the signature. Verify with tests that both produce identical results for the same inputs.

Before

function mergeBusyIntervals(slots: Interval[]): Interval[] {
  const result: Interval[] = [];
  const used: boolean[] = slots.map(() => false);
  for (let i = 0; i < slots.length; i++) {
    if (used[i]) continue;
    let start = slots[i].start;
    let end = slots[i].end;
    let changed = true;
    while (changed) {
      changed = false;
      for (let j = 0; j < slots.length; j++) {
        if (used[j] || j === i) continue;
        if (slots[j].start <= end && slots[j].end >= start) {
          start = Math.min(start, slots[j].start);
          end = Math.max(end, slots[j].end);
          used[j] = true;
          changed = true;
        }
      }
    }
    used[i] = true;
    result.push({ start, end });
  }
  return result.sort((a, b) => a.start - b.start);
}

After

function mergeBusyIntervals(slots: Interval[]): Interval[] {
  const sorted = [...slots].sort((a, b) => a.start - b.start);
  const merged: Interval[] = [];
  for (const slot of sorted) {
    const last = merged[merged.length - 1];
    if (last && slot.start <= last.end) {
      last.end = Math.max(last.end, slot.end);
    } else {
      merged.push({ ...slot });
    }
  }
  return merged;
}

Why

• The sort-then-sweep version is a known pattern that readers recognize in seconds.
• It runs in O(n log n) instead of worst-case O(n³).
• Fewer flags and indices means fewer places for off-by-one bugs.

Steps

1. Make sure the function is as small as possible. Use Extract Method to isolate the algorithm from unrelated work.
2. Pin the current behavior with tests, including edge cases: empty input, one element, touching boundaries, duplicates, unsorted input.
3. Write the new algorithm next to the old one (mergeBusyIntervalsV2). Run both on the same inputs, by test or by property-based comparison.
4. When they agree, replace the old body with the new one. Run the tests.
5. Delete the temporary copy.

Watch out

• "Same results" includes ordering, mutation of inputs, handling of null, error types and rounding. The new version above copies each slot so it does not mutate the caller's array; check such details explicitly.
• Don't substitute when the old algorithm encodes a business rule you do not fully understand. Characterize it with tests first.
• Performance can get worse as well as better. Check large-input behavior if the function sits on a hot path.
• If several algorithms are all valid and must be selectable, that is a Strategy, not a substitution.
• There is no inverse; you can always substitute back.

Related

• Fixes Duplicate Code when replacing hand-rolled code with a library call, and Long Method.
• Extract Method isolates the algorithm first.
• Strategy applies when you need several algorithms at once.

Agent checklist

• Tests covering edge cases existed or were written before the swap.
• Old and new implementations were compared on the same inputs.
• Input mutation, output order and error behavior match.
• The signature did not change.
• The old implementation is deleted.