.find() in a loop is O(n²) wearing a friendly face

PP #1 · 20 Jul 2026 · Web performance

Your list of 5,000 items takes 2 seconds to reconcile after every save. No network call, no rendering — the tab just freezes while plain JavaScript churns. You profile it, and the flame chart points at one line that looks completely harmless:

const local = localItems.find((it) => it.id === incoming.id);

The shape of the trap

.find(), .includes(), .some(), .indexOf() all do the same thing: they walk the array from the start until they get a hit. One call over one array is O(n) — invisible at any realistic size.

The problem is what surrounds it. The line above lives inside a loop over a second collection, because that’s the exact shape of every reconcile, merge, or diff:

“for each item the server sent back, find its local counterpart.”

// O(n · m) — for 5k × 5k that's 25,000,000 comparisons per save
function reconcile(serverItems: Item[], localItems: Item[]) {
  for (const incoming of serverItems) {
    const local = localItems.find((it) => it.id === incoming.id); // linear scan, every iteration
    if (local) merge(local, incoming);
  }
}

Nothing here looks slow. There’s no nested for loop, no obvious red flag — just a friendly array method. But .find() running once per outer item is a nested loop with the braces hidden inside a method call. 5,000 × 5,000 is 25 million comparisons for a single save, and it grows with the square of your data.

The fix is three lines

Stop scanning. Index the inner collection once into a Map, then every lookup is O(1):

// O(n + m) — build the index once, then constant-time lookups
function reconcile(serverItems: Item[], localItems: Item[]) {
  const byId = new Map(localItems.map((it) => [it.id, it]));
  for (const incoming of serverItems) {
    const local = byId.get(incoming.id);
    if (local) merge(local, incoming);
  }
}

That’s the whole change: build a Map keyed by id, swap .find() for .get(). The .includes() / .some() version of this trap gets the same treatment — reach for a Set instead of a Map.

Prove it

Don’t take the big-O on faith — paste this into a console and watch:

const N = 5000;
const server = Array.from({ length: N }, (_, i) => ({ id: i }));
const local = Array.from({ length: N }, (_, i) => ({ id: i }));

console.time('find');
for (const s of server) local.find((l) => l.id === s.id);
console.timeEnd('find'); // ~hundreds of ms to seconds

console.time('map');
const byId = new Map(local.map((l) => [l.id, l]));
for (const s of server) byId.get(s.id);
console.timeEnd('map'); // ~single-digit ms

Expect two to three orders of magnitude. The gap widens as the data grows — double the items and the .find() version gets four times slower, while the Map version merely doubles.

In the wild

This isn’t a toy example. On a GIS platform rendering 100k+ live map entities, visibility checks were doing exactly this — every consumer built a fresh collection and scanned it per check. Moving that to an O(1) registry lookup was one of the biggest single wins in the whole optimization pass.

See the “Visibility lookups” row in the 100k+ map entities case study for the production before/after.

Takeaway

An array method inside a loop is a nested loop in disguise. Any time you’re matching one collection against another — reconcile, merge, dedupe, diff — index one side into a Map or Set first. It’s almost always three lines, and it’s almost always the difference between “instant” and “why is the tab frozen.”

← More Performance Punches