Prefix Sum — Continuous Subarray Sum
↗ LeetCode: Continuous Subarray Sum · Medium · pattern chapter →
Asked atMetaAmazonGoogle
Return true iff there is a subarray of length ≥ 2 whose sum is a multiple of k.
Example 1 — nums = [23,2,4,6,7], k = 6 → true (subarray [2,4]) Example 2 — nums = [23,2,6,4,7], k = 6 → trueExample 3 — nums = [1,0], k = 2 → false
Constraints — 1 ≤ n ≤ 10⁵; 0 ≤ nums[i] ≤ 10⁹; 1 ≤ k ≤ 2³¹−1.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
⏱️Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Every subarray
O(n²). Baseline.
Approach 2 — Prefix mod + first-index map (with length guard)
Insight. If two prefix sums have same remainder mod k AND the distance is ≥ 2, we win. Store first index of each remainder.
Trap — treat prefix at index -1 as 0 (multiple of k). Also handle k = 0 (subarray must sum to 0).
java
boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> first = new HashMap<>();
first.put(0, -1);
int pref = 0;
for (int i = 0; i < nums.length; i++) {
pref += nums[i];
int m = k == 0 ? pref : pref % k;
if (first.containsKey(m)) {
if (i - first.get(m) >= 2) return true;
} else first.put(m, i);
}
return false;
}1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
Execution Trace
Complexity — Time O(n); Space O(k).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute | O(n²) | O(1) | baseline |
| Prefix mod + first-index | O(n) | O(k) | optimum |
When to use which
- "Length ≥ 2" constraint → keep first index (not most recent) to maximize gap.
- "Length ≥ L" → same, check
i - first ≥ L. - "Any sum divisible by k" (no length) → simpler Subarray Sums Divisible by K.
✨AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems