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;
}