Longest subsequence such that absolute difference between every pair is atmost 1
Given an integer array arr[] of size N, the task is to find the longest subsequence S such that for every a[i], a[j] ∈ S and |a[i] – a[j]| ≤ 1.
Examples:
Input: arr[] = {2, 2, 3, 5, 5, 6, 6, 6}
Output: 5
Explanation:
There are 2 such subsequence such that difference between every pair is atmost 1
{2, 2, 3} and {5, 5, 6, 6, 6}
The longest one of these is {5, 5, 6, 6, 6} with length of 5.Input: arr[] = {5, 7, 6, 4, 4, 2}
Output: 3
Approach:
The idea is to observe that for a subsequence with a difference between every possible pair at most one is possible when the subsequence contains elements between [X , X + 1].
- Initialize the maximum length of the required subsequence to 0.
- Create a HashMap to store the frequency of every element of the array.
- Iterate through the Hash Map and for every element a[i] in hash map –
- Find the count of occurrence of element (a[i] + 1), (a[i]) and (a[i] – 1).
- Find the Maximum count out of occurrence of elements (a[i] + 1) or (a[i] – 1).
- If the Total count of occurrence is greater than the maximum length found then update the maximum length of subsequence.
Below is the implementation of the above approach.
C++
#include <iostream> #include <unordered_map> #include <algorithm> using namespace std; // C++ implementation for // Longest subsequence such that absolute // difference between every pair is atmost 1 int longestAr( int n, int arr[]) { unordered_map< int , int > count; // Storing the frequency of each // element in the unordered_map count for ( int i = 0; i < n; i++) { if (count.find(arr[i]) != count.end()) count[arr[i]]++; else count[arr[i]] = 1; } unordered_map< int , int >::iterator it; // Max is used to keep a track of // maximum length of the required // subsequence so far. int max_val = 0; for (it = count.begin(); it != count.end(); it++) { int a = it->first; int cur = 0; int cur1 = 0; int cur2 = 0; // Store frequency of the // given element+1. if (count.find(a + 1) != count.end()) cur1 = count[a + 1]; // Store frequency of the // given element-1. if (count.find(a - 1) != count.end()) cur2 = count[a - 1]; // cur store the longest array // that can be formed using a. cur = count[a] + max(cur1, cur2); // update max_val if cur > max_val. if (cur > max_val) max_val = cur; } return max_val; } // Driver Code int main() { int n = 8; int arr[] = { 2, 2, 3, 5, 5, 6, 6, 6 }; int maxLen = longestAr(n, arr); cout << maxLen << endl; return 0; } |
Java
// Java implementation for // Longest subsequence such that absolute // difference between every pair is atmost 1 import java.util.*; public class w3wiki { public static int longestAr( int n, int arr[]){ Hashtable<Integer, Integer> count = new Hashtable<Integer, Integer>(); // Storing the frequency of each // element in the hashtable count for ( int i = 0 ; i < n; i++) { if (count.containsKey(arr[i])) count.put(arr[i], count.get( arr[i]) + 1 ); else count.put(arr[i], 1 ); } Set<Integer> kset = count.keySet(); Iterator<Integer> it = kset.iterator(); // Max is used to keep a track of // maximum length of the required // subsequence so far. int max = 0 ; while (it.hasNext()) { int a = ( int )it.next(); int cur = 0 ; int cur1 = 0 ; int cur2 = 0 ; // Store frequency of the // given element+1. if (count.containsKey(a + 1 )) cur1 = count.get(a + 1 ); // Store frequency of the // given element-1. if (count.containsKey(a - 1 )) cur2 = count.get(a - 1 ); // cur store the longest array // that can be formed using a. cur = count.get(a) + Math.max(cur1, cur2); // update max if cur>max. if (cur > max) max = cur; } return (max); } // Driver Code public static void main(String[] args) { int n = 8 ; int arr[] = { 2 , 2 , 3 , 5 , 5 , 6 , 6 , 6 }; int maxLen = longestAr(n, arr); System.out.println(maxLen); } } |
Python3
# Python3 implementation for # Longest subsequence such that absolute # difference between every pair is atmost 1 def longestAr(n, arr): count = dict () # Storing the frequency of each # element in the hashtable count for i in arr: count[i] = count.get(i, 0 ) + 1 kset = count.keys() # Max is used to keep a track of # maximum length of the required # subsequence so far. maxm = 0 for it in list (kset): a = it cur = 0 cur1 = 0 cur2 = 0 # Store frequency of the # given element+1. if ((a + 1 ) in count): cur1 = count[a + 1 ] # Store frequency of the # given element-1. if ((a - 1 ) in count): cur2 = count[a - 1 ] # cur store the longest array # that can be formed using a. cur = count[a] + max (cur1, cur2) # update maxm if cur>maxm. if (cur > maxm): maxm = cur return maxm # Driver Code if __name__ = = '__main__' : n = 8 arr = [ 2 , 2 , 3 , 5 , 5 , 6 , 6 , 6 ] maxLen = longestAr(n, arr) print (maxLen) # This code is contributed by mohit kumar 29 |
Javascript
<script> // Javascript implementation for // Longest subsequence such that absolute // difference between every pair is atmost 1 function longestAr(n,arr) { let count = new Map(); // Storing the frequency of each // element in the hashtable count for (let i = 0; i < n; i++) { if (count.has(arr[i])) count.set(arr[i], count.get( arr[i]) + 1 ); else count.set(arr[i], 1); } // Max is used to keep a track of // maximum length of the required // subsequence so far. let max = 0; for (let it of count.keys()) { let a = it; let cur = 0; let cur1 = 0; let cur2 = 0; // Store frequency of the // given element+1. if (count.has(a + 1)) cur1 = count.get(a + 1); // Store frequency of the // given element-1. if (count.has(a - 1)) cur2 = count.get(a - 1); // cur store the longest array // that can be formed using a. cur = count.get(a) + Math.max(cur1, cur2); // update max if cur>max. if (cur > max) max = cur; } return (max); } // Driver Code let n = 8; let arr=[2, 2, 3, 5, 5, 6, 6, 6]; let maxLen = longestAr(n, arr); document.write(maxLen); // This code is contributed by unknown2108 </script> |
C#
// Include namespace system using System; using System.Linq; using System.Collections; using System.Collections.Generic; public class w3wiki { public static int longestAr( int n, int [] arr) { var count = new Dictionary< int , int >(); // Storing the frequency of each // element in the hashtable count for ( int i = 0; i < n; i++) { if (count.ContainsKey(arr[i])) { count[arr[i]] = count[arr[i]] + 1; } else { count[arr[i]] = 1; } } var kset = count.Keys; var it = kset.GetEnumerator(); // Max is used to keep a track of // maximum length of the required // subsequence so far. var max = 0; while (it.MoveNext()) { var a = ( int )it.Current; var cur = 0; var cur1 = 0; var cur2 = 0; // Store frequency of the // given element+1. if (count.ContainsKey(a + 1)) { cur1 = count[a + 1]; } // Store frequency of the // given element-1. if (count.ContainsKey(a - 1)) { cur2 = count[a - 1]; } // cur store the longest array // that can be formed using a. cur = count[a] + Math.Max(cur1,cur2); // update max if cur>max. if (cur > max) { max = cur; } } return (max); } // Driver Code public static void Main(String[] args) { var n = 8; int [] arr = {2, 2, 3, 5, 5, 6, 6, 6}; var maxLen = longestAr(n, arr); Console.WriteLine(maxLen); } } |
Output:
5
Time Complexity: O(n).
Space Complexity: O(n).