We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Length of a Good Subsequence II

Number: 3452

Difficulty: Hard

Paid? No

Companies: Snowflake

Problem Description

Given an integer array nums and a non‐negative integer k, a subsequence is called good if there are at most k positions i (0 ≤ i < (subsequence length) - 1) where the adjacent elements differ. In other words, after “compressing” consecutive equal numbers, the subsequence has at most k+1 constant blocks. The goal is to determine the maximum possible length of a good subsequence of nums.

Key Insights

  • A “good” subsequence may change its value at most k times. Equivalently, it is composed of at most k+1 blocks of equal numbers.
  • Picking many occurrences of the same number (even if they are not consecutive in the original array) does not incur extra cost as long as these picks form one block.
  • When switching from one block (value) to another, you must account for the transition; therefore, there is a tradeoff between taking more occurrences in the current block and preserving a later “window” for additional blocks.
  • An effective strategy is to “group” the occurrences of each distinct number (recording their indices) so that when forming a block you can choose a contiguous segment (by order) of that list. The last element chosen from the block fixes the earliest position from which the following block can be chosen.
  • A dynamic programming approach can be defined on the state (last_index, blocks_remaining) where last_index is the most recent index chosen (with –1 initially) and blocks_remaining is at most k+1.

Space and Time Complexity

Time Complexity: O(n * (k+1) * U * L) in the worst case, where U is the number of distinct values (which can be up to O(n)) and L is the average number of occurrences per distinct number. In practice, binary search and skipping duplicate starting values help reduce the constant factors. Space Complexity: O(n * k) for the memoization table plus O(n) for storing the occurrence lists.

Solution

We use a top‐down dynamic programming approach with memoization. The key observation is that a good subsequence is formed by at most k+1 blocks of constant numbers. For each block, we choose a distinct value v from the remaining part of the array and then decide how many occurrences (a contiguous “prefix” of the occurrence list of v that lie after the last chosen index) to include in the block. The last occurrence chosen in that block sets the earliest position for the next block. We iterate over choices for v (skipping duplicates) and, for each, explore all possible block “lengths”. The final answer is given by dp(–1, k+1).

The data structures used are:

  • A hash table (dictionary) mapping each distinct value in nums to its sorted list of indices.
  • A memoization dictionary caching states defined by (last_index, blocks_remaining).

The algorithm iterates over possible next picks (using binary search on the occurrence list for each chosen value) and combines the best result. The “gotcha” here is to remember that choosing too many occurrences in a block may push the last chosen index too far to allow many picks from future blocks. Hence, we consider every possible ending within a block.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with comments explaining key steps.

# Python solution using recursion with memoization and binary search.
from bisect import bisect_left
from collections import defaultdict
import sys
sys.setrecursionlimit(10000)

def max_good_subseq_length(nums, k):
    n = len(nums)
    # Build a dictionary mapping each number to a sorted list of its indices.
    occ = defaultdict(list)
    for index, num in enumerate(nums):
        occ[num].append(index)
    
    memo = {}
    
    # dp(last_index, blocks_remaining) returns the maximum additional picks
    # possible from indices > last_index using up to blocks_remaining blocks.
    def dp(last_index, blocks_remaining):
        # Base case: no block allowed or no further indices available.
        if blocks_remaining == 0:
            return 0
        # If last_index is already at the end, no further picks can be made.
        if last_index >= n - 1:
            return 0
        # Use memoized result if available.
        if (last_index, blocks_remaining) in memo:
            return memo[(last_index, blocks_remaining)]
        
        best = 0
        used = set()  # To avoid processing the same value twice at the same state.
        # Iterate through indices greater than last_index to consider starting a new block.
        for i in range(last_index + 1, n):
            v = nums[i]
            if v in used:
                continue
            used.add(v)
            occ_list = occ[v]
            # Find the starting position in occ_list where indices are > last_index.
            pos = bisect_left(occ_list, last_index + 1)
            # Try all possible contiguous segments from the occurence list.
            for end_idx in range(pos, len(occ_list)):
                count = end_idx - pos + 1  # Number of elements taken in this block.
                new_last = occ_list[end_idx]  # This becomes the last picked index.
                candidate = count + dp(new_last, blocks_remaining - 1)
                if candidate > best:
                    best = candidate
        memo[(last_index, blocks_remaining)] = best
        return best
    
    return dp(-1, k + 1)

# Example usage:
#print(max_good_subseq_length([1,2,1,1,3], 2))  # Expected output: 4
#print(max_good_subseq_length([1,2,3,4,5,1], 0))  # Expected output: 2
← Back to All Questions