4. Largest Rectangle in Histogram [Facebook]

Previous Questions: 3. Majority Element[Amazon]

4. Largest Rectangle in Histogram [Facebook]

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.

Reference: https://leetcode.com/problems/largest-rectangle-in-histogram/#

Problem: Largest Rectangle in Histogram

How to Approach this problem?

This is approach uses stack.

  1. We are moving from the first left element, and adding it to stack
  2. We are adding element to stack until the moment when we find that element a[i-1] > element a[i]. That means after this moment square of our rectangle will become less and less.
  3. We starting popping element from our stack until we will find such a[j] for which a[j] ≤ a[i] or stack is empty.
  4. Every time we popping element from our stack we calculating square formed with this element. Is it a bit hard to explain, but I will try to draw that. 
Input 1:
    A = [2, 1, 5, 6, 2, 3]
Output 1:
    10
    Explanation 1:
        The largest rectangle is shown in the shaded area, which has area = 10 unit.

Congratulations! You just solved a problem that was asked in interviews at Microsoft , Facebook , Google and Amazon .

Thanks for reading this article, keep learning & growing.

Github: https://github.com/charlieInDen/InterviewQuestions-Swift/