Problem Description

You are given an integer array nums and a positive integer k.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

A subsequence sub of length x is considered valid if it satisfies the following condition:

• The sum of every pair of consecutive elements has the same remainder when divided by k
• In other words: (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k

Your task is to find the length of the longest valid subsequence of nums.

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

• (a + b) % 5 equals (b + c) % 5 equals (c + d) % 5

The key insight is that if (a + b) % k = (b + c) % k, then a % k = c % k. This means in a valid subsequence, all elements at odd positions have the same remainder when divided by k, and all elements at even positions have the same remainder when divided by k.

The solution uses dynamic programming where f[x][y] represents the length of the longest valid subsequence where the last element has remainder x when divided by k, and the second-to-last element has remainder y when divided by k. For each element in the array, we update the DP table by considering it as the next element in subsequences with different remainder patterns.

Intuition

Let's start by understanding what makes a subsequence valid. When we have consecutive pairs with the same sum modulo k, there's a hidden pattern.

Consider three consecutive elements a, b, c in a valid subsequence. We need:

• (a + b) % k = (b + c) % k

Expanding this equation:

• (a + b) % k = (b + c) % k
• This means a + b ≡ b + c (mod k)
• Subtracting b from both sides: a ≡ c (mod k)

This reveals a crucial pattern: elements at positions 0, 2, 4, ... must all have the same remainder when divided by k, and elements at positions 1, 3, 5, ... must also have the same remainder when divided by k.

So a valid subsequence alternates between two remainder values. For example, if the remainders are r1 and r2, the pattern would be: r1, r2, r1, r2, r1, r2, ...

Now, how do we find the longest such subsequence? We need to track:

1. What are the last two remainder values we've seen?
2. How long is the subsequence ending with these two remainders?

This naturally leads to a dynamic programming approach where we maintain f[x][y] representing the length of the longest subsequence where:

• The last element has remainder x
• The second-to-last element has remainder y

When we encounter a new element with remainder x, we can extend any subsequence ending with (..., y, x) to (..., y, x, y). But wait - the new subsequence would end with (x, y), not (y, x). So we update f[x][y] based on f[y][x].

The constraint that consecutive sums must have the same remainder modulo k is automatically satisfied because we're alternating between the same two remainders throughout the subsequence.

Learn more about Dynamic Programming patterns.

Solution Approach

Based on our intuition that valid subsequences alternate between two remainder values, we implement a dynamic programming solution.

State Definition: We define a 2D DP table f[x][y] where:

• x represents the remainder of the last element when divided by k
• y represents the remainder of the second-to-last element when divided by k
• f[x][y] stores the length of the longest valid subsequence ending with these two remainders

Initialization:

f = [[0] * k for _ in range(k)]

We create a k × k matrix initialized with zeros since initially there are no subsequences.

Transition: For each element in nums:

1. First, we compute its remainder: x = nums[i] % k
2. For each possible remainder j from 0 to k-1, we calculate what the previous remainder y should be
3. The key insight: if we want consecutive pairs to sum to j modulo k, and the current element has remainder x, then the previous element must have remainder y = (j - x + k) % k
4. We update: f[x][y] = f[y][x] + 1

The update f[x][y] = f[y][x] + 1 works because:

• f[y][x] represents a subsequence ending with ...y, x
• Adding the current element x creates a subsequence ...y, x, y
• This new subsequence ends with (x, y), so we store it in f[x][y]

Example Walkthrough: If k = 3 and we process an element with remainder x = 2:

• For j = 0: Previous remainder must be y = (0 - 2 + 3) % 3 = 1
  • Update f[2][1] = f[1][2] + 1
• For j = 1: Previous remainder must be y = (1 - 2 + 3) % 3 = 2
  • Update f[2][2] = f[2][2] + 1
• For j = 2: Previous remainder must be y = (2 - 2 + 3) % 3 = 0
  • Update f[2][0] = f[0][2] + 1

Final Answer: We track the maximum value across all f[x][y] throughout the process, which gives us the length of the longest valid subsequence.

The time complexity is O(n × k) where n is the length of the array, and space complexity is O(k²) for the DP table.

Example Walkthrough

Let's walk through a concrete example with nums = [1, 4, 2, 3, 1, 4] and k = 3.

Step 1: Initialize DP table

f = [[0, 0, 0],
     [0, 0, 0],
     [0, 0, 0]]

Step 2: Process nums[0] = 1 (remainder = 1) For each possible sum remainder j:

• j=0: y = (0-1+3)%3 = 2, update f[1][2] = f[2][1] + 1 = 0 + 1 = 1
• j=1: y = (1-1+3)%3 = 0, update f[1][0] = f[0][1] + 1 = 0 + 1 = 1
• j=2: y = (2-1+3)%3 = 1, update f[1][1] = f[1][1] + 1 = 0 + 1 = 1

DP table becomes:

f = [[0, 1, 0],
     [1, 1, 1],
     [0, 0, 0]]

Step 3: Process nums[1] = 4 (remainder = 1)

• j=0: y = 2, update f[1][2] = f[2][1] + 1 = 0 + 1 = 1
• j=1: y = 0, update f[1][0] = f[0][1] + 1 = 1 + 1 = 2
• j=2: y = 1, update f[1][1] = f[1][1] + 1 = 1 + 1 = 2

DP table becomes:

f = [[0, 2, 0],
     [2, 2, 1],
     [0, 0, 0]]

Step 4: Process nums[2] = 2 (remainder = 2)

• j=0: y = 1, update f[2][1] = f[1][2] + 1 = 1 + 1 = 2
• j=1: y = 2, update f[2][2] = f[2][2] + 1 = 0 + 1 = 1
• j=2: y = 0, update f[2][0] = f[0][2] + 1 = 0 + 1 = 1

DP table becomes:

f = [[0, 2, 1],
     [2, 2, 2],
     [1, 2, 1]]

Step 5: Process nums[3] = 3 (remainder = 0)

• j=0: y = 0, update f[0][0] = f[0][0] + 1 = 0 + 1 = 1
• j=1: y = 1, update f[0][1] = f[1][0] + 1 = 2 + 1 = 3
• j=2: y = 2, update f[0][2] = f[2][0] + 1 = 1 + 1 = 2

DP table becomes:

f = [[1, 3, 2],
     [2, 2, 2],
     [1, 2, 1]]

Step 6: Process nums[4] = 1 (remainder = 1)

• j=0: y = 2, update f[1][2] = f[2][1] + 1 = 2 + 1 = 3
• j=1: y = 0, update f[1][0] = f[0][1] + 1 = 3 + 1 = 4
• j=2: y = 1, update f[1][1] = f[1][1] + 1 = 2 + 1 = 3

DP table becomes:

f = [[1, 4, 2],
     [4, 3, 3],
     [1, 2, 1]]

Step 7: Process nums[5] = 4 (remainder = 1)

• j=0: y = 2, update f[1][2] = f[2][1] + 1 = 2 + 1 = 3
• j=1: y = 0, update f[1][0] = f[0][1] + 1 = 4 + 1 = 5
• j=2: y = 1, update f[1][1] = f[1][1] + 1 = 3 + 1 = 4

Final DP table:

f = [[1, 5, 2],
     [5, 4, 3],
     [1, 2, 1]]

Result: The maximum value in the table is 5, which represents the longest valid subsequence.

This subsequence could be [1, 3, 1, 3, 1] (indices 0, 3, 4, and we'd need more elements), where:

• Remainders alternate: 1, 0, 1, 0, 1
• All consecutive sums: (1+3)%3 = 1, (3+1)%3 = 1, etc., giving the same remainder

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × k) where n is the length of the array nums and k is the given positive integer.

The analysis breaks down as follows:

• The outer loop iterates through all n elements in nums
• For each element, the inner loop runs k times (iterating through all possible values of j from 0 to k-1)
• Inside the inner loop, all operations (x % k, modular arithmetic calculations, array access and updates, max comparison) are O(1)
• Therefore, the total time complexity is O(n) × O(k) × O(1) = O(n × k)

Space Complexity: O(k²) where k is the given positive integer.

The space analysis is:

• The 2D array f has dimensions k × k, requiring O(k²) space
• The variable ans and loop variables use O(1) additional space
• Therefore, the total space complexity is O(k²)

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

Common Pitfalls

1. Misunderstanding the DP State Update Logic

The Pitfall: A common mistake is incorrectly updating the DP table or misunderstanding why we use f[x][y] = f[y][x] + 1. Developers might think this is a typo or try to "fix" it to f[x][y] = f[x][y] + 1, which would be incorrect.

Why This Happens: The confusion arises because the indices appear swapped. When extending a subsequence ending with (y, x) by adding another element with remainder x, the new subsequence ends with (x, y) - note the order reversal.

The Correct Understanding:

• f[y][x] represents a subsequence like [..., a, b] where a % k = y and b % k = x
• Adding a new element with remainder y creates [..., a, b, c] where c % k = y
• Now the last two elements are b and c with remainders x and y respectively
• So we store this in f[x][y], not f[y][x]

2. Incorrect Calculation of Previous Remainder

The Pitfall: Using y = (j - x) % k instead of y = (j - x + k) % k when calculating the required previous remainder.

Why This Fails: In Python, the modulo operation can return negative values when the dividend is negative. For example, (-1) % 3 = 2 in Python, but we might expect 2 only after adding k to ensure a positive result.

The Solution: Always add k before taking modulo to ensure the result is in the range [0, k-1]:

prev_mod = (target_sum - current_mod + k) % k

3. Not Handling Single-Element Subsequences

The Pitfall: The DP initialization starts with all zeros, which means single-element subsequences aren't counted initially. The algorithm relies on the update process to handle them.

Why It Still Works: When processing an element with remainder x, one of the iterations will have y = x (when j = 2x % k). This updates f[x][x] = f[x][x] + 1, effectively counting single-element subsequences.

Potential Issue: If you modify the algorithm without understanding this implicit handling, you might break the single-element case. Always verify that your solution correctly handles subsequences of length 1.

4. Forgetting to Track the Maximum

The Pitfall: Returning max(max(row) for row in f) at the end instead of tracking the maximum throughout the process.

Why This Matters: The DP table gets overwritten as we process elements. The maximum length subsequence might not be represented in the final state of the table because later updates might overwrite earlier, longer subsequences.

The Correct Approach:

max_length = 0
for num in nums:
    # ... update logic ...
    max_length = max(max_length, f[x][y])
return max_length

5. Misunderstanding the Problem Constraint

The Pitfall: Thinking that ALL consecutive pairs in the entire array must have the same sum modulo k, rather than understanding it's about finding a subsequence with this property.

The Clarification: We're selecting elements from the array (maintaining order) to form a subsequence where the constraint holds, not checking if the original array satisfies the constraint.