Incorrect Implementation of falling squares problem

Question

So I was solving the falling squares problem.

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.

Thought Process:

1. Initialize and remember first points(both x and y coordinates).
2. Iterate one by one, and if boxes lie on top of one another ,add the height.
3. If this isn't the case, see which of current height or max_height is greater and add it on to the resulting list.

This is my code :

class Solution:
    def falling_squares(self, positions: List[List[int]]) -> List[int]:
        x_coordinate = positions[0][0]
        y_coordinate = positions[0][1]
        max_height = y_coordinate
        result = [max_height]
        for left,position in positions[1:]:
            if left<x_coordinate+y_coordinate:
                max_height+=position
                result.append(max_height)
            else:
                max_height = max(max_height,position)
                result.append(max_height)
            x_coordinate=left
            y_coordinate = position
        return result 

This is the output

Please tell me what I am missing in my logic.

Answer 1

You have a lot of bugs in your code I tried to improve it by fixing the some logic but it was popping another logical error for other leetcode testcases you gave. I ended up re-writing the code.

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        ret = []
        blocks = {}
        for drop in positions:
            x_coordinate = drop[0]
            checked = False
            elongation = drop[1]
            for (block_x, block_xe), prev_h in blocks.copy().items():
                if x_coordinate < block_xe and x_coordinate+elongation > block_x:
                    if blocks.get((x_coordinate,x_coordinate + elongation)):
                        if blocks.get((x_coordinate,x_coordinate + elongation)) < elongation + prev_h:
                            blocks[(x_coordinate,x_coordinate + elongation)] = elongation +prev_h
                    else:
                        blocks[(x_coordinate,x_coordinate + elongation)] = elongation +prev_h
                    checked = True
            if not checked:
                blocks[(x_coordinate, x_coordinate+elongation)] = elongation
            ret.append(max(blocks.values()))
        return ret

Heres the explanation:

line 1: initialising the return list.

line 2: initialising the hash map for blocks. The reason why didn't I just did what you did was because in some cases the block lands on a block which was recorded some iterations ago and not the just previous iteration and its height is greater than max_height. Also this was the main reason which encouraged me to re-write your code.

line 7: iterating through the copy of blocks because i am modifying it in the loop.

line 8-15: checking if the block's x is smaller than the second block's x + its elongation and checking if the block's x + its elongation is greater than second block's x. This is to check if the block is landing on top of any other block.

checking if theres a duplicate of the current block. If yes then we will only add it if its greater than its dupe. Else if there is no duplication which just add it.

line 17: if the block has landed on any other block then checked is switched True, if not then we add it to the hash map.

Theres obviously a faster way of doing it:

Runtime: 883 ms, faster than 26.06% of Python3 online submissions for Falling Squares.
Memory Usage: 15 MB, less than 51.41% of Python3 online submissions for Falling Squares.