#523
Continuous Subarray Sum
Medium Prefix remainders + index
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether there is a subarray of length at least 2 whose sum is a multiple of k.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: is there a piece of length ≥ 2 whose sum is a multiple of k?
Why this works: same remainder twice means the part between them is a multiple of k. Store the first index of each remainder so the gap check (≥ 2) is fair.
Example: [23, 2, 4, 6, 7], k = 6
remainders: 5, 1, 5 …remainder 5 at index 0 and index 2 → gap 2 → [2, 4] sums to 6 ✓
✦Hints open one at a time
Equal remainders of two prefix sums mean the subarray between them sums to a multiple of k.
Store the first index of each remainder and check that the gap is at least 2.
↗Approach
Map remainder → earliest index, starting with {0: -1}. For each i, if the remainder was seen at index j and i - j >= 2, return true. Only store a remainder the first time.
</>Solution (Java)
import java.util.*;
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> first = new HashMap<>();
first.put(0, -1);
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum = (sum + nums[i]) % k;
Integer j = first.get(sum);
if (j == null) first.put(sum, i);
else if (i - j >= 2) return true; // at least two elements
}
return false;
}
}!Common mistake
Storing the latest index; then a length-1 subarray can block a valid longer one.
Complexity
- Time: O(n).
- Space: O(min(n, k)).
