Grokking Microsoft Coding Interview
Ask Author
Back to course home

0% completed

Solution: Largest Rectangle in Histogram
We'll cover the following
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity

Problem Statement

Given an array of integers heights, where heights[i] represents the height of the histogram's bar, return the area of the largest rectangle in the histogram. Each bar has width equal to 1.

Examples

  • Example 1:
    • Input: [4, 2, 3, 2]

  • Expected Output: 8

  • Justification: The largest rectangle can be drawn from the first bar to the fourth bar, having height 2, resulting in an area of 2x4=8.

  • Example 2:

    • Input: [1,3,4,5,2]
  • Expected Output: 9

.....

.....

.....

Like the course? Get enrolled and start learning!