{x}
blog image

Maximum Difference Between Increasing Elements

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

Return the maximum difference. If no such i and j exists, return -1.

 

Example 1:

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

Example 2:

Input: nums = [9,4,3,2]
Output: -1
Explanation:
There is no i and j such that i < j and 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[j] - nums[i] = 10 - 1 = 9.

 

Constraints:

  • n == nums.length
  • 2 <= n <= 1000
  • 1 <= nums[i] <= 109

Solution Explanation: Maximum Difference Between Increasing Elements

This problem asks to find the maximum difference between two elements nums[j] - nums[i] in an array nums such that i < j and nums[i] < nums[j]. The solution leverages a single pass through the array to efficiently find this maximum difference.

Approach: Maintaining Minimum Prefix

The core idea is to keep track of the minimum element encountered so far (min_element) while iterating through the array. For each element, we check if it's greater than the min_element. If it is, we have a potential candidate for the maximum difference. We update the maximum difference (max_diff) accordingly. If the current element is less than or equal to min_element, we update min_element because we might find a larger difference later starting from this smaller element.

Algorithm:

  1. Initialization: Initialize min_element to a large value (e.g., infinity or the largest possible integer value in the language), and max_diff to -1 (representing no valid difference found yet).
  2. Iteration: Iterate through the nums array.
    • Check for Larger Element: If the current element nums[i] is greater than min_element:
      • Calculate the difference nums[i] - min_element.
      • Update max_diff to the maximum of max_diff and the calculated difference.
    • Update Minimum: If the current element is less than or equal to min_element, update min_element to nums[i].
  3. Return Result: After iterating through the entire array, return max_diff.

Code Examples (with explanations):

The provided code examples in multiple languages all implement this algorithm. Let's break down one example (Python):

class Solution:
    def maximumDifference(self, nums: List[int]) -> int:
        mi = inf  # Initialize min_element to infinity (import inf from sys module)
        ans = -1  # Initialize max_diff to -1
        for x in nums:
            if x > mi:  # Check if current element is greater than min_element
                ans = max(ans, x - mi)  # Update max_diff
            else:
                mi = x  # Update min_element
        return ans

The code is concise and directly reflects the algorithm steps. inf from the sys module represents positive infinity, ensuring the initial mi is larger than any element in nums.

Time and Space Complexity Analysis:

  • Time Complexity: O(n), where n is the length of the nums array. We perform a single pass through the array.
  • Space Complexity: O(1). We only use a constant amount of extra space to store mi and ans.

This approach offers an optimal solution for this problem with linear time complexity and constant space complexity, making it highly efficient for large input arrays.