Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For a fixed later element, the greatest increase uses the smallest earlier element. A running prefix minimum captures that choice while preserving the required index order. Only a strictly positive difference qualifies.

Approach

Initialize the minimum with the first value and the best difference with zero. For every later value, compare its difference from the stored minimum with the best, then update the minimum to include it for future positions. Return the best if positive, otherwise -1. Measuring before updating keeps the earlier-element interpretation clear, and equal-valued pairs never count as an increase.

class Solution:
    def maximumDifference(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        mn = nums[0]

        for i in range(1, n):
            res = max(res, nums[i] - mn)
            mn = min(mn, nums[i])

        return res if res != 0 else -1

Complexity analysis

Let n = nums.length. Time: O(n) for one prefix-minimum scan. Auxiliary space: O(1).