Skip to content
RED SAGSkills
medium30 ptsfrontendbinary-search

Virtual List Visible Range

A virtualised list renders only the rows near the viewport. Row i has height heights[i] px; rows are stacked with no gaps, so row i occupies [top_i, top_i + heights[i]) where top_0 = 0.

The viewport shows [scrollTop, scrollTop + viewportHeight). A row is visible if it overlaps the viewport by a positive amount. Find the first and last visible rows, then widen the range by overscan rows on each side, clamped to 0 and heights.length - 1.

Return [start, end] (inclusive). If no row is visible, return [-1, -1].

Example 1

Input: heights = [50,50,50,50,50], scrollTop = 60, viewportHeight = 100, overscan = 0
Output: [1,3]
Explanation: Rows 1, 2 and 3 overlap the window 60 to 160.

Example 2

Input: heights = [50,50,50,50,50], scrollTop = 60, viewportHeight = 100, overscan = 1
Output: [0,4]
Explanation: With overscan 1 the range widens to rows 0 to 4.

Constraints

  • 0 <= heights.length <= 10^5
  • 1 <= heights[i] <= 10^4
  • 0 <= scrollTop <= 10^9
  • 1 <= viewportHeight <= 10^5
  • 0 <= overscan <= 50
Hint 1

Build prefix sums of the heights, then binary search for both ends.

Hint 2

Row i is visible when top_i < scrollTop + viewportHeight and top_i + heights[i] > scrollTop.

Discussion 0

Join free to post in the discussion.

Good practice for: Frontend Developer, Full Stack Developer, Mobile App Developer, Automation Test Engineer, Game Developer

Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.