Given an array A[] consisting of N elements, the task is to find the minimum distance between the minimum and the maximum element of the array.
Examples:
Input: arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 8, 2}
Output: 3
Explanation:
The minimum element(= 1) is present at indices {2, 4}
The maximum element(= 8) is present at indices {7, 10}.
The minimum distance between an occurrence of 1 and 8 is 7 – 4 = 3
Input: arr[] = {1, 3, 69}
Output: 2
Explanation:
The minimum element(= 1) is present at index 0.
The maximum element(= 69) is present at index 2.
Therefore, the minimum distance between them is 2.
Naive Approach:
The simplest approach to solve this problem is as follows:
- Find the minimum and maximum elements of the array.
- Traverse the array and for every occurrence of the maximum element, calculate its distance from all occurrences of the minimum element in the array and update the minimum distance.
- After complete traversal of the array, print all the minimum distance obtained.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach:
Follow the steps below to optimize the above approach:
- Traverse the array to find the minimum and maximum elements.
- Initialize two variables min_index and max_index to store the indices of the minimum and maximum elements of the array respectively. Initialize them with -1.
- Traverse the array. If at any instant, both min_index and max_index is not equal to -1, i.e. both of them have stored a valid index, calculate there a difference.
- Compare this difference with the minimum distance(say, min_dist) and update min_dist accordingly.
- Finally, print the final value of min_dist obtained after the complete traversal of the array.
Below is the implementation of the above approach:
C++
// C++ Program to implement the // above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum // distance between the minimum // and the maximum element int minDistance( int a[], int n) { // Stores the minimum and maximum // array element int maximum = -1, minimum = INT_MAX; // Stores the most recently traversed // indices of the minimum and the // maximum element int min_index = -1, max_index = -1; // Stores the minimum distance // between the minimum and the // maximum int min_dist = n + 1; // Find the maximum and // the minimum element // from the given array for ( int i = 0; i < n; i++) { if (a[i] > maximum) maximum = a[i]; if (a[i] < minimum) minimum = a[i]; } // Find the minimum distance for ( int i = 0; i < n; i++) { // Check if current element // is equal to minimum if (a[i] == minimum) min_index = i; // Check if current element // is equal to maximum if (a[i] == maximum) max_index = i; // If both the minimum and the // maximum element has // occurred at least once if (min_index != -1 && max_index != -1) // Update the minimum distance min_dist = min(min_dist, abs (min_index - max_index)); } // Return the answer return min_dist; } // Driver Code int main() { int a[] = { 3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 8, 2 }; int n = sizeof a / sizeof a[0]; cout << minDistance(a, n); } |
Java
// Java Program to implement // the above approach import java.util.*; class GFG { // Function to find the minimum // distance between the minimum // and the maximum element public static int minDistance( int a[], int n) { // Stores the minimum and maximum // array element int max = - 1 , min = Integer.MAX_VALUE; // Stores the most recently traversed // indices of the minimum and the // maximum element int min_index = - 1 , max_index = - 1 ; // Stores the minimum distance // between the minimum and the // maximum int min_dist = n + 1 ; // Find the maximum and // the minimum element // from the given array for ( int i = 0 ; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } // Find the minimum distance for ( int i = 0 ; i < n; i++) { // Check if current element // is equal to minimum if (a[i] == min) min_index = i; // Check if current element // is equal to maximum if (a[i] == max) max_index = i; // If both the minimum and the // maximum element has // occurred at least once if (min_index != - 1 && max_index != - 1 ) min_dist = Math.min(min_dist, Math.abs(min_index - max_index)); } return min_dist; } // Driver Code public static void main(String[] args) { int n = 12 ; int a[] = { 3 , 2 , 1 , 2 , 1 , 4 , 5 , 8 , 6 , 7 , 8 , 2 }; System.out.println(minDistance(a, n)); } } |
Python3
# Python3 Program to implement the # above approach import sys # Function to find the minimum # distance between the minimum # and the maximum element def minDistance(a, n): # Stores the minimum and maximum # array element maximum = - 1 minimum = sys.maxsize # Stores the most recently traversed # indices of the minimum and the # maximum element min_index = - 1 max_index = - 1 # Stores the minimum distance # between the minimum and the # maximum min_dist = n + 1 # Find the maximum and # the minimum element # from the given array for i in range (n): if (a[i] > maximum): maximum = a[i] if (a[i] < minimum): minimum = a[i] # Find the minimum distance for i in range (n): # Check if current element # is equal to minimum if (a[i] = = minimum): min_index = i # Check if current element # is equal to maximum if (a[i] = = maximum): max_index = i # If both the minimum and the # maximum element has # occurred at least once if (min_index ! = - 1 and max_index ! = - 1 ): # Update the minimum distance min_dist = ( min (min_dist, abs (min_index - max_index))) # Return the answer return min_dist # Driver Code if __name__ = = "__main__" : a = [ 3 , 2 , 1 , 2 , 1 , 4 , 5 , 8 , 6 , 7 , 8 , 2 ] n = len (a) print (minDistance(a, n)) # This code is contributed by Chitranayal |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find the minimum // distance between the minimum // and the maximum element static int minDistance( int []a, int n) { // Stores the minimum and maximum // array element int max = -1, min = Int32.MaxValue; // Stores the most recently traversed // indices of the minimum and the // maximum element int min_index = -1, max_index = -1; // Stores the minimum distance // between the minimum and the // maximum int min_dist = n + 1; // Find the maximum and // the minimum element // from the given array for ( int i = 0; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } // Find the minimum distance for ( int i = 0; i < n; i++) { // Check if current element // is equal to minimum if (a[i] == min) min_index = i; // Check if current element // is equal to maximum if (a[i] == max) max_index = i; // If both the minimum and the // maximum element has // occurred at least once if (min_index != -1 && max_index != -1) min_dist = Math.Min(min_dist, Math.Abs( min_index - max_index)); } return min_dist; } // Driver Code public static void Main() { int n = 12; int []a = { 3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 8, 2 }; Console.WriteLine(minDistance(a, n)); } } // This code is contributed by piyush3010 |
Javascript
<script> // Javascript program to implement // the above approach // Function to find the minimum // distance between the minimum // and the maximum element function minDistance(a, n) { // Stores the minimum and maximum // array element let max = -1, min = Number.MAX_VALUE; // Stores the most recently traversed // indices of the minimum and the // maximum element let min_index = -1, max_index = -1; // Stores the minimum distance // between the minimum and the // maximum let min_dist = n + 1; // Find the maximum and // the minimum element // from the given array for (let i = 0; i < n; i++) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } // Find the minimum distance for (let i = 0; i < n; i++) { // Check if current element // is equal to minimum if (a[i] == min) min_index = i; // Check if current element // is equal to maximum if (a[i] == max) max_index = i; // If both the minimum and the // maximum element has // occurred at least once if (min_index != -1 && max_index != -1) min_dist = Math.min(min_dist, Math.abs(min_index - max_index)); } return min_dist; } // Driver Code let n = 12; let a = [ 3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 8, 2 ]; document.write(minDistance(a, n)); </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!