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 Valid Subsequence II

Number: 3491

Difficulty: Medium

Paid? No

Companies: Meta, Google

Problem Description

Given an integer array nums and a positive integer k, find the length of the longest subsequence of nums that is “valid”. A subsequence sub (of length x) is valid if for every pair of consecutive elements in sub, the value of (sub[i] + sub[i+1]) % k is the same for every i from 0 to x-2.

Key Insights

  • The “validity” of a subsequence is determined entirely by the constant modulo (r) derived from the sum of its first two elements.
  • A single element subsequence is trivially valid (since there is no pair to impose a condition).
  • When building a valid subsequence, once a modulo value r is established, every new element must satisfy (last_element + new_element) % k == r.
  • We can employ dynamic programming by maintaining, for each index, possible chains ending there with a fixed modulo value r.
  • For any two indices i and j (with i < j), a pair (nums[i], nums[j]) gives a potential starting chain with r = (nums[i] + nums[j]) % k. This chain can be extended if a later element satisfies the same pair condition.

Space and Time Complexity

Time Complexity: O(n²) – We iterate through pairs of indices. Space Complexity: O(n * k) – In worst-case each index may store up to k possible modulo values in its DP dictionary.

Solution

We solve the problem using a dynamic programming approach. For each index, we maintain a mapping (dictionary) which stores the length of the longest valid subsequence ending at that index for each possible modulo value r. When processing a pair (i, j) where i < j, calculate r = (nums[i] + nums[j]) % k. Then, if there already exists a chain ending at i with modulo r, extend that chain by including nums[j]. Otherwise, start a new chain from nums[i] and nums[j] with length 2. Finally, the answer is the maximum chain length found over all indices and modulo values, with the fallback that a single element is always valid (length 1) if no chain of length 2 or more exists.

Code Solutions

# Python solution for the problem

def maxValidSubsequenceLength(nums, k):
    n = len(nums)
    # dp[i] is a dictionary: key is modulo r, value is longest chain ending at i with that constant.
    dp = [dict() for _ in range(n)]
    max_len = 1  # a single element is always valid
    # Iterate over all pairs to initialize and update chains
    for j in range(n):
        for l in range(j+1, n):
            r = (nums[j] + nums[l]) % k  # constant modulo value for the chain
            # If there's already a chain ending at j with modulo r, extend it
            curr_len = dp[j].get(r, 0) + 1 if r in dp[j] else 2
            # Update the chain ending at index l with modulo r
            dp[l][r] = max(dp[l].get(r, 0), curr_len)
            max_len = max(max_len, dp[l][r])
    return max_len

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