Maximum Width Ramp

MEDIUM

Description

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.

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.

Constraints:

2 <= nums.length <= 5 * 10⁴
0 <= nums[i] <= 5 * 10⁴

Approaches

Checkout 3 different approaches to solve Maximum Width Ramp. Click on different approaches to view the approach and algorithm in detail.

Brute Force

This approach exhaustively checks every possible pair of indices (i, j) where i < j. For each pair, it verifies if it forms a ramp (nums[i] <= nums[j]) and, if so, calculates its width j - i. The maximum width found across all pairs is the result.

Algorithm

Initialize a variable maxWidth to 0.
Use a nested loop. The outer loop iterates through each possible starting index i from 0 to n-2.
The inner loop iterates through each possible ending index j from i + 1 to n-1.
Inside the inner loop, check the ramp condition: nums[i] <= nums[j].
If the condition is true, it means we've found a valid ramp. We calculate its width j - i and update maxWidth to be the maximum of its current value and the new width.
After checking all pairs, maxWidth will hold the maximum width of any ramp in the array.

The brute-force solution is the most straightforward way to solve the problem. We simply follow the definition of a ramp and its width. We iterate through all possible pairs of indices (i, j) such that i comes before j. For every such pair, we check if nums[i] is less than or equal to nums[j]. If this condition holds, we have found a valid ramp. We then calculate its width, which is j - i, and compare it with the maximum width found so far, updating it if the new width is larger. This process is repeated until all possible pairs have been considered.

class Solution {
    public int maxWidthRamp(int[] nums) {
        int n = nums.length;
        int maxWidth = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] <= nums[j]) {
                    maxWidth = Math.max(maxWidth, j - i);
                }
            }
        }
        return maxWidth;
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of `nums`. The nested loops lead to a quadratic number of comparisons.Space Complexity: O(1), as we only use a constant amount of extra space for variables.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space.

Cons:

Highly inefficient for large inputs due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error on competitive programming platforms for the given constraints.

Code Solutions

Checking out 4 solutions in different languages for Maximum Width Ramp. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Maximum Width Ramp

Patterns:

Two Pointers

Data Structures:

ArrayStackMonotonic Stack

Companies:

Zepto |