3202. Find the Maximum Length of Valid Subsequence II

Intuition

To solve the problem of finding the longest valid subsequence where consecutive pairs have equal sums modulo k, we can utilize a dynamic programming approach. The key insight is to maintain a mapping of remainder values modulo k to the length of subsequences that end with each remainder.

Approach

1. Initialization: Initialize a dictionary or array remainder_to_length to keep track of the maximum length of subsequences that end with each remainder modulo k.
2. Iterate through nums: For each number num in nums, calculate its remainder modulo k.
3. Update lengths: For each remainder, update remainder_to_length by considering adding num to subsequences ending with the previous remainder (curr_remainder + num) % k.
4. Track maximum length: Maintain a variable max_length to store the maximum length found during the iteration.
5. Return result: After iterating through all numbers in nums, max_length will contain the length of the longest valid subsequence.

Complexity

• Time Complexity: O(n), where n is the length of nums. We iterate through nums once and perform constant-time operations for each element.
• Space Complexity: O(k), where k is the value of k. The space is primarily used to store mappings of remainders to lengths of subsequences, which can have up to k entries.

The solution efficiently computes the length of the longest valid subsequence using dynamic programming and hashing, ensuring optimal performance.

Code Explanation

var maximumLength = function (nums, k) {

• Defines a function maximumLength that takes two parameters: nums, an array of integers, and k, a positive integer. The function aims to find the length of the longest valid subsequence where consecutive pairs have equal sums modulo k.

let dp = new Array(k * k).fill(0);

• Initializes an array dp of size k * k filled with zeros. This array will store the maximum lengths of subsequences that end with specific remainders modulo k.

var helper = (x, y) => x * k + y;

• Defines a helper function helper that calculates indices in the dp array based on two remainders x and y using the formula x * k + y. This function simplifies accessing and updating elements in the dp array based on remainders.

nums.forEach((num) => {
  num %= k;
  for (let i = 0; i < k; i++) {
    if (dp[helper(num, i)] + 1 > dp[helper(i, num)]) {
      dp[helper(i, num)] = dp[helper(num, i)] + 1;
    }
  }
});

• Iterates through each number num in the nums array. For each num, computes its remainder modulo k.
• For each remainder num % k, iterates through all possible remainders i from 0 to k-1.
• Checks if adding num to the subsequence ending with remainder i produces a longer valid subsequence than using i as the current remainder.
• Updates the dp array with the new maximum length of subsequences if a longer valid subsequence is found.

  return Math.max(...dp);
};

• Returns the maximum value found in the dp array using Math.max(...dp), which represents the length of the longest valid subsequence found based on the conditions specified.

Code

C++

class Solution {
public:
    int maximumLength(vector& nums, int k) {
        vector dp(k * k, 0);
        
        auto helper = [&](int x, int y, int k) {
            return x * k + y;
        };
        
        for (int num : nums) {
            num %= k;
            for (int i = 0; i < k; i++) {
                if (dp[helper(num, i, k)] + 1 > dp[helper(i, num, k)]) {
                    dp[helper(i, num, k)] = dp[helper(num, i, k)] + 1;
                }
            }
        }
        
        return *max_element(dp.begin(), dp.end());
    }
};

Python

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        dp = [0] * (k * k)
        
        def helper(x, y, k):
            return x * k + y
        
        for num in nums:
            num %= k
            for i in range(k):
                if dp[helper(num, i, k)] + 1 > dp[helper(i, num, k)]:
                    dp[helper(i, num, k)] = dp[helper(num, i, k)] + 1
        
        return max(dp)

Java

class Solution {
    public int maximumLength(int[] nums, int k) {
        int[] dp = new int[k * k];
        
        for (int num : nums) {
            num %= k;
            for (int i = 0; i < k; i++) {
                if (dp[helper(num, i, k)] + 1 > dp[helper(i, num, k)]) {
                    dp[helper(i, num, k)] = dp[helper(num, i, k)] + 1;
                }
            }
        }
        
        int max = 0;
        for (int value : dp) {
            max = Math.max(max, value);
        }
        
        return max;
    }
    
    private int helper(int x, int y, int k) {
        return x * k + y;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumLength = function (nums, k) {
  let dp = new Array(k * k).fill(0);
  var helper = (x, y) => x * k + y;

  nums.forEach((num) => {
    num %= k;
    for (let i = 0; i < k; i++) {
      if (dp[helper(num, i)] + 1 > dp[helper(i, num)]) {
        dp[helper(i, num)] = dp[helper(num, i)] + 1;
      }
    }
  });

  return Math.max(...dp);
};