Falling Blocks


  • 0

    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

  • 1

    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.

  • 1

    @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.


  • 1

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


  • 5
    D

    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;
        }
    }
    

  • 0

    @diptesh it is good


  • 0

    @diptesh
    elegant code!


Log in to reply
 

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