You are given an integer array nums and a non-negative integer k. A sequence of integers seq is called good if there are at most k indices i in the range [0, seq.length - 2] such that seq[i] != seq[i + 1].
Return the maximum possible length of a good subsequence of nums.
Example 1:
Input: nums = [1,2,1,1,3], k = 2
Output: 4
Explanation:
The maximum length subsequence is [1,2,1,1,3].
Example 2:
Input: nums = [1,2,3,4,5,1], k = 0
Output: 2
Explanation:
The maximum length subsequence is [1,2,3,4,5,1].
Constraints:
1 <= nums.length <= 5001 <= nums[i] <= 1090 <= k <= min(nums.length, 25)Problem Overview: You are given an integer array and an integer k. A subsequence is considered good if the number of times adjacent elements in the subsequence have different values is at most k. The goal is to return the maximum possible length of such a subsequence.
Approach 1: Sliding Window with Counting Changes (O(n) time, O(1) space)
If you treat the problem as finding the longest contiguous segment where the number of adjacent value changes is ≤ k, a two‑pointer sliding window works well. Iterate the array with a right pointer and count how many times nums[i] != nums[i-1]. When this count exceeds k, move the left pointer forward while decreasing the change counter when a transition leaves the window. The window size gives the current candidate length. This approach uses simple iteration and constant memory, making it practical when you interpret the constraint over contiguous elements. Sliding window patterns commonly appear in array problems and help maintain constraints in linear time.
Approach 2: Dynamic Programming with Value Tracking (O(nk) time, O(nk) space)
A more general method treats the problem strictly as a subsequence problem. Maintain dp[j][v], the maximum subsequence length ending with value v using exactly j value changes. When processing a new element x, you either extend a subsequence that already ends with x (no additional change) or transition from a subsequence ending with a different value, which increases the change count. Efficient implementations keep track of the best subsequence length for each j so you can update states in constant time per transition. Hash maps store lengths per value, which connects naturally with hash table techniques.
The key insight: the constraint depends only on whether the next value equals the previous one. Dynamic programming groups subsequences by their last value and the number of changes used so far. Each element updates states from j = k down to 0 to avoid overwriting transitions. This pattern is common in dynamic programming problems where the state depends on the previous element and a limited budget of operations.
Recommended for interviews: The dynamic programming approach is the expected solution because the problem explicitly asks for a subsequence rather than a contiguous segment. Sliding window demonstrates awareness of transition counting, but DP shows stronger algorithmic reasoning and handles the general case with precise state transitions.
In this approach, the idea is to use a sliding window technique with two pointers. Track the number of changes (i.e., indices where the current element is different from the previous one) within the window. Adjust the window size by moving the left pointer forward whenever the number of changes exceeds k. The longest window that satisfies the condition is our answer.
The function scans over the list 'nums' using two pointers 'left' and 'right'. The 'right' pointer iterates through the list, and each time a change is detected (non-equal consecutive elements), the 'changes' counter is incremented. If 'changes' exceed 'k', the 'left' pointer is moved forward until 'changes' falls back to 'k' or below. The length of the window is continuously checked and updated if it provides a larger subsequence.
Time Complexity: O(n), where n is the length of the array. Each element is processed at most twice.
Space Complexity: O(1), only a constant amount of extra space is used.
Using dynamic programming, the problem can be solved by defining a table where dp[i][j] represents the maximum length of a good subsequence in the first i elements with j changes. Transition depends on whether we choose to include the i-th element by considering the previous changes. This builds on previous calculated results, allowing for an efficient exploration of the solution space.
In this Python solution, we establish a 2D dp table where dp[i][j] holds the maximum length achievable from the first i elements with j permissible changes of value. Using dynamic programming, we can leverage previously determined solutions by considering the inclusion or exclusion of the current element in computation.
Python
C++
Java
Go
TypeScript
Time Complexity: O(n*k), where n is the length of the array and k is the maximum allowed changes. Each dp state is filled considering k possibilities.
Space Complexity: O(n*k), due to the storage required by the dp table.
According to the state transition equation in Solution 1, if nums[i] = nums[j], then we only need to get the maximum value of f[j][h]. We can maintain this with an array mp of length k + 1. If nums[i] neq nums[j], we need to record the maximum value of f[j][h - 1] corresponding to nums[j], the maximum value and the second maximum value. We can maintain these with an array g of length k + 1.
The time complexity is O(n times k), and the space complexity is O(n times k). Where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window with Counting Changes | Time Complexity: O(n), where n is the length of the array. Each element is processed at most twice. |
| Dynamic Programming | Time Complexity: O(n*k), where n is the length of the array and k is the maximum allowed changes. Each dp state is filled considering k possibilities. |
| Optimized Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Counting Changes | O(n) | O(1) | When interpreting the problem as a contiguous segment where adjacent value changes are limited |
| Dynamic Programming with Hash Map | O(nk) | O(nk) | General subsequence case where elements can be skipped and transitions must be tracked |
3177 & 3176 Find the Maximum Length of a Good Subsequence II & Subsequence I I | DP | LIS • Aryan Mittal • 8,522 views views
Watch 6 more video solutions →Practice Find the Maximum Length of a Good Subsequence I with our built-in code editor and test cases.
Practice on FleetCode