Treemap solution and Segment tree (Java) solution with lazy propagation and coordinates compression
Here is the link I refer to:\nhttps://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/\nhttps://leetcode.com/articles/falling-squares/\n\nI think the fir
Here is the link I refer to:\nhttps://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/\nhttps://leetcode.com/articles/falling-squares/\n\nI think the first link is pretty useful to help you understand the segment tree's basic and lazy propagation. The second link I really appreciate its systematic way to define the interface to solve this using different algorithm. However, the segment tree implementation is not well explained in the article (at least it's hard for me to understand).\nThus, I decided to post my Treemap solution, segment tree solution and segment tree solution with lazy propagation for future readers.\n\nTreeMap Solution: The basic idea here is pretty simple, for each square i, I will find all the maximum height from previously dropped squares range from floorKey(i_start) (inclusive) to end (exclusive), then I will update the height and delete all the old heights.\n```\nimport java.util.SortedMap;\nclass Solution {\n    public List<Integer> fallingSquares(int[][] positions) {\n        List<Integer> res = new ArrayList<>();\n        TreeMap<Integer, Integer> startHeight = new TreeMap<>();\n        startHeight.put(0, 0); \n        int max = 0;\n        for (int[] pos : positions) {\n            int start = pos[0], end = start + pos[1];\n            Integer from = startHeight.floorKey(start);\n            int height = startHeight.subMap(from, end).values().stream().max(Integer::compare).get() + pos[1];\n            max = Math.max(height, max);\n            res.add(max);\n            // remove interval within [start, end)\n            int lastHeight = startHeight.floorEntry(end).getValue();\n            startHeight.put(start, height);\n            startHeight.put(end, lastHeight);\n            startHeight.keySet().removeAll(new HashSet<>(startHeight.subMap(start, false, end, false).keySet()));\n        }\n        return res;\n    }\n}\n```\nSegment tree with coordinates compression: It's easy to understand if go through the links above.\n```\nclass Solution {\n    public List<Integer> fallingSquares(int[][] positions) {\n        int n = positions.length;\n        Map<Integer, Integer> cc = coorCompression(positions);\n        int best = 0;\n        List<Integer> res = new ArrayList<>();\n        SegmentTree tree = new SegmentTree(cc.size());\n        for (int[] pos : positions) {\n            int L = cc.get(pos[0]);\n            int R = cc.get(pos[0] + pos[1] - 1);\n            int h = tree.query(L, R) + pos[1];\n            tree.update(L, R, h);\n            best = Math.max(best, h);\n            res.add(best);\n        }\n        return res;\n    }\n    \n    private Map<Integer, Integer> coorCompression(int[][] positions) {\n        Set<Integer> set = new HashSet<>();\n        for (int[] pos : positions) {\n            set.add(pos[0]);\n            set.add(pos[0] + pos[1] - 1);\n        }\n        List<Integer> list = new ArrayList<>(set);\n        Collections.sort(list);\n        Map<Integer, Integer> map = new HashMap<>();\n        int t = 0;\n        for (int pos : list) map.put(pos, t++);\n        return map;\n    }\n    \n    class SegmentTree {\n        int[] tree;\n        int N;\n        \n        SegmentTree(int N) {\n            this.N = N;\n            int n = (1 << ((int) Math.ceil(Math.log(N) / Math.log(2)) + 1));\n            tree = new int[n];\n        }\n        \n        public int query(int L, int R) {\n            return queryUtil(1, 0, N - 1, L, R);\n        }\n        \n        private int queryUtil(int index, int s, int e, int L, int R) {\n            // out of range\n            if (s > e || s > R || e < L) {\n                return 0;\n            }\n            // [L, R] cover [s, e]\n            if (s >= L && e <= R) {\n                return tree[index];\n            }\n            // Overlapped\n            int mid = s + (e - s) / 2;\n            return Math.max(queryUtil(2 * index, s, mid, L, R), queryUtil(2 * index + 1, mid + 1, e, L, R));\n        }\n        \n        public void update(int L, int R, int h) {\n            updateUtil(1, 0, N - 1, L, R, h);\n        }\n        \n        private void updateUtil(int index, int s, int e, int L, int R, int h) {\n            // out of range\n            if (s > e || s > R || e < L) {\n                return;\n            }\n            tree[index] = Math.max(tree[index], h);\n            if (s != e) {\n                int mid = s + (e - s) / 2;\n                updateUtil(2 * index, s, mid, L, R, h);\n                updateUtil(2 * index + 1, mid + 1, e, L, R, h);\n            }\n        }\n    }\n}\n```\nSegment tree with lazy propagation and coordinates compression: This code is easy to add if you already got the code above.\n```\nclass Solution {\n    public List<Integer> fallingSquares(int[][] positions) {\n        int n = positions.length;\n        Map<Integer, Integer> cc = coorCompression(positions);\n        int best = 0;\n        List<Integer> res = new ArrayList<>();\n        SegmentTree tree = new SegmentTree(cc.size());\n        for (int[] pos : positions) {\n            int L = cc.get(pos[0]);\n            int R = cc.get(pos[0] + pos[1] - 1);\n            int h = tree.query(L, R) + pos[1];\n            tree.update(L, R, h);\n            best = Math.max(best, h);\n            res.add(best);\n        }\n        return res;\n    }\n    \n    private Map<Integer, Integer> coorCompression(int[][] positions) {\n        Set<Integer> set = new HashSet<>();\n        for (int[] pos : positions) {\n            set.add(pos[0]);\n            set.add(pos[0] + pos[1] - 1);\n        }\n        List<Integer> list = new ArrayList<>(set);\n        Collections.sort(list);\n        Map<Integer, Integer> map = new HashMap<>();\n        int t = 0;\n        for (int pos : list) map.put(pos, t++);\n        return map;\n    }\n    \n    class SegmentTree {\n        int[] tree;\n        int[] lazy;\n        int N;\n        \n        SegmentTree(int N) {\n            this.N = N;\n            int n = (1 << ((int) Math.ceil(Math.log(N) / Math.log(2)) + 1));\n            tree = new int[n];\n            lazy = new int[n];\n        }\n        \n        public int query(int L, int R) {\n            return queryUtil(1, 0, N - 1, L, R);\n        }\n        \n        private int queryUtil(int index, int s, int e, int L, int R) {\n            if (lazy[index] != 0) {\n                // apply lazy to node\n                int update = lazy[index];\n                lazy[index] = 0;\n                tree[index] = Math.max(tree[index], update);\n                // check if this is leaf\n                if (s != e) {\n                    lazy[2 * index] = Math.max(lazy[2 * index], update);\n                    lazy[2 * index + 1] = Math.max(lazy[2 * index + 1], update);\n                }\n            }\n            // out of range\n            if (s > e || s > R || e < L) {\n                return 0;\n            }\n            // [L, R] cover [s, e]\n            if (s >= L && e <= R) {\n                return tree[index];\n            }\n            // Overlapped\n            int mid = s + (e - s) / 2;\n            return Math.max(queryUtil(2 * index, s, mid, L, R), queryUtil(2 * index + 1, mid + 1, e, L, R));\n        }\n        \n        public void update(int L, int R, int h) {\n            updateUtil(1, 0, N - 1, L, R, h);\n        }\n        \n        private void updateUtil(int index, int s, int e, int L, int R, int h) {\n            if (lazy[index] != 0) {\n                // apply lazy to node\n                int update = lazy[index];\n                lazy[index] = 0;\n                tree[index] = Math.max(tree[index], update);\n                // check if this is leaf\n                if (s != e) {\n                    lazy[2 * index] = Math.max(lazy[2 * index], update);\n                    lazy[2 * index + 1] = Math.max(lazy[2 * index + 1], update);\n                }\n            }\n            // out of range\n            if (s > e || s > R || e < L) {\n                return;\n            }\n            if (s >= L && e <= R) {\n                tree[index] = Math.max(tree[index], h);\n                if (s != e) {\n                    lazy[2 * index] = Math.max(lazy[2 * index], h);\n                    lazy[2 * index + 1] = Math.max(lazy[2 * index + 1], h);\n                }\n                return;\n            }\n            int mid = s + (e - s) / 2;\n            updateUtil(2 * index, s, mid, L, R, h);\n            updateUtil(2 * index + 1, mid + 1, e, L, R, h);\n            tree[index] = Math.max(tree[2 * index], tree[2 * index + 1]);\n        }\n    }\n}\n```
[]