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

|

616 Discussions

|

  • rajivaiyer
     + 1 comment

    Here's my Java 8 solution, passing all test cases, for Max Score of 50.

    While solving this problem, I could think of three approaches: two using Explicit Stacks, while one using Implicit Stack (via Recursion). All three of them pass ALL Test-Cases, for a Max Score of 50. All of them have been provided in the code, with some explanatory comments.

    class Result {

    // SIMPLEST & BEST APPROACH
    // Largest Rectangle using Linear Iteration, with Stack
    // Passes ALL HackerRank Test-Cases. For Max Score of 50
    // Time-Complexity : WC: O(n) | AC: O(n)
    // Space-Complexity: WC: O(n)   | AC: O(log n) | i.e. Explicit Stack Depth

    public static long solveSimpleIterativeWithStack(List<Integer> h) {
        int n = h.size();

        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;

        for (int i = 0; i <= n; i++) {
            long curHeight = ((i == n) ? 0 : h.get(i));
            while (!stack.isEmpty() && curHeight < h.get(stack.peek())) {
                int height = h.get(stack.pop());
                int width = (stack.isEmpty() ? i : (i - stack.peek() - 1));
                maxArea = Math.max(maxArea, (long) height * width);
            }
            stack.push(i);
        }

        return maxArea;
    }


    // Largest Rectangle using Divide & Conquer (Recursive) Approach
    //      No Stacks used in this Solution.
    // Passes ALL HackerRank Test-Cases. For Max Score of 50
    // Time-Complexity : WC: O(n^2) | AC: O(n * log n)
    // Space-Complexity: WC: O(n)   | AC: O(log n) | i.e. Recursion Depth
    private static long solveDivNCnqRecursive(List<Integer> h, int start, int end) {
        if (start > end) {
            return 0;
        }

        // Find index of minimum height in current range
        int minIndex = start;
        for (int i = (start + 1); i <= end; i++) {
            if (h.get(i) < h.get(minIndex)) {
                minIndex = i;
            }
        }

        // Area using the minimum height across entire range
        long areaWithMin = (long) (h.get(minIndex) * (end - start + 1));

        // Recurse on left and right sublists
        long leftArea = solveDivNCnqRecursive(h, start, minIndex - 1);
        long rightArea = solveDivNCnqRecursive(h, minIndex + 1, end);

        return Math.max(areaWithMin, Math.max(leftArea, rightArea));
    }


    // Largest Rectangle using Divide & Conquer (Non-Recursive / Iterative) Approach
    //      Stack is used to simulate Recursion
    // Passes ALL HackerRank Test-Cases. For Max Score of 50
    // Time-Complexity : WC: O(n^2) | AC: O(n * log n)
    // Space-Complexity: WC: O(n)   | AC: O(log n) | i.e. Explicit Stack Depth
    public static long solveDivNCnqIterative(List<Integer> h) {
        long maxArea = 0;

        Stack<int[]> stack = new Stack<>(); // each element: [start, end]
        stack.push(new int[]{0, h.size() - 1});

        while (!stack.isEmpty()) {
            int[] range = stack.pop();
            int start = range[0], end = range[1];
            if (start > end) continue;

            // Find min index in current range
            int minIndex = start;
            for (int i = start + 1; i <= end; i++) {
                if (h.get(i) < h.get(minIndex)) {
                    minIndex = i;
                }
            }

            // Compute area with this min height
            long areaWithMin = (long) h.get(minIndex) * (end - start + 1);
            maxArea = Math.max(maxArea, areaWithMin);

            // Push left and right ranges
            stack.push(new int[]{start, minIndex - 1});
            stack.push(new int[]{minIndex + 1, end});
        }

        return maxArea;
    }

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

    public static long largestRectangle(List<Integer> h) {
        // Write your code here
        return solveSimpleIterativeWithStack(h);
        // return solveDivNCnqRecursive(h, 0, h.size() - 1);
        // return solveDivNCnqIterative(h);
    }

}

  • ayeayeaye
     + 0 comments

    def largestRectangle3(h):

    area = float("-inf")
numOfBuildings = 0

minHeight = float("inf")

for i in range(len(h)):
    numOfBuildings += 1
    minHeight = min(minHeight, h[i])

    for j in range(i-1, -1,-1):
        if  h[j] >= minHeight:
            numOfBuildings += 1
        else:
            break     

    for j in range(i+1, len(h)):    
        if  h[j] >= minHeight:
            numOfBuildings += 1
        else:
            break

    area = max(area, (numOfBuildings * minHeight)) 
    numOfBuildings = 0
    minHeight = float("inf")       
return area

  • ayeayeaye
     + 0 comments

    Brute force solution without stacks that passes some tests but only fails with time limit exceeded. So, I'd say logic is correct. This is O(N!) algorithm, it generates all the possible arrangements of size 1, size 2, .... size N. Absolutely not optimal but it uncovers the neccessary thought pattern to solve optimally.

    def largestRectangle(h): maxRectangleArea = float("-inf")

    size = 1
while size <= len(h):
    for i in range(len(h)):
        minHeight = float("inf")

        if  i + size > len(h):
            break 

        for j in range(i,i+size):
            minHeight = min(minHeight, h[j])
        maxRectangleArea = max(maxRectangleArea, (minHeight * size))
    size += 1
return maxRectangleArea

  • 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