12 lines brute force solution, O(n ^ 2)


  • 0
    public List<Integer> fallingSquares(int[][] positions) {
        int n = positions.length, max = 0;
        int[] height = new int[n];
        List<Integer> ans = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            height[i] += positions[i][1];
            ans.add((max = Math.max(max, height[i])));
            int l = positions[i][0], r = positions[i][0] + positions[i][1] - 1;
            for(int j = i + 1; j < n; j++)
                if (positions[j][0] <= r && l <= positions[j][0] + positions[j][1] - 1)
                    height[j] = Math.max(height[j], height[i]);
        }
        return ans;
    }

Log in to reply
 

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