962. Maximum Width Ramp

[mah-shamim]

Topics: Array, Stack, Monotonic Stack

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 * 104
• 0 <= nums[i] <= 5 * 104

[kovatz]

We can leverage the concept of a monotonic stack. Here's the solution and explanation:

Approach:

1. Monotonic Decreasing Stack: We create a stack that keeps track of indices of elements in a way such that nums[stack[i]] is in a decreasing order. This allows us to later find pairs (i, j) where nums[i] <= nums[j].
2. Traverse from the End: After creating the stack, we traverse the array from the end (j from n-1 to 0) to try and find the farthest i for each j where nums[i] <= nums[j].
3. Update the Maximum Width: Whenever nums[i] <= nums[j] holds for the current top of the stack, calculate the ramp width j - i and update the maximum width if it's larger.

Let's implement this solution in PHP: 962. Maximum Width Ramp

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function maxWidthRamp($nums) {
    $n = count($nums);
    $stack = [];
    $maxWidth = 0;
    
    // Step 1: Create a decreasing stack
    for ($i = 0; $i < $n; $i++) {
        // Add index only if the current value is less than the value at the index at the top of the stack
        if (empty($stack) || $nums[$stack[count($stack) - 1]] > $nums[$i]) {
            array_push($stack, $i);
        }
    }

    // Step 2: Traverse from the end of the array
    for ($j = $n - 1; $j >= 0; $j--) {
        // While the stack is not empty and nums[stackTop] <= nums[j]
        while (!empty($stack) && $nums[$stack[count($stack) - 1]] <= $nums[$j]) {
            // Calculate the ramp width and update maxWidth
            $i = array_pop($stack);
            $maxWidth = max($maxWidth, $j - $i);
        }
    }

    return $maxWidth;
}

// Example 1
$nums = [6, 0, 8, 2, 1, 5];
echo maxWidthRamp($nums);  // Output: 4

// Example 2
$nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1];
echo maxWidthRamp($nums);  // Output: 7
?>

Explanation:

1. Create a Decreasing Stack:

   • Iterate through the array and add indices to the stack.
   • Only add an index if it corresponds to a value that is less than or equal to the value of the last index in the stack. This ensures that values in the stack are in a decreasing order.

2. Traverse from the End:

   • As we go backward through the array, for each j, pop indices i from the stack as long as nums[i] <= nums[j].
   • Calculate the width j - i and update maxWidth.

3. Why This Works:

   • By maintaining a decreasing stack of indices, we ensure that when we encounter a j with a larger value, it can give us a larger width j - i when i is popped from the stack.

4. Time Complexity:

   • Building the stack takes O(n) time since each index is pushed once.
   • The traversal from the end and popping indices also takes O(n) since each index is popped at most once.
   • Overall, the solution runs in O(n) time, which is efficient for input size up to 5 * 10^4.

Output:

• For nums = [6, 0, 8, 2, 1, 5], the output is 4, corresponding to the ramp (1, 5).
• For nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1], the output is 7, corresponding to the ramp (2, 9).

[mah-shamim]

Thanks to solve the "Maximum Width Ramp" problem efficiently

[kovatz]

Thanks