• Leetcode POTDs

Problem 3201 Find the Maximum Length of Valid Subsequence I

Problem Statement

Link - Problem 3201

Question

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.

Example 1:

Example 2:

Example 3:

Constraints:

• 2 <= nums.length <= 2 * 105
• 1 <= nums[i] <= 107

Solution

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        int type_1 = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i]%2==0){
                type_1++;
            }
        }
        int type_2=0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i]%2==1){
                type_2++;
            }
        }
        bool turn = true;
        int type_3 = 0;
        for(int i = 0; i < nums.size(); i++){
            if(turn && nums[i]%2==0){
                turn=false;
            } else if(!turn && nums[i]%2==1){
                turn=true;
                type_3+=2;
            }
        }
        if(turn==false){
            type_3++;
        }
        turn = true;
        int type_4=0;
        for(int i = 0; i < nums.size(); i++){
            if(turn && nums[i]%2==1){
                turn=false;
            } else if(!turn && nums[i]%2==0){
                type_4+=2;
                turn=true;
            }
        }
        if(turn==false){
            type_4++;
        }
        return max(max(type_1, type_2),max(type_3, type_4));
    }
};

Complexity Analysis

| Algorithm                 | Time Complexity | Space Complexity |
| ------------------------- | --------------- | ---------------- |
| Simple Frequency Counting | O(n)            | O(1)             |

Explanation

Intial Thoughts

This problem can be approached by first identifying the pattern required for a valid subsequence, where each pair of consecutive numbers sums up to either an even or odd number consistently throughout the subsequence. We can consider the numbers to be of two types: even and odd. We need to maximize the length of the valid subsequence, so we should consider all possible scenarios for achieving this. Looking at the solution, we find four different types of subsequences being considered. The first two types involve only odd or even numbers. However, the last two types involve alternating between odd and even numbers. A valid subsequence could end with either an even or odd number depending on the starting number and the type of subsequence we are dealing with.

Intuitive Analysis

The provided solution has correctly analyzed all possible types of valid subsequences. It first counts the number of odd and even numbers separately, and then considers the two alternating scenarios. In each scenario, it pairs the numbers from the start and the end, working its way towards the center to maximize the subsequence length. At the end, it chooses the maximum length from the four types of subsequences. We can intuitively understand that this is the best approach because we have considered all possible arrangements and are choosing the one that gives the maximum length.

1. Intuition

• The problem asks for the longest valid subsequence where the sum of adjacent elements has the same parity.
• To solve this, we can categorize the numbers into two types: even and odd.
• We can then consider four cases: all even numbers, all odd numbers, alternating even and odd numbers starting with even, and alternating even and odd numbers starting with odd.
• The longest valid subsequence will be the maximum length among these four cases.
• This approach works because it considers all possible scenarios for the parity of adjacent elements.
• By counting the number of even and odd numbers, we can determine the maximum length of the valid subsequence.
• The time complexity of this approach is O(n), where n is the length of the input array.

2. Implementation

• We initialize four variables type_1, type_2, type_3, and type_4 to store the count of even numbers, odd numbers, alternating even and odd numbers starting with even, and alternating even and odd numbers starting with odd, respectively.
• We iterate through the input array to count the number of even and odd numbers using if(nums[i]%2==0) and if(nums[i]%2==1).
• We use a boolean variable turn to keep track of the parity of the current number in the alternating sequences.
• We update the type_3 and type_4 variables based on the parity of the current number and the previous number.
• Finally, we return the maximum length among the four cases using max(max(type_1, type_2),max(type_3, type_4)).
• The code uses simple loops and conditional statements to implement the logic.
• The variables are named clearly to indicate their purpose, making the code easy to understand.

Complexity Analysis

Time Complexity:

• The algorithm iterates over the input vector four times using loops (for(int i = 0; i < nums.size(); i++)), resulting in a total of 4*n iterations, which simplifies to O(n) because constant factors are ignored in Big O notation.
• The dominant operations are the if condition checks within the loops (if(nums[i]%2==0) and if(vals[i]%2==1), which are executed a total of 4*n times.
• Given that the number of iterations grows linearly with the size of the input, the time complexity is classified as O(n)

Space Complexity:

• The algorithm uses a constant amount of space to store variables (type_1, type_2, type_3, type_4, and turn), regardless of the size of the input vector.
• No data structures that scale with the input size (e.g., vectors, arrays) are used, minimizing memory usage.
• The constant space usage justifies the space complexity classification as O(1)

Footnote

This question is rated as Medium difficulty.

Hints

The possible sequence either contains all even elements, all odd elements, alternate even odd, or alternate odd even elements.

Considering only the parity of elements, there are only 4 possibilities and we can try all of them.

When selecting an element with any parity, try to select the earliest one.

Similar Questions: