Maximum Difference Between Increasing Elements

Easy
501.

Maximum Difference Between Increasing Elements

Maximum Difference Between Increasing Elements is an easy coding problem on arrays, asked in Amazon and Google interviews.

Given a 0-indexed array nums, find indices i < j with nums[i] < nums[j] that maximise nums[j] - nums[i].

Return that maximum difference, or -1 if no such pair exists.

Example 1

Input
nums = [7,1,5,4]
Output
4
Explanation
i = 1 and j = 2 give 5 - 1 = 4.

Example 2

Input
nums = [9,4,3,2]
Output
-1
Explanation
The array is strictly decreasing, so no valid pair exists.

Example 3

Input
nums = [1,5,2,10]
Output
9

Constraints

  • 2 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumDifference = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Difference Between Increasing Elements — Solution

Maximum Difference Between Increasing Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Difference Between Increasing Elements is an easy coding problem on arrays, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a 0-indexed array nums, find indices i < j with nums[i] < nums[j] that maximise nums[j] - nums[i].

Return that maximum difference, or -1 if no such pair exists.

Example 1

Input: nums = [7,1,5,4]
Output: 4
Explanation: i = 1 and j = 2 give 5 - 1 = 4.

Example 2

Input: nums = [9,4,3,2]
Output: -1
Explanation: The array is strictly decreasing, so no valid pair exists.

Example 3

Input: nums = [1,5,2,10]
Output: 9

Constraints

  • 2 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000000000

Hints for Maximum Difference Between Increasing Elements

  1. Hint 1

    For a fixed j, the best partner is the smallest value anywhere to its left.

  2. Hint 2

    Sweep left to right keeping the running minimum.

  3. Hint 3

    Only update the answer when the current value strictly exceeds that minimum.

How to solve Maximum Difference Between Increasing Elements

This is the "best time to buy and sell stock" scan with one extra rule: the profit must be strictly positive, otherwise the answer is -1.

Approach

  1. Set lo = nums[0] and best = -1.
  2. For each later element: if it exceeds lo, update best with nums[i] - lo.
  3. Otherwise it is a new minimum, so set lo = nums[i].
  4. Return best.

Why it works

Fixing j and minimising nums[i] over i < j maximises the difference for that j, and the running minimum supplies exactly that value in O(1). Sweeping every j therefore covers the global optimum.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Initialising best to 0 hides the "no valid pair" case, which must answer -1.
  • Updating lo before testing the current element allows the degenerate pair i == j.
  • The requirement is nums[i] < nums[j] strictly — equal values do not count.

Reference solution

Python

from typing import List

def maximumDifference(nums: List[int]) -> int:
    best = -1
    lo = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > lo:
            if nums[i] - lo > best:
                best = nums[i] - lo
        else:
            lo = nums[i]
    return best

Java

public static int maximumDifference(int[] nums) {
    int best = -1, lo = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > lo) {
            int d = nums[i] - lo;
            if (d > best) best = d;
        } else {
            lo = nums[i];
        }
    }
    return best;
}

C++

int maximumDifference(vector<int>& nums) {
    int best = -1, lo = nums[0];
    for (int i = 1; i < (int) nums.size(); i++) {
        if (nums[i] > lo) {
            int d = nums[i] - lo;
            if (d > best) best = d;
        } else {
            lo = nums[i];
        }
    }
    return best;
}

JavaScript

var maximumDifference = function(nums) {
    let best = -1, lo = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > lo) {
            const d = nums[i] - lo;
            if (d > best) best = d;
        } else {
            lo = nums[i];
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays