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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Difference Between Increasing Elements

Number: 2144

Difficulty: Easy

Paid? No

Companies: Cisco, Salesforce

Problem Description

Given an array of integers, find the maximum difference between two elements such that the smaller element appears before the larger element in the array. If no such pair exists (i.e., the array is non-increasing), return -1.

Key Insights

  • Keep track of the minimum element encountered so far while iterating through the array.
  • For each element, calculate the difference between the current element and the minimum element so far.
  • Update the maximum difference when a greater valid difference is found.
  • If no valid increasing pair exists, the result remains -1.

Space and Time Complexity

Time Complexity: O(n) (single pass through the array) Space Complexity: O(1) (only constant extra space used)

Solution

Use a single pass through the array to keep a record of the minimum element seen so far. At each step, compute the potential difference between the current element and this minimum. If the current element is greater, update the maximum difference if needed; otherwise, update the minimum element. This approach efficiently finds the maximum difference with O(n) time complexity and O(1) space complexity without requiring any extra data structures.

Code Solutions

# Function to calculate the maximum difference between two increasing elements
def maximum_difference(nums):
    # Initialize the minimum element with the first element
    min_so_far = nums[0]
    # Initialize maximum difference as -1 (indicating no valid pair found yet)
    max_diff = -1
    
    # Iterate through the array starting from the second element
    for num in nums[1:]:
        # If current number is greater than the minimum seen so far, calculate difference
        if num > min_so_far:
            max_diff = max(max_diff, num - min_so_far)
        # Update the minimum element if current number is smaller
        min_so_far = min(min_so_far, num)
    # Return the maximum difference found, or -1 if none exists
    return max_diff

# Example usage:
nums = [7, 1, 5, 4]
print(maximum_difference(nums))
← Back to All Questions