Maximum Difference Between Increasing Elements Solution

The 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] <= 10⁹

Approach overview

Problem Overview: You are given an integer array nums. The goal is to find the maximum value of nums[j] - nums[i] such that j > i and nums[j] > nums[i]. If no increasing pair exists, return -1. The constraint forces you to respect order, so you cannot simply sort the array. The solution must compare elements while preserving their original positions.

Approach 1: Brute Force Comparison (O(n²) time, O(1) space)

The most direct method checks every valid pair. Iterate through the array with index i, then scan all elements to the right using j. Whenever nums[j] > nums[i], compute the difference and update the maximum result. This guarantees the correct answer because every possible increasing pair is evaluated. The drawback is quadratic time complexity since each element compares against all elements after it. This approach is mainly useful for validating logic or when constraints are extremely small. The problem itself belongs to common array scanning patterns where naive pair comparison is the baseline solution.

Approach 2: Single Pass with Minimum Tracking (O(n) time, O(1) space)

The optimal solution tracks the smallest element seen so far while scanning the array from left to right. Maintain a variable minVal initialized to the first element. For each new element nums[i], compute the difference nums[i] - minVal. If this difference is positive, update the maximum answer. Then update minVal = min(minVal, nums[i]) so future elements compare against the smallest prefix value. The key insight: the best candidate for nums[i] is always the minimum value that appeared before it. This eliminates the need for nested loops and converts the search into a single linear pass. The pattern is closely related to greedy prefix tracking problems in array processing and simple greedy optimization.

Recommended for interviews: Interviewers expect the single-pass minimum tracking solution. The brute force approach shows you understand the problem constraints, but the O(n) solution demonstrates pattern recognition and efficient state tracking. Many interview problems use the same idea: keep the best prefix value while scanning forward and update the result using the current element.

Approach 1: Single Pass with Minimum Tracking

In this approach, we traverse the array while maintaining a record of the minimum value encountered so far. For each element, we calculate the difference between the current element and the minimum. If this difference is greater than the current maximum difference, we update it. This way, we ensure a linear passage through the data, providing us an efficient solution.

Python

def maximumDifference(nums):
    minValue = nums[0]
    maxDifference = -1
    for j in range(1, len(nums)):
        if nums[j] > minValue:
            maxDifference = max(maxDifference, nums[j] - minValue)
        else:
            minValue = nums[j]
    return maxDifference

print(maximumDifference([7, 1, 5, 4]))

Java

