LeetCode 3202 - Find the Maximum Length of Valid Subsequence II

This problem asks us to find the length of the longest subsequence in an array nums such that for every consecutive pair of elements in the subsequence, the sum of the pair modulo k is the same. In other words, if we denote a valid subsequence as sub = [a1, a2, ...

leetcodemediumarraydynamic-programming

LeetCode Problem 3202

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem asks us to find the length of the longest subsequence in an array nums such that for every consecutive pair of elements in the subsequence, the sum of the pair modulo k is the same. In other words, if we denote a valid subsequence as sub = [a1, a2, ..., ax], it must satisfy (a1 + a2) % k == (a2 + a3) % k == ... == (a[x-2] + a[x-1]) % k.

The input consists of an integer array nums and a positive integer k. We are guaranteed that nums has at least two elements and all numbers are positive integers. The output is a single integer representing the maximum length of a valid subsequence.

Constraints indicate that nums has at most 1000 elements and k is at most 1000. This tells us that a naive approach examining all subsequences would be too slow, since the number of subsequences grows exponentially with the array length. Edge cases include arrays where no two elements satisfy the modulo condition and cases where all elements are identical or alternating patterns that allow a long valid subsequence.

Approaches

The brute-force approach is to generate all possible subsequences of nums and check for each subsequence if it satisfies the modulo condition. This guarantees correctness because it examines every possible candidate, but it is computationally infeasible due to its exponential time complexity, approximately O(2^n * n) because checking each subsequence takes linear time in its length.

The key observation for an optimal solution is that the condition (sub[i] + sub[i+1]) % k == c is local and accumulative. If we know the longest valid subsequence ending with a particular modulo sum c, we can extend it efficiently by considering each number in order. We can maintain a dictionary mapping each modulo sum c to the longest subsequence length ending with that sum. For each number, we compute potential extensions for all c and update the mapping dynamically. This transforms the problem into a dynamic programming problem with states determined by c.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Generates all subsequences and checks modulo condition
Optimal O(n * k) O(k) Uses dynamic programming by tracking longest subsequence for each modulo sum

Algorithm Walkthrough

  1. Initialize a dictionary dp where dp[c] represents the maximum length of a valid subsequence ending with a pair sum modulo k equal to c. Initially, it is empty.
  2. Iterate through each element num in nums.
  3. For the current number, create a new dictionary next_dp to store updates without affecting the current iteration.
  4. For every modulo sum c currently in dp, check if adding num can extend the subsequence corresponding to c. This requires computing num + prev_num % k == c. Update next_dp[c] accordingly.
  5. Independently, consider num as starting a new subsequence of length 1, and update next_dp for new modulo sums (num + num) % k.
  6. Merge next_dp into dp, keeping the maximum length for each modulo sum.
  7. After processing all numbers, return the maximum value in dp as the answer.

The invariant is that at every step, dp[c] always stores the length of the longest valid subsequence ending with modulo sum c. This guarantees correctness because we never lose the optimal solution for any modulo sum.

Python Solution

from typing import List

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        dp = dict()  # dp[c] = max length of subsequence with pair sum % k == c
        for num in nums:
            next_dp = dp.copy()
            # Extend existing subsequences
            for c, length in dp.items():
                next_c = (c + num) % k
                next_dp[next_c] = max(next_dp.get(next_c, 0), length + 1)
            # Start a new subsequence with current number
            self_c = (num * 2) % k
            next_dp[self_c] = max(next_dp.get(self_c, 0), 1)
            dp = next_dp
        return max(dp.values())

This code initializes a dynamic programming dictionary to track subsequences. For each number, it considers extending existing subsequences or starting new ones. The maximum length is returned at the end. The dictionary dp ensures efficient updates and prevents unnecessary recomputation.

Go Solution

func maximumLength(nums []int, k int) int {
    dp := make(map[int]int)
    for _, num := range nums {
        nextDP := make(map[int]int)
        for c, length := range dp {
            nextC := (c + num) % k
            if nextDP[nextC] < length + 1 {
                nextDP[nextC] = length + 1
            }
        }
        selfC := (num * 2) % k
        if nextDP[selfC] < 1 {
            nextDP[selfC] = 1
        }
        for key, val := range dp {
            if nextDP[key] < val {
                nextDP[key] = val
            }
        }
        dp = nextDP
    }
    maxLen := 0
    for _, val := range dp {
        if val > maxLen {
            maxLen = val
        }
    }
    return maxLen
}

In Go, maps are used similarly to Python dictionaries. Care is taken to update nextDP without modifying dp during iteration. Integer overflow is not an issue due to the problem constraints, and slices are traversed sequentially.

Worked Examples

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

Iteration dp (mod k -> length)
1 {0:1}
2 {0:2, 1:1}
3 {0:3, 1:2}
4 {0:4, 1:3}
5 {0:5, 1:4}

Maximum length = 5

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

Iteration dp (mod k -> length)
1 {2:1}
2 {2:2, 2:1}
3 {2:3, 0:1}
4 {2:3, 0:2}
5 {2:4, 0:2}
6 {2:4, 1:3}

Maximum length = 4

Complexity Analysis

Measure Complexity Explanation
Time O(n * k) For each number, we iterate over at most k modulo sums in dp
Space O(k) Dictionary stores at most k entries corresponding to modulo sums

This complexity is acceptable given the constraints (n and k ≤ 1000).

Test Cases

# Provided examples
assert Solution().maximumLength([1,2,3,4,5], 2) == 5  # longest valid subsequence is the whole array
assert Solution().maximumLength([1,4,2,3,1,4], 3) == 4  # valid subsequence is [1,4,1,4]

# Boundary tests
assert Solution().maximumLength([1,1], 1) == 2  # smallest array
assert Solution().maximumLength([1,2], 3) == 2  # any two numbers form valid subsequence
assert Solution().maximumLength([1], 1) == 1  # single element

# Stress test
assert Solution().maximumLength(list(range(1,1001)), 1000) > 0  # long array with large k
Test Why
[1,2,3,4,5], k=2 Valid subsequence covers the entire array
[1,4,2,3,1,4], k=3 Valid subsequence picks selective elements to satisfy modulo condition
[1,1], k=1 Smallest array, minimum valid subsequence
[1,2], k=3 Any two elements always valid
[1..1000], k=1000 Tests performance with maximum input size

Edge Cases

The first edge case is when all elements in nums are identical. In this situation, every pair will satisfy the modulo condition automatically, and the maximum length should be the length of the entire array. This is correctly handled because each number starts a new subsequence, and the dp updates correctly extend the length.

The second edge case is when nums contains alternating numbers that satisfy different modulo sums. The algorithm correctly tracks multiple modulo sums simultaneously, ensuring it can pick the optimal subsequence across different sums without losing information.

The third edge case is when k is very large compared to the numbers in nums. Here, some modulo sums may never appear in the sequence. The algorithm handles this