962. Maximum Width Ramp

Problem Description

In this problem, we're given an integer array called nums. We are tasked to find the maximum width of a "ramp" within this array. A "ramp" is defined as a pair of indices (i, j) with i < j, where the value at the first index is less than or equal to the value at the second one, i.e., nums[i] <= nums[j]. The width of this ramp is the difference between the two indices, j - i. The goal is to find the maximum width of such a ramp in the given array. If there are no ramps possible, we should return 0.

Intuition

To solve this problem, the intuition is that we can optimize the search for ramps by maintaining candidates for the start of the ramp in a stack. The key observations are:

We would like to start ramps as early as possible in the array but with the smallest possible values.
If we encounter an element greater than or equal to an element at a prospective start of a ramp, we can attempt to form a ramp.
We process the array backwards to assess the widest ramp possible with the start points we've collected.

The solution leverages a stack to store indices of potential "start points" for ramps. These start points are the indices where the value is less than or equal to all later values we've seen so far as we iterate from front to back. Therefore:

We iterate through the array, adding indices to the stack if the current element is smaller than the element at the top of the stack (which corresponds to the last element we added). This way, we keep track of all potential start points.
In a second pass, we iterate from the end of the array to the start. For each element, we compare it with the elements at the indices in our stack.
Since the stack is sorted by the values at those indices, every time we find an element greater than or equal to the value at the top index on the stack, we can pop the index off and calculate the width of a ramp. If the ramp is wider than any prior ramp we've found, we keep track of this new max width.
We continue popping from the stack and calculating ramp widths until the stack is empty or we find an element in nums that is smaller than the value at the current stack's top index, meaning no ramp is possible from this index. If the stack empties, we know we've found the maximum width ramp and we can break early.

By using this approach, we ensure that we always measure the width of ramps that start from the earliest point in the array and are as wide as possible. This stack-based approach allows us to quickly disregard ramp starts that will never be optimal, thus optimizing the search for the maximum width ramp in nums.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The solution makes use of a mono-stack or a stack that preserves order by certain criteria, in this case, the increasing order of values from the front to the back. A mono-stack is an ideal data structure to approach this problem due to the following characteristics:

It's a Last In, First Out (LIFO) structure, which allows us to compare recent entries with new ones efficiently.
It ensures that we have the smallest element seen so far at any given point on the bottom. This potentially results in the largest width ramp.

Here's a step-by-step breakdown of the solution using two main steps:

Building the stack:
- We initialize an empty stack called stk.
- We then iterate through the array nums using index i and the value v at each index.
- If the stack is empty or the current value v is less than the value in nums at the index on the top of the stack (nums[stk[-1]]), we push the current index i onto the stack. This way, we're maintaining a stack of indices where each is a candidate for the start of a ramp (the lowest element so far).
Finding the maximum width ramp:
- Next, we initialize the answer ans as 0.
- We reverse iterate over the array from the last index down to 0.
- For each element, we check if the stack is not empty and the current element nums[i] is greater than or equal to the element at the index from the top of the stack (nums[stk[-1]]).
- If both conditions hold true, it means the current index i can serve as the ending index of a ramp starting at the index from the top of the stack.
- We pop off the index at the top of the stack and use it to calculate the width of the ramp by subtracting the start index from the current index (i - stk.pop()).
- We store the maximum width encountered in ans.
- If at any point the stack becomes empty, we can stop iterating since it means all potential start points of ramps have been evaluated.

By using this approach, the algorithm minimizes comparisons and avoids unnecessary iterations, hence optimizing the search for the maximum width ramp in the array nums. The complexity of the algorithm is O(N), where N is the size of the input array, because each element is pushed to the stack at most once and popped at most once.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example using the array nums = [6, 0, 8, 2, 1, 5].

Building the stack:

Initialize an empty stack stk.

Iterate through each element of nums.

