Problem Narrative

You’re building a TikTok-style video feed for a consumer fintech app with 10M+ DAUs. The feed can contain millions of items, and rendering all rows at once would blow up memory and tank scroll performance. To keep the UI smooth, the client uses list virtualization: only items that intersect the viewport (plus a small buffer) are rendered.

Task

Implement the core virtualization routine.

You are given:

• heights: an array where heights[i] is the pixel height of item i (variable-height rows)
• viewport_height: the viewport height in pixels
• scroll_top: the current scroll offset in pixels from the top of the list
• overscan: number of extra items to render before and after the visible range

Return a tuple (start_index, end_index, top_padding, bottom_padding) where:

• start_index and end_index define the inclusive range of items to render after applying overscan
• top_padding is the total height (pixels) of items strictly before start_index
• bottom_padding is the total height (pixels) of items strictly after end_index

Visibility Rules

• An item is visible if any part of it intersects the viewport interval [scroll_top, scroll_top + viewport_height).
• Clamp the final window to valid indices: 0 <= start_index <= end_index < n.
• If heights is empty, return (0, -1, 0, 0).

Examples

Example 1

Input:

• heights = [20, 30, 10, 40]
• viewport_height = 25
• scroll_top = 15
• overscan = 1

Output:

• (0, 2, 0, 40)

Explanation:

• Prefix sums give item spans: item0 [0,20), item1 [20,50), item2 [50,60), item3 [60,100).
• Viewport is [15,40), so visible items are 0 and 1.
• Overscan=1 expands to render indices [0..2].
• top_padding = 0 (nothing before index 0), bottom_padding = 40 (item3).

Example 2

Input:

• heights = [100, 100, 100]
• viewport_height = 50
• scroll_top = 260
• overscan = 0

Output:

• (2, 2, 200, 0)

Explanation:

• Total height is 300; viewport [260,310) intersects only item2 [200,300).

Constraints

• 0 <= n <= 2 * 10^5
• 1 <= heights[i] <= 10^6
• 0 <= viewport_height <= 10^9
• 0 <= scroll_top <= 10^12
• 0 <= overscan <= 10^5

Notes

• Your solution must be efficient for large n; avoid scanning linearly per scroll event.
• Assume heights does not change during this call (no dynamic inserts/removals).