Leetcode 523. Continuous Subarray Sum
Check whether any contiguous subarray of length ≥ 2 has a sum that's a multiple of k. This reduces to using prefix-sum modulo k and detecting repeated remainders (with index distance ≥ 2) to prove a subarray sum divisible by k.
Asked at:
Meta
DESCRIPTION
Check whether any contiguous subarray of length ≥ 2 has a sum that's a multiple of k. This reduces to using prefix-sum modulo k and detecting repeated remainders (with index distance ≥ 2) to prove a subarray sum divisible by k.
Input:
nums = [23, 2, 4, 6, 7], k = 6
Output:
true
Explanation: The subarray [2, 4] has sum 6, which is divisible by 6. Also [23, 2, 4, 6, 7] has sum 42, divisible by 6.
Constraints:
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- 0 <= sum(nums[i]) <= 2^31 - 1
- 1 <= k <= 2^31 - 1
- Subarray must have length at least 2
Understanding the Problem
Let's understand what we're being asked to do. We have an array like [23, 2, 4, 6, 7] and a value k = 6, and need to check if any contiguous subarray (length ≥ 2) has a sum divisible by k.
Tracing through: subarray [23, 2] has sum 25 (not divisible by 6), subarray [2, 4] has sum 6 (divisible by 6! return true).
Important constraint: The subarray must have at least 2 elements. A single element doesn't count, even if it's divisible by k.
Key insight: We're looking for any qualifying subarray, not all of them. As soon as we find one, we can return true.
Edge cases to consider: What if the array has only one element? (return false since we need length ≥ 2). What if k = 0? What if all elements are negative? What if the entire array sum is divisible by k?
Brute Force Approach
The brute force approach checks every possible contiguous subarray of length ≥ 2. Use nested loops: the outer loop picks the starting index, the inner loop extends to each possible ending index, computing the sum along the way. For each subarray, check if the sum is divisible by k (i.e., sum % k == 0). If any subarray satisfies this condition, return true; otherwise, return false after checking all possibilities.
def check_subarray_sum(nums, k):"""Brute force: Check every contiguous subarray of length >= 2to see if its sum is divisible by k."""n = len(nums)# Outer loop: starting index of subarrayfor i in range(n):current_sum = 0# Inner loop: ending index of subarrayfor j in range(i, n):# Add current element to running sumcurrent_sum += nums[j]# Check if subarray length >= 2 and sum divisible by kif j - i >= 1 and current_sum % k == 0:return True# No valid subarray foundreturn False
Start brute force: check every subarray of length >= 2
0 / 20
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n²) We check all possible subarrays with nested loops. For an array of length n, there are roughly n²/2 subarrays to examine.
Space Complexity: O(1) We only use a constant amount of extra space for loop counters and the running sum variable
Building Intuition
Instead of checking every possible subarray sum (which would be slow), we can use prefix sums modulo k.
If two positions have the same remainder when their prefix sums are divided by k, then the subarray between them has a sum divisible by k! For example, if prefixSum[i] % k = 3 and prefixSum[j] % k = 3, then (prefixSum[j] - prefixSum[i]) % k = 0.
This transforms the problem from checking O(n²) subarrays to tracking remainders as we scan through the array once.
When we see a remainder we've seen before (with index distance ≥ 2), we've found our answer! This is the difference between checking millions of subarrays and one pass with a lookup table.
Think about a running total as you walk through the array. At each step, compute runningSum % k to get the remainder.
If you see the same remainder twice (and they're at least 2 positions apart), it means the elements between those positions sum to a multiple of k. It's like finding two checkpoints at the same 'modulo position' - the distance traveled between them is divisible by k.
Common Mistakes
Optimal Solution
The optimal approach uses prefix sums with modulo arithmetic and a hash map to track remainders. As we iterate through the array, we maintain a running sum and compute runningSum % k. If we've seen this remainder before at an earlier index (with distance ≥ 2), we've found a subarray whose sum is divisible by k. We store each remainder with its first occurrence index in a hash map. Special case: if runningSum % k == 0 at index i ≥ 1, the subarray from start to i is divisible by k.
def check_subarray_sum(nums, k):"""Check if array has a contiguous subarray of size at least 2whose elements sum to a multiple of k."""# Hash map to store first occurrence of each remainderremainder_map = {0: -1}running_sum = 0# Iterate through array computing prefix sumsfor i in range(len(nums)):# Add current element to running sumrunning_sum += nums[i]# Compute remainder when divided by kremainder = running_sum % k# Check if we've seen this remainder beforeif remainder in remainder_map:# Check if subarray length is at least 2if i - remainder_map[remainder] >= 2:return Trueelse:# Store first occurrence of this remainderremainder_map[remainder] = i# No valid subarray foundreturn False
Start: Check for contiguous subarray (length ≥ 2) with sum divisible by k
0 / 12
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) We make a single pass through the array, and each hash map lookup/insert is O(1) on average
Space Complexity: O(min(n, k)) The hash map stores at most min(n, k) entries since there are only k possible remainders (0 to k-1), and we store at most one entry per array position
What We've Learned
- hashmap mastery: Understanding when and why to use hashmap data structure for this type of problem pattern
- Algorithm optimization: Recognizing how to achieve O(n) time complexity through efficient problem decomposition
- Implementation patterns: Learning the key coding techniques that make this solution robust and maintainable
- Problem-solving approach: Developing intuition for when to apply this algorithmic pattern to similar challenges
- Performance analysis: Understanding the time and space complexity trade-offs and why they matter in practice
Related Concepts and Problems to Practice
medium
This problem uses the exact same pattern as Continuous Subarray Sum: prefix sum with hashmap to detect subarrays with specific sum properties. Instead of checking for multiples of k, it checks for exact sum k, making it a perfect practice problem for the same core technique of storing prefix sums in a hashmap.
This lesson provides foundational understanding of prefix sum techniques and how to use hashmaps with prefix sums to solve subarray problems efficiently. It directly teaches the conceptual framework needed to understand why the modulo-based approach works in Continuous Subarray Sum.
Test Your Understanding
Why is hashmap the right data structure for this problem?
hashmap provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early October, 2025
Meta
Senior
Interviewer allowed me to treat numbers as positive only, simplifying things
Late September, 2025
Meta
Mid-level
Late August, 2025
Meta
Mid-level
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.