Maximum Difference Between Increasing Elements

Easy

#1836Time: O(n^2), where n is the number of elements in the `nums` array. This is because we have two nested loops, and in the worst case, the inner loop runs approximately n times for each of the n iterations of the outer loop.Space: O(1), as we only use a constant amount of extra space for variables like `maxDifference`, `i`, and `j`, regardless of the input size.3 companies

Data structures

Array

Companies

Cisco Salesforce MathWorks

Prompt

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] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through all possible pairs of elements (nums[i], nums[j]) where i comes before j. For each valid pair that satisfies nums[i] < nums[j], we calculate the difference and keep track of the maximum difference found.

Algorithm

Initialize a variable maxDifference to -1.
Iterate through the array with an index i from 0 to n-2.
For each i, start a nested iteration with an index j from i+1 to n-1.
Inside the inner loop, check if nums[j] is greater than nums[i].
If it is, calculate the difference diff = nums[j] - nums[i].
Update maxDifference to be the maximum of its current value and diff.
After both loops complete, return maxDifference.

Walkthrough

The brute-force method systematically checks every possible pair of indices (i, j) that satisfy the condition 0 <= i < j < n. We use nested loops to achieve this. The outer loop selects the first element nums[i], and the inner loop selects the second element nums[j].

Inside the inner loop, we check if nums[j] is greater than nums[i]. If it is, we calculate their difference. We maintain a variable, maxDifference, initialized to -1, which is updated whenever a larger difference is found. If no pair satisfies nums[i] < nums[j], the maxDifference remains -1, which is the correct output in that case.

1class Solution {2    public int maximumDifference(int[] nums) {3        int maxDifference = -1;4        int n = nums.length;5        for (int i = 0; i < n; i++) {6            for (int j = i + 1; j < n; j++) {7                if (nums[j] > nums[i]) {8                    int difference = nums[j] - nums[i];9                    if (difference > maxDifference) {10                        maxDifference = difference;11                    }12                }13            }14        }15        return maxDifference;16    }17}

Complexity

Time

O(n^2), where n is the number of elements in the `nums` array. This is because we have two nested loops, and in the worst case, the inner loop runs approximately n times for each of the n iterations of the outer loop.

Space

O(1), as we only use a constant amount of extra space for variables like `maxDifference`, `i`, and `j`, regardless of the input size.

Trade-offs

Pros

Simple to understand and implement.
Guaranteed to find the correct answer.

Cons

Highly inefficient for large input arrays due to its O(n^2) time complexity.
Likely to cause a 'Time Limit Exceeded' error on competitive programming platforms with large test cases.

A more efficient approach is to traverse the array a single time. While iterating, we keep track of the minimum element encountered so far. For each subsequent element, we calculate the difference between it and this running minimum, updating our maximum difference if the new difference is larger.

Algorithm

Initialize maxDifference to -1.
Initialize minElement to a very large value (e.g., Integer.MAX_VALUE).
Iterate through each element num in the nums array.
For each num:
- Check if num is greater than minElement. If it is, it means we found a valid pair. Calculate difference = num - minElement and update maxDifference = Math.max(maxDifference, difference).
- After the check, update minElement = Math.min(minElement, num). This ensures minElement always holds the minimum value encountered so far.
After the loop, return maxDifference.

Walkthrough

This optimized solution is based on the idea that to maximize the difference nums[j] - nums[i] with i < j, for any given j, we need to find the smallest nums[i] where i < j.

We can achieve this in a single pass. We initialize a variable minElement with a very large value and maxDifference with -1. Then, we iterate through the array. In each iteration, the current element num is a potential nums[j]. The minElement variable holds the minimum value seen in all previous iterations, which is our best candidate for nums[i].

If num is greater than minElement, we calculate the difference and update maxDifference. Crucially, after this check, we update minElement with the current num if it's smaller. This ensures that for all future elements, minElement correctly reflects the minimum value seen so far in the array.

1class Solution {2    public int maximumDifference(int[] nums) {3        int maxDifference = -1;4        int minElement = Integer.MAX_VALUE;5        6        for (int num : nums) {7            if (num > minElement) {8                maxDifference = Math.max(maxDifference, num - minElement);9            }10            minElement = Math.min(minElement, num);11        }12        13        return maxDifference;14    }15}

Complexity

Time

O(n), where n is the number of elements in the array. We iterate through the array only once.

Space

O(1), as we only use a constant number of variables (`maxDifference`, `minElement`) to store state, irrespective of the input array's size.

Trade-offs

