FrontendPro

116Implement a virtualized grid with variable row heights, overscan, and scroll restoration

hardAbout 75 minutesCodingreactvirtualizationbinary-searchperformance

Problem

Build a grid that can show 100,000 rows × 50 columns, where rows have different heights.

First, pure helpers:

  • buildOffsets(rowCount, getRowHeight): an array offsets of length rowCount + 1, where offsets[i] is the top of row i and offsets[rowCount] is the total height.
  • findRow(offsets, y): the index of the row containing pixel y, using binary search, clamped to valid rows.
  • getRange(offsets, scrollTop, viewportHeight, overscan): { start, end } (inclusive) of the rows to render, including overscan extra rows on each side.

Then <VirtualGrid rowCount columnCount getRowHeight columnWidth width height overscan={2} renderCell initialScrollTop={0} onScroll />:

  • a scroll container data-testid="viewport" of width × height, with a spacer sized to the full grid;
  • render only the visible rows and the visible columns (plus overscan), each cell absolutely positioned with data-row and data-col, containing renderCell(row, col);
  • on mount, restore initialScrollTop (before the first paint), and call onScroll({ scrollTop, scrollLeft }) on every scroll so the position can be saved (for example in sessionStorage).

Try it yourself

Write your solution, run it, then submit to check it against the tests.

App.jsxReact + DOM

Step-by-step

offsets[0] = 0 and offsets[i + 1] = offsets[i] + getRowHeight(i). Building it is O(n) once; afterwards the top of any row is O(1). (For fixed heights you would just multiply; variable heights need the prefix sums.)

Unlock the full solution

What's inside

  • Step-by-step
  • Approach
  • Solution
  • Complexity
  • Edge cases
  • Follow-up questions
  • Tests

Includes 2 code listings, 5 edge cases, 4 follow-up questions.

One-time payment by UPI, card or net banking. Launch price.

All 150 answersOne payment, yours forever