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:


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:


Output:

Largest Gap between any two elements is: 9

Largest Gap between any two elements is: 25

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: