LC-0962 Medium LeetCode

962. Maximum Width Ramp

Array Two Pointers Stack Monotonic Stack

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 56% Topics: Array, Two Pointers, Stack, Monotonic Stack

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def maxWidthRamp(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        result = 0
        s = []
        for i in A:
            if not s or A[s[-1]] > A[i]:
                s.append(i)
        for j in reversed(xrange(len(A))):
            while s and A[s[-1]] <= A[j]:
                result = max(result, j-s.pop())
        return result

Solution from kamyu104/LeetCode-Solutions · MIT