LeetCode 2016. Maximum Difference Between Increasing Elements Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: Maintaining Prefix Minimum

We use a variable mi to represent the minimum value among the elements currently being traversed, and a variable ans to represent the maximum difference. Initially, mi is set to +∞, and ans is set to -1.

Traverse the array. For the current element x, if x \gt mi, update ans to max(ans, x - mi). Otherwise, update mi to x.

After the traversal, return ans.

Time complexity is O(n), where n is the length of the array. Space complexity is O(1).

PythonJavaC++GoTypeScriptRustJavaScript

class Solution: def maximumDifference(self, nums: List[int]) -> int: mi = inf ans = -1 for x in nums: if x > mi: ans = max(ans, x - mi) else: mi = x return ans(code-box)

class Solution { public int maximumDifference(int[] nums) { int mi = 1 << 30; int ans = -1; for (int x : nums) { if (x > mi) { ans = Math.max(ans, x - mi); } else { mi = x; } } return ans; } }(code-box)

class Solution { public: int maximumDifference(vector<int>& nums) { int mi = 1 << 30; int ans = -1; for (int& x : nums) { if (x > mi) { ans = max(ans, x - mi); } else { mi = x; } } return ans; } };(code-box)

func maximumDifference(nums []int) int { mi := 1 << 30 ans := -1 for _, x := range nums { if mi < x { ans = max(ans, x-mi) } else { mi = x } } return ans }(code-box)

function maximumDifference(nums: number[]): number { let [ans, mi] = [-1, Infinity]; for (const x of nums) { if (x > mi) { ans = Math.max(ans, x - mi); } else { mi = x; } } return ans; }(code-box)

impl Solution { pub fn maximum_difference(nums: Vec<i32>) -> i32 { let mut mi = i32::MAX; let mut ans = -1; for &x in &nums { if x > mi { ans = ans.max(x - mi); } else { mi = x; } } ans } }(code-box)

/** * @param {number[]} nums * @return {number} */ var maximumDifference = function (nums) { let [ans, mi] = [-1, Infinity]; for (const x of nums) { if (x > mi) { ans = Math.max(ans, x - mi); } else { mi = x; } } return ans; };(code-box)