Problem Description

You are given a 0-indexed integer array nums of size n. Your task is to find the maximum difference between two elements in the array where the second element comes after the first element and is greater than it.

Specifically, you need to find the maximum value of nums[j] - nums[i] where:

• 0 <= i < j < n (i comes before j in the array)
• nums[i] < nums[j] (the element at position j must be greater than the element at position i)

If no such pair of indices exists (meaning there's no case where a later element is greater than an earlier element), return -1.

For example:

• If nums = [7, 1, 5, 4], the maximum difference would be 5 - 1 = 4 (choosing i=1 and j=2)
• If nums = [9, 4, 3, 2], no valid pair exists since no later element is greater than an earlier one, so return -1

The solution maintains a running minimum value (mi) as it traverses the array. For each element x, if it's greater than the current minimum, it calculates the difference x - mi and updates the answer if this difference is larger. If x is not greater than the minimum, it updates the minimum to x. This ensures we always have the smallest possible earlier element to maximize the difference with any later greater element.

Intuition

To maximize nums[j] - nums[i], we want to make nums[j] as large as possible and nums[i] as small as possible. However, there's a constraint: i must come before j in the array.

This constraint suggests we should think about the problem from left to right. As we traverse the array, at each position j, we want to know: what's the smallest element that appeared before this position? If we know that, we can calculate the potential difference at position j.

The key insight is that we don't need to remember all previous elements - we only need to track the minimum element seen so far. Why? Because for any position j, if we want to maximize nums[j] - nums[i] where i < j, we should always choose the smallest possible nums[i] from all valid positions before j.

Think of it this way: imagine you're walking through the array from left to right. At each step, you ask yourself two questions:

1. Can the current element form a better difference with the minimum element I've seen so far?
2. Should the current element become the new minimum for future elements to compare against?

If the current element is greater than our tracked minimum, we calculate the difference and update our answer if it's better. If the current element is smaller than or equal to our tracked minimum, it becomes the new minimum because it could potentially create larger differences with future elements.

This greedy approach works because we're always maintaining the best possible "buying point" (minimum value) as we look for the best "selling point" (maximum difference).

Solution Approach

The solution uses a single-pass traversal with two variables to track the necessary information:

1. Initialize variables:

   • mi = inf: Represents the minimum value seen so far. Initially set to infinity so any first element will become the new minimum.
   • ans = -1: Stores the maximum difference found. Initially -1 to handle the case where no valid pair exists.

2. Traverse the array: For each element x in nums:

   • Check if we can form a valid difference: If x > mi, this means we have found a valid pair where the current element is greater than some previous element. Calculate the difference x - mi and update ans if this difference is larger: ans = max(ans, x - mi).
   • Update the minimum: If x <= mi, update mi = x. This element becomes the new minimum for future comparisons.

3. Return the result: After traversing all elements, return ans. If no valid pair was found, ans remains -1.

Why this works:

• By maintaining the minimum element seen so far (mi), we ensure that for any position j, we're always calculating the maximum possible difference with all valid positions i < j.
• The condition x > mi naturally handles the constraint nums[i] < nums[j].
• The position constraint i < j is automatically satisfied because mi only contains values from positions before the current position.

Time Complexity: O(n) - We traverse the array exactly once.

Space Complexity: O(1) - We only use two extra variables regardless of input size.

Example Walkthrough

Let's walk through the solution with nums = [7, 1, 5, 4]:

Initial State:

• mi = inf (minimum value seen so far)
• ans = -1 (maximum difference found)

Step 1: Process element 7 (index 0)

• Is 7 > inf? No
• Update minimum: mi = 7
• Current state: mi = 7, ans = -1

Step 2: Process element 1 (index 1)

• Is 1 > 7? No
• Update minimum: mi = 1
• Current state: mi = 1, ans = -1

Step 3: Process element 5 (index 2)

• Is 5 > 1? Yes! We found a valid pair
• Calculate difference: 5 - 1 = 4
• Update answer: ans = max(-1, 4) = 4
• Since we found a valid difference, we don't update mi
• Current state: mi = 1, ans = 4

Step 4: Process element 4 (index 3)

• Is 4 > 1? Yes! Another valid pair
• Calculate difference: 4 - 1 = 3
• Update answer: ans = max(4, 3) = 4 (no change, 4 is already better)
• Current state: mi = 1, ans = 4

Final Result: Return ans = 4

The maximum difference is 4, achieved by buying at index 1 (value = 1) and selling at index 2 (value = 5).

Let's also trace through a case with no valid pairs: nums = [9, 4, 3, 2]:

Step 1: Process 9 → mi = 9, ans = -1 Step 2: Process 4 → 4 < 9, so mi = 4, ans = -1 Step 3: Process 3 → 3 < 4, so mi = 3, ans = -1 Step 4: Process 2 → 2 < 3, so mi = 2, ans = -1

Final Result: Return ans = -1 (no valid pair found where a later element is greater)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array nums. The algorithm iterates through the array exactly once with a single for loop, performing constant-time operations (comparisons and assignments) for each element.

Space Complexity: O(1). The algorithm uses only a constant amount of extra space regardless of the input size. It maintains just two variables: mi (to track the minimum value seen so far) and ans (to track the maximum difference). These variables do not scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Minimum Update Logic

A common mistake is updating the minimum value regardless of whether we found a valid difference or not:

Incorrect approach:

for num in nums:
    if num > min_value:
        max_diff = max(max_diff, num - min_value)
    min_value = min(min_value, num)  # Wrong: Always updating minimum

Why it's wrong: This updates the minimum even when we find a valid difference, which is actually correct behavior. The real issue is when people try to "optimize" by only updating minimum in the else block but then use min() function incorrectly.

Correct approach:

for num in nums:
    if num > min_value:
        max_diff = max(max_diff, num - min_value)
    else:
        min_value = num  # Only update when num <= min_value

2. Wrong Initial Values

Setting incorrect initial values can lead to wrong results:

Incorrect approach:

min_value = nums[0]  # Wrong if array has only one element
max_diff = 0         # Wrong: should be -1 for "no valid pair" case

Why it's wrong:

• If the array has only one element, there's no valid pair to form a difference
• Starting with max_diff = 0 would incorrectly return 0 instead of -1 when no increasing pair exists

Correct approach:

min_value = float('inf')  # Ensures first element becomes minimum
max_diff = -1             # Correct default for "no valid pair"

3. Handling Edge Cases Incorrectly

Not properly handling arrays where all elements are decreasing or equal:

Test case that breaks incorrect solutions:

nums = [9, 4, 3, 2]  # All decreasing
# Should return -1, but might return 0 if max_diff initialized to 0

nums = [5, 5, 5, 5]  # All equal
# Should return -1, but might return 0 if using >= instead of >

Solution: Ensure the condition explicitly checks num > min_value (strict inequality) and initialize max_diff = -1.

4. Updating Minimum Too Early

Some implementations mistakenly update the minimum before checking for valid differences:

Incorrect approach:

for num in nums:
    min_value = min(min_value, num)  # Wrong: Updates before checking
    if num > min_value:
        max_diff = max(max_diff, num - min_value)

Why it's wrong: This would never find any valid difference because num can never be greater than min_value after we've just potentially updated min_value to be num.

Correct approach: Always check for valid difference first, then update minimum if needed.