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

|

613 Discussions

|

  • alkinemokiye
     + 0 comments

    took me 4 hours to do this, the logic is to find how much range that the number [i] can spread. spread is spread to max [index left] and to max [index right] starting from [i]. the valid range is when the number is higher than [i] number. i dont know if this acceptable since i dont use stack at all.

    public static long largestRectangle(List<Integer> h) {
		long result = Long.MIN_VALUE;
        
        for (int i = 0; i <= h.size() - 1; i++) {
            int left = i;
            int right = i;
            boolean goleft = true;
            boolean goright = true;
            
            while (goleft || goright) {
                int tempLeft = left - 1;
                if (tempLeft >= 0 && h.get(tempLeft) >= h.get(i)) {
                    left = tempLeft;
                } else {
                    goleft = false;
                }
                
                int tempRight = right + 1;
                if (tempRight <= h.size() - 1 && h.get(tempRight) >= h.get(i)) {
                    right = tempRight;
                } else {
                    goright = false;
                }
            }
            
            long tempResult = h.get(i) * (right - left + 1);
            if (result < tempResult) {
                result = tempResult;
            }
        }
    
        return result;
}

  • 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)"

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in