ALGORITHMS IN FRONTEND WORK · CORE

Virtualized list window

Render only the rows that are on screen by finding, from the row heights and the scroll position, the first and last visible row.

Time O(n) to build, O(log n + k) per scrollSpace O(n)5 practice problemsStep-through picture

The idea

A list with 100,000 rows would create 100,000 DOM elements, which makes the page slow to load and to scroll. A virtualized list, also called windowing, only renders the few rows that are actually visible, plus a small buffer. As you scroll, it swaps which rows exist.

To do that, it must answer one question on every scroll: given scrollTop (how far the list is scrolled, in pixels) and viewportHeight (how tall the visible area is), which rows are on screen? If every row has the same height, that's division: the first row is Math.floor(scrollTop / rowHeight).

When rows have different heights, keep a running total called tops: tops[i] is the pixel where row i starts, so it grows as you go down. Because it only grows, you can binary search it to find the first row whose bottom is below scrollTop. Then step forward until the rows start below the bottom of the viewport.

An everyday example

Looking at a long scroll through a window

Imagine a very long paper scroll with notes of different heights, and a small window frame you look through. You don't need to read every note, only the ones in the frame. Someone has written on the edge of the paper where each note starts. To find the first note in the frame, you look up the frame's top edge in those marks, jumping to the middle and halving like in a dictionary. Then you read notes down until one starts below the frame.

How the example maps to the code
In the example	In the code
Where each note starts	`tops[i]`
How far the scroll has moved	`scrollTop`
The height of the window frame	`viewportHeight`
Jumping to the middle of the marks	Binary search with `low`, `high`, and `mid`
The notes you can see	The rows from `first` to `last`

From the slow way to virtualized list window

Start with the obvious way: render every row. A list of 100,000 rows creates 100,000 DOM elements. Each one takes memory and has to be laid out, so the page is slow to open, and every style change has a huge tree to update.
Only the rows that overlap the visible area matter. To find them, you could start at row 0 and add up heights until you pass scrollTop. But that's up to n additions on every scroll event, and scroll events arrive many times per second.
So add the heights up once, ahead of time, into tops: tops[i] is where row i starts and tops[i + 1] is where it ends. Heights are positive, so tops only grows. That means the question "does row i end below scrollTop?" is no for the rows at the top and yes for every row after some point. Binary search finds that point in about log₂ n checks: at most 17 for 100,000 rows.
From that first visible row, step forward while the next row starts above the bottom edge, scrollTop + viewportHeight. That's only as many steps as there are visible rows. Render just those rows, placed at tops[i], inside a spacer as tall as tops[n] so the scrollbar stays the right size. That search plus a short walk is the virtualized list window.

How it works

Build tops: tops[0] = 0 and tops[i + 1] = tops[i] + heights[i]. Row i covers pixels from tops[i] up to tops[i + 1].
Binary search for first, the first row whose bottom tops[mid + 1] is greater than scrollTop. Start with low = 0, high = heights.length - 1, and first = heights.length meaning none.
If tops[mid + 1] > scrollTop, row mid reaches into the view, so save first = mid and look left for an earlier one with high = mid - 1. Otherwise look right with low = mid + 1.
Start last at first and move it forward while the next row starts above the viewport's bottom: tops[last + 1] < scrollTop + viewportHeight.
Return [first, last], or an empty list if the list is scrolled past its end.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

