# Maximum Difference between two elements in array – Largest Gap Problem

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

Example:

```Int [] a = {2, 8, 1, 6, 10, 4}
Output: Maximum difference= 9 (elements are 1 and 10)
Int [] b = {10, 30, 5, 16, 19};
Output:: Maximum difference= 25 (elements are 30 and 5)
```

ApproachUse Nested Loops:

Compare each element with all other elements in the array and calculate the difference and keep track of the maximum difference.

Time Complexity: O(N2)

Java Code:

 public class LargestGapNaive { static void findGap(int [] a){ int maximum_diff = 0; for (int i = 0; i

view raw
LargestGapNaive.java
hosted with ❤ by GitHub

Output:

```Largest Gap between any two elements is: 9
Largest Gap between any two elements is: 25
```

Better Approach:  Track maximum and minimum element

Find the maximum and minimum element in the array and find the difference but this will take two iterations, we can solve this problem in just one iteration. We need to keep track of the maximum and minimum element and difference during iteration.

1. Iterate through all the elements in array.
2. For each element, check if the element is minimum element visited so far or maximum element visited so far, else ignore the element.
1. If current element is either minimum or maximum element in the step above then update the maximum element or minimum element accordingly.
3. Return the difference between maximum element and minimum element.

Time Complexity: O(N)
Java Code:

 public class LargestGapBetter { static void findGap(int [] a){ if(a==null || a.length==0){ System.out.println("Array is null, no solution found"); } int max_so_far=a; int min_so_far=a; int max_diff = 0; for (int i = 1; i max_so_far) max_so_far = a[i]; if(a[i]

Output:

```Largest Gap between any two elements is: 9
```

Largest Gap between any two elements is: 25