algoadvance

You are given a 0-indexed integer array nums of size n. The maximum difference between two elements of nums such that the larger element comes after the smaller element in the array is defined as the maximum value of nums[j] - nums[i] where 0 <= i < j < n and nums[i] < nums[j]. If no such i and j exists, return -1.

Example:

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.

Clarifying Questions

  1. Q: Can the array contain negative integers? A: Yes, the array can contain negative integers.

  2. Q: What is the minimum size of the array? A: The minimum size of the array is 2 as we need at least two elements to calculate the difference.

Strategy

  1. Initialize a variable min_element to store the minimum element encountered so far.
  2. Initialize a variable max_diff to store the maximum difference encountered so far.
  3. Iterate over the array starting from the first element:
    • At each step, update the max_diff with the difference between the current element and min_element if this difference is greater than the already recorded max_diff.
    • Update min_element to be the minimum of itself and the current element.
  4. Return max_diff if it is positive, otherwise return -1.

Code

def maximum_difference(nums):
    if len(nums) < 2:
        return -1
    
    min_element = nums[0]
    max_diff = -1
    
    for i in range(1, len(nums)):
        if nums[i] > min_element:
            max_diff = max(max_diff, nums[i] - min_element)
        min_element = min(min_element, nums[i])
    
    return max_diff

# Example usage:
nums = [7, 1, 5, 4]
print(maximum_difference(nums))  # Output: 4

Time Complexity

This solution efficiently computes the maximum difference by maintaining the minimum element encountered so far and updating the maximum difference in a single pass through the array.

Try our interview co-pilot at AlgoAdvance.com