Maximum Difference Between Increasing Elements LeetCode Solution

Difficulty Level Easy
Frequently asked in Cisco ExpediaViews 2745

Problem Statement

Maximum Difference Between Increasing Elements LeetCode Solution – 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.

Examples & Explanations

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.

Approach

We can find the max difference if we subtract the smallest number from the largest one. But it is possible that the smallest number comes after the occurrence of the largest. So we can not keep a track of both numbers. Let’s then track only the smallest number. Use a variable minELe whose value will be the minimum element visited so far. To find the max difference, simply subtract minEle from each element one by one and store the difference in another variable res. Initialize res = -1, and update res by max (res, nums[i] – minEle ) for i belonging to 0 to | nums |. To ensure nums[i] appear after minELe, we can put a condition before updating res that update res iff nums[i] ≠ minEle.

To find for each element nums[i] the maximum nums[i]-nums[k] (where k<i), we just need to find minimum element in array before i.
so just to iterate through the array and on each iteration:
1. update max diff nums[i]-min is needed
2. update local minimum if needed

Code

C++ code for Maximum Difference Between Increasing Elements

class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int res=-1;
        int minEle=INT_MAX;
        for(int i=0; i<nums.size(); i++) {
            minEle=min(minEle,nums[i]);
            if(nums[i]!=minEle)
                res=max(res,nums[i]-minEle);
        }
        return max(res,-1);
    }
};

Java code for Maximum Difference Between Increasing Elements

class Solution {
    public int maximumDifference(int[] nums) {
        int res=-1;
        int minEle = Integer.MAX_VALUE;
        for(int i=0; i<nums.length; i++) {
            minEle = Math.min(minEle,nums[i]);
            if(nums[i]!=minEle)
                res=Math.max(res,nums[i]-minEle);
        }
        return Math.max(res,-1);
    }
}

Complexity Analysis for Maximum Difference Between Increasing Elements LeetCode Solution

  • Time complexity: O(N)
    • N = size of given array “nums”
    • One loop is used in the algorithm to traverse all elements in nums
  • Space complexity: O(1)
    • No additional space is required
Translate »