Skip to content

← leetcode

Find the Maximum Length of Valid Subsequence II

· Medium

LeetCode problem 3202

The intuition for this algorithm is that since

(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k

had to be true, that implies that the sum of any adjacent values in a valid subsequence must be equal to a value between 0 and k-1 inclusive.

Therefore, we can iterate through all possible values of sums between 0 and k-1 inclusive and find the maximum subsequence length given a possible sum.

code

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        int ans = 0;
        for (int& num : nums) {
            num %= k;
        }

        vector<int> dp (k);
        for (int i = 0; i < k; ++i) {
            fill(dp.begin(), dp.end(), 0);
            for (int& num : nums) {
                dp[num] = dp[(k + i - num) % k] + 1;
                ans = max(ans, dp[num % k]);
            }
        }

        return ans;
    }
};

complexity

  • Time: O(n*k) where n is the number of elements inside nums and k is just the input value k
  • Space: O(k)

learnings

  • its better to precompute modulo k for every element

time taken

  • 5 hours, 21 minutes and 33 seconds
    • I left the timer running-