LeetCode 523 - Continuous Subarray Sum

LeetCode Problem 523

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Prefix Sum

Solution

Problem Understanding

The problem asks us to determine whether an array contains a continuous subarray whose sum is a multiple of k, while also satisfying an important constraint: the subarray must contain at least two elements.

In simpler terms, we need to find whether there exists some contiguous segment of nums, with length >= 2, such that:

$$\text{subarray sum} \bmod k = 0$$

This means the sum must divide evenly by k.

The input consists of:

• nums, an integer array
• k, a positive integer

The output is a boolean:

• Return true if at least one valid subarray exists.
• Return false otherwise.

A key detail is that the subarray must be contiguous. We cannot pick arbitrary elements. Another important note is that 0 is always considered a multiple of k, meaning a subarray sum of 0 is valid.

The constraints are important:

• nums.length can be as large as 10^5
• Individual values can be very large, up to 10^9
• The total sum can approach 2^31 - 1

These constraints immediately suggest that an O(n²) solution will likely be too slow. With 10^5 elements, checking every possible subarray would involve billions of operations in the worst case.

Several edge cases can easily trip up a naive implementation:

• A valid subarray may start at index 0.
• Consecutive zeros, such as [0,0], should return true because their sum is 0, which is divisible by every k.
• We must enforce the minimum subarray length of 2.
• Very large numbers require avoiding repeated summation of ranges.

Because k >= 1, we do not need to handle division-by-zero cases.

Approaches

Brute Force Approach

The brute-force method is to examine every possible contiguous subarray of length at least 2.

For each starting index i, we expand the subarray to every ending index j > i, compute the sum, and check whether:

$$\text{sum} \bmod k = 0$$

A straightforward implementation would repeatedly compute subarray sums, which leads to O(n³) complexity. Even if prefix sums are used to compute subarray sums in constant time, we still need to examine every pair (i, j), resulting in O(n²) time.

This approach is correct because it explicitly checks every possible candidate subarray. However, it becomes too slow for arrays of size 10^5.

Key Insight for an Optimal Solution

The crucial observation comes from modular arithmetic.

Suppose:

$$prefixSum[j] \bmod k = prefixSum[i] \bmod k$$

Then:

$$(prefixSum[j] - prefixSum[i]) \bmod k = 0$$

This means the sum of the subarray between those indices is divisible by k.

Instead of checking all subarrays, we only need to track the remainder of prefix sums modulo k.

If the same remainder appears again later, then the numbers between those two positions form a valid subarray divisible by k.

We use a hash map to store the first occurrence of each remainder. Storing the first occurrence is important because it maximizes the possible subarray length and helps satisfy the minimum length requirement.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks all possible subarrays
Optimal	O(n)	O(min(n, k))	Uses prefix sum remainders and a hash map

Algorithm Walkthrough

Optimal Algorithm Using Prefix Sum Modulo

1. Initialize a hash map that stores the first index where each remainder appears.

We start with:

{0: -1}

This handles cases where a valid subarray begins at index 0. If a prefix sum itself is divisible by k, then:

currentIndex - (-1) >= 2

can validate the length requirement. 2. Initialize a running prefix sum variable.

As we iterate through the array, we continuously accumulate values. 3. For each number in nums, update the running sum.

At index i:

prefixSum += nums[i]

4. Compute the remainder modulo k.

remainder = prefixSum % k

The remainder identifies whether we have seen an equivalent prefix state before. 5. Check whether this remainder has appeared previously.

If it exists in the hash map, we found:

prefixSum[i] % k == prefixSum[previousIndex] % k

Therefore, the subarray between those indices has a sum divisible by k. 6. Verify the subarray length.

We only return true if:

i - previousIndex >= 2

since the problem requires at least two elements. 7. Otherwise, store the remainder if it has not appeared before.

We only store the first occurrence, because earlier indices maximize the possible subarray length. 8. If we finish iterating without finding a valid subarray, return false.

Why it works

The algorithm relies on a mathematical invariant:

If two prefix sums have the same remainder when divided by k, their difference must be divisible by k.

Formally:

$$A \bmod k = B \bmod k$$

implies:

$$(A - B) \bmod k = 0$$

Since a subarray sum equals the difference of two prefix sums, repeated remainders guarantee that the subarray sum is divisible by k. The hash map ensures we can detect this in constant time per element.

Python Solution

from typing import List

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

        for index, num in enumerate(nums):
            prefix_sum += num
            remainder = prefix_sum % k

            if remainder in remainder_to_index:
                previous_index = remainder_to_index[remainder]

                if index - previous_index >= 2:
                    return True
            else:
                remainder_to_index[remainder] = index

        return False

The implementation follows the algorithm directly.

We begin by creating remainder_to_index, a dictionary mapping remainders to the earliest index where they occurred. Initializing {0: -1} is essential because it enables detecting valid subarrays starting from index 0.

The variable prefix_sum tracks the cumulative sum as we iterate through the array.

For each element, we update the prefix sum and compute its remainder modulo k. If this remainder has appeared before, we retrieve the previous index and check whether the distance between indices is at least 2.

If the length requirement is satisfied, we immediately return True.

If the remainder has never been seen, we store its index. We intentionally avoid updating an existing entry because we want the earliest index, which gives the longest possible valid subarray.

If no valid subarray is found after traversing the array, the function returns False.

Go Solution

