Find the Maximum Length of Valid Subsequence I solution and explanation
Google
9 more videos on this problem
Find the Maximum Length of Valid Subsequence | Part I | Part II | Leetcode 3201 | 3202 | MIKcodestorywithMIK · 45:23 · 14K views
Find the Maximum Length of Valid Subsequence I | Detailed Intuition | Leetcode 3201 | MIKcodestorywithMIK · 24:54 · 13K views
Find the Maximum Length of Valid Subsequence I | Leetcode 3201Techdose · 14:56 · 4K views
3201. Find the Maximum Length of Valid Subsequence I (Leetcode Medium)Programming Live with Larry · 15:12 · 1K views
3201. Find the Maximum Length of Valid Subsequence I | Leetcode Daily - PythonLeetcode Daily · 4:22 · 621 views
Find the Maximum Length of Valid Subsequence I | LeetCode 3201 - Pythonimpoldev · 10:37 · 544 views
Find the Maximum Length of Valid Subsequence I | LeetCode 3201 | Java Code | Developer CoderDeveloper Coder · 13:43 · 312 views
3201. Find the Maximum Length of Valid Subsequence I | Leetcode | Python in Tamil | Soumil SpeaksSoumil Speaks · 9:05 · 200 views
3201 Find the Maximum Length of Valid Subsequence I LeetCodeR Sai Siddhu · 13:03 · 137 views
3201. Find the Maximum Length of Valid Subsequence I (leetcode medium)Coder on A Farm · 3:00 · 96 views
The problem
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:
Input: nums = [1,2,3,4]
Output: 4
Explanation:
The longest valid subsequence is [1, 2, 3, 4].
Example 2:
Input: nums = [1,2,1,1,2,1,2]
Output: 6
Explanation:
The longest valid subsequence is [1, 2, 1, 2, 1, 2].
Example 3:
Input: nums = [1,3]
Output: 2
Explanation:
The longest valid subsequence is [1, 3].
Constraints:
2 <= nums.length <= 2 * 1051 <= nums[i] <= 107
Approach overview
Problem Overview: You are given an integer array. The task is to select a subsequence such that the parity of every adjacent pair sum stays the same. In other words, for every adjacent pair (a[i], a[i+1]) in the subsequence, the value of (a[i] + a[i+1]) % 2 must remain constant. The goal is to return the maximum possible length of such a subsequence.
Approach 1: Greedy Approach with Pairwise Checking (O(n) time, O(1) space)
The key observation comes from parity. If (a + b) % 2 = 0, both numbers have the same parity. If (a + b) % 2 = 1, they have different parity. That means a valid subsequence must either keep the same parity for every element (all even or all odd) or strictly alternate between even and odd. Iterate through the array and count how many even and odd numbers exist. The best same-parity subsequence is simply the larger of the two counts. For the alternating case, you greedily construct a subsequence by switching parity whenever possible. The maximum valid length becomes the best result among these options.
Approach 2: Dynamic Programming with State Tracking (O(n) time, O(1) space)
This method explicitly models the constraint using dynamic programming. Track states based on the parity of the last chosen element and the required parity of the pair sum. For each number, compute its parity and update states that represent extending a subsequence with the same sum parity. The transition checks whether (prev + current) % 2 matches the required pattern. Because parity only has two values, the DP state space remains constant. This approach is useful when generalizing to more complex constraints or when building intuition for subsequence state transitions.
Both solutions rely heavily on parity properties and sequential processing of the array, a common pattern in array problems and subsequence optimization tasks. The greedy approach derives directly from parity behavior, while the DP formulation makes the constraint explicit and easier to reason about.
Recommended for interviews: The greedy parity-counting insight is what most interviewers expect. It shows you recognized that the pair constraint collapses into parity patterns. Explaining the DP state formulation first demonstrates problem decomposition, then simplifying it into the greedy counting solution shows strong optimization skills.
Approach 1: Greedy Approach with Pairwise Checking
To find the longest valid subsequence, you can iterate through the list and keep track of the subsequence by maintaining the parity of consecutive pair sums. Start with the entire sequence and verify the condition iteratively, constructing valid subsequences as you proceed through the list.
def max_valid_subsequence_length(nums):
max_length = 0
current_length = 1
for i in range(1, len(nums)):
if (nums[i] + nums[i - 1]) % 2 == (nums[0] + nums[1]) % 2:
current_length += 1
else:
current_length = 2
max_length = max(max_length, current_length)
return max_length
nums = [1, 2, 1, 1, 2, 1, 2]
print(max_valid_subsequence_length(nums))public class Solution {
public static int maxValidSubsequenceLength(int[] nums) {
int maxLength = 0, currentLength = 1;
for (int i = 1; i < nums.length; i++) {
if ((nums[i] + nums[i - 1]) % 2 == (nums[0] + nums[1]) % 2) {
currentLength++;
} else {
currentLength = 2;
}
maxLength = Math.max(maxLength, currentLength);
}
return maxLength;
}
public static void main(String[] args) {
int[] nums = {1, 2, 1, 1, 2, 1, 2};
System.out.println(maxValidSubsequenceLength(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxValidSubsequenceLength(const vector<int>& nums) {
int maxLength = 0, currentLength = 1;
for (size_t i = 1; i < nums.size(); i++) {
if ((nums[i] + nums[i - 1]) % 2 == (nums[0] + nums[1]) % 2) {
currentLength++;
} else {
currentLength = 2;
}
maxLength = max(maxLength, currentLength);
}
return maxLength;
}
int main() {
vector<int> nums = {1, 2, 1, 1, 2, 1, 2};
cout << maxValidSubsequenceLength(nums) << endl;
return 0;
}function maxValidSubsequenceLength(nums) {
let maxLength = 0, currentLength = 1;
for (let i = 1; i < nums.length; i++) {
if ((nums[i] + nums[i - 1]) % 2 === (nums[0] + nums[1]) % 2) {
currentLength++;
} else {
currentLength = 2;
}
maxLength = Math.max(maxLength, currentLength);
}
return maxLength;
}
const nums = [1, 2, 1, 1, 2, 1, 2];
console.log(maxValidSubsequenceLength(nums));#include <stdio.h>
int maxValidSubsequenceLength(int* nums, int size) {
int maxLength = 0, currentLength = 1;
for (int i = 1; i < size; i++) {
if ((nums[i] + nums[i - 1]) % 2 == (nums[0] + nums[1]) % 2) {
currentLength++;
} else {
currentLength = 2;
}
if (currentLength > maxLength) maxLength = currentLength;
}
return maxLength;
}
int main() {
int nums[] = {1, 2, 1, 1, 2, 1, 2};
int length = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxValidSubsequenceLength(nums, length));
return 0;
}using System;
class Solution {
public static int MaxValidSubsequenceLength(int[] nums) {
int maxLength = 0, currentLength = 1;
for (int i = 1; i < nums.Length; i++) {
if ((nums[i] + nums[i - 1]) % 2 == (nums[0] + nums[1]) % 2) {
currentLength++;
} else {
currentLength = 2;
}
maxLength = Math.Max(maxLength, currentLength);
}
return maxLength;
}
static void Main() {
int[] nums = {1, 2, 1, 1, 2, 1, 2};
Console.WriteLine(MaxValidSubsequenceLength(nums));
}
}Use Python's built-in functions to iterate through the array, updating the subsequence length based on pairwise parity.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Dynamic Programming with State Tracking
A dynamic programming approach can be used to track the longest subsequence lengths with different initial parities. Create a DP array where each entry keeps track of the longest subsequence ending at that index.
def max_valid_subsequence_length(nums):
dp = [1] * len(nums)
max_length = 1
for i in range(len(nums)):
for j in range(i):
if (nums[i] + nums[j]) % 2 == (nums[j] + nums[j - 1]) % 2:
dp[i] = dp[j] + 1
max_length = max(max_length, dp[i])
return max_length
nums = [1, 2, 1, 1, 2, 1, 2]
print(max_valid_subsequence_length(nums))public class Solution {
public static int maxValidSubsequenceLength(int[] nums) {
int[] dp = new int[nums.length];
int maxLength = 1;
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if ((nums[i] + nums[j]) % 2 == (nums[j] + nums[j - 1]) % 2) {
dp[i] = dp[j] + 1;
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
public static void main(String[] args) {
int[] nums = {1, 2, 1, 1, 2, 1, 2};
System.out.println(maxValidSubsequenceLength(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxValidSubsequenceLength(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int maxLength = 1;
for (size_t i = 1; i < nums.size(); i++) {
for (size_t j = 0; j < i; j++) {
if ((nums[i] + nums[j]) % 2 == (nums[j] + nums[j - 1]) % 2) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > maxLength) maxLength = dp[i];
}
return maxLength;
}
int main() {
vector<int> nums = {1, 2, 1, 1, 2, 1, 2};
cout << maxValidSubsequenceLength(nums) << endl;
return 0;
}function maxValidSubsequenceLength(nums) {
const dp = Array(nums.length).fill(1);
let maxLength = 1;
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if ((nums[i] + nums[j]) % 2 === (nums[j] + nums[j - 1]) % 2) {
dp[i] = dp[j] + 1;
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
const nums = [1, 2, 1, 1, 2, 1, 2];
console.log(maxValidSubsequenceLength(nums));#include <stdio.h>
int maxValidSubsequenceLength(int* nums, int size) {
int dp[size];
int maxLength = 1;
for (int i = 0; i < size; i++) {
dp[i] = 1; // Minimum length is the element itself
for (int j = 0; j < i; j++) {
if ((nums[i] + nums[j]) % 2 == (nums[j] + nums[j - 1]) % 2) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > maxLength) maxLength = dp[i];
}
return maxLength;
}
int main() {
int nums[] = {1, 2, 1, 1, 2, 1, 2};
int length = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxValidSubsequenceLength(nums, length));
return 0;
}using System;
class Solution {
public static int MaxValidSubsequenceLength(int[] nums) {
int[] dp = new int[nums.Length];
Array.Fill(dp, 1);
int maxLength = 1;
for (int i = 0; i < nums.Length; i++) {
for (int j = 0; j < i; j++) {
if ((nums[i] + nums[j]) % 2 == (nums[j] + nums[j - 1]) % 2) {
dp[i] = dp[j] + 1;
}
}
maxLength = Math.Max(maxLength, dp[i]);
}
return maxLength;
}
static void Main() {
int[] nums = {1, 2, 1, 1, 2, 1, 2};
Console.WriteLine(MaxValidSubsequenceLength(nums));
}
}Pythonic DP solution, leveraging list indexing to accurately derive each valid subsequence maximum length per index.
Time Complexity: O(n^2)
Space Complexity: O(n)
Approach 3: Dynamic Programming
We set k = 2.
Based on the problem description, we know that for a subsequence a_1, a_2, a_3, cdots, a_x, if it satisfies (a_1 + a_2) bmod k = (a_2 + a_3) bmod k. Then a_1 bmod k = a_3 bmod k. This means that the result of taking modulo k for all odd-indexed elements is the same, and the result for all even-indexed elements is the same as well.
We can solve this problem using dynamic programming. Define the state f[x][y] as the length of the longest valid subsequence where the last element modulo k equals x, and the second to last element modulo k equals y. Initially, f[x][y] = 0.
Iterate through the array nums, and for each number x, we get x = x bmod k. Then, we can enumerate the sequences where two consecutive numbers modulo j yield the same result, where j \in [0, k). Thus, the previous number modulo k would be y = (j - x + k) bmod k. At this point, f[x][y] = f[y][x] + 1.
The answer is the maximum value among all f[x][y].
The time complexity is O(n times k), and the space complexity is O(k^2). Here, n is the length of the array nums, and k=2.
function maximumLength(nums: number[]): number {
const k = 2;
const f: number[][] = Array.from({ length: k }, () => Array(k).fill(0));
let ans: number = 0;
for (let x of nums) {
x %= k;
for (let j = 0; j < k; ++j) {
const y = (j - x + k) % k;
f[x][y] = f[y][x] + 1;
ans = Math.max(ans, f[x][y]);
}
}
return ans;
}func maximumLength(nums []int) (ans int) {
k := 2
f := make([][]int, k)
for i := range f {
f[i] = make([]int, k)
}
for _, x := range nums {
x %= k
for j := 0; j < k; j++ {
y := (j - x + k) % k
f[x][y] = f[y][x] + 1
ans = max(ans, f[x][y])
}
}
return
}impl Solution {
pub fn maximum_length(nums: Vec<i32>) -> i32 {
let mut f = [[0; 2]; 2];
let mut ans = 0;
for x in nums {
let x = (x % 2) as usize;
for j in 0..2 {
let y = ((j + 2 - x) % 2) as usize;
f[x][y] = f[y][x] + 1;
ans = ans.max(f[x][y]);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Pairwise Checking | Time Complexity: O(n) |
| Dynamic Programming with State Tracking | Time Complexity: O(n^2) |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Approach with Pairwise Checking | O(n) | O(1) | Best for production and interviews. Uses parity counting and simple iteration. |
| Dynamic Programming with State Tracking | O(n) | O(1) | Useful for understanding subsequence transitions and generalizing similar DP problems. |
Frequently asked questions
Is Find the Maximum Length of Valid Subsequence I easy or hard?
The problem is rated Medium because the constraint on pair sums is not immediately obvious. Once you recognize that parity determines whether sums are even or odd, the solution simplifies to a greedy counting strategy or a small dynamic programming formulation.
Find the Maximum Length of Valid Subsequence I Python/Java solution
Python, Java, C++, and similar languages implement the same logic: iterate through the array, compute each number's parity, and update counts or DP states. The algorithm remains O(n) time and O(1) space regardless of language.
How to solve Find the Maximum Length of Valid Subsequence I in O(n)?
Iterate through the array and track the parity (even or odd) of each element. Use counts of even and odd numbers to evaluate two possibilities: a subsequence where all elements share the same parity, or one that alternates parity so every pair sum has consistent parity. The maximum of these lengths is the answer.
What is the best approach for Find the Maximum Length of Valid Subsequence I?
The greedy parity-based approach is the most efficient solution. Count how many even and odd numbers appear in the array and construct either a same-parity subsequence or an alternating-parity subsequence. This runs in O(n) time with O(1) extra space and avoids building full dynamic programming tables.
Is Find the Maximum Length of Valid Subsequence I asked at Google/Amazon/Meta?
Parity-based array and subsequence problems frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary in wording, the underlying concepts—parity reasoning, subsequences, and dynamic programming—are common interview patterns.
What data structure is used in Find the Maximum Length of Valid Subsequence I?
The solution mainly uses simple counters and parity checks on an array. No advanced data structures are required. The dynamic programming variation keeps a few constant-sized states to track subsequence transitions.
What is the time complexity of Find the Maximum Length of Valid Subsequence I?
The optimal solution runs in O(n) time because the array is scanned once to determine element parity and compute the best subsequence length. Space complexity is O(1) since only a few counters or small DP states are maintained.