Leetcode 523. Continuous Subarray Sum
Check whether any contiguous subarray of length ≥ 2 has a sum that's a multiple of k. This reduces to using prefix-sum modulo k and detecting repeated remainders (with index distance ≥ 2) to prove a subarray sum divisible by k.
DESCRIPTION
Check whether any contiguous subarray of length ≥ 2 has a sum that's a multiple of k. This reduces to using prefix-sum modulo k and detecting repeated remainders (with index distance ≥ 2) to prove a subarray sum divisible by k.
Input:
nums = [23, 2, 4, 6, 7], k = 6
Output:
true
Explanation: The subarray [2, 4] has sum 6, which is divisible by 6. Also [23, 2, 4, 6, 7] has sum 42, divisible by 6.
Constraints:
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- 0 <= sum(nums[i]) <= 2^31 - 1
- 1 <= k <= 2^31 - 1
- Subarray must have length at least 2
Understanding the Problem
Let's understand what we're being asked to do. We have an array like [23, 2, 4, 6, 7] and a value k = 6, and need to check if any contiguous subarray (length ≥ 2) has a sum divisible by k.
Tracing through: subarray [23, 2] has sum 25 (not divisible by 6), subarray [2, 4] has sum 6 (divisible by 6! return true).
Important constraint: The subarray must have at least 2 elements. A single element doesn't count, even if it's divisible by k.
Key insight: We're looking for any qualifying subarray, not all of them. As soon as we find one, we can return true.
Edge cases to consider: What if the array has only one element? (return false since we need length ≥ 2). What if k = 0? What if all elements are negative? What if the entire array sum is divisible by k?
Brute Force Approach
The brute force approach checks every possible contiguous subarray of length ≥ 2. Use nested loops: the outer loop picks the starting index, the inner loop extends to each possible ending index, computing the sum along the way. For each subarray, check if the sum is divisible by k (i.e., sum % k == 0). If any subarray satisfies this condition, return true; otherwise, return false after checking all possibilities.
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n²) We check all possible subarrays with nested loops. For an array of length n, there are roughly n²/2 subarrays to examine.
Space Complexity: O(1) We only use a constant amount of extra space for loop counters and the running sum variable
Building Intuition
Instead of checking every possible subarray sum (which would be slow), we can use prefix sums modulo k.
If two positions have the same remainder when their prefix sums are divided by k, then the subarray between them has a sum divisible by k! For example, if prefixSum[i] % k = 3 and prefixSum[j] % k = 3, then (prefixSum[j] - prefixSum[i]) % k = 0.
This transforms the problem from checking O(n²) subarrays to tracking remainders as we scan through the array once.
When we see a remainder we've seen before (with index distance ≥ 2), we've found our answer! This is the difference between checking millions of subarrays and one pass with a lookup table.
Think about a running total as you walk through the array. At each step, compute runningSum % k to get the remainder.
If you see the same remainder twice (and they're at least 2 positions apart), it means the elements between those positions sum to a multiple of k. It's like finding two checkpoints at the same 'modulo position' - the distance traveled between them is divisible by k.
Common Mistakes
Forgetting the 'length ≥ 2' constraint - need to check that indices are at least 2 apart, not just that remainders match
Not handling the special case where runningSum % k == 0 - this means the subarray from index 0 to current index is divisible by k
Integer overflow when computing prefix sums - for large arrays with large values, the running sum can exceed integer limits
Incorrect modulo handling for negative numbers - in some languages, negative numbers modulo k can give negative results, need to normalize to [0, k-1]
Storing the wrong information in the hash map - we need to store the first occurrence of each remainder to maximize subarray length opportunities
Optimal Solution
The optimal approach uses prefix sums with modulo arithmetic and a hash map to track remainders. As we iterate through the array, we maintain a running sum and compute runningSum % k. If we've seen this remainder before at an earlier index (with distance ≥ 2), we've found a subarray whose sum is divisible by k. We store each remainder with its first occurrence index in a hash map. Special case: if runningSum % k == 0 at index i ≥ 1, the subarray from start to i is divisible by k.
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) We make a single pass through the array, and each hash map lookup/insert is O(1) on average
Space Complexity: O(min(n, k)) The hash map stores at most min(n, k) entries since there are only k possible remainders (0 to k-1), and we store at most one entry per array position
What We've Learned
- hashmap mastery: Understanding when and why to use hashmap data structure for this type of problem pattern
- Algorithm optimization: Recognizing how to achieve O(n) time complexity through efficient problem decomposition
- Implementation patterns: Learning the key coding techniques that make this solution robust and maintainable
- Problem-solving approach: Developing intuition for when to apply this algorithmic pattern to similar challenges
- Performance analysis: Understanding the time and space complexity trade-offs and why they matter in practice
Related Concepts and Problems to Practice
This problem uses the exact same pattern as Continuous Subarray Sum: prefix sum with hashmap to detect subarrays with specific sum properties. Instead of checking for multiples of k, it checks for exact sum k, making it a perfect practice problem for the same core technique of storing prefix sums in a hashmap.
This lesson provides foundational understanding of prefix sum techniques and how to use hashmaps with prefix sums to solve subarray problems efficiently. It directly teaches the conceptual framework needed to understand why the modulo-based approach works in Continuous Subarray Sum.
Test Your Understanding
Why is hashmap the right data structure for this problem?
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early October, 2025
Interviewer allowed me to treat numbers as positive only, simplifying things
Late September, 2025
Late August, 2025
Hello Interview Premium
Your account is free and you can post anonymously if you choose.