Maximum Difference Between Increasing Elements - Solution & Explanation
Problem Statement
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.length2 <= n <= 10001 <= nums[i] <= 109
Approach Overview
Problem Overview: You are given an integer array nums. The goal is to find the maximum value of nums[j] - nums[i] such that j > i and nums[j] > nums[i]. If no increasing pair exists, return -1. The constraint forces you to respect order, so you cannot simply sort the array. The solution must compare elements while preserving their original positions.
Approach 1: Brute Force Comparison (O(n2) time, O(1) space)
The most direct method checks every valid pair. Iterate through the array with index i, then scan all elements to the right using j. Whenever nums[j] > nums[i], compute the difference and update the maximum result. This guarantees the correct answer because every possible increasing pair is evaluated. The drawback is quadratic time complexity since each element compares against all elements after it. This approach is mainly useful for validating logic or when constraints are extremely small. The problem itself belongs to common array scanning patterns where naive pair comparison is the baseline solution.
Approach 2: Single Pass with Minimum Tracking (O(n) time, O(1) space)
The optimal solution tracks the smallest element seen so far while scanning the array from left to right. Maintain a variable minVal initialized to the first element. For each new element nums[i], compute the difference nums[i] - minVal. If this difference is positive, update the maximum answer. Then update minVal = min(minVal, nums[i]) so future elements compare against the smallest prefix value. The key insight: the best candidate for nums[i] is always the minimum value that appeared before it. This eliminates the need for nested loops and converts the search into a single linear pass. The pattern is closely related to greedy prefix tracking problems in array processing and simple greedy optimization.
Recommended for interviews: Interviewers expect the single-pass minimum tracking solution. The brute force approach shows you understand the problem constraints, but the O(n) solution demonstrates pattern recognition and efficient state tracking. Many interview problems use the same idea: keep the best prefix value while scanning forward and update the result using the current element.
Approach 1: Single Pass with Minimum Tracking
In this approach, we traverse the array while maintaining a record of the minimum value encountered so far. For each element, we calculate the difference between the current element and the minimum. If this difference is greater than the current maximum difference, we update it. This way, we ensure a linear passage through the data, providing us an efficient solution.
This C solution uses a single traversal of the array to find the maximum difference between successive numbers. We maintain the minimum value encountered so far and update the maximum difference whenever the current value is larger than this minimal value.
Complexity
Time Complexity: O(n) where n is the number of elements in nums.
Space Complexity: O(1), as we only use a constant amount of extra space.
Approach 2: Brute Force Comparison
Another way to solve this problem is through brute force by checking every possible combination of indices. For each pair, we check if the first element is less than the second and compute the difference. This method might not be the most efficient but ensures cross-validation of outcomes.
This approach involves two nested loops to evaluate each possible pair of indices and calculate the possible maximum difference based on conditions.
Complexity
Time Complexity: O(n^2) due to the nested loops.
Space Complexity: O(1) as just scalar variables are used.
Approach 3: 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 +infty, 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).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Single Pass with Minimum Tracking | Time Complexity: O(n) where n is the number of elements in nums. |
| Brute Force Comparison | Time Complexity: O(n^2) due to the nested loops. |
| Maintaining Prefix Minimum | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n^2) | O(1) | Useful for understanding the problem or when input size is very small |
| Single Pass with Minimum Tracking | O(n) | O(1) | Best general solution; optimal for interviews and large arrays |
Video Solution
Maximum Difference Between Increasing Elements | Easy | Leetcode 2016 | codestorywithMIK • codestorywithMIK • 4,538 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Difference Between Increasing Elements easy or hard?
Maximum Difference Between Increasing Elements Python/Java solution
How to solve Maximum Difference Between Increasing Elements in O(n)?
What is the best approach for Maximum Difference Between Increasing Elements?
Is Maximum Difference Between Increasing Elements asked at Google/Amazon/Meta?
What data structure is used in Maximum Difference Between Increasing Elements?
What is the time complexity of Maximum Difference Between Increasing Elements?
Ready to solve this problem?
Practice Maximum Difference Between Increasing Elements with our built-in code editor and test cases.
Practice on FleetCode