nums and a positive integer k.
A subsequence sub of nums with length x is called valid if it satisfies:
(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k.nums.
Example 1:
Input: nums = [1,2,3,4,5], k = 2
Output: 5
Explanation:
The longest valid subsequence is [1, 2, 3, 4, 5].
Example 2:
Input: nums = [1,4,2,3,1,4], k = 3
Output: 4
Explanation:
The longest valid subsequence is [1, 4, 1, 4].
Constraints:
2 <= nums.length <= 1031 <= nums[i] <= 1071 <= k <= 103Problem Overview: You are given an integer array and a value k. The goal is to build the longest subsequence such that every adjacent pair in the subsequence has the same remainder when their sum is taken modulo k. Order must follow the original array, so the problem becomes finding the longest valid chain of elements whose pairwise modulo condition stays constant.
Approach 1: Prefix Sum and Modulo Grouping (Dynamic Programming) (Time: O(n * k), Space: O(k))
The key observation is that the condition (a + b) % k = target can be rewritten using remainders. If a % k = r, then the next element must have remainder (target - r + k) % k. Iterate through the array and reduce each number to its remainder modulo k. For every possible target remainder 0..k-1, maintain a small DP structure that tracks the longest subsequence ending with each remainder. When you process a new element, compute the required previous remainder that would satisfy the pair condition and extend that subsequence by one. This effectively turns the problem into remainder transitions rather than raw value comparisons. The method works well because the modulo range is limited to k, making the DP compact. This approach directly uses ideas from dynamic programming and remainder grouping from array problems.
Approach 2: Frequency Map for Remainder Conditions (Time: O(n + k^2), Space: O(k))
Another way to view the problem is through remainder frequencies. Convert every value to num % k and count how often each remainder appears. For a fixed target value t, a valid adjacent pair must satisfy (r1 + r2) % k = t. This means remainder r1 pairs with (t - r1 + k) % k. Iterate through all possible target remainders and simulate building the longest alternating chain of compatible remainders using the frequency map. Each step extends the sequence by consuming counts of matching remainders. Because only k remainder classes exist, exploring all pair relationships costs O(k^2). This approach is easier to reason about when you focus on remainder compatibility rather than element positions and relies on constant-time lookups with a hash map or frequency array, a common pattern in hash map based solutions.
Recommended for interviews: The dynamic programming remainder-transition approach is what most interviewers expect. It shows you can transform a numeric constraint into a state transition over modulo classes. Mentioning the brute reasoning about pair remainders demonstrates understanding, but implementing the DP efficiently demonstrates stronger algorithmic thinking.
Use the prefix sum technique and modulo operation to find common remainders. By converting the problem into grouping numbers by their mod results, you can efficiently find the longest subsequence that meets the condition.
This solution uses a dictionary to count how many times each remainder occurs when progressively adding elements of the array and taking modulo k. The maximum count of a remainder signals the longest subsequence satisfying the condition.
Python
JavaScript
Time Complexity: O(n), where n is the length of the nums array.
Space Complexity: O(k), since at most k unique remainders will be stored.
Use a frequency map to group numbers by the remainder of their sums when divided by k. This allows finding sequences that have consistent remainder values.
This solution maps integers to their remainder counts from prefix sums. By iterating through the array, it accumulates these counts and finds the highest frequency of the same remainder, which indicates the longest valid subsequence.
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(k), as at most k different remainder counts need to be stored.
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 is the given positive integer.
| Approach | Complexity |
|---|---|
| Prefix Sum and Modulo Grouping | Time Complexity: O(n), where n is the length of the nums array. |
| Frequency Map for Remainder Conditions | Time Complexity: O(n), where n is the number of elements in nums. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum and Modulo Grouping (DP) | O(n * k) | O(k) | General case when processing elements in order and extending subsequences dynamically |
| Frequency Map for Remainder Conditions | O(n + k^2) | O(k) | Useful when focusing on remainder compatibility and counts rather than element positions |
Find the Maximum Length of Valid Subsequence | Part I | Part II | Leetcode 3201 | 3202 | MIK • codestorywithMIK • 14,456 views views
Watch 9 more video solutions →Practice Find the Maximum Length of Valid Subsequence II with our built-in code editor and test cases.
Practice on FleetCode