class Solution {
    public int maximumDifference(int[] nums) {
        int minValue = nums[0];
        int maxDifference = -1;
        for (int j = 1; j < nums.length; ++j) {
            if (nums[j] > minValue) {
                maxDifference = Math.max(maxDifference, nums[j] - minValue);
            } else {
                minValue = nums[j];
            }
        }
        return maxDifference;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {7, 1, 5, 4};
        System.out.println(sol.maximumDifference(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maximumDifference(vector<int>& nums) {
    int minValue = nums[0];
    int maxDifference = -1;
    for (int j = 1; j < nums.size(); ++j) {
        if (nums[j] > minValue) {
            maxDifference = max(maxDifference, nums[j] - minValue);
        } else {
            minValue = nums[j];
        }
    }
    return maxDifference;
}

int main() {
    vector<int> nums = {7, 1, 5, 4};
    cout << maximumDifference(nums) << endl;
    return 0;
}

JavaScript

function maximumDifference(nums) {
    let minValue = nums[0];
    let maxDifference = -1;
    for (let j = 1; j < nums.length; j++) {
        if (nums[j] > minValue) {
            maxDifference = Math.max(maxDifference, nums[j] - minValue);
        } else {
            minValue = nums[j];
        }
    }
    return maxDifference;
}

console.log(maximumDifference([7, 1, 5, 4]));

#include <stdio.h>
#include <limits.h>

int maximumDifference(int* nums, int numsSize) {
    int minValue = nums[0];
    int maxDifference = -1;
    for (int j = 1; j < numsSize; j++) {
        if (nums[j] > minValue) {
            if (nums[j] - minValue > maxDifference) {
                maxDifference = nums[j] - minValue;
            }
        } else {
            minValue = nums[j];
        }
    }
    return maxDifference;
}

int main() {
    int nums[] = {7, 1, 5, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", maximumDifference(nums, size));
    return 0;
}

using System;

public class Solution {
    public int MaximumDifference(int[] nums) {
        int minValue = nums[0];
        int maxDifference = -1;
        for (int j = 1; j < nums.Length; j++) {
            if (nums[j] > minValue) {
                maxDifference = Math.Max(maxDifference, nums[j] - minValue);
            } else {
                minValue = nums[j];
            }
        }
        return maxDifference;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = new int[] {7, 1, 5, 4};
        Console.WriteLine(sol.MaximumDifference(nums));
    }
}

Python's solution leverages a loop to track the smallest number seen so far and computes the maximum difference whenever encountering a larger number.

Complexity

Time Complexity: O(n) with respect to array size, n.
Space Complexity: O(1) due to the fixed additional memory use.

Try this approach in the editor

Approach 2: Brute Force Comparison

Another way to solve this problem is through brute force by checking every possible combination of indices. For each pair, we check if the first element is less than the second and compute the difference. This method might not be the most efficient but ensures cross-validation of outcomes.

Python

def maximumDifference(nums):
    maxDifference = -1
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] < nums[j]:
                maxDifference = max(maxDifference, nums[j] - nums[i])
    return maxDifference

print(maximumDifference([7, 1, 5, 4]))

Java

class Solution {
    public int maximumDifference(int[] nums) {
        int maxDifference = -1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] < nums[j]) {
                    maxDifference = Math.max(maxDifference, nums[j] - nums[i]);
                }
            }
        }
        return maxDifference;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {7, 1, 5, 4};
        System.out.println(sol.maximumDifference(nums));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int maximumDifference(vector<int>& nums) {
    int maxDifference = -1;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] < nums[j]) {
                maxDifference = max(maxDifference, nums[j] - nums[i]);
            }
        }
    }
    return maxDifference;
}

int main() {
    vector<int> nums = {7, 1, 5, 4};
    cout << maximumDifference(nums) << endl;
    return 0;
}

JavaScript

function maximumDifference(nums) {
    let maxDifference = -1;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] < nums[j]) {
                maxDifference = Math.max(maxDifference, nums[j] - nums[i]);
            }
        }
    }
    return maxDifference;
}

console.log(maximumDifference([7, 1, 5, 4]));

#include <stdio.h>

int maximumDifference(int* nums, int numsSize) {
    int maxDifference = -1;
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] < nums[j] && nums[j] - nums[i] > maxDifference) {
                maxDifference = nums[j] - nums[i];
            }
        }
    }
    return maxDifference;
}

