3202. Find the Maximum Length of Valid Subsequence II

Problem Description

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

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

The task is to find the length of the longest valid subsequence of nums.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, we need to understand the core condition for a valid subsequence: For any two consecutive elements in the subsequence, the sum of those two elements mod k should be the same across the entire subsequence. This translates to needing the modulo result of all odd-indexed elements to be the same, and similarly, all even-indexed elements to have the same result when taken modulo k.

Here's the reasoning process:

Each element in nums is considered as x % k.
We define a 2D array f[x][y] that represents the length of the longest valid subsequence where the last element modulo k is x and the one before last modulo k is y.
Initially, set all f[x][y] to zero, as the subsequence begins empty.
As we iterate over each number in nums, compute x = num % k for the current number.
For each possible j in [0, k), previously consecutive numbers that make (num[j] + num[next]) % k consistent should be considered. The value y is calculated as (j - x + k) % k, giving possible combinations.
Update the state with f[x][y] = f[y][x] + 1, increasing the length of the subsequence when a valid condition is met.
Maintain a variable ans to track and return the maximum value found in f[x][y], which represents the length of the longest valid subsequence.

This dynamic programming approach efficiently constructs subsequences satisfying the condition through matrix indexing, eventually leading us to the desired answer.

Learn more about Dynamic Programming patterns.

Solution Approach

The problem is addressed using a dynamic programming technique. Here's a detailed walkthrough of the solution:

Data Structure Initialization:
A 2D list f with dimensions [k][k] is initialized to zero. This structure holds information about the longest valid subsequence found, where f[x][y] corresponds to the subsequence ending with an element whose modulo result is x, and the previous one was y.
```
f = [[0] * k for _ in range(k)]
```
Iteration through nums:
For each element x in nums, compute x = x % k. This converts each number to its remainder when divided by k, essentially mapping numbers onto the range [0, k).
```
for x in nums:
    x %= k
```
Update the DP Table:
For each possible j in [0, k), find y, the modulo value that would achieve the condition (prev_value + current_value) % k == j. The formula for y is computed as (j - x + k) % k to ensure non-negative values. Update the DP state by incrementing f[x][y] with the value of f[y][x] + 1, as a new valid subsequence can be formed by appending x.
```
for j in range(k):
    y = (j - x + k) % k
    f[x][y] = f[y][x] + 1
```
Track the Maximum Subsequence Length:
Throughout the iteration, maintain a variable ans to store the length of the longest valid subsequence encountered, taking the maximum across all f[x][y].
```
    ans = max(ans, f[x][y])
```
Return the Result:
After processing all elements, return ans, which now holds the length of the longest valid subsequence as per the problem's requirements.
```
return ans
```

By organizing and utilizing the results from previously computed states in a structured manner, this dynamic programming approach achieves efficient enumeration and tracking of valid subsequences.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with a small example to illustrate the approach. Consider the array nums = [3, 8, 5, 7] and k = 4. We aim to find the longest valid subsequence where subsequence sums modulo 4 are consistent.

Step 1: Initialize Data Structure

Create a 2D list f with dimensions [4][4] initialized to zero:

f = [[0, 0, 0, 0], 
     [0, 0, 0, 0], 
     [0, 0, 0, 0], 
     [0, 0, 0, 0]]

Step 2: Iteration through nums

Convert each number in nums to its respective modulo 4 value:
- For 3: 3 % 4 = 3
- For 8: 8 % 4 = 0
- For 5: 5 % 4 = 1
- For 7: 7 % 4 = 3
Now, nums = [3, 0, 1, 3] (transformed with modulo operation).

Step 3: Update the DP Table

Iterate over each number in the updated nums:

For x = 3 (from 3 in nums):
- Iterate j from 0 to 3:
  - When j=0: y = (0 - 3 + 4) % 4 = 1. Update: f[3][1] = f[1][3] + 1 = 1.
  - When j=1: y = (1 - 3 + 4) % 4 = 2. Update: f[3][2] = f[2][3] + 1 = 1.
  - When j=2: y = (2 - 3 + 4) % 4 = 3. Update: f[3][3] = f[3][3] + 1 = 1.
  - When j=3: y = (3 - 3 + 4) % 4 = 0. Update: f[3][0] = f[0][3] + 1 = 1.
For x = 0 (from 8 in nums):
- Iterate j from 0 to 3:
  - When j=0: y = (0 - 0 + 4) % 4 = 0. Update: f[0][0] = f[0][0] + 1 = 1.
  - When j=1: y = (1 - 0 + 4) % 4 = 1. Update: f[0][1] = f[1][0] + 1 = 1.
  - When j=2: y = (2 - 0 + 4) % 4 = 2. Update: f[0][2] = f[2][0] + 1 = 1.
  - When j=3: y = (3 - 0 + 4) % 4 = 3. Update: f[0][3] = f[3][0] + 1 = 2.
For x = 1 (from 5 in nums):
- Iterate j from 0 to 3:
  - When j=0: y = (0 - 1 + 4) % 4 = 3. Update: f[1][3] = f[3][1] + 1 = 2.
  - When j=1: y = (1 - 1 + 4) % 4 = 0. Update: f[1][0] = f[0][1] + 1 = 2.
  - When j=2: y = (2 - 1 + 4) % 4 = 1. Update: f[1][1] = f[1][1] + 1 = 1.
  - When j=3: y = (3 - 1 + 4) % 4 = 2. Update: f[1][2] = f[2][1] + 1 = 1.
