Accepted 38ms Java solution O(nlogn) with explanation


  • 2
    S

    There is a clear invariant in this problem: for any x-coordinate, the only visible building, according to the statement, will be the highest one. Hence, we might need an efficient way to get the highest building for every possible x-coordinate. Now the first question arises, do we need to check all possible x-coordinates? The problem states that intervals with equal height should be merged into a single one, thus, there is no point in performing a check in all x-coordinates; instead, we need a way to identify the points where the highest available building potentially changes, and those points turn out to be the beginning/end of every building. This is because, as all buildings have constant height, a building becomes the highest only when it appears (and there is no one higher), or when the current highest ends (and again there is no one higher). With this in mind, consider a sorted (by the x-coordinate) array of beginnings/ends for all buildings and process such events in the following way:

    • Events with same x-coordinate should be processed together.
    • Every time we find a beginning, we add its height to some collection with the currently available heights.
    • Every time we find an end, we remove its height from that collection.

    What we are doing here is a line swept algorithm: we move an imaginary line along the x-axis, stopping it just at some discrete points where something crucial happens. Here after processing all events taking place at some x-coordinate X, we query our collection for the largest available height H, and if it is larger than our current largest, we update it and add the pair X, H to the result list. And that's it :). The heights collection needs to be efficient on adding, removing, and querying for the largest value. Also, we have to manage the fact that we can have duplicates and we need to consider all of them. In order to achieve O(log n) complexity for those operations, we may code a segment tree (tree leaves will be all buildings), use a TreeSet of some custom <building, height> pair representation, or just use a TreeMap of <height, current count> (I have chosen this one in order to avoid some extra coding). Since we have exactly 2N events, we sort them, and then for each one we perform a constant number of O(logn) operations (from 1 to 3 depending on your implementation), overall complexity is O(nlogn), being n the number of buildings.

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.TreeMap;
    
    public class Solution {
    	public List<int[]> getSkyline(int[][] buildings) {
    		TreeMap<Integer, Integer> availableHeights = new TreeMap<>();
    		List<int[]> view = new ArrayList<>(buildings.length);
    		int N = buildings.length;
    		if (N == 0) {
    			return view;
    		}
    		Event[] events = new Event[N << 1];
    		for (int i = 0; i < N; ++i) {
    			int[] building = buildings[i];
    			events[i << 1] = new Event(building[0], building[2], false);
    			events[1 + (i << 1)] = new Event(building[1], building[2], true);
    		}
    		Arrays.sort(events);
    		int currentHeight = 0;
    		availableHeights.put(0, 1);
    		for (int i = 0, j; i < N << 1; i = j) {
    			for (j = i; j < N << 1 && events[i].x == events[j].x; ++j) {
    				Event event = events[j];
    				if (event.closing) {
    					int counter = availableHeights.get(event.height);
    					if (counter == 1) {
    						availableHeights.remove(event.height);
    					} else {
    						availableHeights.put(event.height, counter - 1);
    					}
    				} else {
    					Integer counter = availableHeights.get(event.height);
    					if (counter == null) {
    						availableHeights.put(event.height, 1);
    					} else {
    						availableHeights.put(event.height, counter + 1);
    					}
    				}
    			}
    			int x = events[i].x;
    			int height = availableHeights.lastKey();
    			if (height != currentHeight) {
    				view.add(new int[] { x, height });
    				currentHeight = height;
    			}
    		}
    		return view;
    	}
    }
    
    class Event implements Comparable<Event> {
    	int x, height;
    	boolean closing;
    
    	public Event(int a, int b, boolean c) {
    		x = a;
    		height = b;
    		closing = c;
    	}
    
    	@Override
    	public int compareTo(Event that) {
    		return x != that.x ? x - that.x : Boolean.compare(closing, that.closing);
    	}
    }

  • 0
    B

    I tried to understand how to solve this problem for weeks... no luck. Then I read this solution. Very Elegant


Log in to reply
 

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