LeetCode 523: Continuous Subarray Sum

Try all subarrays

A subarray has a start index and an end index. With all possible starts and ends we check if the sum is a multiple of $k$ .

Time: $\mathcal{O}(n^2)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        for begin in range(n):
            sub_sum = nums[begin]
            for end in range(begin+1, n):
                sub_sum += nums[end]
                if sub_sum % k == 0:
                    return True
        
        return False

Prefix sums

Say $S(j, k) = \sum_{i=j}^k \texttt{nums}[i]$ is the sum of the subarray nums[j : k+1]. Then, it would be a good subarray if $S(j, k) = 0 \ (\text{mod } k)$ . Now, $S(j, k) = S(0, k) - S(0, j-1)$ . So, for a good subarray, $S(0, k) - S(0, j-1) = 0\ (\text{mod } k)$ , or, $S(0, k) = S(0, j-1) \ (\text{mod } k)$ . If we keep track of prefix-sums (mod $k$ ) of nums, for a good subarray we should find a prefix-sum that we have seen before.

There are $k$ distinct mod_sum‘s. So, time: $\mathcal{O}(n)$ , space: $\mathcal{O}( \max{(k, n)} )$ .

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        # If a prefix sum is 0,
        # it is a candidate for good subarray.
        # So, lets mark 0 as seen.
        seen = {0: -1}
        sum = 0
        for i in range(n):
            sum += nums[i]
            mod_sum = sum % k
            
            # Good subarray should be longer.
            # So we remember the earliest index.
            if mod_sum not in seen:
                seen[mod_sum] = i
                continue
            
            # Length at least 2
            if (i - seen[mod_sum]) > 1:
                return True
        
        return False

unreasonably effective