Virtualizing a List as an Algorithms Problem

This is the last lesson in the course, and it's designed to make one point unmistakably: virtualizing a list is not a rendering trick — it's an algorithms problem, and specifically, it's a problem this course has already given you every tool to solve. This lesson doesn't introduce new techniques; it shows three of them working together.

The problem, restated as a complexity mismatch

A list with 100,000 rows, rendered naively, creates 100,000 real DOM nodes. But a screen can only ever show a small, fixed number of them at once — say, 20, determined by the viewport's height and the row height. The real information need never exceeds that small, bounded number. Rendering 100,000 real nodes to satisfy a 20-row need is doing O(n) work — real DOM creation, real layout cost, real memory — for something that's genuinely O(visible count), a constant, unrelated to how much data exists. This is precisely the "real n versus the n you actually need" theme from the space-complexity and constants lessons early in this course, just showing up at its largest, most consequential scale.

Virtualization: render only the rows currently visible (plus a small buffer), and reuse/recycle DOM nodes as the user scrolls, rather than keeping every row's node alive the entire time.

Fixed row heights: O(1) is enough

If every row is the same height, finding which row index is at the top of the current scroll position needs no search at all:

function getStartRow(scrollTop, rowHeight) {
  return Math.floor(scrollTop / rowHeight); // O(1) — direct formula, no lookup needed
}
 
function getVisibleRange(scrollTop, viewportHeight, rowHeight, totalRows) {
  const startRow = getStartRow(scrollTop, rowHeight);
  const visibleCount = Math.ceil(viewportHeight / rowHeight);
  const endRow = Math.min(startRow + visibleCount + 1, totalRows); // +1 buffer row
  return { startRow, endRow };
}

Fixed heights mean row i's top position is always exactly i * rowHeight — a direct, invertible formula. No lookup, no search, genuinely O(1) per scroll event, regardless of how many total rows exist.

Variable row heights: this is where prefix sums and binary search meet

Real lists often don't have uniform row heights — a chat log, a comment feed, a file browser with wrapped filenames. Now "which row is at this scroll position" can't be answered with a formula — it needs the actual cumulative heights. This is exactly the prefix-sum technique from earlier in this course:

function buildCumulativeHeights(rowHeights) {
  const cumulative = new Array(rowHeights.length + 1).fill(0);
  for (let i = 0; i < rowHeights.length; i++) {
    cumulative[i + 1] = cumulative[i] + rowHeights[i]; // same prefix-sum build as before
  }
  return cumulative;
}

Built once, in O(n) — exactly the prefix-sums lesson's trade: pay O(n) once, so that every later query is cheap. But this time, "cheap" isn't O(1) (there's no direct formula for variable heights) — it's a search: find the row index whose cumulative range contains the given scrollTop. And because cumulative sums of positive heights are, by construction, monotonically increasing — exactly the sortedness property binary search requires — that search is a direct application of binary search:

function findRowAtScrollPosition(cumulativeHeights, scrollTop) {
  let low = 0;
  let high = cumulativeHeights.length - 1;
 
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (cumulativeHeights[mid] <= scrollTop) low = mid + 1;
    else high = mid;
  }
 
  return low - 1; // the row whose range contains scrollTop
}

O(log n) per scroll event, instead of the O(n) linear scan a naive "walk through rows adding up heights until you pass scrollTop" approach would cost. This is a genuine synthesis of two earlier lessons, not a new technique: prefix sums make cumulative position lookups possible at all, and binary search is what makes finding the right one fast, because prefix sums happen to produce exactly the sorted, monotonic structure binary search needs.

The detail that's easy to miss: the scrollbar itself

Rendering only a handful of DOM nodes would, on its own, make the scrollable container think there's only a handful of nodes' worth of content — breaking the scrollbar's size and range. The fix is a spacer element sized to the total height (the last value in the cumulative-heights array, an O(1) read after the one-time O(n) build) — tall enough to give the scrollbar accurate real estate, even though almost none of that space actually contains rendered content. The user's scrolling experience needs to reflect the true O(n) total size of the data, even while the actually rendered content stays O(visible count).

What to remember, and what this course was actually teaching

• List virtualization is doing O(visible count) real DOM work for an O(n) amount of underlying data — a rendering technique that only exists because someone recognized a real complexity mismatch, not a framework trick.
• Fixed row heights need no search at all — row position is a direct O(1) formula.
• Variable row heights need prefix sums (build cumulative positions once, O(n)) plus binary search (find the right row per scroll event, O(log n)) — a genuine combination of two earlier lessons, not a new idea.
• A spacer sized to the true total height keeps the scrollbar honest, even while actual rendered content stays bounded and small.

That combination — recognizing a real-world performance problem, naming its actual complexity mismatch, and reaching for the right pattern from a now-familiar toolkit — is the entire skill this course has been building, one pattern at a time, from the first lesson's nested loop to this one.