Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

If the total has remainder target, the removed subarray must have that same remainder. A subarray's remainder is the difference of its two prefix remainders. For each current prefix, remembering the latest matching earlier prefix gives the shortest removal ending here.

Approach

Return zero if the total is already divisible by p. Otherwise scan prefix remainders, starting with remainder zero at index -1. For current remainder r, look up (r - target) mod p, normalized to a nonnegative remainder, and minimize the distance to its saved index. Then overwrite the current remainder's index with the latest position. Return -1 if the best removal is still the whole array, which the rules forbid.

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        target = sum(nums) % p

        if target == 0:
            return 0

        pr = 0
        seen = {0: -1}
        res = n

        for i in range(n):
            pr = (pr + nums[i]) % p
            # (pr - p1) % p = target
            p1 = (pr - target) % p
            if p1 in seen:
                res = min(res, i - seen[p1])
            seen[pr] = i

        return res if res != n else -1

Complexity analysis

For n numbers, both displayed implementations take O(n) time and use O(min(n, p)) auxiliary space for distinct prefix remainders.