# SE103 Week 3 Post Session Solutions

[Smallest Range Covering Elements from K Lists](https://hackmd.io/4eeKdiurTPKhQRXvQIKa8Q#Smallest-Range-Covering-Elements-from-K-Lists)
[Largest Rectangle in Histogram](https://hackmd.io/4eeKdiurTPKhQRXvQIKa8Q#Largest-Rectangle-in-Histogram)

## Smallest Range Covering Elements from K Lists
Walkthrough question, solution [here](https://hackmd.io/EULh3y_RTHKMUyi6-B5ghQ).

## Largest Rectangle in Histogram
**Java**

/*
For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the
rectangle. If we calculate such area for every bar ‘x’ and find the maximum of
all areas, our task is done. How to calculate area with ‘x’ as smallest bar?
We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’
and index of first smaller bar on right of ‘x’. Let us call these indexes as
‘left index’ and ‘right index’ respectively.

We traverse all bars from left to right, maintaining a stack of bars. Every bar
is pushed to the stack once. A bar is popped from stack when we see a bar of
smaller  height. When a bar is popped, we calculate the area with the popped bar
as smallest bar. How do we get left and right indexes of the popped bar? The
current index tells us the ‘right index’ and index of previous item in stack is
the ‘left index’.
*/

public class Solution {
    public int largestRectangleArea(int[] height) {
        int len = height.length;
        Stack<Integer> s = new Stack<Integer>();
        int maxArea = 0;
        for(int i = 0; i <= len; i++){
            int h = (i == len ? 0 : height[i]);
            if (s.isEmpty() || h >= height[s.peek()]) {
                s.push(i);
            } else {
                int tp = s.pop();
                maxArea = Math.max(maxArea, height[tp] *
                  (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;
            }
        }
        return maxArea;
    }
}

**Python**

class Solution(object):
    def largestRectangleArea(self, heights):
        temp = []
        stack = []
        heights.append(float('-inf'))
        for i, h in enumerate(heights):
            cpos = i
            while stack and h < stack[-1][0]:
                ch, cpos = stack.pop()
                temp.append(ch*(i - cpos ))
            stack.append([h, cpos])
        return max(temp) if temp else 0