Continuous Subarray Sum

This problem requires detecting a continuous subarray whose sum is divisible by k. By maintaining prefix sums modulo k and storing first occurrences in a hash table, you can scan the array in a single pass. The key insight is that if two prefix sums share the same modulo k value and the subarray length is at least two, the subarray sum is divisible by k.

Problem Statement

Given an integer array nums and an integer k, determine whether there exists a continuous subarray of at least size two whose sum is a multiple of k. Return true if such a subarray exists, otherwise return false.

A subarray sum is considered valid if the sum of its elements modulo k equals zero. Your solution must handle large arrays efficiently, using prefix sums and hash table tracking to detect repeating modulo values that indicate valid subarrays.

Examples

Example 1

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

Output: true

[2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2

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

Output: true

[23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42. 42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3

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

Output: false

Example details omitted.

Constraints

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= sum(nums[i]) <= 231 - 1
• 1 <= k <= 231 - 1

Solution Approach

Prefix Sum with Modulo Tracking

Iterate through nums while maintaining the cumulative sum modulo k. Store the first index of each modulo result in a hash map. If a modulo repeats at a later index and the subarray length is at least 2, return true.

Handling Edge Cases

Initialize the hash map with {0: -1} to handle cases where the subarray starts at index 0. Ensure subarray length is at least two to satisfy the problem requirement, preventing false positives from single-element matches.

Time and Space Optimization

The algorithm runs in O(n) time and uses O(n) space due to the hash map. This ensures scalability for the upper constraint of nums length up to 10^5 while keeping all operations per element constant.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) for a single pass through the array. Space complexity is O(n) to store the first occurrence of each modulo in the hash map. No nested loops are needed, making this approach efficient for large inputs.

What Interviewers Usually Probe

• Checks if candidate understands prefix sum modulo technique.
• Observes if candidate handles subarray length edge cases properly.
• Watches for efficient use of hash map to avoid O(n^2) scanning.

Common Pitfalls or Variants

Common pitfalls

• Forgetting to check subarray length >= 2 when modulo repeats.
• Not initializing hash map with 0:-1, causing misses at the array start.
• Assuming negative numbers or k=0 without proper handling can lead to incorrect modulo logic.

Follow-up variants

• Find all subarrays whose sums are multiples of k instead of just one.
• Allow k to be zero, requiring direct sum checks instead of modulo.
• Return the length of the longest valid subarray rather than a boolean.

FAQ

What is the main pattern for solving Continuous Subarray Sum?

Use prefix sums and track modulo k values in a hash map to detect subarrays summing to multiples of k.

Can this problem handle large arrays efficiently?

Yes, the O(n) prefix sum with hash map ensures efficient handling up to the constraint of 10^5 elements.

Why do we store 0:-1 in the hash map?

To account for subarrays starting at index 0, ensuring correct detection of valid sums from the beginning.

How do we avoid single-element false positives?

Always check that the subarray length is at least 2 when a modulo repeats in the hash map.

What if k is negative or zero?

Handle k carefully: negative k works with modulo as usual, but k=0 requires checking subarray sums directly without modulo.