Scale Engineer

Find the Maximum Length of Valid Subsequence II

Med
#2844Time: O(k^2 * N), where N is the number of elements in `nums` and k is the given integer. There are two nested loops for the remainder pairs (`k*k` iterations) and an inner loop that scans the entire `nums` array (N iterations).Space: O(1), as it only uses a few variables to track the lengths and remainders.
Patterns
Dynamic Programming
Data structures
Array

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This brute-force approach is based on a key observation about the structure of a valid subsequence. If a subsequence sub is valid, then (sub[i-1] + sub[i]) % k must be constant for all i. This implies that the sequence of remainders modulo k of the elements in sub must be alternating. For example, the remainders must follow a pattern like r1, r2, r1, r2, ....

The algorithm leverages this by trying every possible pair of remainders (r1, r2). For each of the k*k pairs, it iterates through the input array nums to find the longest subsequence that fits the alternating pattern. While simple to conceptualize, this method is computationally expensive due to its three nested loops.

Algorithm

  1. The fundamental insight is that for a subsequence to be valid, the remainders of its elements modulo k must form an alternating sequence, such as r1, r2, r1, r2, ....
  2. This approach iterates through every possible pair of starting remainders, (rem1, rem2), where 0 <= rem1, rem2 < k.
  3. For each pair, it performs a linear scan through the nums array.
  4. During the scan, it greedily builds the longest possible subsequence that adheres to the alternating rem1, rem2 pattern.
  5. It keeps a counter for the current subsequence length and tracks which remainder is needed next.
  6. The global maximum length found across all k*k pairs is the result.

Walkthrough

The algorithm works by exhaustively checking all possibilities for the two alternating remainders.

  • First, we establish that any valid subsequence must have elements whose remainders modulo k alternate between two values, say rem1 and rem2. This includes the case where rem1 == rem2, which corresponds to a subsequence where all elements have the same remainder.
  • We initialize a variable maxLength to 1, as any single element is a valid subsequence.
  • We then set up two nested loops, one for rem1 from 0 to k-1 and another for rem2 from 0 to k-1.
  • Inside these loops, for each pair (rem1, rem2), we find the length of the longest valid subsequence with this specific alternating remainder pattern. We do this by iterating through nums, keeping track of the neededRem (which starts as rem1 and flips to rem2 and back) and a currentLength.
  • If an element nums[i] has the neededRem, we increment currentLength and update neededRem to the other remainder in the pair.
  • After checking all numbers for a given (rem1, rem2) pair, we update maxLength = max(maxLength, currentLength).
  • Finally, after checking all k*k pairs, maxLength will hold the answer.
class Solution {    public int maximumLength(int[] nums, int k) {        int n = nums.length;        if (n <= 2) {            return n;        }        int maxLength = 0;         // Case where all elements have the same remainder        for (int rem = 0; rem < k; rem++) {            int count = 0;            for (int num : nums) {                if (num % k == rem) {                    count++;                }            }            maxLength = Math.max(maxLength, count);        }         // Case where remainders alternate between rem1 and rem2        for (int rem1 = 0; rem1 < k; rem1++) {            for (int rem2 = 0; rem2 < k; rem2++) {                if (rem1 == rem2) continue;                                int currentLength = 0;                int neededRem = rem1;                for (int num : nums) {                    if (num % k == neededRem) {                        currentLength++;                        // Flip the needed remainder                        neededRem = (neededRem == rem1) ? rem2 : rem1;                    }                }                maxLength = Math.max(maxLength, currentLength);            }        }        return maxLength;    }}

Complexity

Time

O(k^2 * N), where N is the number of elements in `nums` and k is the given integer. There are two nested loops for the remainder pairs (`k*k` iterations) and an inner loop that scans the entire `nums` array (N iterations).

Space

O(1), as it only uses a few variables to track the lengths and remainders.

Trade-offs

Pros

  • The logic is straightforward once the alternating remainder property is understood.

  • It has a very low space complexity, O(1).

Cons

  • The time complexity of O(k^2 * N) is too high for the given constraints (N, k <= 1000), which will result in a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution {public  int maximumLength(int[] nums, int k) {    int[][] f = new int[k][k];    int ans = 0;    for (int x : nums) {      x %= k;      for (int j = 0; j < k; ++j) {        int y = (j - x + k) % k;        f[x][y] = f[y][x] + 1;        ans = Math.max(ans, f[x][y]);      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem