What is the time complexity of the Brute Force approach?

The time complexity of the Brute Force approach is O(n²), where n is the length of the array.

What is the time complexity of the One Pass approach?

The time complexity of the One Pass approach is O(n), as we traverse the array only once.

What is the space complexity of these approaches?

The space complexity is O(1) for both approaches, as we only use a few extra variables.

Maximum Difference Between Increasing Elements

Difficulty: Easy | Acceptance: 66.60% | Paid: No Topics: Array

Given a 0-indexed integer array nums of size n, find the maximum difference nums[j] - nums[i] such that 0 <= i < j < n and nums[i] < nums[j].

Return -1 if no such pair exists.

Examples
Constraints
Brute Force
One Pass

Examples

Example 1:

Input: nums = [7,1,5,4]
Output: 4
Explanation:
The maximum difference occurs with i = 1 and j = 2, nums[2] - nums[1] = 5 - 1 = 4.
Note that with i = 1 and j = 0, the difference nums[0] - nums[1] = 7 - 1 = 6 is invalid because 0 > 1.

Example 2:

Input: nums = [9,4,3,2]
Output: -1
Explanation:
There is no valid pair i < j such that nums[i] < nums[j].

Example 3:

Input: nums = [1,5,2,10]
Output: 9
Explanation:
The maximum difference occurs with i = 0 and j = 3, nums[3] - nums[0] = 10 - 1 = 9.

Constraints

2 <= nums.length <= 1000
1 <= nums[i] <= 10^9

Brute Force

Intuition Check every possible pair (i, j) where i < j to see if they satisfy the condition and track the maximum difference found.

Steps

Initialize max_diff to -1.
Iterate through the array with index i from 0 to n-2.
Iterate through the array with index j from i+1 to n-1.
If nums[j] > nums[i], update max_diff with the maximum of its current value and nums[j] - nums[i].
Return max_diff.

python

from typing import List

class Solution:
    def maximumDifference(self, nums: List[int]) -&gt; int:
        n = len(nums)
        max_diff = -1
        for i in range(n - 1):
            for j in range(i + 1, n):
                if nums[j] &gt; nums[i]:
                    max_diff = max(max_diff, nums[j] - nums[i])
        return max_diff

Complexity

Time: O(n²)
Space: O(1)
Notes: Simple but inefficient for large arrays.

One Pass

Intuition Maintain the minimum element encountered so far. For each subsequent element, the maximum difference ending at that element is the current element minus the minimum seen so far.

Steps

Initialize min_val to nums[0] and max_diff to -1.
Iterate through the array starting from index 1.
If the current element is greater than min_val, calculate the difference and update max_diff if this difference is larger.
Otherwise, update min_val to the current element.
Return max_diff.

python

from typing import List

class Solution:
    def maximumDifference(self, nums: List[int]) -&gt; int:
        min_val = nums[0]
        max_diff = -1
        for i in range(1, len(nums)):
            if nums[i] &gt; min_val:
                max_diff = max(max_diff, nums[i] - min_val)
            else:
                min_val = nums[i]
        return max_diff

Complexity

Time: O(n)
Space: O(1)
Notes: Optimal solution with linear scan.