We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Stacks
  4. Largest Rectangle
  5. Discussions

Largest Rectangle

Sort by

recency

|

612 Discussions

|

  • ukande_kiran
     + 0 comments
    def largestRectangle(h):
	def checkR(number, index, h):
			counter = 0
			for element in range((index +1), len(h)):
					if number <= h[element]:
							counter+=1
					else:
							break
			return counter

	def checkL(number, index, h):
			counter = 0
			for element in reversed(range(index)):
					if number <= h[element]:
							counter+=1
					else:
							break
			return counter

  • emekaonwochei45
     + 0 comments

    def largestRectangle(h):

    def checkR(number, index, h):
    counter = 0
    for element in range((index +1), len(h)):
        if number <= h[element]:
            counter+=1
        else:
            break
    return counter

def checkL(number, index, h):
    counter = 0
    for element in reversed(range(index)):
        if number <= h[element]:
            counter+=1
        else:
            break
    return counter

maxArea = 0
currentArea = 0
# Write your code here
for i in range(len(h)):

    if (i==0):
        R = checkR(h[i], i, h)
        currentArea = (R+1)* h[i]

    elif (i==(len(h)-1)):
        L=checkL(h[i], i, h)
        currentArea = (L+1)*h[i]

    else:
        L = checkL(h[i], i, h)
        R = checkR(h[i], i, h)
        currentArea = (L+R+1)*h[i]

    maxArea = max(currentArea, maxArea)

return maxArea

  • manthansiwach201
     + 0 comments

    why my approach is incorrect?

    def largestRectangle(h): i=0 largestArea = 0 height = math.inf while h: if h[-1]>height: h.pop(-1) else: height= h.pop(-1) i+=1 area = height*i if area>largestArea: largestArea = area return largestArea

  • dehaka
     + 1 comment

    find the previous smaller element and the next smaller element in O(n) time

    total time requires 2 pass over the vector. so O(n) for total time.

    long largestRectangle(int n, const vector<long>& H) {
    vector<int> prevSmaller(n, -1), nextSmaller(n, n);
    stack<int> prev, next;
    prev.push(0);
    next.push(n-1);
    for (int i = n-2; i >= 0; i--) {
        while (!next.empty() and H[i] <= H[next.top()]) next.pop();
        if (!next.empty()) nextSmaller[i] = next.top();
        next.push(i);
    }
    long maxArea = H[0] * nextSmaller[0];
    for (int i = 1; i < n; i++) {
        while (!prev.empty() and H[i] <= H[prev.top()]) prev.pop();
        if (!prev.empty()) prevSmaller[i] = prev.top();
        prev.push(i);
        maxArea = max(maxArea, H[i] * (nextSmaller[i] - prevSmaller[i] - 1));
    }
    return maxArea;
}

    • gbednik
       + 2 comments

      Thank you very much for your code! Two comments here: 1) your time of execution will depend on the input, If for each h, both next smaller and previous smaller elements are not far, it may be O(n). But in the opposite extreme case, e.g. when H is sorted, it will be O(n^2) 2) Still why stacks? Why not find next smaller and previous smaller for each element naively? (see e.g. solution by faisalalotibi98). It would be the same running time

      • dehaka
         + 0 comments

        it does appear to be O(n^2) on 1st glance, that's wat i thought too when i first saw it. the naive way really takes O(n^2), the stack is there to guarantee O(n)

        but every number in H is pushed onto the stack exactly once, and is removed at most once, so the inner while loop add up to a maximum of 2n operations for all iterations of i

        i learned this algo from copilot, u should ask it, it'll explain to u in detail why its O(n) and not O(n^2). just type "c++ explain the previous smaller element algorithm and why its O(n)"

  • gbednik
     + 1 comment

    My code is working, but can anyone please explain to me in a simple way what this problem has to do with stacks?

    long largestRectangle(vector<int> h) 
{
    if (h.size() == 0)
        return 0;
    else if (h.size() == 1)
        return long(h[0]);
        
    int h_min = *min_element(h.begin() , h.end());
    long area_h_min = long(h_min) * long(h.size());
    
    vector<int> h_short;
    vector<int> possible_ans;
    possible_ans.push_back(area_h_min);
    
    for (int i = 0 ; i < h.size() ; i++)
    {
        if (  h[i] > h_min )
        {
            h_short.push_back(h[i]);
        }   
        else if (h[i] == h_min)
        {
            possible_ans.push_back(largestRectangle(h_short));
            h_short.clear();
        }
    }
    possible_ans.push_back(largestRectangle(h_short));
    h_short.clear();
    
    return *max_element(possible_ans.begin() , possible_ans.end());

}

    • dehaka
       + 0 comments

      ur method uses recursion and is definitely at least O(n^2), i cant be bothered to figure out the exact time of this recursion, but note that the brute force method is O(n^2).

      furthermore, there are issues with ur possible_ans, ur creating a local storage in each call stack, not a global storage and passing it by reference during recursion.

      the question wants O(n)

      if u had no time out its because the test cases are weak

      look at my method, its O(n)

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in