**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)

**Approach**: **Use 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(N ^{2})**

**Java Code**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class LargestGapNaive { | |

static void findGap(int [] a){ | |

int maximum_diff = 0; | |

for (int i = 0; i <a.length ; i++) { | |

for (int j = 1; j <a.length ; j++) { | |

int x = a[i]; | |

int y = a[j]; | |

int diff = Math.abs(x–y); | |

if(maximum_diff<diff) | |

maximum_diff = diff; | |

} | |

} | |

System.out.println("Largest Gap between any two elements is: " + maximum_diff); | |

} | |

public static void main(String[] args) { | |

int [] a = {2, 8, 1, 6, 10, 4}; | |

findGap(a); | |

int [] b = {10, 30, 5, 16, 19}; | |

findGap(b); | |

} | |

} |

**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.

- Iterate through all the elements in array.
- For each element, check if the element is minimum element visited so far or maximum element visited so far, else ignore the element.
- If current element is either minimum or maximum element in the step above then update the maximum element or minimum element accordingly.

- Return the difference between maximum element and minimum element.

**Time Complexity: O(N)**

**Java Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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[0]; | |

int min_so_far=a[0]; | |

int max_diff = 0; | |

for (int i = 1; i <a.length ; i++) { | |

if(a[i]>max_so_far) | |

max_so_far = a[i]; | |

if(a[i]<min_so_far) | |

min_so_far = a[i]; | |

} | |

max_diff = max_so_far–min_so_far; | |

System.out.println("Largest Gap between any two elements is: " + max_diff); | |

} | |

public static void main(String[] args) { | |

int [] a = {2, 8, 1, 6, 10, 4}; | |

findGap(a); | |

int [] b = {10, 30, 5, 16, 19}; | |

findGap(b); | |

} | |

} |

**Output**:

Largest Gap between any two elements is: 9

Largest Gap between any two elements is: 25