## Similar Problems

Similar Problems not available

# Maximum Width Ramp - Leetcode Solution

LeetCode: Maximum Width Ramp Leetcode Solution

Difficulty: Medium

The Maximum Width Ramp problem on LeetCode asks us to find the maximum width of a ramp in an integer array. A ramp is defined as a pair (i, j) where i < j and arr[i] ≤ arr[j]. The width of the ramp is j - i.

The first step in solving this problem is to identify that we need to find the maximum width ramp, so we need to iterate through the array and check for the ramp pairs. The brute force approach would be to create nested loops to check all possible ramp pairs and keep track of the maximum width encountered. However, this approach will lead to a time complexity of O(n^2), which is too slow for large arrays.

A more optimal approach is to preprocess the array and create an index array that stores the indices of elements in non-increasing order. This will allow us to search for the largest index j for which arr[j] is greater than or equal to arr[i], in logarithmic time using binary search. We can then calculate the width of the ramp using the indices i and j.

Here's the detailed solution in Python:

```
def maxWidthRamp(arr: List[int]) -> int:
n = len(arr)
index_array = sorted(range(n), key=lambda i: arr[i], reverse=True)
# sort the indices based on decreasing order of elements in arr
max_width = 0
min_index = n
for i in index_array:
# iterate through the sorted indices
max_width = max(max_width, i - min_index)
min_index = min(min_index, i)
# update the minimum index
return max_width
```

We start by calculating the length of the array and creating the index array using the `sorted()`

function. We use a lambda function to sort the indices based on decreasing order of elements in `arr`

, as we need to find the largest index `j`

for each `i`

.

We initialize the `max_width`

to 0 and `min_index`

to the maximum possible value, `n`

. We then iterate through the sorted indices and update the `max_width`

and `min_index`

values based on each index encountered.

For each index `i`

, we check if `i - min_index`

is greater than the current `max_width`

. If yes, we update the `max_width`

. We then update the `min_index`

to the minimum value between the current `min_index`

and `i`

.

Finally, we return the `max_width`

after all the indices have been checked.

The time complexity of this solution is O(nlogn) because of the sorting and binary search operations. The space complexity is also O(n) because of the index array created.

## Maximum Width Ramp Solution Code

`1`