Find the Maximum Length of a Good Subsequence II - Solution & Explanation
Problem Statement
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)
Approach Overview
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 1: Sliding Window Approach
This approach uses the sliding window technique to find the maximum length of a good subsequence. The aim is to maintain a window that can have at most k differences between consecutive elements.
The technique involves two pointers, one representing the start of the window and the other the end, iterating through the array and counting differences. If the differences exceed k, the start pointer is moved forward to reduce the count.
This solution in C initializes two pointers i and j. The pointer j expands the window while counting the number of differences between consecutive elements. If the count exceeds k, the window is shrunk from the left by incrementing i.
Complexity
Time Complexity: O(n), where n is the length of the array. Space Complexity: O(1) as no extra space is used beyond variables.
Approach 2: Greedy Approach with Frequency Count
This approach involves counting the frequency of each number in the array. The idea is to use the most frequent numbers to form the longest possible good subsequence, allowing up to k unique transitions where necessary.
By first counting the frequencies and then iterating over the sorted frequency list, we can focus on building the longest possible sequence that satisfies the conditions.
This C implementation uses a frequency array to count occurrences of each number. Frequencies are sorted in descending order, and the algorithm selects most frequent numbers up to k times, summing their counts to get the maximum possible length of the subsequence.
Complexity
Time Complexity: O(n + n log n) due to sorting, where n is the number of elements. Space Complexity: O(n) for the frequency count array.
Approach 3: Dynamic Programming
We define f[i][h] as the length of the longest good subsequence ending with nums[i] and having no more than h indices satisfying the condition. Initially, f[i][h] = 1. The answer is max(f[i][k]), where 0 \le i < n.
We consider how to calculate f[i][h]. We can enumerate 0 \le j < i, if nums[i] = nums[j], then f[i][h] = max(f[i][h], f[j][h] + 1); otherwise, if h > 0, then f[i][h] = max(f[i][h], f[j][h - 1] + 1). That is:
$
f[i][h]=
\begin{cases}
max(f[i][h], f[j][h] + 1), & if nums[i] = nums[j], \
max(f[i][h], f[j][h - 1] + 1), & if h > 0.
\end{cases}
The final answer is max(f[i][k]), where 0 \le i < n.
The time complexity is O(n^2 times k), and the space complexity is O(n times k). Where n is the length of the array nums.
Due to the large data range of this problem, the above solution will time out and needs to be optimized.
According to the state transition equation, if nums[i] = nums[j], then we only need to get the maximum value of f[j][h], we can maintain it 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 it 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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: |
| Greedy Approach with Frequency Count | Time Complexity: |
| Dynamic Programming | — |
Detailed Complexity Analysis
| 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 |
Video Solution
3177 & 3176 Find the Maximum Length of a Good Subsequence II & Subsequence I I | DP | LIS • Aryan Mittal • 8,770 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Find the Maximum Length of a Good Subsequence II easy or hard?
Find the Maximum Length of a Good Subsequence II Python/Java solution
How to solve Find the Maximum Length of a Good Subsequence II in O(n)?
What is the best approach for Find the Maximum Length of a Good Subsequence II?
Is Find the Maximum Length of a Good Subsequence II asked at Google/Amazon/Meta?
What data structure is used in Find the Maximum Length of a Good Subsequence II?
What is the time complexity of Find the Maximum Length of a Good Subsequence II?
Ready to solve this problem?
Practice Find the Maximum Length of a Good Subsequence II with our built-in code editor and test cases.
Practice on FleetCode