Find the Maximum Length of a Good Subsequence II

Hard

#2822Time: O(N² * K), where N is the length of `nums`. There are three nested loops: iterating through `i` from `0` to `N-1`, `p` from `0` to `i-1`, and `j` from `0` to `K`.Space: O(N * K), for the 2D DP table of size `n x (k+1)`.1 company

Patterns

Dynamic Programming

Data structures

Array Hash Table

Companies

Snowflake

Prompt

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 * 10³
1 <= nums[i] <= 10⁹
0 <= k <= min(50, nums.length)

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a straightforward dynamic programming solution. We define a 2D DP table, dp[i][j], to store the maximum length of a good subsequence ending at index i with exactly j "breaks" (where adjacent elements are different). To compute the value for dp[i][j], we iterate through all previous elements nums[p] (where p < i) and consider extending the subsequences ending at p.

Algorithm

Create a 2D DP table dp[n][k+1], where dp[i][j] stores the maximum length of a good subsequence ending at index i with exactly j breaks.
Initialize a variable maxLength to 1, as any single element is a valid subsequence of length 1.
Iterate through each element nums[i] from i = 0 to n-1.
For each nums[i], initialize dp[i][0] = 1 (a subsequence with just nums[i] has length 1 and 0 breaks).
Iterate through all previous elements nums[p] where p < i.
If nums[p] == nums[i], we can extend a subsequence ending at p without adding a break. For each j from 0 to k, update dp[i][j] = max(dp[i][j], dp[p][j] + 1).
If nums[p] != nums[i], we introduce a new break. For each j from 1 to k, we can extend a subsequence that ended at p with j-1 breaks. Update dp[i][j] = max(dp[i][j], dp[p][j-1] + 1).
After filling the dp table, the answer is the maximum value found in the entire dp table, as the subsequence can end at any index with any number of breaks up to k.

Walkthrough

In this method, we define dp[i][j] as the maximum length of a good subsequence of nums[0...i] that ends with nums[i] and has exactly j breaks. A break occurs when an element is different from the previous one in the subsequence.

To compute dp[i][j], we look at all possible preceding elements nums[p] (where p < i) in the subsequence. Two cases arise:

nums[p] == nums[i]: If we append nums[i] to a subsequence ending in nums[p], the number of breaks does not change. Thus, we can extend any subsequence that ended at p with j breaks. The new length would be dp[p][j] + 1.
nums[p] != nums[i]: If we append nums[i] to a subsequence ending in nums[p], a new break is introduced. This means the subsequence ending at p must have had j-1 breaks. The new length would be dp[p][j-1] + 1.

The base case is that any single element nums[i] forms a subsequence of length 1 with 0 breaks. The final answer is the maximum value across the entire dp table, since the optimal subsequence can end at any index i and use any number of breaks j from 0 to k.

