Falling Squares

HardIntervalssimulation

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Squares are dropped one at a time onto the X-axis. positions[i] = [left, sideLength] describes a square whose bottom edge spans from left to left + sideLength. It falls straight down until it lands on the X-axis or on top of an earlier square. A square only rests on another if their horizontal spans **overlap by a positive length**; squares that merely touch at an edge slide past each other. Once landed, a square stays put. Return an array ans where ans[i] is the height of the tallest stack anywhere after the first i + 1 squares have landed.

Examples

Input: positions = [[1,2],[2,3],[6,1]]
Output: [2,5,5]
The first square reaches height 2. The second overlaps it on [2,3) and lands on top, reaching 2 + 3 = 5. The third lands on the ground at height 1, so the tallest stays 5.
Input: positions = [[100,100],[200,100]]
Output: [100,100]
The second square only touches the first at x = 200, so both rest on the ground.

Constraints

  • 1 <= positions.length <= 1000
  • 1 <= left <= 10^8
  • 1 <= sideLength <= 10^6

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More simulation problems