Last Updated: 26 Feb, 2021
Longest Subsequence With Difference One
Moderate
Asked in companies
You are given an array “nums” of size N. Your task is to find the length of the longest subsequence of array “nums” such that the absolute difference between every adjacent element in the subsequence is one.
For Example:
If “nums” = {2, 1, 3}.
The valid non-empty subsequences of the array are {2}, {1}, {3}, {2, 1}, {1, 3}, {2, 3} and {2, 1, 3}. So, the longest subsequence satisfying the given conditions are {2, 1} and {2, 3}. The length of the longest subsequence is 2. So, the answer is 2.
The subsequence of an array is a sequence of numbers that can be formed by deleting some or no elements without changing the order of the remaining elements. For example, if the given array “nums” = {1, 2, 5, 4, 8}, then {1, 2, 5, 4, 8}, {1, 5, 8}, {2} are some of the valid subsequences whereas the sequence {4, 2} is not a valid subsequence as the order of the elements differ from the original array.
Note:
Any subsequence of length = 1 is also a valid subsequence.
Input format:
The first line contains an integer ‘T', which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first line of each test case contains a single integer N, denoting the size of the array “nums”.
The second line of each test case contains N space-separated integers denoting the elements of the array “nums”.
Output format:
For each test case, print the length of the longest subsequence of array “nums” such that the difference between adjacent elements is one.
Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 5000
-10^9 <= nums[i] <= 10^9
Time limit: 1 second
Approaches
The idea is similar to the LIS problem. We create a dp array of size N and initialize all the elements to 1. We run a loop from i = 0 to N - 1 and for each element, we run another loop from j = i + 1 to N. If the absolute difference between nums[i] and nums[j] is 1, then store the maximum of dp[j] and dp[i] + 1 in dp[j].
Steps:
- Create a dp array of size N and initialize all the elements to 1.
- Run a loop from i = 0 to N - 1 and do:
- Run a loop from j = i + 1 to N and do:
- If abs(nums[j] - nums[i]) == 1, then dp[j] = max(dp[j], dp[i] + 1).
- Run a loop from j = i + 1 to N and do:
- Create a variable maximum to store the length of the longest subsequence satisfying the condition. Initialize it to 0.
- Run a loop from i = 0 to N and do:
- Make maximum = max(maximum, dp[i]).
- Finally, return the maximum.
The idea is to iterate through the array and for each number, search the value of the number-1 and number+1 in the HashMap. Make the value of HashMap[number] = max(HashMap[number - 1], HashMap[number + 1]) + 1.
Then iterate through the HashMap and return the maximum value.
Steps:
- Create a HashMap. Let’s call this map.
- Run a loop from i = 0 to N and do:
- map[nums[i]] = max(map[nums[i] - 1], map[nums[i] + 1]) + 1.
- Create a variable maximum to store the length of the longest subsequence satisfying the condition. Initialize it to 0.
- Run a loop from i = 0 to N and do:
- Make maximum = max(maximum, map[nums[i]]).
- Finally, return the maximum.