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. Largest Rectangle
  2. Discussions

Largest Rectangle

Sort by

recency

|

28 Discussions

|

  • CS_2212256_T
     + 0 comments
    #!/bin/python3

import os
import sys

def largestRectangle(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel value to flush the stack at the end

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else (i - stack[-1] - 1)
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())
    h = list(map(int, input().rstrip().split()))

    result = largestRectangle(h)

    fptr.write(str(result) + '\n')
    fptr.close()

  • ds1b_1641540100
     + 0 comments

    Largest Rectangle solution in Python

    #!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'largestRectangle' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts INTEGER_ARRAY h as parameter.
#

def largestRectangle(heights):
    # Write your code here
    stack = list()
    index = 0
    largest_rectangle = 0
    while index < len(heights):
        if (not stack) or (heights[stack[-1]] <= heights[index]):
            stack.append(index)
            index += 1
        else:
            top_of_stack = stack.pop()
            area = (heights[top_of_stack] *
                    ((index - stack[-1] - 1) if stack else index))
            largest_rectangle = max(largest_rectangle, area)

    while stack:
        top_of_stack = stack.pop()
        area = (heights[top_of_stack] *
                ((index - stack[-1] - 1) if stack else index))
        largest_rectangle = max(largest_rectangle, area)

    return largest_rectangle


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    h = list(map(int, input().rstrip().split()))

    result = largestRectangle(h)

    fptr.write(str(result) + '\n')

    fptr.close()

  • lpatterson762
     + 0 comments

    Same as LeetCodes "Largest Rectangle in Histogram" https://leetcode.com/problems/largest-rectangle-in-histogram/submissions/1092315461/

        stack = [-1]
    h.append(0)
    maxA = 0
    for i in range(len(h)):
        while h[i] < h[stack[-1]]:
            height = h[stack.pop()]
            width = i - stack[-1] -1
            if height * width > maxA:
                maxA = height * width
        stack.append(i)
    return maxA

  • vdaons
     + 0 comments

    Python, recursive, not O(N) but short.

    def largestRectangle(h):
    if h:
        i = min(range(len(h)), key=h.__getitem__)
        return max(h[i] * len(h), largestRectangle(h[:i]), largestRectangle(h[i+1:]))
    return 0

  • cs_iot1b1550052
     + 0 comments

    def largestRectangle(h): # Write your code here stack = [0] area = 0 top = 0 h.append(0) for i in range(1, len(h)):

        if h[i] >= h[stack[-1]]:
        stack.append(i)

    else:
        while stack and h[i] < h[stack[-1]]:
            last = stack.pop()
            if stack:
                area = (i - stack[-1]-1) * h[last]
            else:
                area = i * h[last]
            if  area > top:
                top = area
        stack.append(i)

return top