Skip to main content
Talentd

Find the Maximum Length of Valid Subsequence II - Solution & Explanation

MediumArrayDynamic Programming15 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

You are given an integer array 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.
Return the length of the longest valid subsequence of 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 <= 103
  • 1 <= nums[i] <= 107
  • 1 <= k <= 103

Approach Overview

Problem 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.

Approach 1: Prefix Sum and Modulo Grouping

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Frequency Map for Remainder Conditions

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.

Code

JavaC

Java

C

Complexity

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.

Try this approach in the editor →

Approach 3: Dynamic Programming

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.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sum and Modulo Grouping

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.

Frequency Map for Remainder Conditions

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.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 ConditionsO(n + k^2)O(k)Useful when focusing on remainder compatibility and counts rather than element positions

Video Solution

Find the Maximum Length of Valid Subsequence | Part I | Part II | Leetcode 3201 | 3202 | MIK • codestorywithMIK • 14,796 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Maximum Length of Valid Subsequence II easy or hard?
Find the Maximum Length of Valid Subsequence II is generally classified as a Medium problem. The challenge comes from recognizing that the pair condition can be rewritten using modulo arithmetic and then modeled as a dynamic programming transition between remainder states.
Find the Maximum Length of Valid Subsequence II Python/Java solution
Python, Java, JavaScript, and C implementations typically follow the same idea: compute num % k, maintain DP states for valid remainder transitions, and update the longest subsequence length while scanning the array. The algorithm runs in O(n * k) time and O(k) space.
How to solve Find the Maximum Length of Valid Subsequence II in O(n)?
Strict O(n) is difficult because the target remainder can be any value from 0 to k-1. Most optimized implementations achieve O(n * k) by maintaining DP states for remainder transitions. Each element updates at most k states, which is efficient when k is small relative to n.
What is the best approach for Find the Maximum Length of Valid Subsequence II?
The most reliable approach uses dynamic programming with modulo grouping. Convert each number to its remainder modulo k and track the longest subsequence that satisfies a fixed target remainder for adjacent pair sums. This approach runs in O(n * k) time and O(k) space because transitions only depend on remainder classes rather than the full values.
Is Find the Maximum Length of Valid Subsequence II asked at Google/Amazon/Meta?
Problems involving modulo constraints, subsequences, and dynamic programming are common in interviews at companies like Google, Amazon, and Meta. While this exact problem may appear on platforms like LeetCode, its underlying pattern—modulo-based DP transitions—frequently appears in technical interviews.
What data structure is used in Find the Maximum Length of Valid Subsequence II?
The solution primarily uses arrays or hash maps to store counts or DP states for each remainder modulo k. These structures allow constant-time lookup when determining which remainder can extend the current subsequence.
What is the time complexity of Find the Maximum Length of Valid Subsequence II?
The typical dynamic programming solution runs in O(n * k) time, where n is the length of the array and k is the modulo value. Space complexity is O(k) since only remainder states are stored. Alternative remainder-frequency approaches may run in O(n + k^2) time.

Ready to solve this problem?

Practice Find the Maximum Length of Valid Subsequence II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Length of the Longest Subsequence That Sums to Target

Next

Longest Increasing Subsequence