Index (i)	Value (v)	Top of Stack	Action
0	6	-	Push index 0 onto `stk` (stack is now [0])
1	0	6	Push index 1 onto `stk` since `nums[0] > nums[1]` (stack is now [0, 1])
2	8	0	Do nothing (8 is not smaller than 6 or 0)
3	2	0	Push index 3 onto `stk` since `nums[1] > nums[3]` (stack is now [0, 1, 3])
4	1	2	Push index 4 onto `stk` since `nums[3] > nums[4]` (stack is now [0, 1, 3, 4])
5	5	1	Do nothing (5 is not smaller than 6, 0, 2, or 1)

After this step, stk = [0, 1, 3, 4].

Finding the maximum width ramp:

Initialize ans to 0.
Reverse iterate over nums and compare the current value with the top of stk.

For this example, we start with the last index, 5.

Index (i)	Num Value	Stack (`stk`)	Top of Stack Value	Action	New `ans`
5	5	[0, 1, 3, 4]	1	Pop index 4. Calculate ramp width `5 - 4 = 1`.	1
5	5	[0, 1, 3]	2	Pop index 3. Calculate ramp width `5 - 3 = 2`. Since `2 > 1`, update `ans`.	2
5	5	[0, 1]	0	Do nothing (5 is not smaller than 6 or 0)
4	1	[0, 1]	0	Do nothing (1 is not greater than 0)
3	2	[0, 1]	0	Do nothing (2 is not greater than 0)
2	8	[0, 1]	0	Pop index 1. Calculate ramp width `2 - 1 = 1`. Since `1 < 2`, do not update `ans`.
2	8	[0]	6	Pop index 0. Calculate ramp width `2 - 0 = 2`. Since `2 == 2`, `ans` remains the same.	2
1	0	[]	-	(No action since the stack is empty)

After comparing elements, ans remains at its highest value, which is 2.

At the end of this process, we have determined that the maximum width of a ramp in the array nums = [6, 0, 8, 2, 1, 5] is 2, which occurs between the elements at indices 1 and 3 (value 0 and value 2, respectively), and also between the elements at indices 0 and 2 (value 6 and value 8, respectively). The algorithm optimized the search for the maximum width ramp efficiently, using a mono-stack to keep track of potential starting points and reverse iterating to find the longest ramp possible.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxWidthRamp(self, nums: List[int]) -> int:
5        # Initialize a stack to keep track of indices of the potential start of the ramp.
6        stack = []
7      
8        # Iterate through the given numbers along with their indices.
9        for index, value in enumerate(nums):
10            # If the stack is empty or the current value is less than the value at the last index of the stack,
11            # this could be a potential start of a ramp, so store the index.
12            if not stack or nums[stack[-1]] > value:
13                stack.append(index)
14              
15        # Initialize the answer variable with 0 to keep track of the maximum width.
16        max_width = 0
17      
18        # Iterate backwards from the end of nums to find the maximum ramp.
19        # We go backwards since we're looking for the largest index j (end of the ramp)
20        # that forms a ramp with the start indices in the stack.
21        for i in range(len(nums) - 1, -1, -1):
22            # While the stack is not empty and the current number is greater than or equal to
23            # the number at the index of the top of the stack, we have a potential ramp.
24            while stack and nums[stack[-1]] <= nums[i]:
25                # Calculate the width of the ramp and update the max_width if this ramp is wider.
26                max_width = max(max_width, i - stack.pop())
27            # If the stack becomes empty, no more start positions are left to check,
28            # and the maximum ramp is found.
29            if not stack:
30                break
31              
32        # Return the maximum width of the ramp found.
33        return max_width
34

1class Solution {
2    public int maxWidthRamp(int[] nums) {
3        int n = nums.length; // Store the length of the array
4        Deque<Integer> stack = new ArrayDeque<>(); // Use a deque as a stack for indices
5
6        // Populate the stack with indices of elements where each is the smallest
7        // seen so far from left to right
8        for (int i = 0; i < n; ++i) {
9            if (stack.isEmpty() || nums[stack.peek()] > nums[i]) {
10                stack.push(i);
11            }
12        }
13
14        int maxWidth = 0; // Initialize the maximum width of the ramp
15
16        // Iterate from the end of the array towards the beginning
17        for (int i = n - 1; i >= 0; --i) {
18            // Try to extend the ramp from the end as far as possible
19            while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
20                int startIndex = stack.pop(); // Retrieve the start index of a ramp
21                maxWidth = Math.max(maxWidth, i - startIndex); // Update the maxWidth
22            }
23
24            // If the stack is empty, all possible start indices have been explored
25            if (stack.isEmpty()) {
26                break;
27            }
28        }
29
30        return maxWidth; // Return the maximum width of a ramp found
31    }
32}
33