For x = 3 (from 7 in nums):
- Iterate j from 0 to 3:
  - When j=0: y = (0 - 3 + 4) % 4 = 1. Update: f[3][1] = f[1][3] + 1 = 3.
  - When j=1: y = (1 - 3 + 4) % 4 = 2. Update: f[3][2] = f[2][3] + 1 = 2.
  - When j=2: y = (2 - 3 + 4) % 4 = 3. Update: f[3][3] = f[3][3] + 1 = 2.
  - When j=3: y = (3 - 3 + 4) % 4 = 0. Update: f[3][0] = f[0][3] + 1 = 3.

Step 4: Track the Maximum Subsequence Length

Calculate the maximum value of any f[x][y] after iterations.

ans = max(max(row) for row in f)

In this case, ans = 3, representing the longest valid subsequence.

Step 5: Return the Result

The length of the longest valid subsequence, satisfying the given condition, is 3.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximumLength(self, nums: List[int], k: int) -> int:
5        # Initialize a 2D list (matrix) of size k x k with all values set to 0
6        count_matrix = [[0] * k for _ in range(k)]
7        max_length = 0
8      
9        # Traverse through each number in the input list
10        for num in nums:
11            # Calculate the remainder of the current number with k
12            remainder = num % k
13          
14            # Iterate over each possible remainder
15            for j in range(k):
16                # Calculate complementary remainder required to form a valid pair with `remainder`
17                complement_remainder = (j - remainder + k) % k
18              
19                # Update the matrix with the new sequence length
20                count_matrix[remainder][complement_remainder] = count_matrix[complement_remainder][remainder] + 1
21              
22                # Update the maximum sequence length found
23                max_length = max(max_length, count_matrix[remainder][complement_remainder])
24      
25        # Return the maximum sequence length found
26        return max_length
27

1class Solution {
2    public int maximumLength(int[] nums, int k) {
3        // Initialize a 2D array to keep track of subarray lengths with modulo value
4        int[][] subarrayLengths = new int[k][k];  
5        int maxLength = 0;  // Variable to store the maximum length found
6
7        // Iterate over each element in nums
8        for (int num : nums) {
9            int modValue = num % k;  // Compute the current number's modulo with k
10          
11            // Iterate over all possible modulo values from 0 to k-1
12            for (int j = 0; j < k; ++j) {
13                int requiredMod = (j - modValue + k) % k;  // Compute the required complement modulo
14
15                // Update the subarray length by 1 for the current modulo configuration
16                subarrayLengths[modValue][requiredMod] = subarrayLengths[requiredMod][modValue] + 1;
17
18                // Update the maximum length found so far
19                maxLength = Math.max(maxLength, subarrayLengths[modValue][requiredMod]);
20            }
21        }
22        return maxLength;  // Return the maximum subarray length satisfying the condition
23    }
24}
25

1#include <vector>
2#include <cstring>  // For memset
3#include <algorithm>  // For max function
4
5class Solution {
6public:
7    // Function to find the maximum length of a subsequence with elements having a given modulus
8    int maximumLength(std::vector<int>& nums, int k) {
9        // Initialize a 2D array to store intermediate results
10        int remainderCount[k][k];
11      
12        // Set all elements of the 2D array to 0
13        std::memset(remainderCount, 0, sizeof(remainderCount));
14      
15        int maxLength = 0;  // Variable to keep track of the maximum length
16      
17        // Iterate through each number in the input vector
18        for (int num : nums) {
19            int modValue = num % k;  // Calculate modulus of the number with respect to k
20          
21            // Loop through possible remainder values
22            for (int remainder = 0; remainder < k; ++remainder) {
23                // Calculate the target remainder
24                int targetRemainder = (remainder - modValue + k) % k;
25              
26                // Update the 2D array for the current modValue and targetRemainder
27                remainderCount[modValue][targetRemainder] = remainderCount[targetRemainder][modValue] + 1;
28              
29                // Update maximum length if a longer subsequence is found
30                maxLength = std::max(maxLength, remainderCount[modValue][targetRemainder]);
31            }
32        }
33      
34        // Return the maximum length of the subsequence found
35        return maxLength;
36    }
37};
38

1function maximumLength(nums: number[], k: number): number {
2    // Initialize a 2D array with dimensions k x k, filled with zeros
3    const f: number[][] = Array.from({ length: k }, () => Array(k).fill(0));
4    let ans: number = 0; // To keep track of the maximum length found
5
6    for (let x of nums) {
7        x %= k; // Reduce x mod k to be within the range 0 to k-1
8      
9        // Iterate over each possible remainder j
10        for (let j = 0; j < k; ++j) {
11            // Compute the remainder y that when added to x is equivalent to j mod k
12            const y = (j - x + k) % k;
13            // Update the value in the f array to reflect the longest length ending in x, with sum mod k equal to y
14            f[x][y] = f[y][x] + 1;
15            // Update the maximum length found so far
16            ans = Math.max(ans, f[x][y]);
17        }
18    }
19  
20    return ans; // Return the maximum length found
21}
22

Time and Space Complexity

The time complexity of the given code is O(n * k), where n is the length of the array nums, and k is the given positive integer. This complexity arises because for each element in nums, represented as x, a nested loop iterates k times to update the f matrix.

The space complexity is O(k^2) because the 2D list f is initialized with dimensions k x k, leading to the storage requirement of k * k elements.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know