Maximum Difference in an Array

January 14, 2024

Problem #

Given an array of integers nums, find the maximum difference between any two elements nums[j] and nums[i] such that j > i.

Example:

1. Input: nums = [7, 1, 5, 4] Output: 4 Explanation: The maximum difference is between 5 and 1.

Solution Approach #

The solution involves iterating through the array while keeping track of the minimum element found so far and the maximum difference.

Algorithm Steps #

1. Initialize two variables: min_element to the first element and max_diff to 0.
2. Iterate through the array starting from the second element.
3. Update min_element if a new minimum is found.
4. Calculate the difference between the current element and min_element.
5. Update max_diff if the current difference is greater than max_diff.
6. Return max_diff.

Code (Python) #

def maxDifference(nums):
    if len(nums) < 2:
        return 0

    min_element = nums[0]
    max_diff = 0

    for num in nums[1:]:
        min_element = min(min_element, num)
        max_diff = max(max_diff, num - min_element)

    return max_diff

# Test the function
print(maxDifference([7, 1, 5, 4]))  # Output: 4

Time Complexity #

O(n), where n is the number of elements in the array. The array is traversed once.

Space Complexity #

O(1), as no additional space is used apart from a few variables.