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] <= 107Problem 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.
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.
This code iterates through the array and tracks the parity of sums of each consecutive pair, resetting the subsequence length when the condition is broken.
Time Complexity: O(n) — A single iteration through the array.
Space Complexity: O(1) — Constant space usage.
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.
This DP approach assigns a dp[i] to calculate maximum subsequences ending at each index by checking against all previous indices to count valid pairs.
Time Complexity: O(n^2) — Looping through prior elements for validation.
Space Complexity: O(n) — Storing state for each element.
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.
| Approach | Complexity |
|---|---|
| Greedy Approach with Pairwise Checking | Time Complexity: O(n) — A single iteration through the array. |
| Dynamic Programming with State Tracking | Time Complexity: O(n^2) — Looping through prior elements for validation. |
| Dynamic Programming | — |
| 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. |
Find the Maximum Length of Valid Subsequence I | Detailed Intuition | Leetcode 3201 | MIK • codestorywithMIK • 13,453 views views
Watch 9 more video solutions →Practice Find the Maximum Length of Valid Subsequence I with our built-in code editor and test cases.
Practice on FleetCode