Problem Description

You are given an integer array nums.

A subsequence sub of nums with length x is called valid if it satisfies the following condition:

• (sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2

In other words, when you take consecutive pairs of elements in the subsequence and compute their sum modulo 2, all these results must be equal.

Your task is to 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.

For example, if we have a subsequence [a, b, c, d], it would be valid if:

• (a + b) % 2 = (b + c) % 2 = (c + d) % 2

This means all consecutive pairs in the subsequence must have sums with the same parity (all even or all odd).

Intuition

Let's think about what the constraint (a + b) % 2 = (b + c) % 2 really means.

If (a + b) % 2 = (b + c) % 2, we can expand this:

• (a + b) % 2 = (b + c) % 2
• This means a % 2 + b % 2 and b % 2 + c % 2 have the same parity
• Since b % 2 appears in both sums, for them to have the same parity, we need a % 2 = c % 2

Following this pattern for a longer subsequence [a, b, c, d, e, ...]:

• (a + b) % 2 = (b + c) % 2 implies a % 2 = c % 2
• (b + c) % 2 = (c + d) % 2 implies b % 2 = d % 2
• (c + d) % 2 = (d + e) % 2 implies c % 2 = e % 2

This reveals a pattern: all elements at odd positions (1st, 3rd, 5th...) must have the same parity, and all elements at even positions (2nd, 4th, 6th...) must have the same parity.

Since we're working with modulo 2, each element can only be 0 or 1 after taking modulo. This means we have limited patterns for valid subsequences:

• All odd-positioned elements are 0, all even-positioned elements are 0
• All odd-positioned elements are 0, all even-positioned elements are 1
• All odd-positioned elements are 1, all even-positioned elements are 0
• All odd-positioned elements are 1, all even-positioned elements are 1

To track the longest valid subsequence, we can use dynamic programming where f[x][y] represents the length of the longest valid subsequence ending with the last element having value x % 2 and the second-to-last element having value y % 2. When we encounter a new element with value x % 2, we can extend any valid subsequence ending with y where the pattern (y + x) % 2 matches what we need.

Learn more about Dynamic Programming patterns.

Solution Approach

Based on our intuition, we implement a dynamic programming solution where we track the longest valid subsequences based on the modulo values of the last two elements.

We define f[x][y] as the length of the longest valid subsequence where:

• The last element modulo 2 equals x
• The second-to-last element modulo 2 equals y

Initially, all values in f are set to 0.

Algorithm Steps:

1. Initialize the DP table: Create a 2×2 matrix f since we're working with modulo 2 (k=2).

2. Process each element: For each number in nums:

   • Calculate x = num % 2 to get its parity

3. Update all possible subsequences: For each possible value j from 0 to 1:

   • Calculate what the previous element's modulo value should be: y = (j - x + 2) % 2
   • Here, j represents the target sum modulo value (y + x) % 2 = j
   • Update the DP state: f[x][y] = f[y][x] + 1
   • This means we're extending a subsequence that previously ended with value y and second-to-last value x, by adding the current element with value x

4. Track the maximum: Keep updating the answer with the maximum value found in any f[x][y].

Why the formula y = (j - x + k) % k works:

• We want (y + x) % k = j
• Solving for y: y = (j - x) % k
• Adding k ensures the result is non-negative: y = (j - x + k) % k

Example walkthrough: For nums = [1, 2, 3, 4] with modulo values [1, 0, 1, 0]:

• Processing 1 (x=1): Updates states for possible previous elements
• Processing 2 (x=0): Can extend subsequences ending with appropriate values
• Processing 3 (x=1): Can form valid subsequences like [1,2,3] where odd positions have value 1
• Processing 4 (x=0): Can extend to form [1,2,3,4]

The beauty of this approach is that it automatically handles all four possible patterns (00, 01, 10, 11 for odd/even positions) by tracking all possible last-two-element combinations.

Example Walkthrough

Let's walk through the algorithm with nums = [1, 2, 3, 4].

First, convert to modulo 2: [1, 0, 1, 0]

Initialize f[2][2] = [[0,0], [0,0]] and ans = 0.

Step 1: Process nums[0] = 1 (x = 1)

• For j = 0: y = (0 - 1 + 2) % 2 = 1
  • f[1][1] = f[1][1] + 1 = 0 + 1 = 1
  • This starts a subsequence [1]
• For j = 1: y = (1 - 1 + 2) % 2 = 0
  • f[1][0] = f[0][1] + 1 = 0 + 1 = 1
  • This also starts a subsequence [1]
• Current f: [[0,0], [1,1]], ans = 1

Step 2: Process nums[1] = 2 (x = 0)

• For j = 0: y = (0 - 0 + 2) % 2 = 0
  • f[0][0] = f[0][0] + 1 = 0 + 1 = 1
  • Starts subsequence [2]
• For j = 1: y = (1 - 0 + 2) % 2 = 1
  • f[0][1] = f[1][0] + 1 = 1 + 1 = 2
  • Extends [1] to [1,2] (sum: 1+0=1, odd)
• Current f: [[1,2], [1,1]], ans = 2

Step 3: Process nums[2] = 3 (x = 1)

• For j = 0: y = (0 - 1 + 2) % 2 = 1
  • f[1][1] = f[1][1] + 1 = 1 + 1 = 2
  • Extends some subsequence
• For j = 1: y = (1 - 1 + 2) % 2 = 0
  • f[1][0] = f[0][1] + 1 = 2 + 1 = 3
  • Extends [1,2] to [1,2,3] (sums: 1+0=1, 0+1=1, both odd)
• Current f: [[1,2], [3,2]], ans = 3

Step 4: Process nums[3] = 4 (x = 0)

• For j = 0: y = (0 - 0 + 2) % 2 = 0
  • f[0][0] = f[0][0] + 1 = 1 + 1 = 2
• For j = 1: y = (1 - 0 + 2) % 2 = 1
  • f[0][1] = f[1][0] + 1 = 3 + 1 = 4
  • Extends [1,2,3] to [1,2,3,4] (sums: 1+0=1, 0+1=1, 1+0=1, all odd)
• Final f: [[2,4], [3,2]], ans = 4

The longest valid subsequence is [1,2,3,4] with length 4, where all consecutive pair sums are odd.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × k), where n is the length of the array nums and k = 2.

