# java solution (average O(nlogn)) with explanation

• 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;

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) {
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
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);
}
maxHeight = Math.max(maxHeight, height);
}
• 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).