🎨 Try our Free AI Image Generation Feature

3202. Find the Maximum Length of Valid Subsequence II

avatar
Dare2Solve

1 year ago

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);
};