1#include <vector>
2#include <stack>
3#include <algorithm> // For using max()
4
5class Solution {
6public:
7    int maxWidthRamp(vector<int>& nums) {
8        int n = nums.size(); // Get the size of the input vector.
9        stack<int> indexStack; // Initialize a stack to keep track of indices.
10      
11        // Fill the stack with the indices of elements which are either the first element or smaller than the
12        // the smallest encountered element so far, as they can potentially form the starting point of a ramp.
13        for (int i = 0; i < n; ++i) {
14            if (indexStack.empty() || nums[indexStack.top()] > nums[i]) {
15                indexStack.push(i);
16            }
17        }
18      
19        int maxRampWidth = 0; // Initialize maximum ramp width (answer variable).
20      
21        // Moving from right to left, attempt to find the maximum ramp width by comparing elements
22        // On the stack with elements to their right. As this is a ramp, we're looking for a smaller or equal
23        // number to the left (marked by the index on the stack) of our current number.
24        for (int i = n - 1; i >= 0; --i) {
25            while (!indexStack.empty() && nums[indexStack.top()] <= nums[i]) {
26                // Update maximum ramp width if the current ramp is wider.
27                maxRampWidth = max(maxRampWidth, i - indexStack.top());
28                indexStack.pop(); // Pop from the stack as we found a valid ending point for this starting index.
29            }
30            // There's no need to continue if the stack is empty.
31            if (indexStack.empty()) break;
32        }
33      
34        return maxRampWidth; // Return the maximum width of a ramp found.
35    }
36};
37

1function maxWidthRamp(nums: number[]): number {
2    const n: number = nums.length; // Get the length of the input array.
3    const indexStack: number[] = []; // Initialize an array to work as a stack for indices.
4
5    // Fill the stack with the indices of elements which are either the first element or smaller than
6    // the smallest encountered element so far, as they could be the starting point of a ramp.
7    for (let i = 0; i < n; i++) {
8        if (indexStack.length === 0 || nums[indexStack[indexStack.length - 1]] > nums[i]) {
9            indexStack.push(i);
10        }
11    }
12
13    let maxRampWidth: number = 0; // Initialize the maximum ramp width (answer variable).
14
15    // Move from right to left, attempting to find the maximum ramp width by comparing elements
16    // on the stack with elements to their right. For a ramp, a smaller or equal
17    // number to the left of the current number is sought (marked by the index on the stack).
18    for (let i = n - 1; i >= 0; i--) {
19        while (indexStack.length > 0 && nums[indexStack[indexStack.length - 1]] <= nums[i]) {
20            // Update maximum ramp width if the current ramp is wider.
21            maxRampWidth = Math.max(maxRampWidth, i - indexStack[indexStack.length - 1]);
22            indexStack.pop(); // Pop from the stack as we've found a valid ending point for this starting index.
23        }
24        // There's no need to continue if the stack is empty.
25        if (indexStack.length === 0) {
26            break;
27        }
28    }
29
30    return maxRampWidth; // Return the maximum width of a ramp found.
31}
32
33// Example usage:
34// const nums = [6,0,8,2,1,5];
35// const rampWidth = maxWidthRamp(nums);
36

Time and Space Complexity

The time complexity of the code can be considered as O(N), where N is the length of the input nums list. It is because the first loop iterates over all elements once to build the stack, and the second loop iterates over all elements in the worst case if the stack isn't emptied early. However, each element is added and then popped from the stack at most once, leading to a linear time complexity over the two loops.

The space complexity of the code is O(N) in the worst case when the elements in the nums list are strictly decreasing. In such a case, each nums index would be appended to the stack, thus the stack could grow to the same size as the nums list. In the general case, the space complexity depends on the input but will not exceed O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know