java solution (average O(nlogn)) with explanation


  • 0
    S

    basic idea is use three linked lists to store start, end and height of boxes on the floor. When a new box drops, use binary search to find out which boxes on the floor are "covered" by it, to figure out the height of the new box. After that, replace the "covered" boxes by the new box (which is supposed to be higher), has to deal with the edge case that some box might only partially "covered" by the new box.

    Average time complexity is O(nlogn), if new box only covers a few box on the floor. Worst case time complexity is O(n^2), if new box covers O(n) box on the floor

    class Solution {
        public List<Integer> fallingSquares(int[][] positions) {
            List<Integer> result = new ArrayList<>();
            int maxHeight = 0;
            
            LinkedList<Integer> starts = new LinkedList<>();
            LinkedList<Integer> ends = new LinkedList<>();
            LinkedList<Integer> heights = new LinkedList<>();
    
            for (int[] position : positions) {
                int left = position[0];
                int right = position[0] + position[1];
                
                int startIndex = Collections.binarySearch(starts, left);
                if (startIndex < 0) {
                    startIndex = -(startIndex + 1);
                }
                if (startIndex > 0 && ends.get(startIndex - 1) > left) {
                    startIndex--;
                }
                int endIndex = Collections.binarySearch(ends, right);
                if (endIndex < 0) {
                    endIndex = -(endIndex + 1) - 1;    
                }
                if (endIndex + 1 < starts.size() && starts.get(endIndex + 1) < right) {
                    endIndex++;
                }
                
                if (endIndex < startIndex) {
                    starts.add(startIndex, left);
                    ends.add(startIndex, right);
                    heights.add(startIndex, position[1]);
                    maxHeight = Math.max(maxHeight, position[1]);
                } else {
                    int height = 0;
                    for (int i = startIndex; i <= endIndex; i++) {
                        height = Math.max(height, heights.get(i));
                    }
                    height += position[1];
                    if (starts.get(startIndex) < left) {
                        int end = ends.get(startIndex);
                        ends.set(startIndex, left);
                        startIndex++;
                        //why the above two lines are not enough?  
                        //it does not cover the case a falling small square covers a middle segment of a large square on the floor
                        starts.add(startIndex, left);
                        ends.add(startIndex, end);
                        heights.add(startIndex, heights.get(startIndex - 1));
                        endIndex++; // because a new square is inserted
                    }
                    if (ends.get(endIndex) > right) {
                        starts.set(endIndex, right);
                        endIndex--;
                    }
                    for (int i = endIndex; i >= startIndex; i--) {
                        starts.remove(i);
                        ends.remove(i);
                        heights.remove(i);
                    }
                    starts.add(startIndex, left);
                    ends.add(startIndex, right);
                    heights.add(startIndex, height);
                    maxHeight = Math.max(maxHeight, height);
                }
                result.add(maxHeight);
            }
            return result;
    
        }
    }
    

  • 0

    It is inaccurate to say average as worst case could happen a lot. Besides, remove action on List in Java will shift all the elements after the object to left, even if you do it only once per loop, it would cost an extra O(n).


Log in to reply
 

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