Given an array arr[] consisting of N integers and an integer K, the task is to find the longest subsequence of the given array such that the difference between the maximum and the minimum element in the subsequence is exactly K.
Examples:
Input: arr[] = {1, 3, 2, 2, 5, 2, 3, 7}, K = 1
Output: 5
Explanation:
The longest subsequence whose difference between the maximum and minimum element is K(= 1) is {3, 2, 2, 2, 3}.
Therefore, the length is 5.Input: arr [] = {4, 3, 3, 4}, K = 4
Output: 0
Naive Approach: The simplest approach is to generate all possible subsequences of the given array and for every subsequence, find the difference between the maximum and minimum values in the subsequence. If it is equal to K, update the resultant longest subsequence length. After checking for all subsequences, print the maximum length obtained.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based on the observation that in the required subsequence, only two unique elements can be present, and their difference should be K. The problem can be solved by Hashing, to store the frequency of each array element. Follow the steps below to solve the problem:
- Initialize a variable, say ans, to store the length of the longest subsequence.
- Initialize a hashmap, say M, that stores the frequency of the array elements.
- Traverse the array arr[] using the variable i and for each array element arr[i], increment the frequency of arr[] in M by 1.
- Now traverse the hashmap M and for each key(say X) in M, if (X + K) is also present in the M, then update the value of ans to the maximum of ans and the sum of the value of both the keys.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find longest subsequence// having absolute difference between// maximum and minimum element Kvoid longestSubsequenceLength(int arr[], int N, int K){ // Stores the frequency of each // array element unordered_map<int, int> um; // Traverse the array arr[] for (int i = 0; i < N; i++) // Increment um[arr[i]] by 1 um[arr[i]]++; // Store the required answer int ans = 0; // Traverse the hashmap for (auto it : um) { // Check if it.first + K // exists in the hashmap if (um.find(it.first + K) != um.end()) { // Update the answer ans = max(ans, it.second + um[it.first + K]); } } // Print the result cout << ans;}// Driver Codeint main(){ int arr[] = { 1, 3, 2, 2, 5, 2, 3, 7 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 1; longestSubsequenceLength(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find longest subsequence// having absolute difference between// maximum and minimum element Kstatic void longestSubsequenceLength(int []arr, int N, int K){ // Stores the frequency of each // array element Map<Integer, Integer> um = new HashMap<Integer, Integer>(); // Traverse the array arr[] for(int i = 0; i < N; i++) { if (um.containsKey(arr[i])) um.put(arr[i], um.get(arr[i]) + 1); else um.put(arr[i], 1); } // Store the required answer int ans = 0; // Traverse the hashmap for(Map.Entry<Integer, Integer> e : um.entrySet()) { // Check if it.first + K // exists in the hashmap if (um.containsKey(e.getKey() + K)) { // Update the answer ans = Math.max(ans, e.getValue() + um.get(e.getKey() + K)); } } // Print the result System.out.println(ans);}// Driver Codepublic static void main(String args[]){ int []arr = { 1, 3, 2, 2, 5, 2, 3, 7 }; int N = arr.length; int K = 1; longestSubsequenceLength(arr, N, K);}}// This code is contributed by bgangwar59 |
Python3
# Python3 program for the above approachfrom collections import defaultdict# Function to find longest subsequence# having absolute difference between# maximum and minimum element Kdef longestSubsequenceLength(arr, N, K): # Stores the frequency of each # array element um = defaultdict(int) # Traverse the array arr[] for i in range(N): # Increment um[arr[i]] by 1 um[arr[i]] += 1 # Store the required answer ans = 0 # Traverse the hashmap for it in um.keys(): # Check if it.first + K # exists in the hashmap if (it + K) in um: # Update the answer ans = max(ans, um[it] + um[it + K]) # Print the result print(ans)# Driver Codeif __name__ == "__main__": arr = [1, 3, 2, 2, 5, 2, 3, 7] N = len(arr) K = 1 longestSubsequenceLength(arr, N, K) # This code is contributed by chitranayal. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find longest subsequence// having absolute difference between// maximum and minimum element Kstatic void longestSubsequenceLength(int[] arr, int N, int K){ // Stores the frequency of each // array element Dictionary<int, int> um = new Dictionary<int, int>(); // Traverse the array for(int i = 0; i < N; i++) { // Increase the counter of // the array element by 1 int count = um.ContainsKey(arr[i]) ? um[arr[i]] : 0; if (count == 0) { um.Add(arr[i], 1); } else { um[arr[i]] = count + 1; } } // Store the required answer int ans = 0; // Traverse the hashmap foreach(KeyValuePair<int, int> it in um) { // Check if it.first + K // exists in the hashmap if (um.ContainsKey(it.Key + K)) { // Update the answer ans = Math.Max(ans, (it.Value + um[it.Key + K])); } } // Print the result Console.Write(ans);}// Driver Codepublic static void Main(){ int[] arr = { 1, 3, 2, 2, 5, 2, 3, 7 }; int N = arr.Length; int K = 1; longestSubsequenceLength(arr, N, K);}}// This code is contributed by splevel62. |
Javascript
<script>// Javascript program for the above approach// Function to find longest subsequence// having absolute difference between// maximum and minimum element Kfunction longestSubsequenceLength(arr, N, K){ // Stores the frequency of each // array element var um = new Map(); // Traverse the array arr[] for (var i = 0; i < N; i++) // Increment um[arr[i]] by 1 if(um.has(arr[i])) { um.set(arr[i], um.get(arr[i])+1); } else { um.set(arr[i], 1); } // Store the required answer var ans = 0; // Traverse the hashmap um.forEach((value, key) => { // Check if it.first + K // exists in the hashmap if (um.has(key+K)) { // Update the answer ans = Math.max(ans, value + um.get(key+K)); } }); // Print the result document.write( ans);}// Driver Codevar arr = [ 1, 3, 2, 2, 5, 2, 3, 7 ];var N = arr.length;var K = 1;longestSubsequenceLength(arr, N, K);</script> |
Output:
5
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
