Stokastik

Machine Learning, AI and Programming

Leetcode : The Skyline Problem

Problem Statement

Solution:

It was actually difficult for me to come up with the brute force approach to solve the skyline problem. But that does not mean that getting to the efficient solution was easy. I struggled a lot in order to come to the efficient solution because there were so many scenarios that I was missing out on initially. Coming to think of it, the brute force approach would be to check for all possible start and end points for each building and then verify whether the start or the end point is a key point or not. This should work because all key points is either a start or an end point.

A starting point S with height H, is a key point if H is maximum among all building that are crossing through S. For each input triplet [Si, Ei, Hi], check with all other inputs [Sj, Ej, Hj] (j != i) such that Sj <= Si <= Ej, then [Si, Hi] is a key point if Hj <= Hi or there are no such triplets [Sj, Ej, Hj]. But for the ending points, a pair [E, H] can be a key point for a building X, if E is the ending point for X and H is the height of the building Y, such that height of X is greater than H and X and Y 'intersects' and there are no other buildings crossing through point E having height greater than H.

Red Points indicate Key Points

For each ending point E for a building X, there can be at-max one pair [E, H] which can be a key point. If there multiple H for same E i.e. X intersects with multiple shorter buildings, then take only the H that is maximum. For N inputs, there are 2N start and end point pairs [S, H] and [E, H] and thus the run time complexity for this approach is O(N2). We can reduce the run-time complexity to O(N*logN) by using ordering of buildings information.

We will define a 'block' as follows. Any triplet [S, E, H] where S < E and H > 0 is a 'block'. This triplet can either be one of the input buildings or a sub-part of an input building. Also a triplet [S, E, H] is block if and only if [S, H] is a key point. Thus we will find the key points by constructing the blocks incrementally.

When the buildings are sorted according to their starting positions, we can draw the skyline as follows:

  • If the ending point of the current block X is less than the starting point of the next block Y, the pair [SX, HX] for the current block becomes a key point. Also the pair [EX, 0] becomes a key point. Move to the next block.

Blocks are separated

  • If the ending point of the current block X is greater than or equal to the starting point of the next block Y:
    • If the heights of X and Y are same, i.e HX == HY, then merge them and create a new block with SX' = SX and EX,= max(EX, EY). In the next iteration start with the new block.
    • If HX < HY, then add the pair [SX, HX] to the list of key points.
      • If EX <= EY, then simply move on to the next block and start from Y in the next iteration.
      • If EX > EY, then we need to create a new block, that begins after Y with the triplet [EY, EX, HX]. Add the new block such that the ordering of the blocks according to the starting positions is maintained. Thus we need to store the blocks in a min-heap data structure.

The two cases where HX < HY

    • If HX > HY, then :
      • If EX == SY, then add the pair [SX, HX] to the list of key points. Move on to the next block.
      • If EX < EY, then modify the block Y to the following triplet [EX, EY, HY]. Stay with the current block in next iteration.
      • If EX >= EY, then don't modify the block Y but stay with the current block in next iteration.

The 3 cases where HX > HY

The python implementation for the above algorithm is as follows:

import heapq
class Solution(object):
    def getSkyline(self, buildings):
        if len(buildings) == 0:
            return []
        
        heapq.heapify(buildings)
        key_points = []
        
        while len(buildings) > 0:
            x = heapq.heappop(buildings)
            if len(buildings) == 0:
                key_points.append(x)
                break
                
            y = buildings[0]
            
            if x[1] < y[0]:
                key_points.append(x)
                key_points.append([x[1], y[0], 0])
            
            else:
                if x[2] == y[2]:
                    y = heapq.heappop(buildings)
                    z = x
                    if x[1] < y[1]:
                        z = [x[0], y[1], x[2]]
                    heapq.heappush(buildings, z)
                        
                elif x[2] < y[2]:
                    if y[0] > x[0]:
                        key_points.append([x[0], y[0], x[2]])
                        
                    if x[1] > y[1]:
                        heapq.heappush(buildings, [y[1], x[1], x[2]])
                        
                else:
                    if x[1] == y[0]:
                        key_points.append(x)
                    else:
                        y = heapq.heappop(buildings)
                        if x[1] < y[1]:
                            y[0] = x[1]
                            heapq.heappush(buildings, y)
                        heapq.heappush(buildings, x)  
        
        last = key_points[-1]
        key_points = [[x, y] for x, _, y in key_points] + [[last[1], 0]]
        
        return key_points

Since we are adding new blocks in between and also updating old blocks, thus to keep the blocks sorted in the starting positions we use min-heap data structure to index the blocks. Since the complexity for adding and deleting from min-heap is O(logN), thus the overall run-time complexity of the above code is O(N*logN).

Categories: PROBLEM SOLVING

Tags: , , , ,

Leave a Reply