Pros

Highly efficient with a linear time complexity.
Optimal solution for this problem, easily handling large inputs.
Requires minimal extra space.

Cons

May be slightly less intuitive to come up with compared to the brute-force approach.

Solutions

Solution

1/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public interface NestedInteger { * // Constructor initializes an empty nested list. * public NestedInteger(); * * // Constructor initializes a single integer. * public NestedInteger(int value); * * // @return true if this NestedInteger holds a single integer, rather than a nested list. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer getInteger(); * * // Set this NestedInteger to hold a single integer. * public void setInteger(int value); * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * public void add(NestedInteger ni); * * // @return the nested list that this NestedInteger holds, if it holds a nested list * // Return empty list if this NestedInteger holds a single integer * public List<NestedInteger> getList(); * } */ class Solution { public int depthSum ( List < NestedInteger > nestedList ) { return dfs ( nestedList , 1 ); } private int dfs ( List < NestedInteger > nestedList , int depth ) { int depthSum = 0 ; for ( NestedInteger item : nestedList ) { if ( item . isInteger ()) { depthSum += item . getInteger () * depth ; } else { depthSum += dfs ( item . getList (), depth + 1 ); } } return depthSum ; } }

1/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * function NestedInteger() { * * Return true if this NestedInteger holds a single integer, rather than a nested list. * @return {boolean} * this.isInteger = function() { * ... * }; * * Return the single integer that this NestedInteger holds, if it holds a single integer * Return null if this NestedInteger holds a nested list * @return {integer} * this.getInteger = function() { * ... * }; * * Set this NestedInteger to hold a single integer equal to value. * @return {void} * this.setInteger = function(value) { * ... * }; * * Set this NestedInteger to hold a nested list and adds a nested integer elem to it. * @return {void} * this.add = function(elem) { * ... * }; * * Return the nested list that this NestedInteger holds, if it holds a nested list * Return null if this NestedInteger holds a single integer * @return {NestedInteger[]} * this.getList = function() { * ... * }; * }; */ /** * @param {NestedInteger[]} nestedList * @return {number} */ var depthSum =2  function (nestedList) {3    const dfs = (nestedList, depth) => {4      let depthSum = 0;5      for (const item of nestedList) {6        if (item.isInteger()) {7          depthSum += item.getInteger() * depth;8        } else {9          depthSum += dfs(item.getList(), depth + 1);10        }11      }12      return depthSum;13    };14    return dfs(nestedList, 1);15  };

1# """ # This is the interface that allows for creating nested lists. # You should not implement it, or speculate about its implementation # """ # class NestedInteger: # def __init__(self, value=None): # """ # If value is not specified, initializes an empty list. # Otherwise initializes a single integer equal to value. # """ # # def isInteger(self): # """ # @return True if this NestedInteger holds a single integer, rather than a nested list. # :rtype bool # """ # # def add(self, elem): # """ # Set this NestedInteger to hold a nested list and adds a nested integer elem to it. # :rtype void # """ # # def setInteger(self, value): # """ # Set this NestedInteger to hold a single integer equal to value. # :rtype void # """ # # def getInteger(self): # """ # @return the single integer that this NestedInteger holds, if it holds a single integer # Return None if this NestedInteger holds a nested list # :rtype int # """ # # def getList(self): # """ # @return the nested list that this NestedInteger holds, if it holds a nested list # Return None if this NestedInteger holds a single integer # :rtype List[NestedInteger] # """ class Solution : def depthSum ( self , nestedList : List [ NestedInteger ]) -> int : def dfs ( nestedList , depth ): depth_sum = 0 for item in nestedList : if item . isInteger (): depth_sum += item . getInteger () * depth else : depth_sum += dfs ( item . getList (), depth + 1 ) return depth_sum return dfs ( nestedList , 1 ) ################ class Solution : # iterative def depthSum ( self , nestedList ): stack = [] for nestedInteger in nestedList : stack . append (( 1 , nestedInteger )) ans = 0 while stack : depth , current = stack . pop () if current . isInteger (): ans += depth * current . getInteger () else : lst = current . getList () for nestedInteger in lst : stack . append (( depth + 1 , nestedInteger )) return ans ############ class Solution ( object ): def depthSum ( self , nestedList ): """ :type nestedList: List[NestedInteger] :rtype: int """ def helper ( root , depth ): res = 0 for nested in root : if nested . isInteger (): res += depth * nested . getInteger () else : res += helper ( nested . getList (), depth + 1 ) return res return helper ( nestedList , 1 )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem