LeetCode 523: Continuous Subarray Sum

Problem Restatement

We are given:

nums
k

We need to determine whether there exists a continuous subarray of length at least 2 whose sum is a multiple of k.

That means we need some subarray sum satisfying:

for some integer n.

Equivalently:

The official problem asks whether such a subarray exists, with the subarray length required to be at least 2. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        ...

Examples

Example 1:

nums = [23, 2, 4, 6, 7]
k = 6

Consider the subarray:

[2, 4]

Its sum is:

2 + 4 = 6

Since:

6 % 6 = 0

the answer is:

True

Example 2:

nums = [23, 2, 6, 4, 7]
k = 6

The whole array sum is:

23 + 2 + 6 + 4 + 7 = 42

Since:

42 % 6 = 0

the answer is:

True

Example 3:

nums = [23, 2, 6, 4, 7]
k = 13

No continuous subarray of length at least 2 has sum divisible by 13.

So the answer is:

False

First Thought: Check Every Subarray

A direct solution is:

1. Generate every subarray
2. Compute its sum
3. Check divisibility by k

There are:

O(n^2)

subarrays.

Even with prefix sums, checking all subarrays still costs:

O(n^2)

We need something faster.

Key Insight

Use prefix sums.

Let:

Then the sum of subarray:

(i + 1) to j

is:

We want this value to be divisible by k.

That means:

Rearranging:

This is the crucial observation.

If two prefix sums have the same remainder modulo k, then the subarray between them has sum divisible by k.

Example of the Remainder Trick

Suppose:

At indices 0 and 2, the remainder is the same:

5

Subtracting the prefix sums:

29 - 23 = 6

which is divisible by 6.

The corresponding subarray is:

[2, 4]

Important Length Condition

The subarray must have length at least 2.

If the same remainder appears at indices:

i and j

then the subarray length is:

j - i

So we require:

j - i >= 2

Algorithm

Maintain:

Initialize:

seen = {0: -1}

This handles subarrays starting at index 0.

Then scan the array:

1. Update the running prefix remainder
2. If this remainder appeared before:
   • check whether the distance is at least 2
3. Otherwise, store the current index as the first occurrence

If a valid subarray is found, return True.

Otherwise return False.

Correctness

Let the running prefix sum up to index i be:

Suppose two indices i and j satisfy:

Then:

is divisible by k.

But:

is exactly the sum of the subarray between those positions.

Therefore the corresponding subarray sum is a multiple of k.

The algorithm stores the earliest occurrence of each remainder. When the same remainder appears again at a later index, the algorithm checks whether the subarray length is at least 2.

If such a pair exists, the algorithm returns True.

If the algorithm finishes without finding such a pair, then no subarray of length at least 2 has sum divisible by k.

Therefore the algorithm is correct.

Complexity

Implementation

from typing import List

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        seen = {0: -1}

        prefix_mod = 0

        for i, num in enumerate(nums):
            prefix_mod = (prefix_mod + num) % k

            if prefix_mod in seen:
                if i - seen[prefix_mod] >= 2:
                    return True
            else:
                seen[prefix_mod] = i

        return False

Code Explanation

Store remainder 0 at index -1:

seen = {0: -1}

This allows subarrays starting from index 0.

Track the running prefix remainder:

prefix_mod = 0

Update it for each element:

prefix_mod = (prefix_mod + num) % k

If this remainder appeared before:

if prefix_mod in seen:

then the subarray between the two positions has sum divisible by k.

Check the required length:

if i - seen[prefix_mod] >= 2:
    return True

If this remainder has never appeared, store its first occurrence:

else:
    seen[prefix_mod] = i

We store only the earliest occurrence because it gives the longest possible subarray.

Testing

def test_check_subarray_sum():
    s = Solution()

    assert s.checkSubarraySum([23, 2, 4, 6, 7], 6) is True
    assert s.checkSubarraySum([23, 2, 6, 4, 7], 6) is True
    assert s.checkSubarraySum([23, 2, 6, 4, 7], 13) is False
    assert s.checkSubarraySum([0, 0], 1) is True
    assert s.checkSubarraySum([1, 2, 3], 5) is True
    assert s.checkSubarraySum([1, 0], 2) is False

    print("all tests passed")

Test meaning: