3201. Find the Maximum Length of Valid Subsequence I

Problem Description

You are given an integer array nums.

A subsequence sub of nums with length x is called valid if it satisfies:

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

Return the length of the longest valid subsequence of nums.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Intuition

The problem requires finding the longest subsequence where the sum of each pair of consecutive elements has the same parity (either both sums are even or both are odd). This suggests we can utilize dynamic programming to keep track of subsequences ending with pairs of elements having the same modular conditions.

Here's the approach:

Dynamic Programming Setup: Define f[x][y] as the length of the longest valid subsequence where the last element modulo 2 equals x, and the second last element modulo 2 equals y.
Iterate Through Elements: For each number in nums, compute the modulo with 2 (denoted as x % 2). We then evaluate, for each possible value of j (0 or 1), if it's feasible to extend a subsequence with the current number.
Update States: The transition involves updating f[x][y] = f[y][x] + 1, where y = (j - x + 2) % 2 ensures the parities of adjacent sums are maintained.
Find Maximum Length: The result will be the maximum value found in any state f[x][y], covering all combinations of parities.

This methodology efficiently evaluates possible subsequences and allows for determination of the longest valid one by leveraging the relationship between consecutive elements and their parities.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses a dynamic programming approach where the key idea is to maintain a table f that keeps track of the longest valid subsequences based on the modulo condition of their last two elements.

Here's the breakdown of the approach:

Initialization: Set k = 2 which represents the two possible outcomes for parity (even and odd). Create a 2D list f, initialized to zero with dimensions [k][k], representing possible parities of consecutive elements.
Iterate Over Numbers: Loop through each number x in nums and compute x % k.
Dynamic Programming State Update:
- For each j in the range [0, k), compute the parity difference y as (j - x + k) % k. This is to ensure that you derive the last element of the subsequence by adjusting the parity to maintain valid parity conditions.
- Update the state f[x][y] = f[y][x] + 1, capturing the length of the longest subsequence ending with the given parities.
Track Maximum Length: As the states get updated, maintain a variable ans that holds the maximum value in f, representing the longest valid subsequence found.
Return Result: The final step is to return ans, which contains the length of the longest subsequence found that satisfies the given condition.

This approach efficiently determines the longest subsequence using minimal space and time by leveraging the observed pattern in parity, massively reducing the complexity of potential subsequence evaluation.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's illustrate the dynamic programming solution approach with a simple example. Suppose we have the array nums = [3, 1, 5, 7, 2]. We want to find the longest valid subsequence where consecutive pairs (sub[i], sub[i+1]) of the subsequence have sums with the same parity.

Initialization:
- Set k = 2 because we have two possible parities: even (0) and odd (1).
- Initialize a 2D list f with dimensions [2][2] to track subsequences based on parities. Initially, all values are set to 0: f = [[0, 0], [0, 0]].
Iterate Over Numbers:
- For each number x in nums, compute x % k to determine if the number is even or odd.
Dynamic Programming State Update:
- As we iterate, calculate the new states and update the table f.
- For x = 3: 3 % 2 = 1 (odd):
  - Check all possible previous states:
    - For j = 0 (even), calculate y = (0 - 1 + 2) % 2 = 1. Update: f[1][1] = f[0][1] + 1 = 1.
    - For j = 1 (odd), calculate y = (1 - 1 + 2) % 2 = 0. Update: f[1][0] = f[1][0] + 1 = 1.
  - Current f becomes: f = [[0, 1], [1, 1]].
- For x = 1: 1 % 2 = 1 (odd):
  - Repeat the above process.
  - Current f remains: f = [[0, 2], [2, 1]] (one of the paths is extended).
- For x = 5: 5 % 2 = 1 (odd):
  - Calculate new state values, allowing us to extend the sequence when valid.
  - Current f = [[0, 3], [3, 2]].
- For x = 7: 7 % 2 = 1 (odd):
  - Further extend using similar parity checks.
  - Current f = [[0, 4], [4, 3]].
- For x = 2: 2 % 2 = 0 (even):
  - Update states where possible.
  - Current f = [[0, 5], [5, 4]].
Track Maximum Length:
- Throughout this process, track the maximum value in the table f.
- The maximum value here is 5, indicating the longest valid subsequence has a length of 5, which could be [3, 1, 5, 7, 2] or another valid sequence with the same length.
Return Result:
- The final result, ans = 5, is returned as the length of the longest valid subsequence.

