Problem

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.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4

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

1
2
3
4

Input: nums = [1̲ ,5,2,1̲0̲]
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] <= 10^9

Solution

Method 1 - Single Pass with Minimum Tracking

Intuition

To maximize the difference nums[j] - nums[i] with i < j and nums[i] < nums[j], keep track of the smallest value seen so far as you iterate. For each element, compute the difference with the minimum so far if it’s greater, and update the answer.

Approach

  1. Initialize ans to -1 and min_val to the first element.
  2. Iterate through the array from the second element:
  • If the current element is greater than min_val, update ans with the maximum of ans and the difference.
  • Otherwise, update min_val to the current element.
  1. Return ans after the loop.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
   int maximumDifference(vector<int>& nums) {
      int ans = -1, min_val = nums[0];
      for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > min_val)
           ans = max(ans, nums[i] - min_val);
        else
           min_val = nums[i];
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func maximumDifference(nums []int) int {
   ans := -1
   minVal := nums[0]
   for i := 1; i < len(nums); i++ {
      if nums[i] > minVal {
        if nums[i]-minVal > ans {
           ans = nums[i] - minVal
        }
      } else {
        minVal = nums[i]
      }
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
   public int maximumDifference(int[] nums) {
      int ans = -1, minVal = nums[0];
      for (int i = 1; i < nums.length; i++) {
        if (nums[i] > minVal)
           ans = Math.max(ans, nums[i] - minVal);
        else
           minVal = nums[i];
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
   fun maximumDifference(nums: IntArray): Int {
      var ans = -1
      var minVal = nums[0]
      for (i in 1 until nums.size) {
        if (nums[i] > minVal)
           ans = maxOf(ans, nums[i] - minVal)
        else
           minVal = nums[i]
      }
      return ans
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
   def maximumDifference(self, nums: list[int]) -> int:
      ans: int = -1
      min_val: int = nums[0]
      for num in nums[1:]:
        if num > min_val:
           ans = max(ans, num - min_val)
        else:
           min_val = num
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
   pub fn maximum_difference(nums: Vec<i32>) -> i32 {
      let mut ans = -1;
      let mut min_val = nums[0];
      for &num in nums.iter().skip(1) {
        if num > min_val {
           ans = ans.max(num - min_val);
        } else {
           min_val = num;
        }
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(n) — Single pass through the array.
  • 🧺 Space complexity: O(1) — Only a few variables used.