O(nlogn) solution with 2 min-heaps, and 1 max-heap.

  • 0

    I haven't looked at the O(n) solution, since I wanted to solve this myself. I came up with a O(nlogn) algorithm, which is better than the O(n^2) naive one. OJ accepted it, so I'm happy. :)

    I simply thought that it would be interesting to present, so I'm posting it below.

    This solution involves 3 heaps (2 min heaps and 1 max heap):
    1st. min heap on height of lines.
    2nd. min heap on x-crd of lines.
    3rd. max heap on x-crd of lines.

    Initially I enter all lines (x-crd, height) into all three heaps. The I start picking from the smallest height line in the htHeap, and find out which line from the min x-crd and max-x-crd heaps still exist. Accordingly, I compute the area with these two candidates, and record maxarea if either are bigger. Then I mark the line deleted.

    Even though there are 2 nested while loops, the total runtime is amortized O(nlogn). A simple way to see this is that at most all lines will be deleted from all 3 heaps in the nested while loops before termination. This involves 3 * n * logn = O(nlogn) amortized time. In some iterations only 1 line is deleted, in some iterations many many lines are deleted.

    class Solution {
        typedef int Height;
        typedef int XCrd;
        typedef std::pair<XCrd, Height> Line;
        class CmpHeight {
            bool operator() (const Line& lhs, const Line& rhs) {
                return (lhs.second > rhs.second);
        class CmpXLesser {
            bool operator() (const Line& lhs, const Line& rhs) {
                return (lhs.first > rhs.first);
        class CmpXGreater {
            bool operator() (const Line& lhs, const Line& rhs) {
                return (lhs.first < rhs.first);
        int maxArea(vector<int>& height) {
            std::priority_queue<Line, vector<Line>, CmpHeight>   htHeap; //heap for min height of lines
            std::priority_queue<Line, vector<Line>, CmpXLesser>  xLoHeap;//heap for min x-crd of lines
            std::priority_queue<Line, vector<Line>, CmpXGreater> xHiHeap;//heap for max x-crd of lines
            for(unsigned int i=1; i <= height.size(); i++) {
                Line l = make_pair(i, height[i-1]);
            vector<int> deleted(height.size(), false);
            int maxarea=0;
            while (!htHeap.empty()) {
                Line l = htHeap.top(); htHeap.pop(); //get line with lowest height
                int xmin, xmax;                      //min and max x that are not deleted
                //get min x crd of line still available
                while (deleted[xLoHeap.top().first-1]) {
                xmin = xLoHeap.top().first;
                //get max x crd of line still available
                while (deleted[xHiHeap.top().first-1]) {
                xmax = xHiHeap.top().first;
                int area1 = l.second * abs(l.first - xmin);
                int area2 = l.second * abs(l.first - xmax);
                if (area1 > maxarea) maxarea = area1;
                if (area2 > maxarea) maxarea = area2;
                deleted[l.first-1] = true;
            return maxarea;

Log in to reply

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