Continuous Subarray Sum
Last Updated: March 21, 2026
Understanding the Problem
We need to find a contiguous subarray of length at least 2 whose sum is divisible by k. The key phrase here is "multiple of k," which means the sum could be 0, k, 2k, 3k, and so on. We're not looking for an exact target. We're looking for any sum that leaves a remainder of 0 when divided by k.
This is different from "Subarray Sum Equals K" (LeetCode 560) where we have a fixed target. Here, the target is any value in the infinite set {0, k, 2k, 3k, ...}. Checking against every possible multiple would be impractical, which is the hint that we need a smarter mathematical approach.
The minimum length requirement of 2 is easy to overlook but matters. A single element that's a multiple of k doesn't count. This constraint will influence how we validate our answer in every approach.
Key Constraints:
nums.lengthup to10^5means O(n^2) will be tight (around 10^10 operations in the worst case), so we should aim for O(n)nums[i]can be 0, which means consecutive zeros form a valid subarray (sum = 0, which is a multiple of any k)kcan be very large (up to 2^31 - 1), so we can't create an array indexed by k- The sum can reach 2^31 - 1, so we need to be mindful of integer overflow in some languages
Approach 1: Brute Force
Intuition
The most straightforward approach is to check every possible subarray of length 2 or more, compute its sum, and see if it's divisible by k. We fix a starting index, extend the subarray one element at a time, and check the running sum at each step.
Since we're building the sum incrementally (adding one element at a time as we extend the end pointer), we avoid recomputing the sum from scratch for each subarray. This brings us from O(n^3) down to O(n^2).
Algorithm
- For each starting index
ifrom 0 ton - 2 - Maintain a running sum starting from
nums[i] - For each ending index
jfromi + 1ton - 1, addnums[j]to the running sum - If the running sum is divisible by
k, returntrue - If no valid subarray is found after checking all pairs, return
false
Example Walkthrough
Code
- Time Complexity: O(n^2). We have two nested loops. The outer loop runs n times, and the inner loop runs up to n times for each iteration. Each inner iteration does O(1) work (addition and modulo check).
- Space Complexity: O(1). We only use a running sum variable and loop counters. No extra data structures.
The bottleneck here is the nested loop: for each starting index, we scan every possible ending index. With n up to 10^5, that's up to 5 billion operations. What if we could process each element exactly once and use a mathematical property to detect valid subarrays in O(1) per element?
Approach 2: Prefix Sum + Hash Map (Optimal)
Intuition
Here's the key mathematical insight. If we define prefixSum[j] as the sum of the first j elements, then the sum of any subarray from index i+1 to j is prefixSum[j] - prefixSum[i].
We want this subarray sum to be a multiple of k:
prefixSum[j] - prefixSum[i] ≡ 0 (mod k)
Which means:
prefixSum[j] % k == prefixSum[i] % k
So two prefix sums with the same remainder when divided by k define a subarray whose sum is a multiple of k. This transforms the problem into: find two prefix sums with the same remainder that are at least 2 positions apart.
Now the approach becomes clear. As we compute prefix sums, we store the remainder prefixSum % k in a hash map. If we see the same remainder again and the indices are at least 2 apart, we've found a valid subarray. We store the earliest index for each remainder because we only need to know if a valid pair exists, not find all of them.
One subtle detail: we initialize the map with {0: -1}. This handles the case where the prefix sum itself is a multiple of k (i.e., a subarray starting from index 0). Without this initialization, we'd miss subarrays like [6, 0] with k = 6, where the prefix sum at index 1 is already 6.
The approach rests on a fundamental property of modular arithmetic: if two numbers have the same remainder when divided by k, their difference is divisible by k. Since prefix sums encode subarray sums as differences (sum(i..j) = prefix[j] - prefix[i]), finding two prefix sums with the same remainder is equivalent to finding a subarray whose sum is a multiple of k.
By storing only the earliest index for each remainder, we maximize the distance between matching indices, making it more likely (not less) that the length-2 requirement is satisfied. And the {0: -1} initialization elegantly handles the case where a prefix sum is itself a multiple of k, without needing a special case.
Algorithm
- Create a hash map and initialize it with
{0: -1}(remainder 0 seen at virtual index -1) - Maintain a running prefix sum as we iterate through the array
- For each index
i, computeprefixSum % k - If this remainder already exists in the map and
i - map[remainder] >= 2, returntrue - If the remainder is not in the map, store it with the current index (we only store the first occurrence to maximize the subarray length)
- If we finish without finding a match, return
false
Code
- Time Complexity: O(n). We iterate through the array once. Each iteration does O(1) work: one addition, one modulo operation, and one hash map lookup/insert.
- Space Complexity: O(min(n, k)). The hash map stores at most one entry per distinct remainder. There are at most k possible remainders (0 through k-1), and we process at most n elements. So the map holds at most min(n, k) entries.