func checkSubarraySum(nums []int, k int) bool {
	remainderToIndex := map[int]int{
		0: -1,
	}

	prefixSum := 0

	for index, num := range nums {
		prefixSum += num
		remainder := prefixSum % k

		if previousIndex, exists := remainderToIndex[remainder]; exists {
			if index-previousIndex >= 2 {
				return true
			}
		} else {
			remainderToIndex[remainder] = index
		}
	}

	return false
}

The Go implementation mirrors the Python logic closely.

Go maps are used for constant-time remainder lookup. The initialization:

map[int]int{0: -1}

serves the same purpose as in Python, handling subarrays starting at index 0.

Since Go integers are sufficiently large for this problem's constraints, integer overflow is not a concern. The input guarantees that the total sum does not exceed 2^31 - 1.

Unlike Python dictionaries, Go maps return an additional boolean value (exists) to indicate whether a key is present. This avoids ambiguity when a remainder maps to index 0.

Worked Examples

Example 1

Input:

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

Initial state:

remainder_to_index = {0: -1}
prefix_sum = 0

Index	Num	Prefix Sum	Remainder	Hash Map	Action
0	23	23	5	{0:-1}	Store 5 → 0
1	2	25	1	{0:-1,5:0}	Store 1 → 1
2	4	29	5	{0:-1,5:0,1:1}	5 seen before at index 0, length = 2, return True

The subarray:

[2, 4]

sums to:

6

which is divisible by 6.

Example 2

Input:

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

Index	Num	Prefix Sum	Remainder	Action
0	23	23	5	Store 5 → 0
1	2	25	1	Store 1 → 1
2	6	31	1	Seen before at 1, length = 1, invalid
3	4	35	5	Seen before at 0, length = 3, return True

The valid subarray is:

[2, 6, 4]

whose sum is:

12

which is divisible by 6.

Example 3

Input:

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

Index	Num	Prefix Sum	Remainder	Action
0	23	23	10	Store
1	2	25	12	Store
2	6	31	5	Store
3	4	35	9	Store
4	7	42	3	Store

No repeated remainder produces a valid subarray of length at least 2, so the answer is False.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed once
Space	O(min(n, k))	At most one entry per unique remainder

The algorithm scans the array exactly once, and every hash map operation is average O(1), resulting in linear time complexity.

The space complexity depends on how many distinct remainders appear. Since remainders range from 0 to k - 1, the hash map can contain at most min(n, k) entries.

Test Cases

solution = Solution()

assert solution.checkSubarraySum([23, 2, 4, 6, 7], 6) is True  # Example 1
assert solution.checkSubarraySum([23, 2, 6, 4, 7], 6) is True  # Example 2
assert solution.checkSubarraySum([23, 2, 6, 4, 7], 13) is False  # Example 3

assert solution.checkSubarraySum([0, 0], 1) is True  # consecutive zeros
assert solution.checkSubarraySum([5, 0, 0], 3) is True  # zero-sum subarray
assert solution.checkSubarraySum([1, 2], 4) is False  # minimum size, no match
assert solution.checkSubarraySum([6, 6], 6) is True  # exact multiple
assert solution.checkSubarraySum([1, 1], 2) is True  # sum divisible by k
assert solution.checkSubarraySum([1, 2, 3], 5) is True  # [2,3] sums to 5
assert solution.checkSubarraySum([1], 1) is False  # single element invalid
assert solution.checkSubarraySum([1000000000, 1000000000], 2) is True  # large numbers
assert solution.checkSubarraySum([23, 2, 6, 4, 7], 100) is False  # no valid subarray
assert solution.checkSubarraySum([5, 5, 5], 5) is True  # repeated remainder
assert solution.checkSubarraySum([1, 0], 2) is False  # length 2 but not divisible

Test Case Summary

Test	Why
[23,2,4,6,7], k=6	Validates basic positive case
[23,2,6,4,7], k=6	Tests longer valid subarray
[23,2,6,4,7], k=13	Validates failure case
[0,0], k=1	Ensures zero-sum handling
[5,0,0], k=3	Tests subarray sum of zero
[1,2], k=4	Minimum valid length without match
[6,6], k=6	Exact divisible pair
[1,1], k=2	Small valid input
[1,2,3], k=5	Valid middle subarray
[1], k=1	Single element should fail
Large values	Confirms handling of large integers
Large k	Ensures correct modulo behavior
Repeated values	Validates repeated remainder logic
[1,0], k=2	Tests near-valid edge case

Edge Cases

Consecutive Zeros

An array like:

[0, 0]

can easily cause mistakes in naive implementations. Since 0 is divisible by every k, this should return True.

Our implementation handles this naturally. After processing the second zero, the remainder remains 0, which already exists in the hash map at index -1. The distance becomes 2, satisfying the length condition.

Valid Subarray Starting at Index Zero

Consider:

[6, 6]

with k = 6.

The sum of the prefix itself is divisible by k. Without initializing:

{0: -1}

we would miss this case because there would be no earlier matching remainder.

The sentinel value -1 effectively represents an empty prefix before the array starts.

Matching Remainder but Invalid Length

Consider:

[23, 2, 6]

with k = 6.

At one point, the same remainder appears again, but the distance between indices may only be 1. A careless implementation might incorrectly return True.

Our implementation explicitly checks:

index - previous_index >= 2

which guarantees the subarray contains at least two elements.

Large Input Size

Since n can reach 100000, nested loops would time out.

The hash map approach processes each element once, ensuring linear time complexity and making it efficient even at maximum input size.