Posts Largest Rectangle in Histogram
Post
Cancel

Largest Rectangle in Histogram

Problem Description

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

leetcode

Solution

snapshot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
class Solution {
    
    public int largestRectangleArea(int[] heights) {

        int n = heights.length;

        //store the index of the graph which is nearest smallest than the current bar on the left side
        int[] nearestOnLeft = getNearestSmallerOnLeftIndex(heights);

        //store the index of the graph which is nearest smallest than the current bar on the right side
        int[] nearestOnRight = getNearestSmallerOnRightIndex(heights);

        //init
        int maxArea = 0;

        //loop through all the bars
        for(int i=0; i<n; i++){
            
            //current height of the bar
            int h = heights[i];

            //init
            int leftArea = 0;
            int rightArea = 0;

            //if there is no bar on left which is smaller than the current one, we can consider everything towards left
            if(nearestOnLeft[i] == -1){
                leftArea = h * (i+1);
            //else, multiply current height by distance from the nearest bar which has smaller size on left 
            }else{
                leftArea = h * (i-nearestOnLeft[i]);
            }

            //if there is no bar on right which is smaller than the current one, we can consider everything towards right
            if(nearestOnRight[i] == -1){
                rightArea = h * (n-i);
            //else, multiply current height by distance from the nearest bar which has smaller size on right 
            }else{
                rightArea = h * (nearestOnRight[i]-i);
            }

            //the current bar will be included in both leftArea and rightArea, so remove that overlap
            int currentTotal = leftArea + rightArea - h;

            //update maxArea possible till now
            maxArea = Math.max(maxArea, currentTotal);

        }
        
        return maxArea;
        
    }

    private static int[] getNearestSmallerOnRightIndex(int[] a) {

        int n = a.length;
        int[] nearestSmaller = new int[n];

        Arrays.fill(nearestSmaller, -1);

        Stack<Integer> stack = new Stack<>();
        stack.push(n-1);

        for(int i=n-2; i>=0; i--){
            if(a[stack.peek()] < a[i]){
                nearestSmaller[i] = stack.peek();
                stack.push(i);
            }else{
                while(!stack.isEmpty() && a[stack.peek()] >= a[i]){
                    stack.pop();
                }

                if(!stack.isEmpty()){
                    nearestSmaller[i] = stack.peek();
                }//else it will be -1

                stack.push(i);

            }
        }

        return nearestSmaller;

    }

    private static int[] getNearestSmallerOnLeftIndex(int[] a) {

        int n = a.length;
        int[] nearestSmaller = new int[n];

        Arrays.fill(nearestSmaller, -1);

        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for(int i=1; i<n; i++){
            if(a[stack.peek()] < a[i]){
                nearestSmaller[i] = stack.peek();
                stack.push(i);
            }else{
                while(!stack.isEmpty() && a[stack.peek()] >= a[i]){
                    stack.pop();
                }

                if(!stack.isEmpty()){
                    nearestSmaller[i] = stack.peek();
                }//else it will be -1

                stack.push(i);

            }
        }

        return nearestSmaller;

    }


}
This post is licensed under CC BY 4.0 by the author.