Continuous Subarray Sum
Problem Statement
Given an integer array nums and an integer k, return true if nums has a contiguous subarray of length at least 2 whose sum is a multiple of k. Otherwise, return false.
Input
An integer array nums and a positive integer k.
Output
A boolean indicating whether some contiguous subarray of length at least 2 has a sum divisible by k.
Constraints
- •
1 <= nums.length <= 10^5 - •
0 <= nums[i] <= 10^9 - •
0 <= sum(nums[i]) <= 2^31 - 1 - •
1 <= k <= 2^31 - 1
Examples
Example 1
nums = [23,2,4,6,7], k = 6
trueExample 2
nums = [23,2,6,4,7], k = 6
trueExample 3
nums = [23,2,6,4,7], k = 13
falseLearning Objectives
- Recognise divisibility of a subarray sum as an equal-remainder prefix-sum problem.
- Store the first index for each remainder so the length constraint is easiest to check.
- Seed remainder **0** at index **-1** to handle subarrays starting at index **0**.
- Use modulo carefully and avoid dividing by zero in variants outside the official constraints.
Intuition
Pattern Recognition
This is a prefix-sum-with-hashmap problem where the target is divisibility rather than an exact sum. The O(n^2) approach tries every subarray and checks whether its sum is a multiple of k. Prefix sums let us avoid recomputing, and modulo lets us avoid storing large sums.
If two prefix sums have the same remainder after division by k, their difference is divisible by k. That difference is exactly the sum of the subarray between those prefix boundaries. Because the problem requires length at least 2, store the earliest index for each remainder and check that the repeated remainder is at least two indices away.
Common mistakes
- ×Checking only whether the running remainder is **0** and missing subarrays that start later.
- ×Storing the latest index for a remainder instead of the first, which can destroy a valid longer distance.
- ×Forgetting the length requirement and returning true for a one-element multiple of **k**.
- ×Forgetting to seed remainder **0** at index **-1** for subarrays starting at the beginning.
Algorithm Explanation
Key idea
Track prefixSum modulo k. When a remainder repeats, the sum between the earlier prefix boundary and the current index is divisible by k. Store only the first index for each remainder so the distance is as large as possible. Seed remainder 0 at index -1 so a valid prefix of length at least 2 is handled naturally.
Walkthrough
For nums = [23,2,4,6,7] and k = 6, start with remainder map {0:-1}. At index 0, the prefix remainder is 5, so store 5 -> 0. At index 1, the remainder becomes 1, so store 1 -> 1. At index 2, the remainder becomes 5 again. Remainder 5 was first seen at index 0, and 2 - 0 = 2, so the subarray from index 1 through 2 has length 2 and sum divisible by 6.
Algorithm
- Create a hashmap from remainder to earliest index.
- Insert remainder 0 with index -1.
- Maintain the running remainder while scanning nums.
- For each index, update the remainder with the current value modulo k.
- If the remainder has been seen, check whether the distance from its first index is at least 2.
- If the distance is large enough, return true.
- If the remainder is new, store the current index as its first occurrence.
- Return false if no repeated remainder satisfies the length requirement.
Solutions
Solution: First index by prefix remainder
Use equal prefix remainders to detect a subarray sum divisible by k. Keeping the earliest index for each remainder makes the length check straightforward and avoids overwriting a useful start boundary.
Step-by-step
- Seed firstIndexByRemainder with 0 -> -1.
- Scan the array while maintaining the prefix remainder modulo k.
- If the remainder was seen before, compute the distance from its first index.
- Return true when that distance is at least 2.
- If the remainder is new, store the current index.
- Return false after the scan if no valid repeated remainder appears.
O(n)
O(min(n, k))
Each index is processed once, and there can be at most one stored entry per distinct remainder.
Java implementation
Dry Run
Sample input
nums = [23,2,4,6,7], k = 6. The map starts with remainder 0 at index -1.
| index | nums[index] | prefix remainder | first-index map before update | distance or action | answer |
|---|---|---|---|---|---|
| 0 | 23 | 5 | {0:-1} | store 5 at 0 | false |
| 1 | 2 | 1 | {0:-1, 5:0} | store 1 at 1 | false |
| 2 | 4 | 5 | {0:-1, 5:0, 1:1} | seen at 0, length 2 | true |
The repeated remainder 5 means the prefix difference from after index 0 through index 2 is divisible by 6, giving subarray [2,4].
Interview Tips
State the modular arithmetic plainly: equal remainders imply the difference is divisible by k. Then focus on the length constraint, which is why the map stores the first index and why remainder 0 is seeded at -1. Under the official constraints k is positive; if an interviewer changes that, discuss how to avoid modulo by zero before applying this template.
Likely follow-ups
- How would you count all subarrays whose sum is divisible by **k** instead of returning a boolean?
- How would the solution change if negative numbers were allowed?
- How would you return the actual subarray bounds once one is found?
- What changes if the minimum required length is **m** instead of **2**?
Similar Problems
Key Takeaways
- Two equal prefix remainders mean the subarray between them has sum divisible by **k**.
- Store the first index for each remainder to preserve the longest possible distance.
- Seed **0 -> -1** so prefixes starting at index **0** are checked correctly.
- The length-at-least-2 rule must be checked before returning true.