LeetCode 962: Maximum Width Ramp Solution

Master LeetCode problem 962 (Maximum Width Ramp), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

962. Maximum Width Ramp

Medium

Array Two Pointers Stack Monotonic Stack

Problem Explanation

Explanation:

To solve this problem, we can use a stack to keep track of potential ramps. We iterate through the array from left to right. If the current element is less than or equal to the element at the top of the stack, we push the index onto the stack. Otherwise, we keep popping elements from the stack until we find one less than or equal to the current element. During this process, we calculate the maximum width of the ramp.

Time Complexity:

The time complexity of this approach is O(n) where n is the number of elements in the input array.

Space Complexity:

The space complexity of this approach is O(n) where n is the number of elements in the input array.

Solution Code

class Solution {
    public int maxWidthRamp(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int maxWidth = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (stack.isEmpty() || nums[i] < nums[stack.peek()]) {
                stack.push(i);
            }
        }
        
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
                maxWidth = Math.max(maxWidth, i - stack.pop());
            }
        }
        
        return maxWidth;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 962 (Maximum Width Ramp)?

This page provides optimized solutions for LeetCode problem 962 (Maximum Width Ramp) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 962 (Maximum Width Ramp)?

The time complexity for LeetCode 962 (Maximum Width Ramp) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 962 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 962 in Java, C++, or Python.

Back to LeetCode Solutions