Minimum distance between peak elements in a given array
Given an array arr[], the task is to find the minimum distance between the two peak elements in the given array.
Examples:
Input: arr[] = {2, 3, 1, 2, 4, 1, 2}
Output: 2
Explanation: The peak elements in the given array are {2, 3, 1, 2, 4, 1, 2}. Hence the distance between 4 and 2 is (6 – 4) = 2 which is the minimum possible.Input: arr[] = {1, 2}
Output: -1
Explanation: There is only one peak element in the given array.
Approach: The given problem can be solved by observing the fact that for the distance to be minimum, only the distances of the adjacent peak elements is needed to be considered. Therefore, iterate the given array and for each peak element, calculate its distance from the last found peak element whose index can be maintained in a variable idx. The minimum of all these distances is the required answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum distance // between two peak elements void MinimumDistance( int arr[], int n) { // Stores the minimum distance between // two peak elements int mn = INT_MAX; // Store the index of peak element int idx = -1; // Checking for the 1st elements of array if (arr[0] >= arr[1]) { idx = 0; } for ( int i = 1; i < n - 1; i++) { if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) { if (idx == -1) { idx = i; } else { mn = min(mn, i - idx); } idx = i; } } // Checking for last element of the array if (arr[n - 1] >= arr[n - 2] && idx != -1) { mn = min(mn, n - 1 - idx); } // If number of peak elements is less than 2 if (mn == INT_MAX) cout << -1; // Print Answer else cout << mn; } // Driver Code int main() { int arr[] = { 2, 3, 1, 2, 4, 1, 2 }; int n = sizeof (arr) / sizeof (arr[0]); MinimumDistance(arr, n); return 0; } // This code is contributed by Samim Hossain Mondal. |
Java
// Java implementation of the above approach import java.io.*; import java.util.*; class GFG { // Function to find the minimum distance // between two peak elements public static void MinimumDistance( int [] arr) { // Stores the minimum distance between // two peak elements int min = Integer.MAX_VALUE; // Store the index of peak element int idx = - 1 ; int n = arr.length; // Checking for the 1st elements of array if (arr[ 0 ] >= arr[ 1 ]) { idx = 0 ; } for ( int i = 1 ; i < n - 1 ; i++) { if (arr[i] >= arr[i - 1 ] && arr[i] >= arr[i + 1 ]) { if (idx == - 1 ) { idx = i; } else { min = Math.min(min, i - idx); } idx = i; } } // Checking for last element of the array if (arr[n - 1 ] >= arr[n - 2 ] && idx != - 1 ) { min = Math.min(min, n - 1 - idx); } // If number of peak elements is less than 2 if (min == Integer.MAX_VALUE) System.out.println(- 1 ); // Print Answer else System.out.println(min); } // Driver Code public static void main(String[] args) { int arr[] = { 2 , 3 , 1 , 2 , 4 , 1 , 2 }; MinimumDistance(arr); } } |
Python3
# Python implementation of the above approach # Function to find the minimum distance # between two peak elements def MinimumDistance(arr): # Stores the minimum distance between # two peak elements less = 10 * * 9 ; # Store the index of peak element idx = - 1 ; n = len (arr); # Checking for the 1st elements of array if (arr[ 0 ] > = arr[ 1 ]): idx = 0 ; for i in range ( 1 , n - 1 ): if (arr[i] > = arr[i - 1 ] and arr[i] > = arr[i + 1 ]): if (idx = = - 1 ): idx = i; else : less = min (less, i - idx); idx = i; # Checking for last element of the array if (arr[n - 1 ] > = arr[n - 2 ] and idx ! = - 1 ): less = min (less, n - 1 - idx); # If number of peak elements is less than 2 if (less = = 10 * * 9 ): print ( - 1 ); # Print Answer else : print (less); # Driver Code arr = [ 2 , 3 , 1 , 2 , 4 , 1 , 2 ]; MinimumDistance(arr); # This code is contributed by gfgking |
C#
// C# implementation of the above approach using System; class GFG { // Function to find the minimum distance // between two peak elements public static void MinimumDistance( int [] arr) { // Stores the minimum distance between // two peak elements int min = int .MaxValue; // Store the index of peak element int idx = -1; int n = arr.Length; // Checking for the 1st elements of array if (arr[0] >= arr[1]) { idx = 0; } for ( int i = 1; i < n - 1; i++) { if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) { if (idx == -1) { idx = i; } else { min = Math.Min(min, i - idx); } idx = i; } } // Checking for last element of the array if (arr[n - 1] >= arr[n - 2] && idx != -1) { min = Math.Min(min, n - 1 - idx); } // If number of peak elements is less than 2 if (min == int .MaxValue) Console.Write(-1); // Print Answer else Console.Write(min); } // Driver Code public static void Main() { int [] arr = { 2, 3, 1, 2, 4, 1, 2 }; MinimumDistance(arr); } } // This code is contributed by gfgking |
Javascript
<script> // Javascript implementation of the above approach // Function to find the minimum distance // between two peak elements function MinimumDistance(arr) { // Stores the minimum distance between // two peak elements let min = Number.MAX_SAFE_INTEGER; // Store the index of peak element let idx = -1; let n = arr.length; // Checking for the 1st elements of array if (arr[0] >= arr[1]) { idx = 0; } for (let i = 1; i < n - 1; i++) { if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) { if (idx == -1) { idx = i; } else { min = Math.min(min, i - idx); } idx = i; } } // Checking for last element of the array if (arr[n - 1] >= arr[n - 2] && idx != -1) { min = Math.min(min, n - 1 - idx); } // If number of peak elements is less than 2 if (min == Number.MAX_SAFE_INTEGER) document.write(-1); // Print Answer else document.write(min); } // Driver Code let arr = [2, 3, 1, 2, 4, 1, 2]; MinimumDistance(arr); // This code is contributed by gfgking </script> |
2
Time Complexity: O(N)
Auxiliary Space: O (1)