Java O(N^2) Solution


  • 0
    H
    class Solution {
        public List<Integer> fallingSquares(int[][] positions) {
            final List<Integer> res = new LinkedList<Integer>();
            int max = 0;
            int[] h = new int[positions.length];
            for (int i = 0; i < positions.length; ++i) {
                h[i] = positions[i][1];
                int end = positions[i][0] + positions[i][1] - 1;
                for (int j = 0; j < i; ++j) {
                    if (positions[j][0] + positions[j][1] - 1 >= positions[i][0] && end >= positions[j][0]) {
                        h[i] = Math.max(h[i], h[j] + positions[i][1]);
                    }
                }
                max = Math.max(max, h[i]);
                res.add(max);
            }
            return res;
        }
    }
    

Log in to reply
 

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