Facebook Pixel

3177. Find the Maximum Length of a Good Subsequence II

HardArrayHash TableDynamic Programming
Leetcode Link

Problem Description

You are given an integer array nums and a non-negative integer k. A sequence of integers seq is considered "good" if there are at most k indices i in the range [0, seq.length - 2] where seq[i] != seq[i + 1]. The task is to return the maximum possible length of a "good" subsequence of nums.

Intuition

To tackle this problem, we use dynamic programming. Our goal is to find the longest subsequence of nums such that there are at most k pairs of consecutive elements that are different.

Let's define f[i][h] as the length of the longest good subsequence ending at the i-th position with at most h transitions (where transitions are defined as indices where consecutive elements differ). Initially, f[i][h] is set to 1, representing the subsequence containing only nums[i].

Key Steps:

  • For each element nums[i], we consider all preceding elements nums[j] (where j < i).
  • If nums[i] == nums[j], this means no new transition is added, and we can extend the subsequence ending at j to include nums[i]. Thus, f[i][h] = max(f[i][h], f[j][h] + 1).
  • If nums[i] != nums[j] and we still have the allowance to add a transition (h > 0), we can extend the subsequence ending at j while incrementing the transition count, i.e., f[i][h] = max(f[i][h], f[j][h - 1] + 1).
  • The answer will be the maximum value among all f[i][k], where 0 ≤ i < n.

Optimization:

  • Direct computation with nested loops would be inefficient due to time complexity O(n^2 * k).
  • To optimize, we maintain arrays mp for remembering maximum values of subsequence lengths and g, an additional data structure, for efficiently keeping track of transitions and lengths.
  • By using these structures, we can efficiently update and query maximum values needed for our state transitions.

The solution thus efficiently computes the desired longest good subsequence by leveraging dynamic programming optimized with auxiliary arrays.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution involves a dynamic programming approach combined with specific data structures to manage state transitions efficiently. Let's walk through the implementation:

  1. Initial Setup:

    • We initialize a 2D list f where f[i][h] represents the length of the longest good subsequence ending at nums[i] with at most h transitions.
    • We also maintain a list of dictionaries mp, where mp[h][x] keeps track of the maximum subsequence length for the value x with at most h transitions.

  2. Transition Management with G:

    • An additional list g is utilized where g[h] stores three values:
      • g[h][0]: the last value processed for the given transition count h.
      • g[h][1]: the length of the longest subsequence for the above value.
      • g[h][2]: the second longest subsequence length if the current g[h][0] is the same as a previous value when updating g[h][1].

  3. Iterating Over Each Element:

    • For each element nums[i], iterate through every transition count h from 0 to k.
    • Compute f[i][h] using previously recorded values:
      • Start with f[i][h] = mp[h][nums[i]].
      • If h > 0, calculate possible transitions using g:
        • If nums[i] is not the same as g[h-1][0], consider g[h-1][1].
        • If it is the same, use g[h-1][2].

  4. Updating State:

    • Add one to f[i][h] to include nums[i] in subsequence length.
    • Update mp[h][nums[i]] to possible new maximum.
    • Adjust g[h] to maintain highest and second highest subsequences correctly:
      • If nums[i] is different from g[h][0], update g[h][1] and g[h][2] accordingly.
      • If the same, directly update g[h][1].

  5. Final Calculation:

    • Throughout the process, track the highest value in f to determine the longest good subsequence.

Here’s the efficient computation using dynamic programming with memorization and tracking arrays, enabling the solution to scale for larger datasets:

class Solution:
    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

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let's walk through an example:

