Question 35 : Find maximum difference between two elements such that larger element appears after the smaller number.

Given array of integers, find Maximum difference between two elements such that larger element appears after the smaller number

For example :

int arr[]={14, 12, 70, 15, 95, 65, 22, 30};
Max Difference =95-12 = 83

Java — One Pass

public class MaxDifference {

    public static int maxDifference(int[] arr) {
        if (arr == null || arr.length < 2) return 0;

        int minSoFar = arr[0];
        int maxDiff = 0;

        for (int i = 1; i < arr.length; i++) {
            int diff = arr[i] - minSoFar;
            if (diff > maxDiff) {
                maxDiff = diff;
            }
            if (arr[i] < minSoFar) {
                minSoFar = arr[i];
            }
        }
        return maxDiff;
    }
}

Python

def max_difference(arr):
    if not arr or len(arr) < 2:
        return 0

    min_so_far = arr[0]
    max_diff = 0

    for x in arr[1:]:
        diff = x - min_so_far
        if diff > max_diff:
            max_diff = diff
        if x < min_so_far:
            min_so_far = x

    return max_diff

Alternative — Brute Force

public static int maxDiffBrute(int[] arr) {
    int maxDiff = 0;

    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            maxDiff = Math.max(maxDiff, arr[j] - arr[i]);
        }
    }
    return maxDiff;
}

Python
def max_diff_brute(arr):
    max_diff = 0
    n = len(arr)

    for i in range(n):
        for j in range(i+1, n):
            max_diff = max(max_diff, arr[j] - arr[i])
    return max_diff



  
    
    
    
    
  

  

    
Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    

      One pass (track min so far)
    
    

      O(n)
    
    

      O(1)
    
    

      ⭐ Best & optimal
    
  

  

    

      Brute force nested loops
    
    

      O(n²)
    
    
O(1)
    

      ❌ Slow for large n