[25.29 - v2.0.0]
I found that the problem statement wasn’t very clear in turns how exactly the solution should look like (the figure helped a lot though). The solution part didn’t give me as such of insight as what the return value of the solution (the code) should be.
When I saw the return value (from the code) I was wondering why does it look like the problem is much simpler then it appears. Please correct me and pinpoint at my misunderstanding but it appears that code could be much less and space complexity can be reduced. Time complexity is same in turns of big O is same but still less iterations.
static class Building {
public int left;
public int right;
public int height;
public Building(int left, int right, int height) {
this.left = left;
this.right = right;
this.height = height;
}
}
public static List<Building> solve(List<Building> buildings) {
List<Building> result = new ArrayList<>();
int x = buildings.get(buildings.size() - 1).right;
for (int i = 0; i <= x; i++) {
int currH = 0, right = 0;
for (Building b : buildings) {
if (b.right < i) continue;
if (b.left > i) break;
if (x < b.right) x = b.right;
currH = Math.max(b.height, currH);
right = Math.max(b.right, right);
}
int idx = result.size() - 1;
if (idx < 0 || result.get(idx).height != currH) {
result.add(new Building(i, i, currH));
} else {
Building last = result.get(idx);
last.height = currH;
last.right = i;
}
}
return result;
}