We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Length of Valid Subsequence I

Number: 3490

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of integers nums, a subsequence sub (which can be obtained by deleting some or no elements without changing the order) is defined to be "valid" if for every pair of consecutive elements in sub, (sub[i] + sub[i+1]) % 2 is the same across the entire subsequence. In other words, either every adjacent pair sums up to an even number (which happens when both numbers have the same parity) or to an odd number (when the numbers have different parities). The task is to return the length of the longest valid subsequence possible.

Key Insights

  • If the common modulo value is 0 then every adjacent pair’s sum is even. This forces every two consecutive numbers to have the same parity; in fact, the entire subsequence must be all even or all odd.
  • If the common modulo value is 1 then every consecutive pair sums to odd. This forces the subsequence to alternate parities.
  • The maximum valid subsequence will be the best among:
    • The subsequence consisting of all even numbers.
    • The subsequence consisting of all odd numbers.
    • The longest alternating subsequence (respecting the original order).
  • A greedy scan is sufficient to extract the longest alternating subsequence from the array.

Space and Time Complexity

Time Complexity: O(n) – We scan the array a constant number of times. Space Complexity: O(1) – Only a few counters and variables are used.

Solution

We consider two cases:

  1. Constant modulo = 0: The valid subsequence must have all numbers with the same parity. Its maximum possible length is the larger of the counts of even numbers or odd numbers.
  2. Constant modulo = 1: The valid subsequence needs to alternate parities. We can greedily traverse the array and pick an element if its parity differs from the last chosen element. This produces the longest alternating subsequence possible from the given order. Finally, the answer is the maximum among the two cases above.

Data structures used:

  • Simple integer counters for even, odd, and the current length of the alternating sequence. Technique:
  • One pass to count evens and odds.
  • One pass (greedy) to build the longest alternating subsequence. The overall answer is the maximum of (count_evens, count_odds, alternating_length).

Code Solutions

# Python solution with comments
def maxValidSubsequenceLength(nums):
    # Count the number of even and odd numbers in the array.
    even_count = sum(1 for num in nums if num % 2 == 0)
    odd_count = len(nums) - even_count

    # Compute the longest alternating subsequence using a greedy approach.
    # Initialize the alternating sequence length to 0.
    alt_length = 0
    last_parity = None  # Track parity of the last added element
    
    for num in nums:
        curr_parity = num % 2
        # If this is the first element, or the parity is different than the last chosen element,
        # include it in the alternating subsequence.
        if last_parity is None or curr_parity != last_parity:
            alt_length += 1
            last_parity = curr_parity
    
    # The longest valid subsequence is the maximum between:
    # 1. All even numbers or all odd numbers (constant modulo = 0).
    # 2. The longest alternating subsequence (constant modulo = 1).
    return max(even_count, odd_count, alt_length)

# Example usages:
print(maxValidSubsequenceLength([1,2,3,4]))       # Output: 4
print(maxValidSubsequenceLength([1,2,1,1,2,1,2]))   # Output: 6
print(maxValidSubsequenceLength([1,3]))             # Output: 2
← Back to All Questions