DEV Community

Cover image for 962. Maximum Width Ramp
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

962. Maximum Width Ramp

962. Maximum Width Ramp

Difficulty: Medium

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

Solution:

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) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// 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
?>
Enter fullscreen mode Exit fullscreen mode

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).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay