Maximum Difference Between Increasing Elements

EASY

Description

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

Checkout 2 different approaches to solve Maximum Difference Between Increasing Elements. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Maximum Difference Between Increasing Elements. Click on different languages to view the code.

/** * // 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 ; } }

Video Solution

Watch the video walkthrough for Maximum Difference Between Increasing Elements

Data Structures:

Array

Companies:

Cisco |Salesforce |MathWorks |