# Maximum Difference Between Increasing Elements **Difficulty:** EASY [External](https://leetcode.com/problems/maximum-difference-between-increasing-elements) Canonical: https://scaleengineer.com/dsa/problems/maximum-difference-between-increasing-elements **Data structures:** Array **Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [Salesforce](https://scaleengineer.com/companies/salesforce), [MathWorks](https://scaleengineer.com/companies/mathworks) --- ## Problem 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` # Approaches ## Brute Force Approach 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. **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. **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. ### Explanation 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. ```java class Solution { public int maximumDifference(int[] nums) { int maxDifference = -1; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (nums[j] > nums[i]) { int difference = nums[j] - nums[i]; if (difference > maxDifference) { maxDifference = difference; } } } } return maxDifference; } } ``` ### 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`. ## Single Pass with Minimum Tracking 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. **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. **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. ### Explanation 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. ```java class Solution { public int maximumDifference(int[] nums) { int maxDifference = -1; int minElement = Integer.MAX_VALUE; for (int num : nums) { if (num > minElement) { maxDifference = Math.max(maxDifference, num - minElement); } minElement = Math.min(minElement, num); } return maxDifference; } } ``` ### 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`. # Solutions ### Java ```java /** * // 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 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 ; } } ``` ### JavaScript ```javascript /** * // 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 = function (nestedList) { const dfs = (nestedList, depth) => { let depthSum = 0; for (const item of nestedList) { if (item.isInteger()) { depthSum += item.getInteger() * depth; } else { depthSum += dfs(item.getList(), depth + 1); } } return depthSum; }; return dfs(nestedList, 1); }; ``` ### Python ```python # """ # 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 ) ```