Find the Maximum Length of Valid Subsequence I

Find the Maximum Length of Valid Subsequence I - Problem

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.

Input & Output

Example 1 — Basic Mixed Array

$ Input: nums = [1,2,3,4]

› Output: 4

💡 Note: We can select the entire array [1,2,3,4]. Adjacent sums: (1+2)%2=1, (2+3)%2=1, (3+4)%2=1. All have the same parity.

Example 2 — All Same Parity

$ Input: nums = [2,4,6,8]

› Output: 4

💡 Note: All numbers are even. We can select all: [2,4,6,8]. Adjacent sums: (2+4)%2=0, (4+6)%2=0, (6+8)%2=0. All even sums.

Example 3 — Small Array

$ Input: nums = [1,3]

› Output: 2

💡 Note: Only one pair possible: [1,3]. Sum: (1+3)%2=0. Valid subsequence of length 2.

Constraints

1 ≤ nums.length ≤ 10³
1 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Array

[1,2,3,4] with mixed even/odd numbers

Check Patterns

Test all 4 possible parity patterns for adjacent sums

Find Maximum

Return the longest valid subsequence length

Key Takeaway

🎯 Key Insight: Only 4 parity patterns exist - track them efficiently in one pass

Asked in

G Google 15 f Meta 12 a Amazon 10

The key insight is recognizing that only 4 parity patterns exist for adjacent sums. The optimal approach tracks all patterns in a single O(n) pass using O(1) space, achieving maximum efficiency.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subsequences	O(n × 2ⁿ)	O(n)	Generate all possible subsequences and check validity
Optimized - Smart Pattern Tracking	O(n)	O(1)	Track best sequences for each pattern in a single pass
Dynamic Programming - Pattern Recognition	O(n)	O(1)	Recognize only 4 parity patterns exist and use DP for each

Brute Force - Try All Subsequences — Algorithm Steps

Generate all possible subsequences
For each subsequence, check if all adjacent sums have same parity
Track the maximum valid length

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 2^n possible subsequences

Validate

Check if adjacent sums have same parity

Track Max

Keep the longest valid subsequence length

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int maxLength = 1;
    
    // Try all possible subsequences
    for (int mask = 1; mask < (1 << numsSize); mask++) {
        int subseq[1000];
        int subseqSize = 0;
        
        for (int i = 0; i < numsSize; i++) {
            if (mask & (1 << i)) {
                subseq[subseqSize++] = nums[i];
            }
        }
        
        if (subseqSize < 2) continue;
        
        // Check if subsequence is valid
        int valid = 1;
        int firstParity = (subseq[0] + subseq[1]) % 2;
        for (int i = 1; i < subseqSize - 1; i++) {
            if ((subseq[i] + subseq[i + 1]) % 2 != firstParity) {
                valid = 0;
                break;
            }
        }
        
        if (valid && subseqSize > maxLength) {
            maxLength = subseqSize;
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, numsSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2ⁿ)

2^n subsequences, each taking O(n) time to validate

✓ Linear Growth

Space Complexity

O(n)

Space to store current subsequence during generation

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~15 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler