|
Be the first user to complete this post
|
Add to List |
300. Find the Largest Gap Between Elements in an Array
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, calculate the difference and keep track of the maximum difference.
Time Complexity: O(N2)
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 elements and differences during iteration.
- Iterate through all the elements in the array.
- For each element, check if the element is the minimum element visited so far or the maximum element visited so far, else ignore the element.
- If the current element is either the minimum or maximum in the above step, then update the maximum or minimum element accordingly.
- Return the difference between the maximum element and the minimum element.
Output:
Largest Gap between any two elements is: 9 Largest Gap between any two elements is: 25