Using Monotonic Stack
1. Understanding Monotonic Stack Technique
A monotonic stack is a stack where the elements are either entirely non-increasing or non-decreasing. This property allows for efficient solutions to problems involving comparisons between elements, particularly in scenarios where we need to find the next greater or smaller element.
| Property | Description | Usage Example |
|---|---|---|
| Monotonic Property | Elements in the stack follow a consistent order (increasing or decreasing) | Stack maintains elements in increasing order from bottom to top |
| Time Complexity | O(n) amortized for processing n elements | Each element is pushed and popped at most once |
| Space Complexity | O(n) in worst case (all elements in stack) | Stack stores up to n elements |
Example: Finding Next Greater Element
function nextGreaterElement(arr) {
const result = new Array(arr.length).fill(-1);
const stack = [];
for (let i = arr.length - 1; i >= 0; i--) {
while (stack.length && stack[stack.length - 1] <= arr[i]) {
stack.pop();
}
if (stack.length > 0) {
result[i] = stack[stack.length - 1];
}
stack.push(arr[i]);
}
return result;
}
// Example usage:
const nums = [4, 5, 2, 10];
console.log(nextGreaterElement(nums)); // [5, 10, 10, -1]
Note: The stack maintains elements in decreasing order. For each element, we pop all smaller elements from the top of the stack before pushing the current element.
2. Finding Next Greater Element I
| Property | Description | Example |
|---|---|---|
| Input | Array of integers | [1, 2, 1] |
| Output | Array where each element is replaced by the next greater element to its right | [2, -1, -1] |
| Approach | Monotonic stack to efficiently find next greater elements |
Example: Finding Next Greater Element
function nextGreaterElement(nums) {
const result = new Array(nums.length).fill(-1);
const stack = [];
for (let i = nums.length - 1; i >= 0; i--) {
while (stack.length && stack[stack.length - 1] <= nums[i]) {
stack.pop();
}
if (stack.length && stack[stack.length - 1] > nums[i]) {
result[i] = stack[stack.length - 1];
}
stack.push(nums[i]);
}
return result;
}
// Example usage:
const input = [1, 2, 1];
console.log(nextGreaterElement(input)); // Output: [2, -1, -1]
Note: The stack maintains elements in decreasing order. For each element, we pop smaller elements from the stack and assign the top of the stack as the next greater element.
3. Finding Next Greater Element II
Given a circular array, find the next greater element for each element in the array. The next greater element of an element is the first greater element to its right, wrapping around to the beginning if necessary.
| Property | Description | Example |
|---|---|---|
| Input | Circular array of integers | [1, 2, 1] |
| Output | Array of next greater elements | [2, -1, 2] |
Example: Finding Next Greater Element II
function nextGreaterElements(nums) {
const n = nums.length;
const result = new Array(n).fill(-1);
const stack = [];
// Traverse the array twice to simulate circular behavior
for (let i = 2 * n - 1; i >= 0; i--) {
const num = nums[i % n];
while (stack.length && stack[stack.length - 1] <= num) {
stack.pop();
}
if (stack.length && i < n) {
result[i] = stack[stack.length - 1];
}
stack.push(num);
}
return result;
}
// Example usage
const nums = [1, 2, 1];
console.log(nextGreaterElements(nums)); // Output: [2, -1, 2]
Note: The algorithm uses a monotonic stack to efficiently find the next greater element in O(n) time by traversing the array twice.
4. Finding Next Smaller Element
Given an array of integers, the "Next Smaller Element" problem asks us to find the first smaller element to the right of each element in the array. If no such element exists, we return -1 for that position.
| Element | Next Smaller Element | Explanation |
|---|---|---|
| 4 | 2 |
First element smaller than 4 to its right is 2 |
| 2 | 1 |
First element smaller than 2 to its right is 1 |
| 1 | -1 |
No element to the right is smaller than 1 |
| 5 | 3 |
First element smaller than 5 to its right is 3 |
| 3 | -1 |
No element to the right is smaller than 3 |
Example: Algorithm Implementation
function nextSmallerElement(arr) {
const result = [];
const stack = [];
for (let i = arr.length - 1; i >= 0; i--) {
while (stack.length && stack[stack.length - 1] >= arr[i]) {
stack.pop();
}
if (stack.length === 0) {
result.push(-1);
} else {
result.push(stack[stack.length - 1]);
}
stack.push(arr[i]);
}
return result.reverse();
}
// Example usage:
const input = [4, 2, 1, 5, 3];
console.log(nextSmallerElement(input)); // Output: [2, 1, -1, 3, -1]
Note: The monotonic stack is maintained in decreasing order to efficiently find the next smaller element.
5. Finding Previous Greater Element
| Element | Previous Greater Element | Index | Notes |
|---|---|---|---|
| arr | [4, 10, 5, 18, 3] |
[1, 2, 3, 4, 5] |
Input array of integers |
Example: Finding Previous Greater Element
const arr = [4, 10, 5, 18, 3];
const result = [];
const stack = [];
for (let i = 0; i < arr.length; i++) {
while (stack.length > 0 && arr[stack[stack.length - 1]] <= arr[i]) {
stack.pop();
}
if (stack.length === 0) {
result.push(-1); // No previous greater element
} else {
result.push(stack[stack.length - 1]); // Index of previous greater element
}
stack.push(i);
}
console.log(result); // [-1, 0, 1, 2, -1]
Note: The result array contains indices of the previous greater elements. If no such element exists, -1 is returned.
6. Finding Stock Span
The stock span problem is a classic application of monotonic stacks. For each day, we want to find how many consecutive previous days (including the current day) have stock prices less than or equal to the current price.
| Input | Description | Example |
|---|---|---|
| prices | Array of stock prices for consecutive days | [100, 80, 60, 70, 60, 75, 85] |
| Output | Description | Example |
|---|---|---|
| span | Array where each element represents the span for that day | [1, 1, 1, 2, 1, 4, 6] |
Example: Calculating Stock Span
function calculateSpan(prices) {
const span = new Array(prices.length);
const stack = [];
for (let i = 0; i < prices.length; i++) {
while (stack.length > 0 && prices[stack[stack.length - 1]] <= prices[i]) {
stack.pop();
}
span[i] = stack.length === 0 ? i + 1 : i - stack[stack.length - 1];
stack.push(i);
}
return span;
}
// Example usage:
const prices = [100, 80, 60, 70, 60, 75, 85];
console.log(calculateSpan(prices)); // [1, 1, 1, 2, 1, 4, 6]
Note: The monotonic stack maintains indices of elements in increasing order of their prices. For each element, we calculate how many previous elements are smaller or equal to it.
7. Finding Largest Rectangle Area
Given an array of heights representing bars in a histogram, find the largest rectangular area that can be formed.
| Property | Description | Notes |
|---|---|---|
| Input | Array of integers representing bar heights | Each height is a non-negative integer |
| Output | Maximum area of rectangle in histogram | Area = height × width |
Example: Histogram with Heights [2, 1, 5, 6, 2, 3]
function largestRectangleArea(heights) {
const stack = [];
let maxArea = 0;
for (let i = 0; i <= heights.length; i++) {
const currentHeight = i === heights.length ? 0 : heights[i];
while (stack.length > 0 && heights[stack[stack.length - 1]] > currentHeight) {
const height = heights[stack.pop()];
const width = i - (stack.length === 0 ? -1 : stack[stack.length - 1]) - 1;
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
return maxArea;
}
// Example usage:
const heights = [2, 1, 5, 6, 2, 3];
console.log(largestRectangleArea(heights)); // Output: 10
Note: The algorithm uses a monotonic increasing stack to efficiently compute the largest rectangle area in O(n) time.
8. Finding Maximal Rectangle
Given a binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
| Property | Description | Example |
|---|---|---|
| Input | Binary matrix (2D array of 0s and 1s) | |
| Output | Maximum area of rectangle with all 1s | 6 |
Example: Maximal Rectangle
function maximalRectangle(matrix) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
const heights = new Array(cols).fill(0);
let maxArea = 0;
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
}
const area = largestRectangleInHistogram(heights);
maxArea = Math.max(maxArea, area);
}
return maxArea;
}
function largestRectangleInHistogram(heights) {
const stack = [];
let maxArea = 0;
for (let i = 0; i <= heights.length; i++) {
while (stack.length && (i === heights.length || heights[stack[stack.length - 1]] > heights[i])) {
const h = heights[stack.pop()];
const w = i - (stack.length ? stack[stack.length - 1] + 1 : 0);
maxArea = Math.max(maxArea, h * w);
}
stack.push(i);
}
return maxArea;
}
// Example usage:
const matrix = [
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
];
console.log(maximalRectangle(matrix)); // Output: 6
Note: This approach uses the concept of finding the largest rectangle in a histogram for each row, leveraging the monotonic stack to efficiently compute the maximum area.
9. Removing Duplicate Letters
Use a monotonic stack to remove duplicate letters from a string while maintaining the lexicographically smallest result.
| Step | Action | Description |
|---|---|---|
| 1 | stack = [] |
Initialize an empty stack to maintain the result. |
| 2 | last_occurrence = map of char to last index |
Record the last occurrence of each character in the string. |
| 3 | used = set of chars in stack |
Track characters already in the stack to avoid duplicates. |
| 4 | Iterate through each character in the string | For each character, check if it can be added to the stack. |
| 5 | while stack and stack[-1] > char and last_occurrence[stack[-1]] > i |
Pop from stack if the top element is larger than current char and will appear later. |
| 6 | stack.append(char) |
Add current character to stack if not already used. |
Example: Removing Duplicates
function removeDuplicateLetters(s) {
const lastOccurrence = {};
for (let i = 0; i < s.length; i++) {
lastOccurrence[s[i]] = i;
}
const stack = [];
const used = new Set();
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (used.has(char)) continue;
while (stack.length > 0 &&
stack[stack.length - 1] > char &&
lastOccurrence[stack[stack.length - 1]] > i) {
const removed = stack.pop();
used.delete(removed);
}
stack.push(char);
used.add(char);
}
return stack.join('');
}
// Example usage:
console.log(removeDuplicateLetters("bcabc")); // "abc"
console.log(removeDuplicateLetters("cbacdcbc")); // "acdb"10. Finding Sum of Subarray Minimums
This problem involves finding the sum of minimum elements across all contiguous subarrays of an array. A monotonic stack approach efficiently computes this by determining for each element how many subarrays it is the minimum of.
| Property | Description | Notes |
|---|---|---|
| Input | Array of integers | Can contain duplicates |
| Output | Sum of minimums across all subarrays | Modulo 10^9 + 7 |
Example: Calculate sum of subarray minimums
function sumSubarrayMins(arr) {
const MOD = 1000000007;
const n = arr.length;
const left = new Array(n);
const right = new Array(n);
const stack = [];
// Find left boundaries (first smaller element to the left)
for (let i = 0; i < n; i++) {
while (stack.length && arr[stack[stack.length - 1]] > arr[i]) {
stack.pop();
}
left[i] = stack.length === 0 ? -1 : stack[stack.length - 1];
stack.push(i);
}
stack.length = 0;
// Find right boundaries (first smaller element to the right)
for (let i = n - 1; i >= 0; i--) {
while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {
stack.pop();
}
right[i] = stack.length === 0 ? n : stack[stack.length - 1];
stack.push(i);
}
let result = 0;
for (let i = 0; i < n; i++) {
const count = (i - left[i]) * (right[i] - i);
result = (result + arr[i] * count) % MOD;
}
return result;
}
// Example usage:
console.log(sumSubarrayMins([3, 1, 2, 4])); // Output: 17
Note: The key insight is that for each element, we calculate how many subarrays it is the minimum of using its left and right boundaries. These boundaries are determined using a monotonic stack to efficiently find the nearest smaller elements.
11. Trapping Rain Water
Given an array of non-negative integers representing heights of bars, compute how much water can be trapped after raining.
| Property | Description | Example |
|---|---|---|
| height | Array of non-negative integers representing bar heights | [0,1,0,2,1,0,1,3,2,1,2,1] |
| waterTrapped | Total units of water that can be trapped | 6 |
Example: Trapping Rain Water
function trap(height) {
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0;
let water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
// Example usage:
const height = [0,1,0,2,1,0,1,3,2,1,2,1];
console.log(trap(height)); // Output: 6
Note: The algorithm uses two pointers to efficiently calculate trapped water by tracking maximum heights from both ends.
12. Finding Maximum Width Ramp
A ramp in an array is defined as a pair of indices (i, j) where i <= j and A[i] <= A[j]. The width of the ramp is j - i. The task is to find the maximum width ramp in the array.
| Property | Description | Example |
|---|---|---|
| Array | Input array of integers | [6, 0, 8, 2, 1, 5] |
| Ramp | Pair (i, j) where i <= j and A[i] <= A[j] | (1, 5) with values (0, 5) |
| Width | Distance between indices j - i | 5 - 1 = 4 |
Example: Finding Maximum Width Ramp
function maxWidthRamp(nums) {
let stack = [];
let n = nums.length;
// Build a decreasing stack of indices
for (let i = 0; i < n; i++) {
if (stack.length === 0 || nums[stack[stack.length - 1]] > nums[i]) {
stack.push(i);
}
}
let maxWidth = 0;
// Traverse from right to left to find max width
for (let j = n - 1; j >= 0; j--) {
while (stack.length > 0 && nums[stack[stack.length - 1]] <= nums[j]) {
let i = stack.pop();
maxWidth = Math.max(maxWidth, j - i);
}
}
return maxWidth;
}
// Example usage
console.log(maxWidthRamp([6, 0, 8, 2, 1, 5])); // Output: 4
Note: The monotonic stack is built with indices in decreasing order of their values. Then, we traverse the array from right to left to find the maximum width ramp efficiently.