# Falling Blocks

• Given a playfield that has width columns, and there are blocks falling from above similar to Tetris. All blocks are rectangle in shape and is defined by the following class:

``````class Block {
int left;
int right;   // inclusive. block's width = (right - left + 1)
int height;
}
``````

Where 0 <= left < right < width.

Implement the following `FallingBlock` class:

``````class FallingBlock {
public FallingBlock(int width);
public void fallBlock(Block block);
// get the maximum height of all blocks.
public int getMaxHeight();
}
``````

Example:

``````FallingBlock obj = new FallingBlock(6);
obj.fallBlock(new Block(1 /* left */, 3 /* right */, 2 /* height */));
``````
``````│                  │
│  ┌──────┐        │
│  │      │        │
└──└──────┘────────┘
``````
``````obj.getMaxHeight() -> 2
``````

``````obj.fallBlock(new Block(3 /* left */, 4 /* right */, 2 /* height */));
``````
``````│       ┌────┐     │
│       │    │     │
│  ┌────└─┬──┘     │
│  │      │        │
└──└──────┘────────┘
``````
``obj.getMaxHeight() -> 4``

• I think a linked list can apply to this problem:

``````class Node {
int start;
int height;
Node* next;
Node(int start, int height):start(start), height(height){};
};
``````

Every time a new block `x` comes, we scan the list and find two node:

1. node a: `a.start < x.left && a.next.start >= x.left`
2. node b: `b.start <= x.right && b.next.start > x.right`

then we update the status:

1. we merge the nodes between a and b as a new node (if a and b are same, we just create a new one)
2. height of the new node will be the heighest one between a and b.

Complexity Analisys:

1. every fall: O(n)
2. get max height: O(1), since we can calculate and store it during each fall.

• @xidui very intersting approach, what happens when we have the following sequence :

1. block [1,4] height 2 ,max height = 2
2. block [2,3] height 4 ,max height = 6

Does algoirthm split block [1,4] on three blocks when block [2,3] arrives?:
[1,2] height 2,
[2,3] height 6
[3,4] height 2

When next block [1,2] with height 1 comes , it doesn't change max height, only the height of block[1,2] is updated to 3.

• @elmirap
Yes! that's exactly what I mean~
BTW, your explanation with an example seem good!

• Can we try something like this:

``````class FallingBlock {
private final int[] heights;
private final int width;
private int maxHeight;

public FallingBlock(int width) {
this.width = width;
heights = new int[width];
Arrays.fill(heights, 0);
maxHeight = 0;
}
public void fallBlock(Block block) {
int max = 0;
for (int i = block.left; i <= block.right; i++) {
max = Math.max(max, heights[i]);
}
for (int i = block.left; i <= block.right; i++) {
heights[i] = max + block.height;
maxHeight = Math.max(maxHeight, heights[i]);
}
}
// get the maximum height of all blocks.
public int getMaxHeight() {
return maxHeight;
}
}
``````

• @diptesh it is good

• @diptesh
elegant code!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.