This example demonstrates how to update the dynamic programming table and find the sequence with the longest parity-consistent sums.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximumLength(self, nums: List[int]) -> int:
5        k = 2
6        # Initialize a 2D list to keep track of sequences with different remainders
7        remainder_count = [[0] * k for _ in range(k)]
8        max_length = 0
9      
10        # Iterate through each number in the list
11        for num in nums:
12            # Calculate the remainder of the current number when divided by k
13            remainder = num % k
14            # Update dp table for current number
15            for j in range(k):
16                previous_remainder = (j - remainder + k) % k
17                remainder_count[remainder][previous_remainder] = remainder_count[previous_remainder][remainder] + 1
18                # Update the maximum length found so far
19                max_length = max(max_length, remainder_count[remainder][previous_remainder])
20      
21        return max_length
22

1class Solution {
2    public int maximumLength(int[] nums) {
3        int k = 2; // Define the modulus value
4        int[][] frequency = new int[k][k]; // Initialize a 2D array to hold frequency counts
5        int maxLength = 0; // Variable to store the maximum length found
6
7        for (int num : nums) { // Iterate over the elements in nums array
8            num %= k; // Calculate modulo of num with k
9            for (int j = 0; j < k; ++j) { // Iterate over each possible value modulo k
10                int y = (j - num + k) % k; // Calculate the required complement to make a sum divisible by k
11                frequency[num][y] = frequency[y][num] + 1; // Update the frequency table with current element
12                maxLength = Math.max(maxLength, frequency[num][y]); // Update the maximum length found
13            }
14        }
15        return maxLength; // Return the maximum length of subarray found
16    }
17}
18

1class Solution {
2public:
3    int maximumLength(std::vector<int>& nums) {
4        const int k = 2; // Modulo divisor to handle the remainders (can be adjusted based on requirements)
5        int dp[k][k];    // Dynamic programming table to store longest lengths for each remainder pair
6        memset(dp, 0, sizeof(dp)); // Initialize the dp table with zeroes
7        int maxLength = 0; // Variable to store the maximum length found
8
9        // Iterate through each number in the input vector
10        for (int num : nums) {
11            int remainder = num % k; // Find the remainder of the number with respect to k
12
13            for (int j = 0; j < k; ++j) {
14                int requiredRemainder = (j - remainder + k) % k; // Calculate the remainder needed to form the sequence
15
16                // Update the dp table with the new length found and track the maximum
17                dp[remainder][requiredRemainder] = dp[requiredRemainder][remainder] + 1;
18
19                // Update the maximum length found so far
20                maxLength = std::max(maxLength, dp[remainder][requiredRemainder]);
21            }
22        }
23        return maxLength; // Return the maximum length of the sequence found
24    }
25};
26

1function maximumLength(nums: number[]): number {
2    const k = 2; // Define the modulus base 'k'
3    const f: number[][] = Array.from({ length: k }, () => Array(k).fill(0)); // Create a 2D array of size k x k, initialized to 0
4    let ans: number = 0; // Variable to store the maximum subarray length
5  
6    // Traverse through each number in the array
7    for (let x of nums) {
8        x %= k; // Take modulus of current number to classify based on remainder
9      
10        // Iterate through possible remainders
11        for (let j = 0; j < k; ++j) {
12            const y = (j - x + k) % k; // Calculate adjusted index for modular arithmetic to handle negative results
13          
14            // Update the subarray length for the current remainder configuration
15            f[x][y] = f[y][x] + 1;
16          
17            // Track the maximum length encountered so far
18            ans = Math.max(ans, f[x][y]);
19        }
20    }
21  
22    return ans; // Return the maximum length found
23}
24

Time and Space Complexity

The time complexity of the code is O(n * k), where n is the length of the array nums and k = 2. This is because the algorithm iterates over each element in nums (hence O(n)) and performs operations up to k times (hence O(k)) due to the nested loop structure. The time complexity can be simplified to O(n) since k is a constant.

The space complexity is O(k^2). This arises from the usage of a two-dimensional list f of size k x k. Given that k = 2, the space complexity is effectively O(1), because it is constant and does not depend on the input size n.

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

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

Question 1 out of 10

What's the relationship between a tree and a graph?

A graph is a special tree

A tree is a special graph

No relationship

They are the same thing

I don’t know