Jubin Soni - Portfolio & Blog

Solution to Last Week's Challenge

Last week's problem was: DSA: Interval Scheduling Problems

The optimal solution uses dsa: interval scheduling problems pattern with careful state management.

Complexity Analysis:

Time Complexity: O(n)
Space Complexity: O(1)

In the landscape of technical interviews, few patterns are as deceptively simple yet powerful as the Monotonic Stack. While a standard stack follows the Last-In-First-Out (LIFO) principle, a monotonic stack adds a specific constraint: elements must be stored in a strictly increasing or strictly decreasing order. This pattern is a favorite among recruiters at top-tier firms like Google and Meta because it tests a candidate’s ability to reduce a naive $O(N^2)$ nested-loop solution into a sleek, linear $O(N)$ optimization. It is the go-to tool for solving "nearest neighbor" problems where you need to find the first element to the left or right that satisfies a specific comparison.

Beyond the whiteboard, monotonic stacks power critical components in real-world systems. In financial applications, they are used to calculate stock spans and identify price breakouts. In browser engines, they help manage layout rendering by determining visibility and occlusion. Even in data processing pipelines, this pattern assists in finding the largest rectangular area under a histogram, which is a foundational concept in image processing and signal analysis. Understanding this pattern isn't just about passing an interview; it's about mastering a fundamental optimization technique for streaming data.

Theory

The core concept of a monotonic stack is maintaining an ordered sequence of elements while processing a collection. When a new element arrives that violates the "monotonicity" (the order), we pop elements from the stack until the order is restored.

There are two primary types:

Monotonic Increasing: Elements are stored from smallest to largest. When we encounter a smaller element than the stack top, we pop. This is used to find the Next Smaller Element.
Monotonic Decreasing: Elements are stored from largest to smallest. When we encounter a larger element than the stack top, we pop. This is used to find the Next Greater Element.

The time complexity is $O(N)$ because, despite the nested while loop, each element is pushed onto the stack exactly once and popped at most once. The space complexity is $O(N)$ in the worst case where the input is already sorted in the desired order.

Pattern Visualization

The logic follows a standard template. We iterate through the array, and for every element, we check if it "challenges" the current stack top.

Implementation

Let's look at the classic "Next Greater Element" problem. Given an array, find the first element to the right that is larger than the current element for every index.

Brute Force Approach

The naive approach uses nested loops to search the remainder of the array for every element.

python

def next_greater_brute(nums):
    res = [-1] * len(nums)
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[j] > nums[i]:
                res[i] = nums[j]
                break
    return res
# Time Complexity: O(n^2)
# Space Complexity: O(1) excluding output

Optimized Monotonic Stack Approach

By using a monotonic decreasing stack, we can solve this in a single pass.

python

def next_greater_optimized(nums):
    n = len(nums)
    res = [-1] * n
    stack = [] # Stores indices

    for i in range(n):
        # While stack is not empty and current element is 
        # greater than the element at the stack's top index
        while stack and nums[i] > nums[stack[-1]]:
            index = stack.pop()
            res[index] = nums[i]
        
        stack.append(i)
    
    return res
# Time Complexity: O(n)
# Space Complexity: O(n)

Complexity Analysis Table

Feature	Brute Force	Monotonic Stack
Time Complexity	$O(N^2)$	$O(N)$
Space Complexity	$O(1)$	$O(N)$
Best Case	$O(N^2)$	$O(N)$
Scalability	Poor for large datasets	Excellent
Typical Use Case	Small arrays (< 1000)	Large data streams

Common Patterns

1. Next Smaller Element (Increasing Stack)

Used for problems like "Largest Rectangle in Histogram."

python

while stack and nums[i] < nums[stack[-1]]:
    stack.pop()
stack.append(i)

2. Stock Span Problem (Indices Difference)

Instead of storing values, we store indices to calculate the distance between the current element and its predecessor.

python

def stock_span(prices):
    stack = [] # Stores indices
    span = [0] * len(prices)
    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] <= price:
            stack.pop()
        span[i] = i + 1 if not stack else i - stack[-1]
        stack.append(i)
    return span

Practice Problems

The following chart maps common problems based on their typical interview frequency and difficulty level.

This Week's Interview Challenge

Problem: Next Greater Element II (Circular)

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Example 1:

Input: nums = [1, 2, 1]
Output: [2, -1, 2]
Explanation: The first 1's next greater is 2; 2 has no next greater; the second 1's next greater is 2 (circularly).

Example 2:

Input: nums = [5, 4, 3, 2, 1]
Output: [-1, 5, 5, 5, 5]

Constraints:

$1 \le nums.length \le 10^4$
$-10^9 \le nums[i] \le 10^9$

Hints:

How do you handle circularity? You could concatenate the array to itself or simulate it using the modulo operator.
If you iterate through the array twice, can you treat the second pass as the "circular" lookup?
Use a monotonic decreasing stack to store indices, similar to the standard Next Greater Element.

Template Code:

python

class Solution:
    def nextGreaterElements(self, nums: list[int]) -> list[int]:
        # Your code here
        pass

Submit your solution and check back next week for the detailed answer!

Conclusion

The Monotonic Stack is a quintessential "optimization" pattern. It transforms problems that appear to require exhaustive searching into linear scans by maintaining a history of "unresolved" elements. When preparing for interviews, remember the golden rule: if a problem asks for the "nearest" element with a specific property in a linear sequence, your first thought should be a Monotonic Stack.

Interview Tips:

Always dry-run your stack pops with a small example to ensure your comparison logic (> vs >=) is correct.
Consider whether you need to store the actual values or just the indices in your stack. Storing indices is usually more versatile.
Be mindful of duplicates; decide if "greater than" means strictly greater or greater than or equal to based on the problem requirements.

https://leetcode.com/tag/monotonic-stack/ https://en.wikipedia.org/wiki/Stack_(abstract_data_type) https://visualgo.net/en/list?slide=1