Watch 6 video solutions for Find the Maximum Length of a Good Subsequence II, a hard level problem involving Array, Hash Table, Dynamic Programming. This walkthrough by Aryan Mittal has 8,522 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 5 * 1031 <= nums[i] <= 1090 <= k <= min(50, nums.length)Problem Overview: You are given an integer array and a limit k. A subsequence is considered good if the number of positions where adjacent elements differ is at most k. The task is to select a subsequence with the maximum possible length while keeping the number of value transitions ≤ k.
Approach 1: Sliding Window with Transition Count (O(n) time, O(1) space)
This approach treats the problem similarly to a longest valid segment problem. Iterate through the array using two pointers and track how many times adjacent values change inside the current window. When the transition count exceeds k, move the left pointer forward and update the count. The window length represents the current candidate subsequence length. The key operation is maintaining a running count of value changes while expanding and shrinking the window. This works well when the optimal subsequence closely follows the original order and you want a linear-time scan.
Approach 2: Greedy with Frequency Count (O(n) time, O(m) space)
Another practical strategy maintains frequency counts of elements inside the current window using a hash table. Track the most frequent value and compare it with the window length. If too many elements differ from the dominant value, shrink the window. The idea is similar to problems where you keep the majority element and allow limited deviations. Each step performs constant-time updates to the frequency map and adjusts the window boundaries. This greedy strategy works well when the optimal subsequence tends to cluster around frequently appearing values.
Approach 3: Dynamic Programming with Hash Maps (O(nk) time, O(nk) space)
The most general solution uses dynamic programming. Maintain dp[v][c], the maximum length of a subsequence ending with value v using exactly c transitions. When processing each element, you can either extend a subsequence ending with the same value (no new transition) or extend the best subsequence with c-1 transitions and switch values. A global array keeps track of the best subsequence length for each transition count so updates stay efficient. Hash maps store states for values that appear, avoiding large fixed arrays. Each iteration updates states for all k transition levels.
Recommended for interviews: The dynamic programming approach is typically what interviewers expect. It clearly models the subsequence constraint and handles arbitrary value patterns. Sliding window and greedy techniques are useful for reasoning about local segments, but the DP formulation demonstrates deeper understanding of subsequence transitions and state optimization using array iteration and hash-based state tracking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Transition Count | O(n) | O(1) | When treating the problem as a longest valid contiguous segment with limited value changes |
| Greedy with Frequency Count | O(n) | O(m) | When frequent values dominate the sequence and a majority-based window works well |
| Dynamic Programming with Hash Maps | O(nk) | O(nk) | General solution for subsequences with up to k transitions |