Maximum Width Ramp Problem

Problem

A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i.

Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0.

Examples

Example 1:

Input: nums = [6,0,8,2,1,5]
Output: 4
Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5.

Example 2:

Input: nums = [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.

Solution

Method 1 - Naive

Iterate through all possible pairs (i, j) to find the maximum width that satisfies nums[i] <= nums[j].
This approach involves nested loops leading to O(n^2) time complexity, which is inefficient for large arrays.

Method 2 - Using right max array and two-pointer technique

The goal is to find the maximum distance, and instead of explicitly calculating for every index, key is to eliminate redundant calculations for many indices.

For example, in the array [6, 0, 8, 2, 1, 5], once we determine that for number 0, the right end of the ramp (let’s call it j) is 5, we can skip calculations for indices between 0 and 5 concerning j = 5, since their distances to 5 would be less than the distance from 0 to 5.

This is a classical two-pointer problem. The right pointer expands the range, and the left pointer contracts it. The trick is for the left pointer to iterate over the original array, while the right pointer iterates over an array that stores the maximum values on the right for each index.

Code

Java

public class Solution {
    public int maxWidthRamp(int[] nums) {
        int n = nums.length;
        int[] rMax = new int[n];
        
        // Create an array to store the maximum values to the right of each index
        rMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rMax[i] = Math.max(rMax[i + 1], nums[i]);
        }
        
        int left = 0, right = 0;
        int ans = 0;
        
        // Use the two-pointer technique to find the maximum width ramp
        while (right < n) {
            while (left < right && nums[left] > rMax[right]) {
                left++;  // Move left pointer to the right
            }
            ans = Math.max(ans, right - left);  // Calculate the width of the current ramp
            right++;  // Move right pointer to the right
        }
        
        return ans;
    }

}

Python

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        n = len(nums)
        rMax = [0] * n
        
        # Create an array to store the maximum values to the right of each index
        rMax[n - 1] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            rMax[i] = max(rMax[i + 1], nums[i])
        
        left = 0
        right = 0
        ans = 0
        
        # Use the two-pointer technique to find the maximum width ramp
        while right < n:
            while left < right and nums[left] > rMax[right]:
                left += 1  # Move left pointer to the right
            ans = max(ans, right - left)  # Calculate the width ramp
            right += 1  # Move right pointer to the right
        
        return ans

Complexity

⏰ Time complexity: O(n), because there are two passes over the input array: one to create the rMax array and another to find the maximum width ramp using two pointers.
🧺 Space complexity: O(n) due to the additional rMax array storage.

Method 3 - Sorting the indices

Sort the indices in a separate array based on the elements of the original array.

For the array [6, 0, 8, 2, 1, 5], the sorted indices array would be [1, 4, 3, 5, 0, 2].

These indices are now ordered according to the values of the elements in non-decreasing order. For any indices i and j where i < j, if index[i] < index[j] (meaning the smaller element appears before the larger element in the original array), it can be a candidate for the solution. Iterate through the array while maintaining the minimum index encountered so far.

Code

Java

public class Solution {
    public int maxWidthRamp(int[] nums) {
        int n = nums.length;
        Integer[] indices = new Integer[n];
        
        // Populate the indices array with values from 0 to n-1
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        // Sort indices based on the values in the nums array
        Arrays.sort(indices, Comparator.comparingInt(i -> nums[i]));
        
        int minIndex = n;  // Initialize minIndex to n (outside the array bounds)
        int maxWidth = 0;  // Initialize maxWidth to 0
        
        // Traverse the sorted indices to find the maximum width ramp
        for (int i = 0; i < n; i++) {
            int idx = indices[i];  // Current index in the sorted indices array
            maxWidth = Math.max(maxWidth, idx - minIndex);  // Update maxWidth with the maximum width found
            minIndex = Math.min(minIndex, idx);  // Update minIndex with the minimum index encountered
        }
        
        return maxWidth;  // Return the maximum width of the ramp
    }
}