Example: Given nums = [1, 3, 2, 3, 4, 3] and k = 1, we aim to find the maximum possible length of a "good" subsequence.

  1. Initial Setup:

    • Prepare a 2D list f where f[i][h] is initialized with zeros.
    • Maintain dictionaries mp to store the maximum subsequence length for each value.

  2. Iterate Over Each Element:

    • First Element (1):
      • f[0][0] = 1 (Since it's the starting element, no transitions are required).
      • Update mp[0][1] to 1.
    • Second Element (3):
      • Calculate f[1][0] → Cannot increase subsequence without transition since 3 is not 1.
      • f[1][1] = mp[0][1] + 1 = 2 (Allowing a transition from 1 to 3).
      • Update mp[1][3] to 2.
    • Third Element (2):
      • f[2][0] = 1 (Starting new subsequence).
      • f[2][1] = 2 (Continuation from either 3 or 1 with a transition).
    • Fourth Element (3):
      • f[3][0] = 1 (Starting new subsequence).
      • f[3][1] = max(mp[0][3] + 1 (no new transition, but sequence starts), mp[1][2] + 1 (with transition from 2 to 3)) = 3.
      • Update mp[1][3] to 3.
    • Fifth Element (4):
      • f[4][0] = 1.
      • f[4][1] = 3 (Using mp[0][3] + 1).
    • Sixth Element (3):
      • f[5][0] = 1.
      • f[5][1] = max(mp[0][3] + 1, mp[1][4] + 1) = 4 (Transition from 4 to 3 allowed, including the maximum good sequence).

  3. Final Calculation:

    • The maximum found in f[i][k] is 4. Thus, the longest subsequence is of length 4.

Through this step-by-step breakdown, observe how dynamic programming combined with state management via mp and arrays allows efficient computation of the maximum length of a "good" subsequence.

Solution Implementation

1from typing import List
2from collections import defaultdict
3
4class Solution:
5    def maximumLength(self, nums: List[int], k: int) -> int:
6        n = len(nums)
7      
8        # Initialize a 2D list `f` to store the maximum length of subsequences 
9        # ending at each position i with up to h deletions
10        f = [[0] * (k + 1) for _ in range(n)]
11      
12        # Create a list of defaultdicts `mp` to track the longest subsequence length 
13        # ending with each number for up to h deletions
14        mp = [defaultdict(int) for _ in range(k + 1)]
15      
16        # Initialize a 2D list `g` to store auxiliary information needed for optimization
17        g = [[0] * 3 for _ in range(k + 1)]
18      
19        ans = 0 # This will hold the maximum subsequence length found
20      
21        # Iterate over each number in the list `nums`
22        for i, x in enumerate(nums):
23            # Check for each possible value of deletions h from 0 to k
24            for h in range(k + 1):
25                # Set f[i][h] to the current max found in mapping for this h and number x
26                f[i][h] = mp[h][x]
27              
28                # If we have more than 0 deletions allowed, we consider switching from previous best subsequences
29                if h:
30                    # If the best subsequence from the previous step ends with a different number
31                    if g[h - 1][0] != nums[i]:
32                        f[i][h] = max(f[i][h], g[h - 1][1])
33                    else:
34                        f[i][h] = max(f[i][h], g[h - 1][2])
35              
36                # Increase the length of the subsequence
37                f[i][h] += 1
38              
39                # Update the mapping `mp` with the new maximum subsequence length for this number and deletions
40                mp[h][nums[i]] = max(mp[h][nums[i]], f[i][h])
41              
42                # Update auxiliary array `g` with the maximum two sequence lengths ending with number x
43                if g[h][0] != x:
44                    if f[i][h] >= g[h][1]:
45                        g[h][2] = g[h][1]
46                        g[h][1] = f[i][h]
47                        g[h][0] = x
48                    else:
49                        g[h][2] = max(g[h][2], f[i][h])
50                else:
51                    g[h][1] = max(g[h][1], f[i][h])
52              
53                # Update the global answer
54                ans = max(ans, f[i][h])
55      
56        # Return the maximum subsequence length found
57        return ans
58
1class Solution {
2    public int maximumLength(int[] nums, int k) {
3        int n = nums.length;
4        // Dynamic programming table to store longest subarrays with different distinct counts
5        int[][] dp = new int[n][k + 1];
6
7        // Array of maps to track the frequency of numbers for each distinct count level
8        Map<Integer, Integer>[] frequencyMap = new HashMap[k + 1];
9        Arrays.setAll(frequencyMap, i -> new HashMap<>());
10
11        // Temporary array to store highest and second highest lengths of subarrays
12        int[][] subsequenceData = new int[k + 1][3];
13      
14        // Variable to store the maximum length found
15        int maxLength = 0;
16
17        for (int i = 0; i < n; ++i) {
18            for (int h = 0; h <= k; ++h) {
19                // Get the current longest length from the map for the current number and distinct level
20                dp[i][h] = frequencyMap[h].getOrDefault(nums[i], 0);
21
22                // Consider using one less distinct element by updating the longest length considering new addition
23                if (h > 0) {
24                    if (subsequenceData[h - 1][0] != nums[i]) {
25                        // Update if number is different from the last longest different number
26                        dp[i][h] = Math.max(dp[i][h], subsequenceData[h - 1][1]);
27                    } else {
28                        // Update if number is the same as the last longest different number
29                        dp[i][h] = Math.max(dp[i][h], subsequenceData[h - 1][2]);
30                    }
31                }
32              
33                // Increase current length by including current number
34                ++dp[i][h];
35
36                // Merge the current length into the frequency map for current distinct count
37                frequencyMap[h].merge(nums[i], dp[i][h], Integer::max);
38
39                // Update subsequenceData to have the longest and second longest lengths for each distinct number
40                if (subsequenceData[h][0] != nums[i]) {
41                    if (dp[i][h] >= subsequenceData[h][1]) {
42                        subsequenceData[h][2] = subsequenceData[h][1];
43                        subsequenceData[h][1] = dp[i][h];
44                        subsequenceData[h][0] = nums[i];
45                    } else {
46                        subsequenceData[h][2] = Math.max(subsequenceData[h][2], dp[i][h]);
47                    }
48                } else {
49                    subsequenceData[h][1] = Math.max(subsequenceData[h][1], dp[i][h]);
50                }
51
52                // Update the maximum length found
53                maxLength = Math.max(maxLength, dp[i][h]);
54            }
55        }
56        return maxLength;
57    }
58}
59
1class Solution {
2public:
3    int maximumLength(vector<int>& nums, int k) {
4        int n = nums.size();
5
6        // DP table of n x (k + 1), where f[i][h] keeps the maximum length of a subarray
7        // ending at index i with h allowed replacements.
8        vector<vector<int>> f(n, vector<int>(k + 1, 0));
9      
10        // A vector of hash maps, mp[h] keeps track of the maximum length of subarray with
11        // h replacements for each unique number encountered so far.
12        vector<unordered_map<int, int>> mp(k + 1);
13      
14        // Helper table g[h][j]: 
15        // - g[h][0] stores the number that currently has the maximum subarray length with h replacements.
16        // - g[h][1] stores the maximum subarray length with h replacements.
17        // - g[h][2] stores the second to the maximum subarray length.
18        vector<vector<int>> g(k + 1, vector<int>(3, 0));
19
20        int ans = 0;
21
22        // Iterate over each element in nums.
23        for (int i = 0; i < n; ++i) {
24            // Check for each number of replacements ranging from 0 to k.
25            for (int h = 0; h <= k; ++h) {
26                // Start with the best known length ending at 'i' for any identical elements seen so far.
27                f[i][h] = mp[h][nums[i]];
28
29                // If at least one replacement is permitted.
30                if (h > 0) {
31                    // Check if the current number is the same as the number with the max subarray.
32                    if (g[h - 1][0] != nums[i]) {
33                        // Choose the maximum length excluding the current number and proceed.
34                        f[i][h] = max(f[i][h], g[h - 1][1]);
35                    } else {
36                        // Otherwise, use the second max length subarray.
37                        f[i][h] = max(f[i][h], g[h - 1][2]);
38                    }
39                }
40
41                // Increment the subarray length by including nums[i].
42                ++f[i][h];
43
44                // Update the hash map with the best length found so far.
45                mp[h][nums[i]] = max(mp[h][nums[i]], f[i][h]);
46
47                // Update helper table g according to the replacement scenarios and lengths.
48                if (g[h][0] != nums[i]) {
49                    if (f[i][h] >= g[h][1]) {
50                        g[h][2] = g[h][1];
51                        g[h][1] = f[i][h];
52                        g[h][0] = nums[i];
53                    } else {
54                        g[h][2] = max(g[h][2], f[i][h]);
55                    }
56                } else {
57                    g[h][1] = max(g[h][1], f[i][h]);
58                }
59
60                // Update the overall maximum length found.
61                ans = max(ans, f[i][h]);
62            }
63        }
64
65        return ans;
66    }
67};
68
1// Find the maximum length of a subsequence of an array with at most 'k' distinct integers
2function maximumLength(nums: number[], k: number): number {
3    const n = nums.length; // Length of input array
4    // Create a 2D array 'f' to store maximum lengths at different positions and counts k
5    const f: number[][] = Array.from({ length: n }, () => Array(k + 1).fill(0));
6    // Create an array of Maps 'mp' to track frequency of elements for different distinct counts
7    const mp: Map<number, number>[] = Array.from({ length: k + 1 }, () => new Map());
8    // Create a 2D array 'g' to track top two maximum lengths and the element that gave max lengths
9    const g: number[][] = Array.from({ length: k + 1 }, () => Array(3).fill(0));
10  
11    let ans = 0; // This will hold the final result, maximum length found
12
13    // Traverse each element in the provided array
14    for (let i = 0; i < n; i++) {
15        // Traverse for each possible number of distinct integers we can have, from 0 to k
16        for (let h = 0; h <= k; h++) {
17            // Calculate maximum length of sequence ending at index 'i' with 'h' distinct elements
18            f[i][h] = mp[h].get(nums[i]) || 0;
19          
20            // If more than 0 distinct elements are allowed
21            if (h > 0) {
22                if (g[h - 1][0] !== nums[i]) {
23                    // If the most contributing element is not current, consider the second best
24                    f[i][h] = Math.max(f[i][h], g[h - 1][1]);
25                } else {
26                    // Consider the second-best when the element is the same as the most contributing
27                    f[i][h] = Math.max(f[i][h], g[h - 1][2]);
28                }
29            }
30          
31            // Increment the maximum subsequence length found at this step
32            f[i][h]++;
33          
34            // Update the frequency map with the calculated length
35            mp[h].set(nums[i], Math.max(mp[h].get(nums[i]) || 0, f[i][h]));
36          
37            // Update 'g' with the top two lengths for different distinct counts
38            if (g[h][0] !== nums[i]) {
39                if (f[i][h] >= g[h][1]) {
40                    g[h][2] = g[h][1];
41                    g[h][1] = f[i][h];
42                    g[h][0] = nums[i];
43                } else {
44                    g[h][2] = Math.max(g[h][2], f[i][h]);
45                }
46            } else {
47                g[h][1] = Math.max(g[h][1], f[i][h]);
48            }
49
50            // Update the overall maximum length
51            ans = Math.max(ans, f[i][h]);
52        }
53    }
54
55    // Return the maximum length found
56    return ans;
57}
58

Time and Space Complexity

The time complexity of the code can be analyzed by considering the two nested loops. The outer loop iterates over the list nums, which has a length of n, and the inner loop iterates k + 1 times. Therefore, the time complexity is O(n * (k + 1)), which simplifies to O(n * k).

The space complexity is determined by the auxiliary data structures used in the code: the 2D lists f and mp, along with the list g. The list f is of size n * (k + 1), and mp is a list of k + 1 dictionaries that could potentially grow large but are functionally bounded by the input. The list g has a fixed size of 3 * (k + 1). Therefore, the primary contributing factor is f, leading to a space complexity of O(n * k).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How does merge sort divide the problem into subproblems?

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More