For each element in nums, we iterate through k possible values (the inner loop with j ranging from 0 to k-1). Since we process all n elements and perform k iterations for each element, the total time complexity is O(n × k). With k = 2, this simplifies to O(2n) = O(n).

The space complexity is O(k²), where k = 2.

The 2D array f is initialized with dimensions k × k, which requires k² space. Since k = 2 is a constant in this code, the space complexity is O(2²) = O(4) = O(1) constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect DP State Update Order

A critical pitfall is updating the wrong DP states or in the wrong order. The code shows dp[remainder][target_remainder] = dp[target_remainder][prev_remainder] + 1, but this can be confusing because we're simultaneously reading from and writing to the DP table.

The Issue: When we update dp[remainder][target_remainder], we might accidentally overwrite a value we need to read later in the same iteration.

Solution: The current implementation is actually correct because for each element, we only update states where the first index is the current element's remainder. Since we're iterating through different prev_remainder values, we won't read and write to the same cell in one iteration.

2. Misunderstanding the Subsequence Validity Condition

Developers often misinterpret what makes a subsequence valid. The condition requires that ALL consecutive pairs have the same sum parity, not that elements alternate in some pattern.

The Issue: Assuming subsequences must follow patterns like [odd, even, odd, even] or [even, odd, even, odd].

Solution: Recognize that valid subsequences can have patterns like:

• All same parity: [1, 3, 5, 7] where all sums are even
• Mixed parities: [1, 2, 3, 4] where consecutive sums alternate but remain consistent

3. Off-by-One Error in Modulo Calculation

The formula target_remainder = (prev_remainder - remainder + modulo) % modulo might be implemented incorrectly.

The Issue: Forgetting to add modulo before taking the modulo operation, which can result in negative values in languages that preserve sign in modulo operations.

Incorrect:

target_remainder = (prev_remainder - remainder) % modulo  # Can be negative!

Correct:

target_remainder = (prev_remainder - remainder + modulo) % modulo

4. Not Handling Edge Cases

The Issue: Not considering arrays with length 1 or 2, where any subsequence is automatically valid.

Solution: The current DP approach naturally handles these cases since:

• A single element forms a valid subsequence of length 1
• Any two elements form a valid subsequence of length 2
• The DP correctly counts these cases

5. Confusion About DP Table Meaning

The Issue: Misinterpreting what dp[i][j] represents. It's NOT the length of subsequences with i odd elements and j even elements.

Clarification: dp[i][j] represents the maximum length of a valid subsequence where:

• The last element has remainder i when divided by 2
• The second-to-last element has remainder j when divided by 2
• All consecutive pairs in this subsequence have the same sum parity