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 <= 103Use 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.
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.
C
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.
| 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. |
Longest Increasing Subsequence - Dynamic Programming - Leetcode 300 • NeetCode • 432,482 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