Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
There are several squares being dropped onto the X-axis of a 2D plane.
You are given a 2D integer array positions where positions[i] = [lefti, sideLengthi] represents the ith square with a side length of sideLengthi that is dropped with its left edge aligned with X-coordinate lefti.
Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands on the top side of another square or on the X-axis. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved.
After each square is dropped, you must record the height of the current tallest stack of squares.
Return an integer array ans where ans[i] represents the height described above after dropping the ith square.
Example 1:
Input: positions = [[1,2],[2,3],[6,1]] Output: [2,5,5] Explanation: After the first drop, the tallest stack is square 1 with a height of 2. After the second drop, the tallest stack is squares 1 and 2 with a height of 5. After the third drop, the tallest stack is still squares 1 and 2 with a height of 5. Thus, we return an answer of [2, 5, 5].
Example 2:
Input: positions = [[100,100],[200,100]] Output: [100,100] Explanation: After the first drop, the tallest stack is square 1 with a height of 100. After the second drop, the tallest stack is either square 1 or square 2, both with heights of 100. Thus, we return an answer of [100, 100]. Note that square 2 only brushes the right side of square 1, which does not count as landing on it.
Constraints:
1 <= positions.length <= 10001 <= lefti <= 1081 <= sideLengthi <= 106Problem summary: There are several squares being dropped onto the X-axis of a 2D plane. You are given a 2D integer array positions where positions[i] = [lefti, sideLengthi] represents the ith square with a side length of sideLengthi that is dropped with its left edge aligned with X-coordinate lefti. Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands on the top side of another square or on the X-axis. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved. After each square is dropped, you must record the height of the current tallest stack of squares. Return an integer array ans where ans[i] represents the height described above after dropping the ith square.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Segment Tree
[[1,2],[2,3],[6,1]]
[[100,100],[200,100]]
the-skyline-problem)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #699: Falling Squares
class Node {
Node left;
Node right;
int l;
int r;
int mid;
int v;
int add;
public Node(int l, int r) {
this.l = l;
this.r = r;
this.mid = (l + r) >> 1;
}
}
class SegmentTree {
private Node root = new Node(1, (int) 1e9);
public SegmentTree() {
}
public void modify(int l, int r, int v) {
modify(l, r, v, root);
}
public void modify(int l, int r, int v, Node node) {
if (l > r) {
return;
}
if (node.l >= l && node.r <= r) {
node.v = v;
node.add = v;
return;
}
pushdown(node);
if (l <= node.mid) {
modify(l, r, v, node.left);
}
if (r > node.mid) {
modify(l, r, v, node.right);
}
pushup(node);
}
public int query(int l, int r) {
return query(l, r, root);
}
public int query(int l, int r, Node node) {
if (l > r) {
return 0;
}
if (node.l >= l && node.r <= r) {
return node.v;
}
pushdown(node);
int v = 0;
if (l <= node.mid) {
v = Math.max(v, query(l, r, node.left));
}
if (r > node.mid) {
v = Math.max(v, query(l, r, node.right));
}
return v;
}
public void pushup(Node node) {
node.v = Math.max(node.left.v, node.right.v);
}
public void pushdown(Node node) {
if (node.left == null) {
node.left = new Node(node.l, node.mid);
}
if (node.right == null) {
node.right = new Node(node.mid + 1, node.r);
}
if (node.add != 0) {
Node left = node.left, right = node.right;
left.add = node.add;
right.add = node.add;
left.v = node.add;
right.v = node.add;
node.add = 0;
}
}
}
class Solution {
public List<Integer> fallingSquares(int[][] positions) {
List<Integer> ans = new ArrayList<>();
SegmentTree tree = new SegmentTree();
int mx = 0;
for (int[] p : positions) {
int l = p[0], w = p[1], r = l + w - 1;
int h = tree.query(l, r) + w;
mx = Math.max(mx, h);
ans.add(mx);
tree.modify(l, r, h);
}
return ans;
}
}
// Accepted solution for LeetCode #699: Falling Squares
type node struct {
left *node
right *node
l, mid, r int
v, add int
}
func newNode(l, r int) *node {
return &node{
l: l,
r: r,
mid: (l + r) >> 1,
}
}
type segmentTree struct {
root *node
}
func newSegmentTree() *segmentTree {
return &segmentTree{
root: newNode(1, 1e9),
}
}
func (t *segmentTree) modify(l, r, v int, n *node) {
if l > r {
return
}
if n.l >= l && n.r <= r {
n.v = v
n.add = v
return
}
t.pushdown(n)
if l <= n.mid {
t.modify(l, r, v, n.left)
}
if r > n.mid {
t.modify(l, r, v, n.right)
}
t.pushup(n)
}
func (t *segmentTree) query(l, r int, n *node) int {
if l > r {
return 0
}
if n.l >= l && n.r <= r {
return n.v
}
t.pushdown(n)
v := 0
if l <= n.mid {
v = max(v, t.query(l, r, n.left))
}
if r > n.mid {
v = max(v, t.query(l, r, n.right))
}
return v
}
func (t *segmentTree) pushup(n *node) {
n.v = max(n.left.v, n.right.v)
}
func (t *segmentTree) pushdown(n *node) {
if n.left == nil {
n.left = newNode(n.l, n.mid)
}
if n.right == nil {
n.right = newNode(n.mid+1, n.r)
}
if n.add != 0 {
n.left.add = n.add
n.right.add = n.add
n.left.v = n.add
n.right.v = n.add
n.add = 0
}
}
func fallingSquares(positions [][]int) []int {
ans := make([]int, len(positions))
t := newSegmentTree()
mx := 0
for i, p := range positions {
l, w, r := p[0], p[1], p[0]+p[1]-1
h := t.query(l, r, t.root) + w
mx = max(mx, h)
ans[i] = mx
t.modify(l, r, h, t.root)
}
return ans
}
# Accepted solution for LeetCode #699: Falling Squares
class Node:
def __init__(self, l, r):
self.left = None
self.right = None
self.l = l
self.r = r
self.mid = (l + r) >> 1
self.v = 0
self.add = 0
class SegmentTree:
def __init__(self):
self.root = Node(1, int(1e9))
def modify(self, l, r, v, node=None):
if l > r:
return
if node is None:
node = self.root
if node.l >= l and node.r <= r:
node.v = v
node.add = v
return
self.pushdown(node)
if l <= node.mid:
self.modify(l, r, v, node.left)
if r > node.mid:
self.modify(l, r, v, node.right)
self.pushup(node)
def query(self, l, r, node=None):
if l > r:
return 0
if node is None:
node = self.root
if node.l >= l and node.r <= r:
return node.v
self.pushdown(node)
v = 0
if l <= node.mid:
v = max(v, self.query(l, r, node.left))
if r > node.mid:
v = max(v, self.query(l, r, node.right))
return v
def pushup(self, node):
node.v = max(node.left.v, node.right.v)
def pushdown(self, node):
if node.left is None:
node.left = Node(node.l, node.mid)
if node.right is None:
node.right = Node(node.mid + 1, node.r)
if node.add:
node.left.v = node.add
node.right.v = node.add
node.left.add = node.add
node.right.add = node.add
node.add = 0
class Solution:
def fallingSquares(self, positions: List[List[int]]) -> List[int]:
ans = []
mx = 0
tree = SegmentTree()
for l, w in positions:
r = l + w - 1
h = tree.query(l, r) + w
mx = max(mx, h)
ans.append(mx)
tree.modify(l, r, h)
return ans
// Accepted solution for LeetCode #699: Falling Squares
/**
* [0699] Falling Squares
*
* There are several squares being dropped onto the X-axis of a 2D plane.
* You are given a 2D integer array positions where positions[i] = [lefti, sideLengthi] represents the i^th square with a side length of sideLengthi that is dropped with its left edge aligned with X-coordinate lefti.
* Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands on the top side of another square or on the X-axis. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved.
* After each square is dropped, you must record the height of the current tallest stack of squares.
* Return an integer array ans where ans[i] represents the height described above after dropping the i^th square.
*
* Example 1:
* <img alt="" src="https://assets.leetcode.com/uploads/2021/04/28/fallingsq1-plane.jpg" style="width: 500px; height: 505px;" />
* Input: positions = [[1,2],[2,3],[6,1]]
* Output: [2,5,5]
* Explanation:
* After the first drop, the tallest stack is square 1 with a height of 2.
* After the second drop, the tallest stack is squares 1 and 2 with a height of 5.
* After the third drop, the tallest stack is still squares 1 and 2 with a height of 5.
* Thus, we return an answer of [2, 5, 5].
*
* Example 2:
*
* Input: positions = [[100,100],[200,100]]
* Output: [100,100]
* Explanation:
* After the first drop, the tallest stack is square 1 with a height of 100.
* After the second drop, the tallest stack is either square 1 or square 2, both with heights of 100.
* Thus, we return an answer of [100, 100].
* Note that square 2 only brushes the right side of square 1, which does not count as landing on it.
*
*
* Constraints:
*
* 1 <= positions.length <= 1000
* 1 <= lefti <= 10^8
* 1 <= sideLengthi <= 10^6
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/falling-squares/
// discuss: https://leetcode.com/problems/falling-squares/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
impl Solution {
// Credit: https://leetcode.com/problems/falling-squares/discuss/845821/Rust-translated-8ms-100
pub fn falling_squares(positions: Vec<Vec<i32>>) -> Vec<i32> {
let mut map = std::collections::BTreeMap::<i32, i32>::new();
map.insert(0, 0);
let mut max = 0;
let mut result = vec![];
for pos in &positions {
let start = pos[0];
let end = pos[0] + pos[1];
let mut h = 0;
let mut k = 0;
if let Some((&key, &height)) = map.range(..=start).last() {
h = height;
k = key;
}
let mut iter = map.range(k..).skip(1);
while let Some((&key, &height)) = iter.next() {
if key >= end {
break;
}
h = std::cmp::max(h, height);
}
h += pos[1];
max = std::cmp::max(max, h);
result.push(max);
if let Some((&tail, &height)) = map.range(..end).last() {
map.insert(start, h);
map.insert(end, height);
}
let mut iter = map.range(start..).skip(1);
let mut list = vec![];
while let Some((&key, &height)) = iter.next() {
if key < end {
list.push(key)
} else {
break;
}
}
for key in list {
map.remove(&key);
}
}
result
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_0699_example_1() {
let positions = vec![vec![1, 2], vec![2, 3], vec![6, 1]];
let result = vec![2, 5, 5];
assert_eq!(Solution::falling_squares(positions), result);
}
#[test]
fn test_0699_example_2() {
let positions = vec![vec![100, 100], vec![200, 100]];
let result = vec![100, 100];
assert_eq!(Solution::falling_squares(positions), result);
}
}
// Accepted solution for LeetCode #699: Falling Squares
class Node {
left: Node | null = null;
right: Node | null = null;
l: number;
r: number;
mid: number;
v: number = 0;
add: number = 0;
constructor(l: number, r: number) {
this.l = l;
this.r = r;
this.mid = (l + r) >> 1;
}
}
class SegmentTree {
private root: Node = new Node(1, 1e9);
public modify(l: number, r: number, v: number): void {
this.modifyNode(l, r, v, this.root);
}
private modifyNode(l: number, r: number, v: number, node: Node): void {
if (l > r) {
return;
}
if (node.l >= l && node.r <= r) {
node.v = v;
node.add = v;
return;
}
this.pushdown(node);
if (l <= node.mid) {
this.modifyNode(l, r, v, node.left!);
}
if (r > node.mid) {
this.modifyNode(l, r, v, node.right!);
}
this.pushup(node);
}
public query(l: number, r: number): number {
return this.queryNode(l, r, this.root);
}
private queryNode(l: number, r: number, node: Node): number {
if (l > r) {
return 0;
}
if (node.l >= l && node.r <= r) {
return node.v;
}
this.pushdown(node);
let v = 0;
if (l <= node.mid) {
v = Math.max(v, this.queryNode(l, r, node.left!));
}
if (r > node.mid) {
v = Math.max(v, this.queryNode(l, r, node.right!));
}
return v;
}
private pushup(node: Node): void {
node.v = Math.max(node.left!.v, node.right!.v);
}
private pushdown(node: Node): void {
if (node.left == null) {
node.left = new Node(node.l, node.mid);
}
if (node.right == null) {
node.right = new Node(node.mid + 1, node.r);
}
if (node.add != 0) {
let left = node.left,
right = node.right;
left!.add = node.add;
right!.add = node.add;
left!.v = node.add;
right!.v = node.add;
node.add = 0;
}
}
}
function fallingSquares(positions: number[][]): number[] {
const ans: number[] = [];
const tree = new SegmentTree();
let mx = 0;
for (const [l, w] of positions) {
const r = l + w - 1;
const h = tree.query(l, r) + w;
mx = Math.max(mx, h);
ans.push(mx);
tree.modify(l, r, h);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
For each of q queries, scan the entire range to compute the aggregate (sum, min, max). Each range scan takes up to O(n) for a full-array query. With q queries: O(n × q) total. Point updates are O(1) but queries dominate.
Building the tree is O(n). Each query or update traverses O(log n) nodes (tree height). For q queries: O(n + q log n) total. Space is O(4n) ≈ O(n) for the tree array. Lazy propagation adds O(1) per node for deferred updates.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.