Scale Engineer

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
CiscoSalesforceMathWorks

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] <= 109

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.

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

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.

Solutions

/** * // 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 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 →

Next problem