Monotonic Stack in Problem Solving

Overview

• Introduction to the concept of a monotonic stack.
• Used in coding interviews to solve certain problems efficiently.
• Monotonic stack retains order of elements using greedy logic.
• Two types of order:
  • Monotonically Increasing: Elements stay the same or increase left to right.
  • Monotonically Decreasing: Elements stay the same or decrease left to right.

Example Problem

• Given the heights of five people, find the height of the next tallest person.
• If no taller person exists, store -1.

Brute Force Solution

• Iterate through each height and check the rest of the array.
• Time complexity: (O(n^2)).

Efficient Solution Using Monotonic Stack

• Iterate from right to left, maintaining a monotonically decreasing stack.
• This ensures higher elements are on the right.
• Steps:
  • Use the stack to store greater heights as encountered.
  • If stack is empty, assign -1 (no greater height exists).
  • Continuously maintain the decreasing order while inserting elements.

Step-by-Step Example

• Heights: [2, 1, 2, 4, 3]
• Process each height from right to left:
  1. Height 3: Stack empty → Assign -1 → Add 3 to stack.
  2. Height 4: Stack empty after popping 3 → Assign -1 → Add 4 to stack.
  3. Height 2: Top of stack is 4 (greater) → Assign 4 → Add 2 to stack.
  4. Height 1: Top of stack is 2 (greater) → Assign 2 → Add 1 to stack.
  5. Height 2: Pop 1 and 2 to maintain order → Top is 4 (greater) → Assign 4 → Add 2 to stack.

Code Explanation

• Function takes an array of heights.
• Creates an array of integers and a monotonic stack.
• Iterates from right to left:
  • While stack is non-empty and top is ( \leq ) current height, pop from stack.
  • If stack empty, assign -1 else stack top is next greater height.
  • Push current height onto stack.
• Return result array.

Complexity

• Time complexity is ( O(n) ) due to efficient stack operations, avoiding ( O(n^2) ).

Conclusion

• Monotonic stack is useful for efficient problem solving by maintaining order and reducing complexity.
• Like, comment, and subscribe if this explanation was helpful.