3201. Find the Maximum Length of Valid Subsequence I

Intuition

To find the longest valid subsequence where the sum of every adjacent pair modulo 2 is the same, we can leverage properties of even and odd numbers. Specifically, sequences of even or odd numbers will satisfy the condition trivially.

Approach

1. Counting Evens and Odds: First, count the number of even and odd numbers in the array nums.
2. Longest Subsequence Calculation: The longest valid subsequence can be formed by selecting either all even numbers or all odd numbers. Hence, the length of the longest valid subsequence will be the maximum of the count of even numbers or the count of odd numbers.

Complexity

• Time Complexity: O(n), where n is the length of the array nums. We only need to iterate through the array once to count evens and odds.
• Space Complexity: O(1). We are using a constant amount of extra space for storing counts of even and odd numbers.

Code Explanation

Initialization

let a = 0,
  b = 0,
  c = 0,
  d = 0;

• Initializes four variables: - a: Counter for even numbers. - b: Counter for odd numbers. - c: Length of the valid subsequence ending with the last even number encountered. - d: Length of the valid subsequence ending with the last odd number encountered.

Loop through Array

    for (let num of nums) {

• Begins a for ... of loop to iterate through each element num in the array nums.

Conditional Logic

if (num % 2 === 0) {
  a++;
  c = d + 1;
} else {
  b++;
  d = c + 1;
}

• Checks if the current num is even (num % 2 === 0): - Increments a (count of even numbers). - Updates c to d + 1 (length of the subsequence ending with the current even number).
• If num is odd: - Increments b (count of odd numbers). - Updates d to c + 1 (length of the subsequence ending with the current odd number).
• Ends the for ... of loop after iterating through all elements of nums.

Return Statement

return Math.max(a, b, c, d);

• Calculates the maximum length among a, b, c, and d using Math.max.
• Returns this maximum length, which represents the length of the longest valid subsequence according to the given conditions.

Code

C++

class Solution {
public:
    int maximumLength(vector& nums) {
        int a = 0, b = 0, c = 0, d = 0;
        for (int num : nums) {
            if (num % 2 == 0) {
                a++;
                c = d + 1;
            } else {
                b++;
                d = c + 1;
            }
        }
        return max({a, b, c, d});
    }
};

Python

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        a, b, c, d = 0, 0, 0, 0
        for num in nums:
            if num % 2 == 0:
                a += 1
                c = d + 1
            else:
                b += 1
                d = c + 1
        return max(a, b, c, d)

Java

class Solution {
    public int maximumLength(int[] nums) {
        int a = 0, b = 0, c = 0, d = 0;
        for (int num : nums) {
            if (num % 2 == 0) {
                a++;
                c = d + 1;
            } else {
                b++;
                d = c + 1;
            }
        }
        return Math.max(Math.max(a, b), Math.max(c, d));
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumLength = function(nums) {
    let a = 0, b = 0, c = 0, d = 0;
    for (let num of nums) {
        if (num % 2 === 0) {
            a++;
            c = d + 1;
        } else {
            b++;
            d = c + 1;
        }
    }
    return Math.max(a, b, c, d);
};