Longest Subsequence With Adjacent Difference One
01 · Problem
Given an integer array nums, pick a subsequence (keep the original order, skipping any elements you like) such that every two consecutive picked elements differ by exactly 1 in absolute value (|x - y| == 1). The values may go up and down.
Return the length of the longest such subsequence. A single element is always valid, so the answer is at least 1.
02 · Examples
nums = [10,9,4,5,4,8,6]
3
Both [10,9,8] and [4,5,4] are valid subsequences of length 3, and none of length 4 exists.
nums = [1,2,3,2,3,7,2,1]
7
Take [1,2,3,2,3,2,1], skipping only the 7. Each neighbouring pair differs by exactly 1.
nums = [5,5,5]
1
Equal neighbours differ by 0, so only single-element subsequences are valid.
03 · Constraints
- 011 <= nums.length <= 105
- 02-109 <= nums[i] <= 109
- 03A single element is a valid subsequence
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.