Given an array of size **n**. The task is to find the longest subsequence such that difference between adjacents is one. Time Complexity of O(n) is required.

**Examples:**

Input : arr[] = {10, 9, 4, 5, 4, 8, 6} Output : 3 As longest subsequences with difference 1 are, "10, 9, 8", "4, 5, 4" and "4, 5, 6". Input : arr[] = {1, 2, 3, 2, 3, 7, 2, 1} Output : 7 As longest consecutive sequence is "1, 2, 3, 2, 3, 2, 1".

**Method 1:** Previously an approach having time complexity of O(n^{2}) have been discussed in this post.

**Method 2 (Efficient Approach):** The idea is to create a hash map having tuples in the form **(ele, len)**, where **len** denotes the length of the longest subsequence ending with the element **ele**. Now, for each element arr[i] we can find the length of the values arr[i]-1 and arr[i]+1 in the hash table and consider the maximum among them. Let this maximum value be **max**. Now, the length of longest subsequence ending with arr[i] would be **max+1**. Update this length along with the element arr[i] in the hash table. Finally, the element having the maximum length in the hash table gives the longest length subsequence.

## C++

`// C++ implementation to find longest subsequence ` `// such that difference between adjacents is one ` `#include <bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// function to find longest subsequence such ` `// that difference between adjacents is one ` `int` `longLenSub(` `int` `arr[], ` `int` `n) ` `{ ` ` ` `// hash table to map the array element with the ` ` ` `// length of the longest subsequence of which ` ` ` `// it is a part of and is the last element of ` ` ` `// that subsequence ` ` ` `unordered_map<` `int` `, ` `int` `> um; ` ` ` ` ` `// to store the longest length subsequence ` ` ` `int` `longLen = 0; ` ` ` ` ` `// traverse the array elements ` ` ` `for` `(` `int` `i=0; i<n; i++) ` ` ` `{ ` ` ` `// initialize current length ` ` ` `// for element arr[i] as 0 ` ` ` `int` `len = 0; ` ` ` ` ` `// if 'arr[i]-1' is in 'um' and its length ` ` ` `// of subsequence is greater than 'len' ` ` ` `if` `(um.find(arr[i]-1) != um.end() && ` ` ` `len < um[arr[i]-1]) ` ` ` `len = um[arr[i]-1]; ` ` ` ` ` `// if 'arr[i]+1' is in 'um' and its length ` ` ` `// of subsequence is greater than 'len' ` ` ` `if` `(um.find(arr[i]+1) != um.end() && ` ` ` `len < um[arr[i]+1]) ` ` ` `len = um[arr[i]+1]; ` ` ` ` ` `// update arr[i] subsequence length in 'um' ` ` ` `um[arr[i]] = len + 1; ` ` ` ` ` `// update longest length ` ` ` `if` `(longLen < um[arr[i]]) ` ` ` `longLen = um[arr[i]]; ` ` ` `} ` ` ` ` ` `// required longest length subsequence ` ` ` `return` `longLen; ` `} ` ` ` `// Driver program to test above ` `int` `main() ` `{ ` ` ` `int` `arr[] = {1, 2, 3, 4, 5, 3, 2}; ` ` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]); ` ` ` `cout << ` `"Longest length subsequence = "` ` ` `<< longLenSub(arr, n); ` ` ` `return` `0; ` `} ` |

## Python3

`# Python3 implementation to find longest ` `# subsequence such that difference between ` `# adjacents is one ` `from` `collections ` `import` `defaultdict ` ` ` `# function to find longest subsequence such ` `# that difference between adjacents is one ` `def` `longLenSub(arr, n): ` ` ` ` ` `# hash table to map the array element ` ` ` `# with the length of the longest ` ` ` `# subsequence of which it is a part of ` ` ` `# and is the last element of that subsequence ` ` ` `um ` `=` `defaultdict(` `lambda` `:` `0` `) ` ` ` `longLen ` `=` `0` ` ` `for` `i ` `in` `range` `(n): ` ` ` ` ` `# / initialize current length ` ` ` `# for element arr[i] as 0 ` ` ` `len1 ` `=` `0` ` ` ` ` `# if 'arr[i]-1' is in 'um' and its length ` ` ` `# of subsequence is greater than 'len' ` ` ` `if` `(arr[i ` `-` `1` `] ` `in` `um ` `and` ` ` `len1 < um[arr[i] ` `-` `1` `]): ` ` ` `len1 ` `=` `um[arr[i] ` `-` `1` `] ` ` ` ` ` `# f 'arr[i]+1' is in 'um' and its length ` ` ` `# of subsequence is greater than 'len' ` ` ` `if` `(arr[i] ` `+` `1` `in` `um ` `and` ` ` `len1 < um[arr[i] ` `+` `1` `]): ` ` ` `len1 ` `=` `um[arr[i] ` `+` `1` `] ` ` ` ` ` `# update arr[i] subsequence ` ` ` `# length in 'um' ` ` ` `um[arr[i]] ` `=` `len1 ` `+` `1` ` ` ` ` `# update longest length ` ` ` `if` `longLen < um[arr[i]]: ` ` ` `longLen ` `=` `um[arr[i]] ` ` ` ` ` `# required longest length ` ` ` `# subsequence ` ` ` `return` `longLen ` ` ` `# Driver code ` `arr ` `=` `[` `1` `, ` `2` `, ` `3` `, ` `4` `, ` `5` `, ` `3` `, ` `2` `] ` `n ` `=` `len` `(arr) ` `print` `(` `"Longest length subsequence ="` `, ` ` ` `longLenSub(arr, n)) ` ` ` `# This code is contributed by Shrikant13 ` |

**Output:**

Longest length subsequence = 6

**Time Complexity:** O(n).

**Auxiliary Space:** O(n).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments