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] <= 109In 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) due to the nested loops.
Space Complexity: O(1) as just scalar variables are used.
| 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. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,212 views views
Watch 9 more video solutions →Practice Maximum Difference Between Increasing Elements with our built-in code editor and test cases.
Practice on FleetCode