Java TreeMap solution.


  • 0

    code with comment.
    TreeMap solution.

    class Solution {
        public static class Metadata {
            public int right, height;
            public Metadata(int right, int height) {
                this.right = right;
                this.height = height;
            }
        }
        TreeMap<Integer, Metadata> map = new TreeMap<Integer, Metadata>(); //left as key, "right + height" as value
        
        public List<Integer> fallingSquares(int[][] positions) {
            List<Integer> result = new LinkedList<Integer>();
            Integer globalMax = 0;
            for(int[] sq: positions) {
                int left = sq[0];
                int right = left + sq[1];
                int maxHeight = 0;   //temporary max height for those intervals that intersect with the new falling square.
                Integer key = map.lowerKey(right);
    
                //walk thru ther intervals that overlap with current falling square 
                while (key != null && !(left >= map.get(key).right || key >= right)) { 
                    Metadata original = map.get(key);
                    maxHeight = Math.max(maxHeight, original.height); // update the temporary maxHeight.
                    map.remove(key);                       // remove the original entry.
                    if(key < left) {                       // left part is beyond the current falling square, insert a new one
                        map.put(key, new Metadata(left, original.height));
                    }
                    if(original.right > right) {           // right part is beyond the current falling square, insert a new one
                        map.put(right, original);
                    }
                    key = map.lowerKey(key);
                }
                
                map.put(left, new Metadata(right, maxHeight + right - left));  // insert the interval for the current falling square.
                globalMax = Math.max(globalMax, maxHeight + right - left);     // update the global maxHeight.
                result.add(globalMax);
            }
            return result;
        }
    }
    

Log in to reply
 

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