Be the first user to complete this post

  • 0
 Add to List
Beginner

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)

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(N2)

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 the array.
  2. For each element, check if the element is minimum element visited so far or the maximum element visited so far, else ignore the element.
    1. If the 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.

Code:


Output:

Largest Gap between any two elements is: 9

Largest Gap between any two elements is: 25

Also Read: