Discussion on Largest Rectangle Challenge

Sort by

recency

|

617 Discussions

|

2 weeks ago+ 0 comments

This is one of the hard ones. I watched a YouTube video on how to solve it. And here is my code. It is pretty descriptive IMHO. Easy to read. The key is whenever the height decreases, the previous taller builds effectively reached the end of their lives. And we can calculate their max areas. And we can extend the starting position of the new lower height to the leftest one that is 'killed' by this new lower height. Adding a '0' to the end of the height so that at the end, all the leftover heights are killed by this '0' and we can calculate their max areas.

def largestRectangle(h):

h.append(0)
alive = [[0, h[0]]]
maxArea = 0

for pos, val in enumerate(h):
    if pos == 0:
        continue
    if len(alive)>0 and val < alive[-1][1]:
        while len(alive)>0 and val < alive[-1][1]:
            dead = alive.pop()
            maxArea = max(maxArea, dead[1]*(pos-dead[0]))
            start = dead[0]

        alive.append([start, val])
    else:
        alive.append([pos, val])    
return maxArea

1 month ago+ 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);
    }

}

2 months ago+ 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

2 months ago+ 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

4 months ago+ 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;
}

Sort by

|

617 Discussions

|

Cookie support is required to access HackerRank