function visibleRange(heights, scrollTop, viewportHeight) {
const tops = [0];
for (let i = 0; i < heights.length; i++) {
tops.push(tops[i] + heights[i]);
}
let low = 0;
let high = heights.length - 1;
let first = heights.length;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (tops[mid + 1] > scrollTop) {
first = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
let last = first;
while (last + 1 < heights.length && tops[last + 1] < scrollTop + viewportHeight) {
last++;
}
return first < heights.length ? [first, last] : [];
}

How fast it is

Time	`O(n) to build, O(log n + k) per scroll`
Extra memory	`O(n)`

The running totals are built once per change of heights. Each scroll position is then a binary search plus a walk over the k visible rows.

Best caseO(log n)
tops is already built and only one row is visible, so the call is the search plus one step.
Average caseO(log n + k)
tops is kept between scroll events and k rows fit on screen, usually a few dozen.
Worst caseO(n)
The viewport is taller than the whole list, so the walk visits all n rows. The code as shown also rebuilds tops on every call, which is O(n); real lists rebuild it only when heights change.

Common mistakes

Using >= instead of > when comparing a row's bottom with scrollTop. A row that ends exactly at the top edge isn't visible, so it shouldn't be first.
Looping from row 0 on every scroll event to find the first visible row. That is O(n) per event and becomes janky for long lists.
Forgetting the scrolled-past-the-end case. With no visible row, return an empty range instead of reading past the array.
Changing row heights without updating tops. The list then renders the wrong rows and the scrollbar size is wrong.

When to use it

Look for these clues in a problem:

A list or table has thousands of rows but only a few fit on screen.
You are given row heights and a scroll position and must find which rows are visible.
The question mentions windowing, infinite scroll, overscan, or keeping the DOM small.
Running totals of sizes must be searched quickly on every scroll event.

Check yourself

Answer each one in your head first, then open it.

Why is the check tops[mid + 1] > scrollTop and not >=?

A row whose bottom is exactly at scrollTop ends at the top edge, so none of it shows. With >=, it would be counted as the first visible row.

About how many checks does the search need for 1,000,000 rows?

About 20, because 2 to the 20th power is just over a million. Each check halves the range.

Why doesn't the code binary search for last too?

Only the k visible rows are walked, and you have to render those k rows anyway, so the walk adds nothing to the cost. A second search would only help if k were huge.

How tall must the spacer inside the scroll container be?

tops[n], the sum of all heights. The scrollbar then has the same size and range as if every row were rendered.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

#728Row Offsets with Live Updates

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The search relies on one fact: because every height is positive, tops grows, so "row i ends below scrollTop" is false up to some row and true from then on. The loop keeps this rule: every row before low is hidden, every row after high ends below scrollTop, and first is the earliest row seen so far that ends below it. Each check keeps the rule and shrinks the range by at least one, so the loop ends with first as the earliest such row, or heights.length if there is none.

Row first really is visible. It ends below the top edge, and it starts where row first - 1 ends, which is at or above scrollTop, so it starts above the bottom edge too. Every row before it ends at or above the top edge, so none of them shows.

The walk is right because every row after first already ends below the top edge. Such a row is visible exactly when it starts above the bottom edge. Rows start lower and lower, so the first one that starts at or below the bottom edge proves that every later row is hidden too, and the walk can stop there.

Going deeper

3 more ideas

Why binary search works here

Heights are positive, so tops only grows: each row starts below the one before. That means "row i ends below scrollTop" is false for some rows at the top and then true for every row after. Binary search finds the first true in O(log n) steps, the same way it finds the first failing commit in a sorted history.

Overscan and measuring

Libraries render a few extra rows above and below, called overscan, so fast scrolling doesn't show blank space before the next update. Often heights aren't known until a row is rendered; the list then starts with an estimated height, measures each row after it renders, and updates tops. Keeping the first visible row in place while heights change avoids content jumping under the user.

How fast it is

Building tops is O(n), but only when heights change. Each scroll then costs O(log n) for the search plus O(k) for the k visible rows. With fixed heights, the first row is a single division, O(1).

Work it by hand

Every step in a table, with why

Find the visible rows among 8 rows of different heights. The search goes left once and right twice, and the row that starts exactly at the bottom edge is left out.

heights = [35, 55, 20, 65, 45, 30, 50, 40], scrollTop = 140, viewportHeight = 110, so tops = [0, 35, 90, 110, 175, 220, 250, 300, 340] and the view covers pixels 140 to 250

Step	Loop	`low`, `high`	Row	Check	Result	Why
1	build	-	all 8	running totals	`tops` has 9 values	One extra value at the end: `tops[8] = 340` is the bottom of the last row and the full height of the list.
2	search	0, 7	`mid = 3`	`tops[4] = 175 > 140`: yes	`first = 3`, `high = 2`	Row 3 ends below the top edge, so it could be the first visible row. Save it and look left for an earlier one.
3	search	0, 2	`mid = 1`	`tops[2] = 90 > 140`: no	`low = 2`	Row 1 ends at pixel 90, above the view. The first visible row is further down.
4	search	2, 2	`mid = 2`	`tops[3] = 110 > 140`: no	`low = 3`	Row 2 ends at 110, still above the view. Now `low > high`, so the search ends with `first = 3`.
5	walk	-	row 4	`tops[4] = 175 < 250`: yes	`last = 4`	Row 4 starts above the bottom edge, so it is visible.
6	walk	-	row 5	`tops[5] = 220 < 250`: yes	`last = 5`	Row 5 starts at 220, still inside the view.
7	walk	-	row 6	`tops[6] = 250 < 250`: no	stop	Row 6 starts exactly at the bottom edge, so none of it shows. The walk stops.

It returns [3, 5]: rows 3, 4, and 5 are visible. The search took 3 checks instead of scanning from row 0, and the walk stopped at the first row below the view.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
Virtualized list window	`O(log n)`	`O(n)`	Long lists with rows of different heights. The search runs on each scroll, plus the `k` visible rows.
Render every row	`O(n)`	`O(n)`	A few hundred rows or fewer. It's simpler, and the browser's own find-in-page, focus, and accessibility tools see every row.
Fixed-height division	`O(1)`	`O(1)`	Every row has the same height, like a simple table or log view.
Fenwick tree of heights	`O(log n)`	`O(n)`	Heights change often after measuring, and rebuilding all the running totals each time would be too slow.

Extra memory: O(n) for tops, one number per row plus one. The search and the walk use only a few counters.

How the steps grow

Virtualized list window, Fenwick tree of heights O(log n)
Render every row O(n)
Fixed-height division O(1)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
Virtualized list window	3	10	20
Render every row	10	1,000	1 million
Fixed-height division	1	1	1
Fenwick tree of heights	3	10	20

Inputs that need care

6 tricky inputs

An empty list: heights = []: tops is [0], high is -1, so the search never runs and first stays 0 = heights.length. It returns [].
Scrolled past the end: scrollTop = 400 with a list 340 pixels tall: No row ends below 400, so first stays heights.length and it returns [] instead of reading past the array.
A row ends exactly at the top edge: heights = [35, 55], scrollTop = 35: tops[1] = 35 > 35 is false, so row 0 is treated as hidden and first = 1. Using >= here would wrongly include row 0.
A negative scrollTop, from the bounce when overscrolling on touch screens: Every row's bottom is greater than a negative number, so first = 0. The walk then counts rows from the top, which is correct.
viewportHeight = 0, as when the list is hidden or not yet measured: The walk adds nothing, so it returns [first, first]: one row. That's harmless for rendering, but don't treat it as "the user can see this row".
Rows of height 0: tops has equal neighbors but never goes down, so the yes-or-no question still flips only once and the search still works. A zero-height row that sits at the top edge counts as hidden.

Variations and follow-ups

Twists interviewers add

Fixed row height

When every row has height h, skip tops: first = Math.floor(scrollTop / h) and last = Math.min(n - 1, Math.ceil((scrollTop + viewportHeight) / h) - 1). Both are O(1), which is why fixed-height lists are the simplest to virtualize.

Overscan

Render a few extra rows above first and below last. When the user scrolls fast, those rows are already there, so no blank space flashes before the next update.

Measured heights with a Fenwick tree

Often heights are only known after a row renders, so lists start with an estimate and measure later. Rebuilding tops after each measurement is O(n). A Fenwick tree stores the running totals so that changing one height and finding the row at a pixel offset both take O(log n).

Grids

Spreadsheets and data grids virtualize both directions. Run the same search on the row tops with scrollTop and on the column lefts with scrollLeft, and render only the cells where the two ranges cross.

In an interview

Spot it, explain it, answer follow-ups

Spot it from "thousands of rows", "only render what's visible", "scrollTop", or "row heights". If the heights vary, the hint is that running totals are sorted, so binary search applies.
Explain it in three steps: running totals, a binary search for the first row that ends below the top edge, and a short walk for the last row that starts above the bottom edge. Say why > and < are strict.
Test by hand: a row ending exactly at scrollTop, a row starting exactly at the bottom edge, scrolling to the very end, scrolling past it, and an empty list.
Expect the follow-up "heights are unknown until rendered". Answer: start with an estimate, measure rendered rows, update the totals from the changed row on (or use a Fenwick tree), and keep the first visible row in place so content doesn't jump.

Where frontend code uses it

The same idea in real UI code

react-window, react-virtualized, TanStack Virtual, and Angular CDK's virtual scroll all compute a visible window from item sizes and the scroll offset; with variable sizes, react-window binary searches the measured item offsets.
Data grids in spreadsheets and admin dashboards virtualize both rows and columns so tables with millions of cells stay fast.
Chat apps and social feeds with infinite scroll render only nearby messages and keep the scroll position anchored while new items load.

Virtualized list window

The idea

An everyday example

Looking at a long scroll through a window

From the slow way to virtualized list window

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why binary search works here

Overscan and measuring

How fast it is

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Fixed row height

Overscan

Measured heights with a Fenwick tree

Grids

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

Looking at a long scroll through a window

From the slow way to virtualized list window

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why binary search works here

Overscan and measuring

How fast it is

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Fixed row height

Overscan

Measured heights with a Fenwick tree

Grids

In an interview

Where frontend code uses it

Related algorithms