Problem

Given an array of numbers, write an algorithm to find the maximum difference between any two elements in the array.

Examples

Example 1:

Input: nums = [3,6,9,1]
Output: 8
Explanation: The sorted form of the array is [1,3,6,9], and max diff is between first and last element as 8

Similar Problems

Maximum Gap Problem

Solution

Method 1 - Naive approach

Compare each element with every other element in the array, calculate the differences, and record the maximum difference

Code

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }

        int maximumDiff = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int diff = Math.abs(nums[j] - nums[i]);
                if (maximumDiff < diff) {
                    maximumDiff = diff;
                }
            }
        }
        return maximumDiff;
    }
}
Python
def maximum_gap(nums):
    if len(nums) < 2:
        return 0

    maximum_diff = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            diff = abs(nums[j] - nums[i])
            if maximum_diff < diff:
                maximum_diff = diff

    return maximum_diff

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Track max and min element

To find the maximum and minimum element in the array and their difference in a single iteration, follow these steps:

  1. Loop through all the elements in the array.
  2. For each element, determine if it is the smallest or largest element encountered so far. If it is, update the respective minimum or maximum value.
  3. After completing the iteration, return the difference between the maximum and minimum elements.

Code

Java
public class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }

        // Initialize minimum and maximum elements
        int minElement = Integer.MAX_VALUE;
        int maxElement = Integer.MIN_VALUE;

        // Find the minimum and maximum elements in one iteration
        for (int num : nums) {
            if (num < minElement) {
                minElement = num;
            }
            if (num > maxElement) {
                maxElement = num;
            }
        }

        // The maximum gap in the array
        return maxElement - minElement;
    }
}
Python
def maximum_gap(nums):
    if len(nums) < 2:
        return 0

    # Initialize minimum and maximum elements
    min_element = float("inf")
    max_element = float("-inf")

    # Find the minimum and maximum elements in one iteration
    for num in nums:
        if num < min_element:
            min_element = num
        if num > max_element:
            max_element = num

    # The maximum gap in the array
    return max_element - min_element

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)