Leetcode 962: Maximum Width Ramp

Input: The input is a single integer array nums of size n (2 <= n <= 50,000), where each element nums[i] (0 <= nums[i] <= 50,000) represents an integer value in the array.

Example: Input: nums = [3, 5, 7, 1, 4, 2, 6]

Constraints:

• 2 <= nums.length <= 50,000

• 0 <= nums[i] <= 50,000

Output: The output is an integer representing the maximum width of a ramp in the array. If no ramp exists, return 0.

Example: Output: 4

Constraints:

• The result must be a non-negative integer.

Goal: The goal is to find the maximum width of a ramp by iterating over the array, checking pairs (i, j) where nums[i] <= nums[j], and computing the width (j - i) for each valid pair.

Steps:

• 1. Traverse the array while maintaining a stack to store the indices of elements in a way that ensures nums[i] <= nums[j] for valid pairs.

• 2. For each element in the array, try to find a corresponding j index that results in a larger width.

• 3. Track the maximum width encountered during the traversal.

Goal: The array nums is guaranteed to have at least two elements. The elements of the array are non-negative integers.

Steps:

• The length of the array is between 2 and 50,000.

• Each element in the array is between 0 and 50,000.

Assumptions:

• The array nums will always have at least two elements, and all elements will be integers within the given range.

• Input: Input: nums = [3, 5, 7, 1, 4, 2, 6]

• Explanation: In this case, the maximum width ramp is found between indices (1, 5) where nums[1] = 5 and nums[5] = 2. The width is 5 - 1 = 4.

• Input: Input: nums = [9, 8, 7, 6, 5]

• Explanation: Here, no valid ramp can be formed because every pair of elements nums[i] and nums[j] with i < j violates the condition nums[i] <= nums[j]. Thus, the result is 0.

• Input: Input: nums = [1, 2, 3, 4, 5]

• Explanation: In this case, the ramp can be formed between the first and the last index, with a width of 4 - 0 = 4.

Approach: To solve the problem efficiently, we can use a stack to help keep track of indices that could form valid ramps. The stack will ensure that we can find a pair of indices i and j such that nums[i] <= nums[j], and we can calculate the width j - i.

Observations:

• The problem can be reduced to finding a pair of indices i and j such that nums[i] <= nums[j], and maximizing j - i.

• A brute force solution would require checking all pairs, which could be inefficient for large arrays.

• Using a stack to store indices and then traversing the array backwards allows us to efficiently find the maximum width without explicitly checking every pair.

Steps:

• 1. Initialize a stack to keep track of indices in the array.

• 2. Traverse the array and push indices onto the stack where the elements are in a decreasing order.

• 3. Traverse the array from right to left, and for each element, find the earliest index in the stack where nums[i] <= nums[j].

• 4. Update the maximum width based on the difference between indices and continue until all possible pairs are checked.

Empty Inputs:

• The input will always have at least two elements, so this case is not possible.

Large Inputs:

• For large arrays with 50,000 elements, the solution must be efficient enough to handle the constraints.

Special Values:

• When the array elements are all the same, any pair of indices (i, j) will form a valid ramp with the maximum width being j - i.

Constraints:

• The input array will always have at least two elements, and each element will be within the range 0 <= nums[i] <= 50,000.

int maxWidthRamp(vector<int>& nums) {
    stack<int> s;
    for(int i = 0; i < nums.size(); i++)
        if(s.empty() || nums[s.top()] > nums[i])
            s.push(i);
    
    int res = 0;
    for(int i = nums.size() - 1; i >= 0; i--)
        while(!s.empty() && nums[s.top()] <= nums[i])
            res = max(res, i - s.top()), s.pop();
    
    return res;
}

1 : Function Declaration

int maxWidthRamp(vector<int>& nums) {

Declares the function to compute the maximum width ramp in an array.

2 : Stack Initialization

    stack<int> s;

Initializes an empty stack to store indices of potential starting points for the ramp.

3 : Outer Loop

    for(int i = 0; i < nums.size(); i++)

Iterates through the array to populate the stack with indices of decreasing elements.

4 : Stack Condition

        if(s.empty() || nums[s.top()] > nums[i])

Checks if the stack is empty or if the current element is smaller than the element at the top of the stack.

5 : Push Index

            s.push(i);

Pushes the current index onto the stack as a potential starting point for a ramp.

6 : Result Initialization

    int res = 0;

Initializes the variable `res` to store the maximum width of the ramp.

7 : Reverse Loop

    for(int i = nums.size() - 1; i >= 0; i--)

Iterates through the array in reverse to calculate the widest ramp.

8 : While Loop Condition

        while(!s.empty() && nums[s.top()] <= nums[i])

Checks if the current element can form a ramp with the index at the top of the stack.

9 : Calculate Ramp

            res = max(res, i - s.top()), s.pop();

Calculates the width of the ramp, updates the result, and pops the stack.

10 : Return Statement

    return res;

Returns the maximum width of the ramp found in the array.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n) because we traverse the array twice: once to fill the stack and once to calculate the maximum width.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) due to the stack used to store indices.

Leetcode 962: Maximum Width Ramp

Explore →