Given an array arr[], return an array of size 2 consisting of 2 values, the first one the minDistance and the second one maxDistance. Here minDistance is the minimum distance between any two distinct critical points and maxDistance is the maximum distance between any two distinct critical points and by chance, if there are less than two critical points then it should return [-1, -1].
Examples:
Input: arr[] = {3, 1}
Output: {-1, -1}
Explanation: There are no critical points in Array
Input: arr[] = {5, 3, 1, 2, 5, 1, 2}
Output: {1, 3}
Explanation: There are three critical points at indexes 2, 4 and 5 in the Array (0 Based Indexing). So the minimum distance is between 4 and 5 which is 1 and the maximum distance is 2.
Approach: The task can be solved by storing the indices of critical points. Follow the below steps to solve the problem:
- Iterate over the array and if we get a critical point then we will insert it in the position array
- Check if its size is less than or equal to 1, if this is true then we simply need to return the array which contains -1 and -1
- Else we will get the maximum distance by subtracting the last value and the first value of the position array and the minimum distance we can get by using the equation mval=min(mval, pos[i]-pos[i-1]), for all i>1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check whether that point is a critical// point or not based on the present, previous and next// value.bool isCriticalPoint(int prev, int pres, int next){ // Critical point condition if ((prev < pres && pres > next) || (prev > pres && pres < next)) return true; return false;}// Function to find the required distancesvector<int> maxmincriticaldis(vector<int>& arr, int n){ // Store the position vector<int> pos; // Start from index 1 as we are gonna pass // arr[i-1] and at i=0 i-1 becomes -ve // to avoid that error we start from index 1 for (int i = 1; i < n - 1; i++) { // If this point is critical point then it's // index is inserted in the pos array if (isCriticalPoint(arr[i - 1], arr[i], arr[i + 1])) pos.push_back(i); } vector<int> ans; // If the pos array size is either 0 or 1 // then we will simply add -1 and -1 to the answer array // as it is not possible to find the max and min // distance with 1 or 0 elements in the array. if (pos.size() <= 1) { ans.push_back(-1); ans.push_back(-1); } else { // We find the minimum difference between the // positions of the critical points based on the // values of indexes. int mval = INT_MAX; for (int i = 1; i < pos.size(); i++) mval = min(mval, pos[i] - pos[i - 1]); ans.push_back(mval); // Maximum difference will obviously be between // the first and the last element of the pos array. ans.push_back(pos[pos.size() - 1] - pos[0]); } return ans;}// Driver Codeint main(){ vector<int> arr = { 5, 3, 1, 2, 5, 1, 2 }; int n = arr.size(); vector<int> ans = maxmincriticaldis(arr, n); for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";}// This Code is contributed by Omkar Subhash Ghongade. |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check whether that point is a critical// point or not based on the present, previous and next// value.static boolean isCriticalPoint(int prev, int pres, int next){ // Critical point condition if ((prev < pres && pres > next) || (prev > pres && pres < next)) return true; return false;}// Function to find the required distancesstatic Vector<Integer> maxmincriticaldis(int[] arr, int n){ // Store the position Vector<Integer> pos = new Vector<Integer>(); // Start from index 1 as we are gonna pass // arr[i-1] and at i=0 i-1 becomes -ve // to astatic void that error we start from index 1 for (int i = 1; i < n - 1; i++) { // If this point is critical point then it's // index is inserted in the pos array if (isCriticalPoint(arr[i - 1], arr[i], arr[i + 1])) pos.add(i); } Vector<Integer> ans = new Vector<Integer>(); // If the pos array size is either 0 or 1 // then we will simply add -1 and -1 to the answer array // as it is not possible to find the max and min // distance with 1 or 0 elements in the array. if (pos.size() <= 1) { ans.add(-1); ans.add(-1); } else { // We find the minimum difference between the // positions of the critical points based on the // values of indexes. int mval = Integer.MAX_VALUE; for (int i = 1; i < pos.size(); i++) mval = Math.min(mval, pos.get(i) - pos.get(i-1)); ans.add(mval); // Maximum difference will obviously be between // the first and the last element of the pos array. ans.add(pos.get(pos.size() - 1) - pos.get(0)); } return ans;}// Driver Codepublic static void main(String[] args){ int[] arr = { 5, 3, 1, 2, 5, 1, 2 }; int n = arr.length; Vector<Integer> ans = maxmincriticaldis(arr, n); for (int i = 0; i < ans.size(); i++) System.out.print(ans.get(i)+ " ");}}// This code is contributed by 29AjayKumar |
Python3
# Python 3 program for the above approachimport sys# Function to check whether that point is a critical# point or not based on the present, previous and next# value.def isCriticalPoint(prev, pres, next): # Critical point condition if ((prev < pres and pres > next) or (prev > pres and pres < next)): return True return False# Function to find the required distancesdef maxmincriticaldis(arr, n): # Store the position pos = [] # Start from index 1 as we are gonna pass # arr[i-1] and at i=0 i-1 becomes -ve # to avoid that error we start from index 1 for i in range(1, n - 1): # If this point is critical point then it's # index is inserted in the pos array if (isCriticalPoint(arr[i - 1], arr[i], arr[i + 1])): pos.append(i) ans = [] # If the pos array size is either 0 or 1 # then we will simply add -1 and -1 to the answer array # as it is not possible to find the max and min # distance with 1 or 0 elements in the array. if (len(pos) <= 1): ans.append(-1) ans.append(-1) else: # We find the minimum difference between the # positions of the critical points based on the # values of indexes. mval = sys.maxsize for i in range(1, len(pos)): mval = min(mval, pos[i] - pos[i - 1]) ans.append(mval) # Maximum difference will obviously be between # the first and the last element of the pos array. ans.append(pos[len(pos) - 1] - pos[0]) return ans# Driver Codeif __name__ == "__main__": arr = [5, 3, 1, 2, 5, 1, 2] n = len(arr) ans = maxmincriticaldis(arr, n) for i in range(len(ans)): print(ans[i], end=" ") # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections;class GFG{ // Function to check whether that point is a critical// point or not based on the present, previous and next// value.static bool isCriticalPoint(int prev, int pres, int next){ // Critical point condition if ((prev < pres && pres > next) || (prev > pres && pres < next)) return true; return false;}// Function to find the required distancesstatic ArrayList maxmincriticaldis(ArrayList arr, int n){ // Store the position ArrayList pos = new ArrayList(); // Start from index 1 as we are gonna pass // arr[i-1] and at i=0 i-1 becomes -ve // to avoid that error we start from index 1 for (int i = 1; i < n - 1; i++) { // If this point is critical point then it's // index is inserted in the pos array if (isCriticalPoint((int)arr[i - 1], (int)arr[i], (int)arr[i + 1])) pos.Add(i); } ArrayList ans = new ArrayList(); // If the pos array size is either 0 or 1 // then we will simply add -1 and -1 to the answer array // as it is not possible to find the max and min // distance with 1 or 0 elements in the array. if (pos.Count <= 1) { ans.Add(-1); ans.Add(-1); } else { // We find the minimum difference between the // positions of the critical points based on the // values of indexes. int mval = Int32.MaxValue; for (int i = 1; i < pos.Count; i++) mval = Math.Min(mval, (int)pos[i] - (int)pos[i - 1]); ans.Add(mval); // Maximum difference will obviously be between // the first and the last element of the pos array. ans.Add((int)pos[pos.Count - 1] - (int)pos[0]); } return ans;}// Driver Codepublic static void Main(){ ArrayList arr = new ArrayList(); arr.Add(5); arr.Add(3); arr.Add(1); arr.Add(2); arr.Add(5); arr.Add(1); arr.Add(2); int n = arr.Count; ArrayList ans = maxmincriticaldis(arr, n); for (int i = 0; i < ans.Count; i++) Console.Write(ans[i] + " ");}}// This Code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to check whether that point is a critical // point or not based on the present, previous and next // value. function isCriticalPoint(prev, pres, next) { // Critical point condition if ((prev < pres && pres > next) || (prev > pres && pres < next)) return true; return false; } // Function to find the required distances function maxmincriticaldis(arr, n) { // Store the position let pos = []; // Start from index 1 as we are gonna pass // arr[i-1] and at i=0 i-1 becomes -ve // to avoid that error we start from index 1 for (let i = 1; i < n - 1; i++) { // If this point is critical point then it's // index is inserted in the pos array if (isCriticalPoint(arr[i - 1], arr[i], arr[i + 1])) pos.push(i); } let ans = []; // If the pos array size is either 0 or 1 // then we will simply add -1 and -1 to the answer array // as it is not possible to find the max and min // distance with 1 or 0 elements in the array. if (pos.length <= 1) { ans.push(-1); ans.push(-1); } else { // We find the minimum difference between the // positions of the critical points based on the // values of indexes. let mval = Number.MAX_VALUE; for (let i = 1; i < pos.length; i++) mval = Math.min(mval, pos[i] - pos[i - 1]); ans.push(mval); // Maximum difference will obviously be between // the first and the last element of the pos array. ans.push(pos[pos.length - 1] - pos[0]); } return ans; } // Driver Code let arr = [5, 3, 1, 2, 5, 1, 2]; let n = arr.length; let ans = maxmincriticaldis(arr, n); for (let i = 0; i < ans.length; i++) document.write(ans[i] + " ")// This code is contributed by Potta Lokesh </script> |
Output
1 3
Time Complexity: O(n), n is the number of elements in the Array.
Auxiliary Space: O(n), we are using extra space in the function.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
