699. Falling Squares
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public List<Integer> fallingSquares(int[][] positions) {
        int n = positions.length;
        int[] maxHeights = new int[n];
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int xStart = positions[i][0];
            int squareSize = positions[i][1];
            int xEnd = xStart + squareSize;
            maxHeights[i] += squareSize;

            for (int j = i + 1; j < n; j++) {
                int xStart2 = positions[j][0];
                int squareSize2 = positions[j][1];
                int xEnd2 = xStart2 + squareSize2;
                if (xStart2 < xEnd && xStart < xEnd2) {  // If squares overlap
                    maxHeights[j] = Math.max(maxHeights[j], maxHeights[i]);
                }
            }
        }

        int highest = -1;
        for (int height : maxHeights) {
            highest = Math.max(highest, height);
            result.add(highest);
        }
        return result;
    }
}

```
['Java']