Find the Maximum Length of Valid Subsequence II

Find the Maximum Length of Valid Subsequence II - Problem

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.

Input & Output

Example 1 — Basic Valid Subsequence

$ Input: nums = [1,2,3,4], k = 3

› Output: 4

💡 Note: The subsequence [1,2,3,4] is valid: (1+2)%3=0, (2+3)%3=2, (3+4)%3=1. Wait, this doesn't work. Let me recalculate. Actually [1,4] works: we only have one pair (1+4)%3=2, so length=2.

Example 2 — Single Element

$ Input: nums = [1], k = 2

› Output: 1

💡 Note: Single element subsequence [1] is valid by definition, length=1

Example 3 — Multiple Valid Pairs

$ Input: nums = [1,2,1,2], k = 2

› Output: 4

💡 Note: The subsequence [1,2,1,2] is valid: (1+2)%2=1, (2+1)%2=1, (1+2)%2=1. All consecutive pairs have same remainder.

Constraints

1 ≤ nums.length ≤ 10³
1 ≤ nums[i] ≤ 10⁶
2 ≤ k ≤ 10³

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and modulus k

Process

Find subsequence where consecutive pair sums have same remainder

Output

Length of longest valid subsequence

Key Takeaway

🎯 Key Insight: Use DP to track longest sequences by remainder pairs, avoiding exponential subsequence enumeration

Asked in

G Google 25 M Meta 20 A Amazon 18 M Microsoft 15

The key insight is to use dynamic programming to track the longest valid subsequence ending with each pair of remainders. The optimal approach uses a 2D DP table where dp[i][j] represents the longest subsequence ending with remainders i and j. Time: O(n × k²), Space: O(k²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subsequences	O(2^n × n)	O(n)	Generate all possible subsequences and check validity
Optimized DP with Better State Management	O(n × k²)	O(k²)	Improved DP approach with cleaner state transitions and better space usage
Dynamic Programming - Track Remainder Pairs	O(n × k²)	O(k²)	Use 2D DP to track longest sequences ending with each remainder pair

Brute Force - Try All Subsequences — Algorithm Steps

Generate all 2^n subsequences
For each subsequence, check if consecutive pairs have same (a+b)%k
Return length of longest valid subsequence

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible subsequences

Validate

Check if consecutive pairs have same modulo

Track

Keep track of longest valid subsequence

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    int maxLength = 0;
    
    // Try all possible subsequences using bit manipulation
    for (int mask = 1; mask < (1 << numsSize); mask++) {
        int subsequence[1000];
        int subLen = 0;
        
        for (int i = 0; i < numsSize; i++) {
            if (mask & (1 << i)) {
                subsequence[subLen++] = nums[i];
            }
        }
        
        if (subLen < 2) {
            if (subLen > maxLength) {
                maxLength = subLen;
            }
            continue;
        }
        
        // Check if subsequence is valid
        int isValid = 1;
        int targetMod = (subsequence[0] + subsequence[1]) % k;
        
        for (int i = 1; i < subLen - 1; i++) {
            if ((subsequence[i] + subsequence[i + 1]) % k != targetMod) {
                isValid = 0;
                break;
            }
        }
        
        if (isValid && subLen > maxLength) {
            maxLength = subLen;
        }
    }
    
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strcmp(token, "\n") != 0) {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n)

Generate 2^n subsequences, each takes O(n) time to validate

⚠ Quadratic Growth

Space Complexity

O(n)

Store current subsequence during generation

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler