We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Difference Between Increasing Elements

Difficulty: Easy

Problem 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.

Key Insights

  • We need to find pairs (i, j) where i < j and nums[i] < nums[j].
  • The maximum difference can be calculated as nums[j] - nums[i].
  • We can maintain a minimum value seen so far while iterating through the array to efficiently calculate the maximum difference.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The approach involves iterating through the array while maintaining the minimum value encountered so far. For each element, we check if the current element can form a valid pair with the minimum value seen so far. If it can, we calculate the difference and update the maximum difference accordingly. This ensures we only traverse the array once, leading to a linear time complexity.

Code Solutions

def maximumDifference(nums):
    min_value = float('inf')
    max_diff = -1
    
    for num in nums:
        if num > min_value:
            max_diff = max(max_diff, num - min_value)
        min_value = min(min_value, num)
    
    return max_diff
← Back to All Questions