int main() {
    int nums[] = {7, 1, 5, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", maximumDifference(nums, size));
    return 0;
}

using System;

public class Solution {
    public int MaximumDifference(int[] nums) {
        int maxDifference = -1;
        for (int i = 0; i < nums.Length; i++) {
            for (int j = i + 1; j < nums.Length; j++) {
                if (nums[i] < nums[j]) {
                    maxDifference = Math.Max(maxDifference, nums[j] - nums[i]);
                }
            }
        }
        return maxDifference;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = new int[]{7, 1, 5, 4};
        Console.WriteLine(sol.MaximumDifference(nums));
    }
}

Python's approach embraces the raw comparison by checking every viable pair, a method limited in large datasets by redundancy but helpful in educational elucidation.

Complexity

Time Complexity: O(n^2), leveraging exhaustive matching.
Space Complexity: O(1), accommodating only simple variables.

Try this approach in the editor

Approach 3: Maintaining Prefix Minimum

We use a variable mi to represent the minimum value among the elements currently being traversed, and a variable ans to represent the maximum difference. Initially, mi is set to +infty, and ans is set to -1.

Traverse the array. For the current element x, if x \gt mi, update ans to max(ans, x - mi). Otherwise, update mi to x.

After the traversal, return ans.

Time complexity is O(n), where n is the length of the array. Space complexity is O(1).

TypeScript

function maximumDifference(nums: number[]): number {
    let [ans, mi] = [-1, Infinity];
    for (const x of nums) {
        if (x > mi) {
            ans = Math.max(ans, x - mi);
        } else {
            mi = x;
        }
    }
    return ans;
}

func maximumDifference(nums []int) int {
	mi := 1 << 30
	ans := -1
	for _, x := range nums {
		if mi < x {
			ans = max(ans, x-mi)
		} else {
			mi = x
		}
	}
	return ans
}

Rust

impl Solution {
    pub fn maximum_difference(nums: Vec<i32>) -> i32 {
        let mut mi = i32::MAX;
        let mut ans = -1;

        for &x in &nums {
            if x > mi {
                ans = ans.max(x - mi);
            } else {
                mi = x;
            }
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Single Pass with Minimum Tracking	Time Complexity: O(n) with respect to array size, n. Space Complexity: O(1) due to the fixed additional memory use.
Brute Force Comparison	Time Complexity: O(n^2), leveraging exhaustive matching. Space Complexity: O(1), accommodating only simple variables.
Maintaining Prefix Minimum	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Comparison	O(n^2)	O(1)	Useful for understanding the problem or when input size is very small
Single Pass with Minimum Tracking	O(n)	O(1)	Best general solution; optimal for interviews and large arrays

Frequently asked questions

Is Maximum Difference Between Increasing Elements easy or hard?

Maximum Difference Between Increasing Elements is classified as an Easy problem on LeetCode with an acceptance rate around 66%. The challenge mainly tests recognition of the prefix minimum tracking pattern and efficient single-pass array processing.

Maximum Difference Between Increasing Elements Python/Java solution

Most implementations follow the same logic: maintain a variable for the minimum prefix value and update the maximum difference while iterating through the array. This pattern is straightforward to implement in Python, Java, C++, C, or JavaScript with a single loop.

How to solve Maximum Difference Between Increasing Elements in O(n)?

Traverse the array from left to right while maintaining the smallest value encountered so far. For each element, compute the difference between the current value and that minimum. Update the maximum difference if the result is positive, then update the minimum value if the current number is smaller.

What is the best approach for Maximum Difference Between Increasing Elements?

The best approach is a single-pass scan while tracking the minimum value seen so far. For each element nums[i], compute nums[i] - minVal where minVal is the smallest earlier element. Update the maximum difference if the value is positive. This runs in O(n) time with O(1) extra space.

Is Maximum Difference Between Increasing Elements asked at Google/Amazon/Meta?

Problems based on prefix minimum tracking and array scanning appear frequently in interviews at companies like Amazon and Google. While this exact question may vary, the pattern of maintaining a running minimum and computing differences is commonly tested.

What data structure is used in Maximum Difference Between Increasing Elements?

The solution only requires a simple array traversal with a few variables to track the minimum value and the current maximum difference. No additional data structures such as hash maps or stacks are required.

What is the time complexity of Maximum Difference Between Increasing Elements?

The optimal algorithm runs in O(n) time because the array is scanned once while maintaining the minimum prefix value. A naive brute force solution checks all pairs and takes O(n^2) time. Both approaches use O(1) additional space.

Maximum Difference Between Increasing Elements solution and explanation

The problem

Approach overview

Approach 1: Single Pass with Minimum Tracking

Approach 2: Brute Force Comparison

Approach 3: Maintaining Prefix Minimum

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Difference Between Increasing Elements solution and explanation

The problem

Approach overview

Approach 1: Single Pass with Minimum Tracking

Approach 2: Brute Force Comparison

Approach 3: Maintaining Prefix Minimum

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems