# An initial solution, Java O(n^2), beat 95%

• The solution uses similar idea as in Google's skyline problem.

``````class Solution {
public List<Integer> fallingSquares(int[][] positions) {
List<Integer> res = new ArrayList<>();
if (positions == null || positions.length == 0) return res;
List<Point> skyLine = new ArrayList<>();
// Setup
int maxHeight = positions[0][1];
int height = 0;
for (int i = 1; i < positions.length; i++) {
int startPosition = positions[i][0];
int endPosition = positions[i][0] + positions[i][1];
int start = binarySearch(skyLine, startPosition);
height = start == -1 ? 0 : skyLine.get(start).y;
for (int j = start + 1; j < skyLine.size(); j++) {
if (skyLine.get(j).x >= endPosition) break;
height = Math.max(height, skyLine.get(j).y);
}
height += positions[i][1];
// clean up
int index = start + 1;
int endHeight = start == -1 ? 0 : skyLine.get(start).y;
while (index < skyLine.size() && skyLine.get(index).x < endPosition) {
endHeight = skyLine.get(index).y;
skyLine.remove(index);
}
int startIndex = -1;
if (start != -1 && skyLine.get(start).x == positions[i][0]) {
skyLine.get(start).y = height;
startIndex = start;
} else {
startIndex = start + 1;
}
if (startIndex + 1 < skyLine.size() && skyLine.get(startIndex + 1).x == endPosition) {
// do nothing
} else {
skyLine.add(startIndex + 1, new Point(endPosition, endHeight));
}
maxHeight = Math.max(height, maxHeight);
//for (Point p : skyLine) System.out.print(p + " # ");
//System.out.println();
}
return res;
}

private int binarySearch(List<Point> nums, int target) {
int lo = 0, hi = nums.size() - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (nums.get(mid).x > target) hi = mid - 1;
else lo = mid + 1;
}
return hi;
}

public static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return x + " " + y;
}
}
}
``````

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