HARD NC#27 Stack - Monotonic Stack

84. Largest Rectangle in Histogram

šŸ“– Problem

Given an array of integers heights representing histogram's bar height, return the area of largest rectangle in the histogram.

šŸ§  Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • ā€¢Array methods (`push`, `pop`, `shift`, `slice`)
  • ā€¢Object/Map/Set usage patterns
  • ā€¢Function parameter and return typing

Logical Thinking Concepts

  • ā€¢Define invariants before coding
  • ā€¢Check edge cases first (`[]`, single element, duplicates)
  • ā€¢Estimate time/space before implementation
  • ā€¢Apply Monotonic Stack reasoning pattern

šŸ’” Approach

  • ā†’ Use monotonic increasing stack to track indices
  • ā†’ When current height < stack top, pop and calculate area
  • ā†’ For popped bar, width extends from current index to previous stack index
  • ā†’ Width = stack.empty() ? current index : current index - stack.top() - 1
  • ā†’ Add sentinel (0 height) at end to ensure all bars are processed
  • ā†’ Time: O(n), Space: O(n)

šŸ› ļø Hints & Pitfalls

Hints

  • ā€¢Use monotonic increasing stack to track indices
  • ā€¢When current height < stack top, pop and calculate area
  • ā€¢For popped bar, width extends from current index to previous stack index

Common Pitfalls

  • ā€¢Width = stack.empty() ? current index : current index - stack.top() - 1
  • ā€¢Add sentinel (0 height) at end to ensure all bars are processed
  • ā€¢Time: O(n), Space: O(n)

šŸ§Ŗ Test Cases

Hidden tests on submit: 2

Test Case 1
Not run
Input:
largestRectangleArea([2,1,5,6,2,3]);
Expected:
10
Test Case 2
Not run
Input:
largestRectangleArea([2,4]);
Expected:
4
Test Case 3
Not run
Input:
largestRectangleArea([1]);
Expected:
1

šŸ“ Code Editor

šŸ“š Reference Solution

ā–¼
āŒ˜K Search āŒ˜ā†© Run āŒ˜S Submit