LeetCode 3201 - Find the Maximum Length of Valid Subsequence I

The problem asks us to find the longest subsequence in an integer array nums where each adjacent pair of elements in the subsequence has the same parity sum, modulo 2.

leetcodemediumarraydynamic-programming

LeetCode Problem 3201

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to find the longest subsequence in an integer array nums where each adjacent pair of elements in the subsequence has the same parity sum, modulo 2. In other words, if we sum consecutive elements in the subsequence and take each sum modulo 2, all these results must be equal.

The input is an integer array of length at least 2 and up to 200,000, with element values between 1 and 10,000,000. The output is a single integer, representing the length of the longest subsequence that satisfies the parity condition.

The constraints indicate that a brute-force approach that enumerates all subsequences would be infeasible because there are exponentially many subsequences. We must find a linear or linearithmic solution to handle the upper bounds efficiently.

Important edge cases include arrays with all odd numbers, all even numbers, alternating patterns, and very short arrays (length 2). The problem guarantees at least two elements, so we do not need to handle empty arrays.

Approaches

A brute-force approach would generate all possible subsequences of nums and check for each one whether consecutive sums modulo 2 are the same. This approach is correct but extremely slow because the number of subsequences grows exponentially with the array length. For the upper limit of 200,000 elements, this is entirely infeasible.

The key observation that allows an optimal solution is based on the parity of numbers. Since (a + b) % 2 depends only on the parity of a and b, there are only two possible parity sums: 0 for even sums and 1 for odd sums. Therefore, the subsequence can be extended greedily by including an element if its sum with the previous element has the same parity as the current running sum. This reduces the problem to a linear scan of the array, checking the parity of sums and maintaining the longest valid subsequence length.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Generates all subsequences and checks each one
Optimal O(n) O(1) Linear scan, extending subsequence based on parity checks

Algorithm Walkthrough

  1. Initialize a counter max_len to 1, representing the length of the current valid subsequence. Set prev_parity_sum to None, which will store the parity of the sum of the last two elements in the subsequence.
  2. Iterate over the array from the second element to the end. At each step, calculate the sum of the current element and the previous element modulo 2.
  3. If prev_parity_sum is None (first iteration), assign it to the current parity sum. Increment max_len to 2 because the first two elements form a valid subsequence.
  4. For subsequent elements, compare the current parity sum with prev_parity_sum. If they are equal, increment max_len because the subsequence can be extended. Otherwise, reset prev_parity_sum to the current sum and consider the subsequence starting from the previous element.
  5. Continue until the end of the array. Return max_len as the result.

Why it works: The algorithm maintains the invariant that prev_parity_sum always represents the parity of sums for the longest valid subsequence ending at the current position. By checking only the last element and the new candidate, we ensure that all sums modulo 2 remain consistent, producing the correct answer.

Python Solution

from typing import List

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return len(nums)
        
        max_len = 1
        prev_parity_sum = None
        current_len = 1
        
        for i in range(1, len(nums)):
            parity_sum = (nums[i - 1] + nums[i]) % 2
            if prev_parity_sum is None or parity_sum == prev_parity_sum:
                current_len += 1
            else:
                current_len = 2  # restart subsequence from previous element
            prev_parity_sum = parity_sum
            max_len = max(max_len, current_len)
        
        return max_len

The Python implementation starts by handling arrays smaller than 2. It tracks the current subsequence length and the parity sum of consecutive elements. Each element is checked against the previous parity sum. If it matches, the subsequence is extended; otherwise, the subsequence is restarted from the previous element. The maximum length found is returned.

Go Solution

func maximumLength(nums []int) int {
    if len(nums) < 2 {
        return len(nums)
    }

    maxLen := 1
    currentLen := 1
    var prevParitySum *int

    for i := 1; i < len(nums); i++ {
        paritySum := (nums[i-1] + nums[i]) % 2
        if prevParitySum == nil || *prevParitySum == paritySum {
            currentLen++
        } else {
            currentLen = 2
        }
        prevParitySum = &paritySum
        if currentLen > maxLen {
            maxLen = currentLen
        }
    }

    return maxLen
}

The Go solution mirrors the Python logic. We use a pointer for prevParitySum to handle the first iteration cleanly. Slice indexing and modulo arithmetic are used similarly. The current subsequence length is tracked, and the maximum is updated iteratively.

Worked Examples

Example 1: nums = [1, 2, 3, 4]

i nums[i-1]+nums[i] % 2 prev_parity_sum current_len max_len
1 3 % 2 = 1 None -> 1 2 2
2 5 % 2 = 1 1 3 3
3 7 % 2 = 1 1 4 4

Return 4

Example 2: nums = [1, 2, 1, 1, 2, 1, 2]

The parity sums alternate consistently, giving max_len = 6.

Example 3: nums = [1, 3]

Single parity sum, length 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through the array once, performing constant-time operations per element
Space O(1) Only a few integer variables are used, no additional data structures

The algorithm scales linearly with the input size, suitable for arrays up to 200,000 elements.

Test Cases

# Example cases
assert Solution().maximumLength([1,2,3,4]) == 4  # contiguous valid
assert Solution().maximumLength([1,2,1,1,2,1,2]) == 6  # alternating valid
assert Solution().maximumLength([1,3]) == 2  # minimal array

# Edge cases
assert Solution().maximumLength([2,2,2,2]) == 4  # all even numbers
assert Solution().maximumLength([1,1,1,1]) == 4  # all odd numbers
assert Solution().maximumLength([1,2]) == 2  # minimal valid subsequence
assert Solution().maximumLength([1,2,3,5,8,13,21]) == 3  # mix parity
assert Solution().maximumLength([1,2,3,4,5,6,7,8,9,10]) == 10  # long valid subsequence
Test Why
[1,2,3,4] basic contiguous valid subsequence
[1,2,1,1,2,1,2] longest alternating subsequence
[1,3] minimal array size
[2,2,2,2] all even numbers
[1,1,1,1] all odd numbers
[1,2] minimal valid subsequence
[1,2,3,5,8,13,21] mix parity, partial valid sequences
[1..10] long consecutive valid subsequence

Edge Cases

One important edge case is an array of length 2. Since the problem guarantees at least 2 elements, the algorithm must handle this directly. Our solution correctly identifies the pair as valid, returning 2.

Another edge case is an array with all numbers having the same parity. In this case, every consecutive sum is even, so the longest subsequence is the entire array. The algorithm handles this naturally because the parity sum does not change.

A third edge case is an alternating parity array. For example, [1,2,1,2,1] has alternating odd-even sums. The algorithm correctly tracks the running subsequence and counts the longest contiguous sequence with consistent parity sums.

These edge cases validate that the algorithm works for minimum input size, uniform parity, and alternating patterns.