Maximum Difference Between Increasing Elements — Solution
Maximum Difference Between Increasing Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Difference Between Increasing Elements is an easy coding problem on arrays, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a 0-indexed array nums, find indices i < j with nums[i] < nums[j] that maximise nums[j] - nums[i].
Return that maximum difference, or -1 if no such pair exists.
Example 1
Input: nums = [7,1,5,4]
Output: 4
Explanation: i = 1 and j = 2 give 5 - 1 = 4.
Example 2
Input: nums = [9,4,3,2]
Output: -1
Explanation: The array is strictly decreasing, so no valid pair exists.
Example 3
Input: nums = [1,5,2,10]
Output: 9
Constraints
2 <= nums.length <= 10001 <= nums[i] <= 1000000000
Hints for Maximum Difference Between Increasing Elements
Hint 1
For a fixed
j, the best partner is the smallest value anywhere to its left.Hint 2
Sweep left to right keeping the running minimum.
Hint 3
Only update the answer when the current value strictly exceeds that minimum.
How to solve Maximum Difference Between Increasing Elements
This is the "best time to buy and sell stock" scan with one extra rule: the profit must be strictly positive, otherwise the answer is -1.
Approach
- Set
lo = nums[0]andbest = -1. - For each later element: if it exceeds
lo, updatebestwithnums[i] - lo. - Otherwise it is a new minimum, so set
lo = nums[i]. - Return
best.
Why it works
Fixing j and minimising nums[i] over i < j maximises the difference for that j, and the running minimum supplies exactly that value in O(1). Sweeping every j therefore covers the global optimum.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Initialising
bestto0hides the "no valid pair" case, which must answer-1. - Updating
lobefore testing the current element allows the degenerate pairi == j. - The requirement is
nums[i] < nums[j]strictly — equal values do not count.
Reference solution
Python
from typing import List
def maximumDifference(nums: List[int]) -> int:
best = -1
lo = nums[0]
for i in range(1, len(nums)):
if nums[i] > lo:
if nums[i] - lo > best:
best = nums[i] - lo
else:
lo = nums[i]
return bestJava
public static int maximumDifference(int[] nums) {
int best = -1, lo = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > lo) {
int d = nums[i] - lo;
if (d > best) best = d;
} else {
lo = nums[i];
}
}
return best;
}C++
int maximumDifference(vector<int>& nums) {
int best = -1, lo = nums[0];
for (int i = 1; i < (int) nums.size(); i++) {
if (nums[i] > lo) {
int d = nums[i] - lo;
if (d > best) best = d;
} else {
lo = nums[i];
}
}
return best;
}JavaScript
var maximumDifference = function(nums) {
let best = -1, lo = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] > lo) {
const d = nums[i] - lo;
if (d > best) best = d;
} else {
lo = nums[i];
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays