Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Fix the common remainder x of adjacent-pair sums. If the current value has remainder r, its predecessor must have remainder (x - r) mod k. The best subsequence can therefore be tracked using only its final remainder, rather than its entire sequence.

Approach

Try every target remainder x from zero through k - 1. For that target, scan the array with a map whose entry for each remainder stores the longest valid subsequence ending there. For a current remainder r, replace its entry with the previous value for (x - r) mod k plus one, treating missing entries as zero. Update the overall maximum.

The previous value is read before the assignment, so the current element is used only once even when both remainders are equal. For distinct complementary remainders, their best lengths evolve monotonically as occurrences arrive, so the new extension cannot shorten the existing state. Trying all target remainders covers every possible valid subsequence.

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        res = 0

        for x in range(k):
            map = defaultdict(int)
            # (a, b) % k == x
            # (a % k + b % k) % k == x
            # b % k == (x - a % k) % k
            for num in nums:
                num %= k
                # To extend a subsequence with current num, take count of the best subsequence that ends with (x - num) % k and add 1
                map[num] = map[(x - num) % k] + 1
                res = max(res, map[num])

        return res

Complexity analysis

Let n = nums.length. Time: O(n * k). Auxiliary space: O(k) for one residue-state map at a time.