Python

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        n = len(nums)
        indices = list(range(n))
        
        # Sort indices based on the values in nums
        indices.sort(key=lambda i: nums[i])
        
        min_index = n
        max_width = 0
        
        # Traverse the sorted indices to find the maximum width ramp
        for i in range(n):
            idx = indices[i]
            max_width = max(max_width, idx - min_index)
            min_index = min(min_index, idx)
        
        return max_width

Complexity

⏰ Time complexity: O(n log n) due to sorting
🧺 Space complexity: O(n) for using extra indices array

Method 4 - Monotonic Stack

Another way is to maintain a stack of elements in decreasing order.

Consider the array: [6, 0, 8, 2, 1, 5]

Decreasing order stack: [6, 0].

There’s no need to add 8 to the stack. For any element on the right where 8 could be part of a solution (as the left end of a ramp), 0 can also serve as the left end and provide a larger ramp length because the index of 0 is less than that of 8. Thus, 8 will never be the left end of the longest ramp.

The same logic applies to 2, 1, and 5.

Once the stack is built, start iterating the array from the end, treating the current element as the right end of the ramp and the stack’s top element as the left end. If the stack’s top element meets the condition, a candidate ramp is found.

The key is: we can now pop that element from the stack. Why? Suppose we are currently at index j and the stack’s top is at index i.

So, the ramp is i..j.

As we iterate backward, the next right end will be j-1. Even if it forms a ramp with i, its length will be shorter than the current ramp (j-i). Thus, there’s no point in keeping 0 in the stack now.

Continue popping elements off the stack whenever a candidate ramp is found, as the current candidate ramp is the best possible ramp using the stack’s top element as the left end.

Code

Java

public class Solution {
    public int maxWidthRamp(int[] nums) {
        int n = nums.length;
        Deque<Integer> stk = new ArrayDeque<>();
        
        // Create a monotonic decreasing stack with indices
        for (int i = 0; i < n; i++) {
            if (stk.isEmpty() || nums[i] < nums[stk.peek()]) {
                stk.push(i); // Push the index onto the stack
            }
        }

        int maxWidth = 0;
        // Traverse the array from the end to find the maximum width ramp
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.isEmpty() && nums[i] >= nums[stk.peek()]) {
                // Calculate the width of the ramp and update maxWidth
                maxWidth = Math.max(maxWidth, i - stk.pop());
            }
        }
        
        return maxWidth; // Return the maximum width of the ramp found
    }
}

Python

 class Solution:
     def maxWidthRamp(self, nums: List[int]) -> int:
         n = len(nums)
         stack = []
         
         # Create a monotonic decreasing stack with indices
         for i in range(n):
             if not stack or nums[i] < nums[stack[-1]]:
                 stack.append(i)  # Push the index onto the stack
 
         max_width = 0
         # Traverse the array from the end to find the maximum width ramp
         for i in range(n - 1, -1, -1):
             while stack and nums[i] >= nums[stack[-1]]:
                 # Calculate the width of the ramp and update max_width
                 max_width = max(max_width, i - stack.pop())
         
         return max_width  # Return the maximum width of the ramp found

Complexity

⏰ Time complexity: O(n), since we traverse the array a constant number of times.
🧺 Space complexity: O(n), due to the space needed for the stack.

Problem#

Examples#

Solution#

Method 1 - Naive#

Method 2 - Using right max array and two-pointer technique#

Code#

Java#

Python#

Complexity#

Method 3 - Sorting the indices#

Code#

Java#

Python#

Complexity#

Method 4 - Monotonic Stack#

Code#

Java#

Python#

Complexity#

Problem

Examples

Solution

Method 1 - Naive

Method 2 - Using right max array and two-pointer technique

Code

Java

Python

Complexity

Method 3 - Sorting the indices

Code

Java

Python

Complexity

Method 4 - Monotonic Stack

Code

Java

Python

Complexity