Continuous Subarray Sum
Understanding the Problem
We need to find a contiguous subarray of length at least 2 whose sum is divisible by k. "Multiple of k" means the sum can be 0, k, 2k, 3k, and so on. There is no single target value, only the condition that the sum leaves a remainder of 0 when divided by k.
Because the target is any value in the infinite set {0, k, 2k, 3k, ...}, checking the sum against each multiple is impractical. The condition has to be expressed in terms of remainders instead.
The minimum length requirement of 2 means a single element that is a multiple of k does not count. Every approach has to enforce this when validating a match.
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 total sum can reach 2^31 - 1, exactly the 32-bit signed maximum, so in languages with fixed-width integers a 64-bit accumulator keeps the running sum clear of the boundary
Approach 1: Brute Force
Intuition
Check every possible subarray of length 2 or more, compute its sum, and test whether it is divisible by k. We fix a starting index, extend the subarray one element at a time, and check the running sum at each step.
Building the sum incrementally as the end index advances avoids recomputing each subarray's sum from scratch, which brings the cost 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 nested loop is the bottleneck: for each starting index, we scan every possible ending index, which is up to 5 billion sum checks when n is 10^5. The next approach replaces the inner loop with a property of remainders that detects a valid subarray in O(1) per element.
Approach 2: Prefix Sum + Hash Map (Optimal)
Intuition
Define prefixSum[j] as the sum of the first j elements. The sum of any subarray from index i+1 to j is then 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.
As we compute the running prefix sum, we store each remainder prefixSum % k in a hash map, keyed to the first index where it appeared. When the same remainder appears again at index i and i - firstIndex >= 2, we have found a valid subarray.
We also initialize the map with {0: -1}, treating the empty prefix (sum 0 before any element) as seen at index -1. This covers subarrays that start at index 0. With nums = [6, 0] and k = 6, the prefix sum at index 1 is 6, its remainder is 0, and 1 - (-1) = 2 passes the length check. Without the initialization, this case would be missed.
Storing only the earliest index per remainder never misses an answer. If a remainder repeats at index i but the gap is shorter than 2, keeping the older index instead of overwriting it can only make future gaps for that remainder longer. So if any pair of equal-remainder prefix sums at least 2 apart exists, the pair formed with the earliest occurrence also qualifies, and the algorithm reports it.
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
Example Walkthrough
Using nums = [23, 2, 6, 4, 7] and k = 6:
The repeat of remainder 1 at index 2 fails the length check, and the stored index 1 is kept. The repeat of remainder 5 at index 3 matches index 0, the gap of 3 satisfies the length requirement, and the function returns true for the subarray [2, 6, 4] with sum 12.
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.