Draw the skyline [25.29 - v2.0.0] - space complexity and amount of code

#1

[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;
}
0 Likes

#2

I’m having trouble understanding what you’re asking, can you clarify? For example, are you saying the code you provided has better space and time complexity than the solution in the book?

0 Likes

#3

Assuming I’m right with my understanding, I was wondering why the solution in book is the way it is where in could be simpler. Again, if my understanding is correct then solution that I posted is simpler to understand (subjective) and has better space complexity. Put it all together, problem seams to be much simpler as it’s presented in the book.

0 Likes

#4

Just wondering if this is the same problem as 16.15 from the 1st edition? Or is it a variant?
Can you maybe explain your algorithm?

0 Likes