Problem Statement in English

You’re given an array nums of positive integers and a positive integer p.

Find the shortest subarray that you can remove from the array such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

If there is no such subarray, return -1.

Approach

You will need to have solved similar problems on subarrays divisible by k, and some variants like 974. Subarray Sums Divisible by K and 3381. Maximum Subarray Sum With Length Divisible by K before attempting this one.

The idea is then very similar - we still use the same prefix sum strategy with a hashmap to store the prefix sums modulo p.

But since the twist in this question is that we want to remove the shortest possible subarray that will make the sum of the remaining elements in nums divisible by p, that means we’ll need to remove the longest possible subarray that we’ve already seen whose sum modulo p when removed from the current prefix sum modulo p will give us the same value as sum(nums) % p.

If we ever need to remove 0 from the current prefix sum, that means the current subarray is the one we need to remove. That’s why we initialize the hashmap with {0: -1}.

Solution in Python


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        s = sum(nums)
        if s % p == 0:
            return 0

        # this is the remainder we need to remove from the array 
        # to make the sum divisible by p
        target = s % p

        hm = {0: -1}
        res = inf
        curr = 0

        for i, num in enumerate(nums):
            # current prefix sum modulo p
            curr = (curr + num) % p

            # what we need to subtract from curr 
            # to get target when we take mod p
            need = (curr - target) % p

            if need in hm:
                # it is guaranteed that the index in the hashmap 
                # will be the longest possible that we have seen so far
                res = min(res, i - hm[need])

            # store the current prefix sum modulo p
            # since it is the latest index, it will be the longest possible
            hm[curr] = i

        return res if res < inf else -1

Complexity

  • Time: $O(n)$
    Since we iterate through the array once.

  • Space: $O(p)$
    We use a hashmap to store the prefix sums modulo p.

Mistakes I Made

I botched the calculation of the required prefix sum modulo p initially, which led to incorrect results. After correcting that, the solution worked as expected.

And we are done.