Largest Rectangle in Histogram

Question: Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

You may read the full question here.

Approach 1: Let’s begin with the naive solution —

//Approach 1:
//Runtime: 679ms
//Memory usage: 42.4MB
class Solution {
    public int largestRectangleArea(int[] heights) {
        int largestArea = 0;
        for(int start = 0; start<heights.length; start++){
            int shortestHeight = heights[start];
            for(int end = start; end<heights.length; end++){
                if(shortestHeight>heights[end]){
                    shortestHeight = heights[end];
                }
                largestArea = Math.max(largestArea, shortestHeight * (end - start + 1));
            }
        }
        return largestArea;
    }
}

Approach 2: A little improvisation using recursion —

//Approach 2:
//Runtime: 234ms
//Memory usage: 43.5MB
class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights.length>0){
            return approach(heights, 0, heights.length-1);    
        }
        return 0;
    }
    
    private int approach(int[] heights, int start, int end){
        if(start==end){
            return heights[start];
        }
        int[] s = findSmallest(heights, start, end);
        int smallestVal = s[0];
        int smallestInd = s[1];
        
        //Full Length
        int fullArea = smallestVal * (end-start+1);
        //Left
        int leftArea = approach(heights, start, Math.max(smallestInd-1, start));
        //Right
        int rightArea = approach(heights, Math.min(smallestInd+1, end), end);
        return Math.max(fullArea, Math.max(leftArea, rightArea));
    }
    
    private int[] findSmallest(int[] array, int start, int end){
        int smallest = Integer.MAX_VALUE;
        int index = -1;
        for(int i = start;i<=end; i++){
            if(smallest>array[i]){
                smallest = array[i];
                index = i;
            }
        }
        return new int[]{smallest, index};
    }
}

Long way to go…

Find more posts here.

Cheers & Chao!