17-Line O(n log n)-time O(n)-space C++ Accepted Easy Solution w/ Explanations


  • 46

    General idea:

    • Step 1:

      Use a multimap to sort all boundary points. For a start point of an interval, let the height be positive; otherwise, let the height be negative. Time complexity: O(n log n)

    • Step 2:

      Use a multiset (rather than a heap/priority_queue) to maintain the current set of heights to be considered. If a new start point is met, insert the height into the set, otherwise, delete the height. The current max height is the back() element of the multiset. For each point, the time complexity is O(log n). The overall time complexity is O(n log n).

    • Step 3:

      Delete the points with equal heights. Time: O(n)


    Time Complexity: O(n log n)

    Space Complexity: O(n)


    C++

    class Solution {
    public:
    	vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
    
            // Step 1:
    		multimap<int, int> coords;
    		for (const vector<int> & building : buildings) {
    			coords.emplace(building[0], building[2]);
    			coords.emplace(building[1], -building[2]);
    		}
    
            // Step 2:
    		multiset<int> heights = { 0 };
    		map<int, int> corners;
    		for (const pair<int, int> & p : coords) {
    			if (p.second > 0) {
    				heights.insert(p.second);
    			}
    			else {
    				heights.erase(heights.find(-p.second));
    			}
    			int cur_y = *heights.rbegin();
    			corners[p.first] = cur_y;
    		}
    
            // Step 3:
    		function<bool(pair<int, int> l, pair<int, int> r)> eq2nd = [](pair<int, int> l, pair<int, int> r){ return l.second == r.second;  };
    		vector<pair<int, int>> results;
    		unique_copy(corners.begin(), corners.end(), back_insert_iterator<vector<pair<int, int>>>(results), eq2nd);
    		return results;
    	}
    };
    

    In fact, the last two steps can be merged together:

    Yet another solution (C++):

    class Solution {
    public:
    	vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
    		multimap<int, int> coords;
    		for (const vector<int> & building : buildings) {
    			coords.emplace(building[0], building[2]);
    			coords.emplace(building[1], -building[2]);
    		}
    
    		multiset<int> heights = { 0 };
    		vector<pair<int, int>> corners;
    		int x = -1;
    		int y = 0;
    		for (const pair<int, int> & p : coords) {
    			if ((x >= 0) && (p.first != x) && (corners.empty() || (corners.rbegin()->second != y))) {
    				corners.emplace_back(x, y);
    			}
    
    			if (p.second >= 0) {
    				heights.insert(p.second);
    			}
    			else {
    				heights.erase(heights.find(-p.second));
    			}
    
    			x = p.first;
    			y = *heights.rbegin();
    		}
    		
    		if (!corners.empty()) {
    			corners.emplace_back(x, 0);
    		}
    		
    		return corners;
    	}
    };

  • 1
    Y

    the logic is simple and clear!

    thank you for providing us this beautiful solution.


  • 0
    S

    Great idea! One question: I think in the first step, multimap insertion is logN time, not constant. So the overall time for step 1 is O(nlogn), instead of O(n), right?


  • 0

    @stonezms Thank you very much for pointing out my mistake. I have revised my answer according to your comments.


  • 0
    B

    You don't need (corners.rbegin()->second != 0) in the last if statement, it will never add 0 at the end in for loop.


  • 0

    @bloomer Yes, it is. Thank you for pointing this out.


  • 1
    B

    @zhiqing_xiao so for coords, you don't really need a multimap, just a single vector will do - algorithrm based on @maplain and @jinwu's solutions here and here. But their java solutions erases elements in a priority_queue, which costs O(n) each time, and making their solution O(n^2).

    In C++, we can use multiset's find function combined with erase(), costing only O(log(n)), making our solution O(nlog(n)).

    I'm posting the algorithm under this thread to make it easier to see for all the C++ coders out there (only 16 lines!).

    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int,int>> heights;
            for (vector<int> b:buildings) {
                heights.push_back({b[0],-b[2]});
                heights.push_back({b[1],b[2]});
            }
            sort(heights.begin(),heights.end());
            
            int prev=0,cur;
            multiset<int> mset {0};
            vector<pair<int,int>> res;
            
            for (pair<int,int> h:heights) {
                if (h.second<0) mset.insert(-h.second);
                else mset.erase(mset.find(h.second));
                
                cur=*mset.rbegin();
                if (prev!=cur) {
                    res.push_back({h.first,cur});
                    prev=cur;
                }
            }
            
            return res;
        }
    };
    

  • 0

    @baselRus Yeah. vector+sort can be used to replace the multi-map. Thank you for your attention and sharing.


Log in to reply
 

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