Maximum Difference Between Increasing Elements

Maximum Difference Between Increasing Elements - Problem

Array Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [7,1,5,4,6]

› Output: 5

💡 Note: The maximum difference is 6 - 1 = 5, where i = 1 and j = 4 (nums[1] = 1, nums[4] = 6)

Example 2 — No Valid Pair

$ Input: nums = [9,4,3,2]

› Output: -1

💡 Note: No valid pair exists since the array is in decreasing order, so no i < j with nums[i] < nums[j]

Example 3 — Small Difference

$ Input: nums = [1,5,2,10]

› Output: 9

💡 Note: Maximum difference is 10 - 1 = 9, where i = 0 and j = 3

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers [7,1,5,4,6]

Process

Find pairs (i,j) where i < j and nums[i] < nums[j], calculate differences

Output

Return maximum difference: 5 (from 6 - 1)

Key Takeaway

🎯 Key Insight: Track the minimum element seen so far to maximize the difference with future elements

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is to track the minimum element seen so far while iterating through the array. For each element, calculate the difference with the minimum and update the maximum difference. Best approach uses single pass optimization with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Check all pairs (i,j) where i < j and nums[i] < nums[j]
Single Pass Optimization	O(n)	O(1)	Track minimum element seen so far while calculating maximum difference

Brute Force — Algorithm Steps

For each index i from 0 to n-2
For each index j from i+1 to n-1
If nums[i] < nums[j], update maximum difference

Visualization

Tap to expand

Step-by-Step Walkthrough

Check All Pairs

Compare each element with all elements to its right

Filter Valid Pairs

Only consider pairs where nums[i] < nums[j]

Find Maximum

Track the maximum difference found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops iterate through all pairs (i,j) where i < j

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables for tracking maximum difference

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler