#3202

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Find the Maximum Length of Valid Subsequence II

Determine the maximum length of a valid subsequence using state transition dynamic programming with careful modulo constraints.

array dynamic programming

Problem Statement

Given an integer array nums and an integer k, a subsequence sub of nums is called valid if the sum of any two consecutive elements modulo k is consistent throughout the subsequence. Your task is to compute the length of the longest valid subsequence following this rule.

Return an integer representing the maximum possible length of a valid subsequence. A subsequence does not need to be contiguous but must preserve the order of elements from nums. Constraints: 2 <= nums.length <= 103, 1 <= nums[i] <= 107, 1 <= k <= 103.

Examples

Example 1

Input: nums = [1,2,3,4,5], k = 2

Output: 5

The longest valid subsequence is [1, 2, 3, 4, 5] .

Example 2

Input: nums = [1,4,2,3,1,4], k = 3

Output: 4

The longest valid subsequence is [1, 4, 1, 4] .

Constraints

2 <= nums.length <= 103
1 <= nums[i] <= 107
1 <= k <= 103

Solution Approach

Fix Initial Modulo State

Select the first pair of elements and compute their sum modulo k. Treat this value as a fixed target for the subsequence. This reduces the DP state space and ensures all future transitions only consider valid modulo sums.

Dynamic Programming Table

Construct a DP table where dp[i][val] stores the length of the longest valid subsequence ending at index i with modulo value val. Iterate through nums, updating dp[i][val] by extending previous valid subsequences that satisfy the modulo constraint.

State Transition Updates

For each element, evaluate if appending it to a previous subsequence maintains the fixed modulo sum. Update the DP state accordingly and track the maximum length seen. This ensures optimal subsequence length while respecting the modulo condition.

Complexity Analysis

Metric	Value
Time	O(n \times k)
Space	O(k^2)

Time complexity is O(n \times k) since each element is compared against k possible modulo states. Space complexity is O(k^2) to maintain DP tables for all modulo combinations efficiently.

What Interviewers Usually Probe

Are you considering the correct state space for DP transitions with modulo constraints?
Can you optimize memory usage by storing only necessary DP states?
Have you correctly handled the subsequence selection without breaking the original array order?

Common Pitfalls or Variants

Common pitfalls

Forgetting to fix the initial modulo value, which can lead to incorrect subsequence validation.
Incorrectly assuming contiguous subsequences instead of true subsequences preserving order.
Updating DP states without checking if the modulo constraint is maintained, causing invalid subsequences.

Follow-up variants

Find maximum length subsequence where the sum of every three consecutive elements modulo k is consistent.
Compute maximum length valid subsequence with alternating modulo conditions for even and odd indices.
Determine longest valid subsequence when elements must satisfy a sum modulo constraint with a moving window of size 2.

FAQ

What is the primary DP pattern used in Find the Maximum Length of Valid Subsequence II?

The main pattern is state transition dynamic programming with a fixed modulo value to track valid subsequences.

Do subsequences need to be contiguous in this problem?

No, valid subsequences can skip elements but must preserve the original order of nums.

How does fixing the initial modulo value help?

It reduces the DP state space by setting a target modulo sum, ensuring all transitions maintain validity.

What is the expected time complexity for large nums arrays?

Time complexity is O(n \times k), where n is the array length and k is the modulo constraint.

Can GhostInterview show intermediate subsequence states?

Yes, it visualizes DP updates and highlights subsequence extensions that respect the modulo rule.

terminal

Solution

Solution 1: Dynamic Programming

Based on the problem description, we know that for a subsequence $a_1, a_2, a_3, \cdots, a_x$, if it satisfies $(a_1 + a_2) \bmod k = (a_2 + a_3) \bmod k$, then $a_1 \bmod k = a_3 \bmod k$. This means that the result of taking modulo $k$ for all odd-indexed elements is the same, and the result for all even-indexed elements is the same as well.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        f = [[0] * k for _ in range(k)]
        ans = 0
        for x in nums:
            x %= k
            for j in range(k):
                y = (j - x + k) % k
                f[x][y] = f[y][x] + 1
                ans = max(ans, f[x][y])
        return ans

Continue Practicing

#3201 find the maximum length of valid subsequence i #3196 maximize total cost of alternating subarrays #3193 count the number of inversions