Find the Maximum Length of a Good Subsequence II solution and explanation
7 more videos on this problem
3177 & 3176 Find the Maximum Length of a Good Subsequence II & Subsequence I I | DP | LISAryan Mittal · 26:01 · 8K views
Leetcode | Biweekly Contest 132 | 3176 | 3177 | Find the Maximum Length of a Good Subsequence II.Pretest Passed · 22:07 · 1K views
3177. Find the Maximum Length of a Good Subsequence II | DP | Map | Binary SearchTech Courses · 13:56 · 795 views
【每日一题】LeetCode 3177. Find the Maximum Length of a Good Subsequence IIHuifeng Guan · 31:50 · 634 views
3177. Find the Maximum Length of a Good Subsequence II (Leetcode Hard)Programming Live with Larry · 34:41 · 506 views
3177 Find the Maximum Length of a Good Subsequence II | leetcode | contest 132 | solved | java |Ssquare · 1:03 · 74 views
3177. Find the Maximum Length of a Good Subsequence II 求出最长好子序列 II LeetCode 力扣题解程序员写代码 · 9:15 · 22 views
Find the Maximum Length of a Good Subsequence 1 and 2 | Leetcode Biweekly Contest 132Kumar K [Amazon] · 1:06:52 · 1K views
The problem
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.
def max_good_subsequence_length(nums, k):
max_length = 0
different_seq = 0
i = 0
for j in range(len(nums)):
if j > 0 and nums[j] != nums[j - 1]:
different_seq += 1
while different_seq > k:
if nums[i] != nums[i + 1]:
different_seq -= 1
i += 1
max_length = max(max_length, j - i + 1)
return max_length
# Example usage:
nums = [1, 2, 1, 1, 3]
k = 2
print(max_good_subsequence_length(nums, k))public class Solution {
public int maxGoodSubsequenceLength(int[] nums, int k) {
int maxLength = 0, differentSeq = 0;
for (int i = 0, j = 0; j < nums.length; j++) {
if (j > 0 && nums[j] != nums[j - 1]) {
differentSeq++;
}
while (differentSeq > k) {
if (nums[i] != nums[i + 1]) differentSeq--;
i++;
}
maxLength = Math.max(maxLength, j - i + 1);
}
return maxLength;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 1, 1, 3};
int k = 2;
System.out.println(sol.maxGoodSubsequenceLength(nums, k));
}
}#include <vector>
#include <iostream>
using namespace std;
int maxGoodSubsequenceLength(vector<int>& nums, int k) {
int maxLength = 0, differentSeq = 0;
for (int i = 0, j = 0; j < nums.size(); j++) {
if (j > 0 && nums[j] != nums[j - 1]) {
differentSeq++;
}
while (differentSeq > k) {
if (nums[i] != nums[i + 1]) differentSeq--;
i++;
}
maxLength = max(maxLength, j - i + 1);
}
return maxLength;
}
int main() {
vector<int> nums = {1, 2, 1, 1, 3};
int k = 2;
cout << maxGoodSubsequenceLength(nums, k) << endl;
return 0;
}function maxGoodSubsequenceLength(nums, k) {
let maxLength = 0, differentSeq = 0;
for (let i = 0, j = 0; j < nums.length; j++) {
if (j > 0 && nums[j] !== nums[j - 1]) {
differentSeq++;
}
while (differentSeq > k) {
if (nums[i] !== nums[i + 1]) differentSeq--;
i++;
}
maxLength = Math.max(maxLength, j - i + 1);
}
return maxLength;
}
// Example usage:
const nums = [1, 2, 1, 1, 3];
const k = 2;
console.log(maxGoodSubsequenceLength(nums, k));#include <stdio.h>
int maxGoodSubsequenceLength(int* nums, int numsSize, int k) {
int maxLength = 0, differentSeq = 0;
for (int i = 0, j = 0; j < numsSize; j++) {
if (j > 0 && nums[j] != nums[j - 1]) {
differentSeq++;
}
while (differentSeq > k) {
if (nums[i] != nums[i + 1]) differentSeq--;
i++;
}
if(j - i + 1 > maxLength) {
maxLength = j - i + 1;
}
}
return maxLength;
}
int main() {
int nums[] = {1, 2, 1, 1, 3};
int k = 2;
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = maxGoodSubsequenceLength(nums, numsSize, k);
printf("%d\n", result);
return 0;
}using System;
class Solution {
public int MaxGoodSubsequenceLength(int[] nums, int k) {
int maxLength = 0, differentSeq = 0;
for (int i = 0, j = 0; j < nums.Length; j++) {
if (j > 0 && nums[j] != nums[j - 1]) {
differentSeq++;
}
while (differentSeq > k) {
if (nums[i] != nums[i + 1]) differentSeq--;
i++;
}
maxLength = Math.Max(maxLength, j - i + 1);
}
return maxLength;
}
static void Main() {
var solution = new Solution();
int[] nums = { 1, 2, 1, 1, 3 };
int k = 2;
Console.WriteLine(solution.MaxGoodSubsequenceLength(nums, k));
}
}This Python solution implements a sliding window with two pointers i and j to maintain the count of differences. The window expands and contracts to ensure it has at most k differences.
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.
from collections import Counter
def max_good_subsequence_length(nums, k):
freq = Counter(nums)
freqs = sorted(freq.values(), reverse=True)
max_length = 0
for i in range(len(freqs)):
if k >= 0:
max_length += freqs[i]
k -= 1
return max_length
# Example usage:
nums = [1, 2, 1, 1, 3]
k = 2
print(max_good_subsequence_length(nums, k))import java.util.*;
public class Solution {
public int maxGoodSubsequenceLength(int[] nums, int k) {
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
List<Integer> freqs = new ArrayList<>(freqMap.values());
freqs.sort(Collections.reverseOrder());
int maxLength = 0;
for (int i = 0; i < freqs.size() && k >= 0; i++) {
maxLength += freqs.get(i);
k--;
}
return maxLength;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 1, 1, 3};
int k = 2;
System.out.println(sol.maxGoodSubsequenceLength(nums, k));
}
}#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int maxGoodSubsequenceLength(vector<int>& nums, int k) {
map<int, int> freqMap;
for (int num : nums) freqMap[num]++;
vector<int> freqs;
for (auto p : freqMap) {
freqs.push_back(p.second);
}
sort(freqs.rbegin(), freqs.rend());
int maxLength = 0;
for (int i = 0; i < freqs.size() && k >= 0; i++) {
maxLength += freqs[i];
k--;
}
return maxLength;
}
int main() {
vector<int> nums = {1, 2, 1, 1, 3};
int k = 2;
cout << maxGoodSubsequenceLength(nums, k) << endl;
return 0;
}function maxGoodSubsequenceLength(nums, k) {
const freqMap = new Map();
for (const num of nums) {
freqMap.set(num, (freqMap.get(num) || 0) + 1);
}
const freqs = Array.from(freqMap.values()).sort((a, b) => b - a);
let maxLength = 0;
for (let i = 0; i < freqs.length && k >= 0; i++) {
maxLength += freqs[i];
k--;
}
return maxLength;
}
// Example usage:
const nums = [1, 2, 1, 1, 3];
const k = 2;
console.log(maxGoodSubsequenceLength(nums, k));#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)b - *(int*)a);
}
int maxGoodSubsequenceLength(int* nums, int numsSize, int k) {
int freq[numsSize];
for (int i = 0; i < numsSize; i++) freq[i] = 0;
for (int i = 0; i < numsSize; i++) freq[nums[i] - 1]++;
qsort(freq, numsSize, sizeof(int), compare);
int maxLength = 0;
for (int i = 0; i < numsSize && k >= 0; i++) {
if(freq[i] > 0) {
maxLength += freq[i];
k--;
}
}
return maxLength;
}
int main() {
int nums[] = {1, 2, 1, 1, 3};
int k = 2;
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = maxGoodSubsequenceLength(nums, numsSize, k);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
class Solution {
public int MaxGoodSubsequenceLength(int[] nums, int k) {
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (int num in nums) {
if (!freq.ContainsKey(num)) {
freq[num] = 0;
}
freq[num]++;
}
List<int> freqs = freq.Values.ToList();
freqs.Sort((a, b) => b - a);
int maxLength = 0;
for (int i = 0; i < freqs.Count && k >= 0; i++) {
maxLength += freqs[i];
k--;
}
return maxLength;
}
static void Main() {
var solution = new Solution();
int[] nums = { 1, 2, 1, 1, 3 };
int k = 2;
Console.WriteLine(solution.MaxGoodSubsequenceLength(nums, k));
}
}This Python solution utilizes the Counter class to count each element, sorts the frequency list in descending order, and select frequencies for subsequences with possible k transitions.
Time Complexity: O(n + m log m), where n is the length of the input list and m the number of unique elements. Space Complexity: O(m) for storage of frequencies.
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.
function maximumLength(nums: number[], k: number): number {
const n = nums.length;
const f: number[][] = Array.from({ length: n }, () => Array(k + 1).fill(0));
const mp: Map<number, number>[] = Array.from({ length: k + 1 }, () => new Map());
const g: number[][] = Array.from({ length: k + 1 }, () => Array(3).fill(0));
let ans = 0;
for (let i = 0; i < n; i++) {
for (let h = 0; h <= k; h++) {
f[i][h] = mp[h].get(nums[i]) || 0;
if (h > 0) {
if (g[h - 1][0] !== nums[i]) {
f[i][h] = Math.max(f[i][h], g[h - 1][1]);
} else {
f[i][h] = Math.max(f[i][h], g[h - 1][2]);
}
}
f[i][h]++;
mp[h].set(nums[i], Math.max(mp[h].get(nums[i]) || 0, f[i][h]));
if (g[h][0] !== nums[i]) {
if (f[i][h] >= g[h][1]) {
g[h][2] = g[h][1];
g[h][1] = f[i][h];
g[h][0] = nums[i];
} else {
g[h][2] = Math.max(g[h][2], f[i][h]);
}
} else {
g[h][1] = Math.max(g[h][1], f[i][h]);
}
ans = Math.max(ans, f[i][h]);
}
}
return ans;
}func maximumLength(nums []int, k int) int {
n := len(nums)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, k+1)
}
mp := make([]map[int]int, k+1)
for i := range mp {
mp[i] = make(map[int]int)
}
g := make([][3]int, k+1)
ans := 0
for i := 0; i < n; i++ {
for h := 0; h <= k; h++ {
f[i][h] = mp[h][nums[i]]
if h > 0 {
if g[h-1][0] != nums[i] {
if g[h-1][1] > f[i][h] {
f[i][h] = g[h-1][1]
}
} else {
if g[h-1][2] > f[i][h] {
f[i][h] = g[h-1][2]
}
}
}
f[i][h]++
if f[i][h] > mp[h][nums[i]] {
mp[h][nums[i]] = f[i][h]
}
if g[h][0] != nums[i] {
if f[i][h] >= g[h][1] {
g[h][2] = g[h][1]
g[h][1] = f[i][h]
g[h][0] = nums[i]
} else if f[i][h] > g[h][2] {
g[h][2] = f[i][h]
}
} else {
if f[i][h] > g[h][1] {
g[h][1] = f[i][h]
}
}
if f[i][h] > ans {
ans = f[i][h]
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: |
| Greedy Approach with Frequency Count | Time Complexity: |
| Dynamic Programming | – |
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 |
Frequently asked questions
Is Find the Maximum Length of a Good Subsequence II easy or hard?
The problem is rated Hard because it requires designing a multi-dimensional dynamic programming state and optimizing transitions efficiently. Handling subsequences rather than contiguous segments makes the reasoning more complex than typical sliding window problems.
Find the Maximum Length of a Good Subsequence II Python/Java solution
Most solutions iterate through the array and update dynamic programming states. Python implementations typically use dictionaries for dp[value][changes], while Java versions use HashMap structures or arrays when the value range is small. Both achieve O(nk) time complexity.
How to solve Find the Maximum Length of a Good Subsequence II in O(n)?
A linear-time heuristic uses a sliding window with frequency counting. Maintain a window, track element frequencies with a hash table, and keep the window valid while the number of differing elements stays within k. Each element enters and leaves the window at most once, giving O(n) time.
What is the best approach for Find the Maximum Length of a Good Subsequence II?
The most reliable approach uses dynamic programming. Track the longest subsequence ending with each value while counting how many value transitions have been used. The DP state dp[value][changes] is updated while scanning the array, giving an O(nk) time solution that handles arbitrary value distributions.
Is Find the Maximum Length of a Good Subsequence II asked at Google/Amazon/Meta?
Problems involving subsequence dynamic programming and transition counting appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test DP state design, hash map optimization, and reasoning about sequence transitions.
What data structure is used in Find the Maximum Length of a Good Subsequence II?
Common implementations use hash tables to store subsequence states by value and dynamic programming arrays indexed by transition count. Sliding window approaches also rely on hash maps to track element frequencies inside the current window.
What is the time complexity of Find the Maximum Length of a Good Subsequence II?
The optimal dynamic programming solution runs in O(nk) time where n is the array length and k is the maximum allowed number of value changes. Each element updates states for all transition counts from 0 to k. Space complexity is also O(nk) when storing subsequence lengths for each value and transition level.