Maximum Width Ramp

Leetcode Problem:

• Maximum Width Ramp

Summary

• The problem requires finding the maximum width of a ramp in an integer array
• A ramp is defined as a pair (i, j) where i < j and nums[i] <= nums[j]
• The width of the ramp is j - i
• The goal is to find the maximum width of such a ramp in the given array.

Approach

• Binary Search Approach: The solution uses a binary search approach to find the maximum width of the ramp
• It initializes two pointers, one at the start and one at the end of the array
• It calculates the middle index and checks if there is a ramp starting from that index
• If there is, it moves the left pointer to the right of the middle index
• Otherwise, it moves the right pointer to the left of the middle index
• This process continues until the left pointer is greater than the right pointer.

Complexity

• O(n log n) due to the binary search, where n is the size of the array

Explanation

• The solution starts by initializing two pointers, one at the start and one at the end of the array
• It calculates the middle index and checks if there is a ramp starting from that index
• If there is, it moves the left pointer to the right of the middle index
• Otherwise, it moves the right pointer to the left of the middle index
• This process continues until the left pointer is greater than the right pointer
• The solution uses a binary search approach to find the maximum width of the ramp, which allows it to efficiently search for the ramp
• The time complexity of the solution is O(n log n) due to the binary search, where n is the size of the array.

Solution Code:

class Solution {
public:
    int maxWidthRamp(vector& nums) {
        int l = 0;
        int r = nums.size() - 1;
        int ans = 0;
        while(l <= r){
            int win_size = (l + r) / 2;
            bool success = false;
            int minValue = 5*10000;
            for(int i = 0; i < nums.size()- win_size; i++){
                minValue = min(minValue, nums[i]);
                if(minValue <= nums[i+win_size]){
                    success = true;
                }
            }
            if(success){
                l = win_size + 1;
                ans = win_size;
            } else {
                r = win_size - 1;
            }

        }
        return ans;
    }
};