Problem statement

https://leetcode.com/problems/maximum-width-ramp/

Solution

Let us sort pairs (value, index). Then we can start to traverse from smallest values and update imin is minimum index so far.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def maxWidthRamp(self, A):
        imin, res = float('Inf'), 0
        for a, i in sorted([(a, i) for i, a in enumerate(A)]):
            res = max(res, i - imin)
            imin = min(imin, i)

        return res

Remark

There is also O(n) time complexity solution, using monotonic stack. Another way to solve in O(n) is to use cumulative min of prefixes, cumulative max of suffixes and two pointers approach.