3202. Find the Maximum Length of Valid Subsequence II LeetCode Solution

In this guide, you will get 3202. Find the Maximum Length of Valid Subsequence II LeetCode Solution with the best time and space complexity. The solution to Find the Maximum Length of Valid Subsequence II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find the Maximum Length of Valid Subsequence II solution in C++
Find the Maximum Length of Valid Subsequence II solution in Java
Find the Maximum Length of Valid Subsequence II solution in Python
Additional Resources

3202. Find the Maximum Length of Valid Subsequence II LeetCode Solution image

Problem Statement of Find the Maximum Length of Valid Subsequence II

You are given an integer array nums and a positive integer k.
A subsequence sub of nums with length x is called valid if it satisfies:

(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == … == (sub[x – 2] + sub[x – 1]) % k.

Return the length of the longest valid subsequence of nums.

Example 1:

Input: nums = [1,2,3,4,5], k = 2
Output: 5
Explanation:
The longest valid subsequence is [1, 2, 3, 4, 5].

Example 2:

Input: nums = [1,4,2,3,1,4], k = 3
Output: 4
Explanation:
The longest valid subsequence is [1, 4, 1, 4].

Constraints:

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

Complexity Analysis

Time Complexity: O(k^2 + nk)
Space Complexity: O(k^2)

3202. Find the Maximum Length of Valid Subsequence II LeetCode Solution in C++

class Solution {
 public:
  // Similar to 3201. Find the Maximum Length of Valid Subsequence I
  int maximumLength(vector<int>& nums, int k) {
    // dp[i][j] := the maximum length of a valid subsequence, where the last
    // number mod k equal to i and the next desired number mod k equal to j
    vector<vector<int>> dp(k, vector<int>(k));

    // Extend the pattern xyxyxy...xy.
    for (const int x : nums)
      for (int y = 0; y < k; ++y)
        dp[x % k][y] = dp[y][x % k] + 1;

    return accumulate(dp.begin(), dp.end(), 0,
                      [](int acc, const vector<int>& row) {
      return max(acc, ranges::max(row));
    });
  }
};
/* code provided by PROGIEZ */

3202. Find the Maximum Length of Valid Subsequence II LeetCode Solution in Java

class Solution {
  // Similar to 3201. Find the Maximum Length of Valid Subsequence I
  public int maximumLength(int[] nums, int k) {
    // dp[i][j] := the maximum length of a valid subsequence, where the last
    // number mod k equal to i and the next desired number mod k equal to j
    int[][] dp = new int[k][k];

    // Extend the pattern xyxyxy...xy.
    for (final int x : nums)
      for (int y = 0; y < k; ++y)
        dp[x % k][y] = dp[y][x % k] + 1;

    return Arrays.stream(dp).flatMapToInt(Arrays::stream).max().getAsInt();
  }
}
// code provided by PROGIEZ

3202. Find the Maximum Length of Valid Subsequence II LeetCode Solution in Python

class Solution:
  # Similar to 3201. Find the Maximum Length of Valid Subsequence I
  def maximumLength(self, nums: list[int], k: int) -> int:
    # dp[i][j] := the maximum length of a valid subsequence, where the last
    # number mod k equal to i and the next desired number mod k equal to j
    dp = [[0] * k for _ in range(k)]

    # Extend the pattern xyxyxy...xy.
    for x in nums:
      for y in range(k):
        dp[x % k][y] = dp[y][x % k] + 1

    return max(map(max, dp))
 # code by PROGIEZ