Maximum distance between two elements whose absolute difference is K
Given an array arr[] and a number K, the task to find the maximum distance between two elements whose absolute difference is K. If it is not possible to find any maximum distance then print ā-1ā.
Example:
Input: arr[] = {3, 5, 1, 4, 2, 2}
Output: 5
Explanation:
The max distance between the two elements (3, 2) at index 0 and 5 is 5.Input: arr[] = {11, 2, 3, 8, 5, 2}
Output: 3
Explanation:
The max distance between the two elements (3, 2) at index 2 and 5 is 3.
Naive Approach: The idea is to pick each element(say arr[i]) one by one, search for the previous element (arr[i] ā K) and the next element (arr[i] + K). If any of the two-element exists then find the maximum distance between the current element with its next or previous element.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Implementation:-
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that find maximum distance // between two elements whose absolute // difference is K int maxDistance( int arr[], int K, int N) { //variable to store answer int ans = -1; //traversing array for ( int i=1;i<N;i++) { for ( int j=i-1;j>=0;j--) { //checking if the absolute difference is K or not if ( abs (arr[i]-arr[j])==K) { ans=max(ans,i-j); } } } return ans; } // Driver code int main() { // Given array arr[] int arr[] = { 11, 2, 3, 8, 5, 2 }; int N = sizeof (arr) / sizeof (arr[0]); // Given difference K int K = 2; // Function call cout << maxDistance(arr, K, N); return 0; } // This code is contributed by shubhamrajput6156 |
Java
// Java program for the above approach class GFG { // Function that find maximum distance // between two elements whose absolute // difference is K public static int maxDistance( int [] arr, int K, int N) { //variable to store answer int ans = - 1 ; //traversing array for ( int i = 1 ;i < N;i++) { for ( int j = i - 1 ;j >= 0 ;j--) { //checking if the absolute difference is K or not if (Math.abs(arr[i] - arr[j]) == K) { ans = Math.max(ans,i - j); } } } return ans; } // Driver code public static void main(String[] args) { // Given array arr[] int [] arr = { 11 , 2 , 3 , 8 , 5 , 2 }; int N = arr.length; // Given difference K int K = 2 ; // Function call System.out.print(maxDistance(arr, K, N)); } } // This code is contributed by bhardwajji |
Python3
# C++ program for the above approach # Function that find maximum distance # between two elements whose absolute # difference is K def maxDistance(arr, K, N): # variable to store answer ans = - 1 for i in range ( 1 , N): for j in range (i - 1 , - 1 , - 1 ): # checking if the absolute difference is K or not if abs (arr[i] - arr[j]) = = K: ans = max (ans, i - j) return ans #driver code # given array arr = [ 11 , 2 , 3 , 8 , 5 , 2 ] N = len (arr) # Given difference K K = 2 print (maxDistance(arr, K, N)) |
C#
// C# program for the above approach using System; public class GFG { // Function that find maximum distance // between two elements whose absolute // difference is K static int MaxDistance( int [] arr, int K, int N) { // variable to store answer int ans = -1; // traversing array for ( int i = 1; i < N; i++) { for ( int j = i - 1; j >= 0; j--) { // checking if the absolute difference is K or not if (Math.Abs(arr[i] - arr[j]) == K) { ans = Math.Max(ans, i - j); } } } return ans; } // Driver code static void Main( string [] args) { // Given array arr[] int [] arr = { 11, 2, 3, 8, 5, 2 }; int N = arr.Length; // Given difference K int K = 2; // Function call Console.WriteLine(MaxDistance(arr, K, N)); } } // this code is contributed by bhardwajji |
Javascript
// Javascript program for the above approach // Function that finds maximum distance between two elements // whose absolute difference is K function maxDistance(arr, K, N) { // variable to store answer let ans = -1; // traversing array for (let i = 1; i < N; i++) { for (let j = i - 1; j >= 0; j--) { // checking if the absolute difference is K or not if (Math.abs(arr[i] - arr[j]) === K) ans = Math.max(ans, i - j); } } return ans; } // Driver code // Given array arr[] const arr = [11, 2, 3, 8, 5, 2]; const N = arr.length; // Given difference K const K = 2; // Function call console.log(maxDistance(arr, K, N)); |
2
Time Complexity:- O(N^2)
Auxiliary Space:- O(1)
Efficient Approach: To optimize the above approach, the idea is to use hashmap. Below are the steps:
- Traverse the array and store the index of the first occurrence in a HashMap.
- Now, for each element in the array arr[], check if arr[i] + K and arr[i] ā K is present in the hashmap or not.
- If present, then update the distance from both the elements with the arr[i] and check for the next element.
- Print the maximum distance obtained after the above steps.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that find maximum distance // between two elements whose absolute // difference is K int maxDistance( int arr[], int K, int N) { // To store the first index unordered_map< int , int > Map; // Traverse elements and find // maximum distance between 2 // elements whose absolute // difference is K int maxDist = 0; for ( int i = 0; i < N; i++) { // If this is first occurrence // of element then insert // its index in map if (Map.find(arr[i]) == Map.end()) Map[arr[i]] = i; // If next element present in // map then update max distance if (Map.find(arr[i] + K) != Map.end()) { maxDist = max(maxDist, i - Map[arr[i] + K]); } // If previous element present // in map then update max distance if (Map.find(arr[i] - K) != Map.end()) { maxDist = max(maxDist, i - Map[arr[i] - K]); } } // Return the answer if (maxDist == 0) return -1; else return maxDist; } // Driver code int main() { // Given array arr[] int arr[] = { 11, 2, 3, 8, 5, 2 }; int N = sizeof (arr) / sizeof (arr[0]); // Given difference K int K = 2; // Function call cout << maxDistance(arr, K, N); return 0; } // This code is contributed by divyeshrabadiya07 |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function that find maximum distance // between two elements whose absolute // difference is K static int maxDistance( int [] arr, int K) { // To store the first index Map<Integer, Integer> map = new HashMap<>(); // Traverse elements and find // maximum distance between 2 // elements whose absolute // difference is K int maxDist = 0 ; for ( int i = 0 ; i < arr.length; i++) { // If this is first occurrence // of element then insert // its index in map if (!map.containsKey(arr[i])) map.put(arr[i], i); // If next element present in // map then update max distance if (map.containsKey(arr[i] + K)) { maxDist = Math.max( maxDist, i - map.get(arr[i] + K)); } // If previous element present // in map then update max distance if (map.containsKey(arr[i] - K)) { maxDist = Math.max(maxDist, i - map.get(arr[i] - K)); } } // Return the answer if (maxDist == 0 ) return - 1 ; else return maxDist; } // Driver Code public static void main(String args[]) { // Given array arr[] int [] arr = { 11 , 2 , 3 , 8 , 5 , 2 }; // Given difference K int K = 2 ; // Function call System.out.println( maxDistance(arr, K)); } } |
Python3
# Python3 program for the above approach # Function that find maximum distance # between two elements whose absolute # difference is K def maxDistance(arr, K): # To store the first index map = {} # Traverse elements and find # maximum distance between 2 # elements whose absolute # difference is K maxDist = 0 for i in range ( len (arr)): # If this is first occurrence # of element then insert # its index in map if not arr[i] in map : map [arr[i]] = i # If next element present in # map then update max distance if arr[i] + K in map : maxDist = max (maxDist, i - map [arr[i] + K]) # If previous element present # in map then update max distance if arr[i] - K in map : maxDist = max (maxDist, i - map [arr[i] - K]) # Return the answer if maxDist = = 0 : return - 1 else : return maxDist # Driver code # Given array arr[] arr = [ 11 , 2 , 3 , 8 , 5 , 2 ] # Given difference K K = 2 # Function call print (maxDistance(arr,K)) # This code is contributed by Stuti Pathak |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function that find maximum distance // between two elements whose absolute // difference is K static int maxDistance( int [] arr, int K) { // To store the first index Dictionary< int , int > map = new Dictionary< int , int >(); // Traverse elements and find // maximum distance between 2 // elements whose absolute // difference is K int maxDist = 0; for ( int i = 0; i < arr.Length; i++) { // If this is first occurrence // of element then insert // its index in map if (!map.ContainsKey(arr[i])) map.Add(arr[i], i); // If next element present in // map then update max distance if (map.ContainsKey(arr[i] + K)) { maxDist = Math.Max(maxDist, i - map[arr[i] + K]); } // If previous element present // in map then update max distance if (map.ContainsKey(arr[i] - K)) { maxDist = Math.Max(maxDist, i - map[arr[i] - K]); } } // Return the answer if (maxDist == 0) return -1; else return maxDist; } // Driver Code public static void Main(String []args) { // Given array []arr int [] arr = { 11, 2, 3, 8, 5, 2 }; // Given difference K int K = 2; // Function call Console.WriteLine( maxDistance(arr, K)); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program for the above approach // Function that find maximum distance // between two elements whose absolute // difference is K function maxDistance(arr, K, N) { // To store the first index var map = new Map(); // Traverse elements and find // maximum distance between 2 // elements whose absolute // difference is K var maxDist = 0; for ( var i = 0; i < N; i++) { // If this is first occurrence // of element then insert // its index in map if (!map.has(arr[i])) map.set(arr[i], i); // If next element present in // map then update max distance if (map.has(arr[i] + K)) { maxDist = Math.max(maxDist, i - map.get(arr[i] + K)); } // If previous element present // in map then update max distance if (map.has(arr[i] - K)) { maxDist = Math.max(maxDist, i - map.get(arr[i] - K)); } } // Return the answer if (maxDist == 0) return -1; else return maxDist; } // Driver code // Given array arr[] var arr = [11, 2, 3, 8, 5, 2]; var N = arr.length; // Given difference K var K = 2; // Function call document.write( maxDistance(arr, K, N)); // This code is contributed by famously. </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)