1class Solution {2    public int maximumLength(int[] nums, int k) {3        int n = nums.length;4        if (n == 0) return 0;5        6        // dp[i][j]: max length of a good subsequence ending at index i with j breaks.7        int[][] dp = new int[n][k + 1];8        int maxLength = 0;9 10        for (int i = 0; i < n; i++) {11            // A subsequence with only nums[i] has length 1 and 0 breaks.12            dp[i][0] = 1;13            14            for (int p = 0; p < i; p++) {15                if (nums[p] == nums[i]) {16                    // Same element, no new break.17                    for (int j = 0; j <= k; j++) {18                        if (dp[p][j] > 0) {19                            dp[i][j] = Math.max(dp[i][j], dp[p][j] + 1);20                        }21                    }22                } else {23                    // Different element, one new break.24                    for (int j = 1; j <= k; j++) {25                        if (dp[p][j - 1] > 0) {26                            dp[i][j] = Math.max(dp[i][j], dp[p][j - 1] + 1);27                        }28                    }29                }30            }31        }32 33        for (int i = 0; i < n; i++) {34            for (int j = 0; j <= k; j++) {35                maxLength = Math.max(maxLength, dp[i][j]);36            }37        }38        39        return maxLength;40    }41}

Complexity

Time

O(N² * K), where N is the length of `nums`. There are three nested loops: iterating through `i` from `0` to `N-1`, `p` from `0` to `i-1`, and `j` from `0` to `K`.

Space

O(N * K), for the 2D DP table of size `n x (k+1)`.

Trade-offs

Pros

The logic is a direct translation of the problem definition into a DP state, making it relatively easy to understand.

Cons

The time complexity of O(N² * K) is too high for the given constraints, leading to a Time Limit Exceeded (TLE) error.

This approach significantly optimizes the naive DP solution by eliminating the innermost loop. Instead of re-scanning all previous elements for each state, we maintain auxiliary data structures that store the necessary maximum lengths. This allows us to compute the DP transitions in constant time (on average), reducing the overall time complexity.

Algorithm

Initialize two main data structures:
- maxLenForVal: An array of k+1 HashMaps. maxLenForVal[j] will map a number v to the maximum length of a subsequence ending with v using j breaks.
- maxLenOverall: An array of size k+1. maxLenOverall[j] will store the overall maximum length of any subsequence with j breaks, irrespective of the ending value.
Initialize ans = 0.
Iterate through each num in the input array nums.
For each num, iterate j from k down to 0. This downward iteration is crucial to ensure we use the state from before processing the current num.
Inside the loop, calculate the maximum length of a subsequence ending with num and j breaks. This is the maximum of two possibilities:
1. Extending a subsequence ending with the same number num: 1 + maxLenForVal[j].getOrDefault(num, 0).
2. Extending a subsequence ending with a different number (creating a break): 1 + maxLenOverall[j-1] (only if j > 0).
Let this new length be currentMaxLen.
Update the state for subsequent elements: maxLenForVal[j].put(num, currentMaxLen) and maxLenOverall[j] = max(maxLenOverall[j], currentMaxLen).
Update the overall answer: ans = max(ans, currentMaxLen).
After iterating through all numbers, ans will hold the result.

Walkthrough

The key observation for optimization is that to calculate the max length of a subsequence ending with nums[i] and j breaks, we only need two pieces of information from the state before processing nums[i]:

The max length of a subsequence ending with the same value nums[i] using j breaks.
The max length of any subsequence using j-1 breaks (to which we can append nums[i] to create a new break).

We can maintain these values as we iterate through nums. We use an array of HashMaps, maxLenForVal, to track the first piece of information, and a simple array, maxLenOverall, for the second. For each element num in nums, we calculate the best possible lengths for subsequences ending with num for all possible break counts j. Then, we use these new lengths to update our two tracking structures.

By iterating j from k down to 0, we cleverly use the maxLenOverall values from the state before processing the current num, avoiding the need for a temporary array to store intermediate results for the current element.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maximumLength(int[] nums, int k) {6        int n = nums.length;7        int ans = 0;8 9        // maxLenForVal[j] is a map from value -> maxLength for a subsequence with j breaks10        Map<Integer, Integer>[] maxLenForVal = new HashMap[k + 1];11        for (int i = 0; i <= k; i++) {12            maxLenForVal[i] = new HashMap<>();13        }14 15        // maxLenOverall[j] is the max length of any subsequence with j breaks16        int[] maxLenOverall = new int[k + 1];17 18        for (int num : nums) {19            for (int j = k; j >= 0; j--) {20                // Case 1: The previous element in the subsequence is the same as num.21                // The number of breaks remains j.22                int lenSame = 1 + maxLenForVal[j].getOrDefault(num, 0);23 24                // Case 2: The previous element is different from num.25                // This introduces a new break, so the previous subsequence had j-1 breaks.26                int lenDiff = 1;27                if (j > 0) {28                    lenDiff = 1 + maxLenOverall[j - 1];29                }30 31                // The max length for a subsequence ending with num and having j breaks32                int currentMaxLen = Math.max(lenSame, lenDiff);33 34                // Update the states for the next element35                maxLenForVal[j].put(num, currentMaxLen);36                maxLenOverall[j] = Math.max(maxLenOverall[j], currentMaxLen);37                38                ans = Math.max(ans, currentMaxLen);39            }40        }41        return ans;42    }43}

Complexity

Time

O(N * K), where N is the length of `nums`. We have a loop through `nums` (N iterations) and a nested loop for `k` (K iterations). The map operations inside take, on average, O(1) time.

Space

O(D * K), where D is the number of distinct elements in `nums`. In the worst case, D can be up to N, making the space complexity O(N * K).

Trade-offs

Pros

Highly efficient with a time complexity of O(N * K), which passes the given constraints.
Effectively solves the problem by optimizing the DP state transitions.

Cons

The space complexity can be high, up to O(D * K) where D is the number of distinct elements, which can be O(N * K) in the worst case.
The logic is more complex than the naive DP approach, involving multiple data structures and a specific loop order.

Solutions

Solution

1class Solution {2public3  int maximumLength(int[] nums, int k) {4    int n = nums.length;5    int[][] f = new int[n][k + 1];6    Map<Integer, Integer>[] mp = new HashMap[k + 1];7    Arrays.setAll(mp, i->new HashMap<>());8    int[][] g = new int[k + 1][3];9    int ans = 0;10    for (int i = 0; i < n; ++i) {11      for (int h = 0; h <= k; ++h) {12        f[i][h] = mp[h].getOrDefault(nums[i], 0);13        if (h > 0) {14          if (g[h - 1][0] != nums[i]) {15            f[i][h] = Math.max(f[i][h], g[h - 1][1]);16          } else {17            f[i][h] = Math.max(f[i][h], g[h - 1][2]);18          }19        }20        ++f[i][h];21        mp[h].merge(nums[i], f[i][h], Integer : : max);22        if (g[h][0] != nums[i]) {23          if (f[i][h] >= g[h][1]) {24            g[h][2] = g[h][1];25            g[h][1] = f[i][h];26            g[h][0] = nums[i];27          } else {28            g[h][2] = Math.max(g[h][2], f[i][h]);29          }30        } else {31          g[h][1] = Math.max(g[h][1], f[i][h]);32        }33        ans = Math.max(ans, f[i][h]);34      }35    }36    return ans;37  }38}

1class Solution {2public:3  int maximumLength(vector<int> &nums, int k) {4    int n = nums.size();5    vector<vector<int>> f(n, vector<int>(k + 1));6    vector<unordered_map<int, int>> mp(k + 1);7    vector<vector<int>> g(k + 1, vector<int>(3));8    int ans = 0;9    for (int i = 0; i < n; ++i) {10      for (int h = 0; h <= k; ++h) {11        f[i][h] = mp[h][nums[i]];12        if (h > 0) {13          if (g[h - 1][0] != nums[i]) {14            f[i][h] = max(f[i][h], g[h - 1][1]);15          } else {16            f[i][h] = max(f[i][h], g[h - 1][2]);17          }18        }19        ++f[i][h];20        mp[h][nums[i]] = max(mp[h][nums[i]], f[i][h]);21        if (g[h][0] != nums[i]) {22          if (f[i][h] >= g[h][1]) {23            g[h][2] = g[h][1];24            g[h][1] = f[i][h];25            g[h][0] = nums[i];26          } else {27            g[h][2] = max(g[h][2], f[i][h]);28          }29        } else {30          g[h][1] = max(g[h][1], f[i][h]);31        }32        ans = max(ans, f[i][h]);33      }34    }35    return ans;36  }37};

1class Solution:2    def maximumLength(self, nums: List[int], k: int) -> int: n = len(nums) f = [[0] * (k + 1) for _ in range(n)] mp = [defaultdict(int) for _ in range(k + 1)] g = [[0] * 3 for _ in range(k + 1)] ans = 0 for i, x in enumerate(nums): for h in range(k + 1): f[i][h] = mp[h][x] if h: if g[h - 1][0] != nums[i]: f[i][h] = max(f[i][h], g[h - 1][1]) else: f[i][h] = max(f[i][h], g[h - 1][2]) f[i][h] += 1 mp[h][nums[i]] = max(mp[h][nums[i]], f[i][h]) if g[h][0] != x: if f[i][h] >= g[h][1]: g[h][2] = g[h][1] g[h][1] = f[i][h] g[h][0] = x else: g[h][2] = max(g[h][2], f[i][h]) else: g[h][1] = max(g[h][1], f[i][h]) ans = max(ans, f[i][h]) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem