Continuous Subarray Sum - Solution & Explanation
Problem Statement
Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.
A good subarray is a subarray where:
- its length is at least two, and
- the sum of the elements of the subarray is a multiple of
k.
Note that:
- A subarray is a contiguous part of the array.
- An integer
xis a multiple ofkif there exists an integernsuch thatx = n * k.0is always a multiple ofk.
Example 1:
Input: nums = [23,2,4,6,7], k = 6 Output: true Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Example 2:
Input: nums = [23,2,6,4,7], k = 6 Output: true Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42. 42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:
Input: nums = [23,2,6,4,7], k = 13 Output: false
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1090 <= sum(nums[i]) <= 231 - 11 <= k <= 231 - 1
Approach Overview
Problem Overview: Given an integer array nums and an integer k, determine whether the array contains a continuous subarray of at least length 2 whose total sum is a multiple of k. In other words, check if there exist indices i < j such that the sum of elements from i to j is divisible by k.
Approach 1: Iterative Brute Force (Naive Approach) (Time: O(n²), Space: O(1))
Start from each index i and iteratively expand the subarray by adding elements nums[j]. Maintain a running sum while extending the window. After every extension where the subarray length is at least 2, check if sum % k == 0. This approach directly tests all possible subarrays of length ≥2. It works but quickly becomes slow for large arrays because the number of subarrays grows quadratically. It’s mainly useful for understanding the problem or validating small inputs.
Approach 2: Prefix Sum with Modulo and HashMap (Time: O(n), Space: O(n))
The key observation comes from modular arithmetic. If two prefix sums have the same remainder when divided by k, the subarray between them must sum to a multiple of k. While iterating through the array, compute a running prefix sum and store prefixSum % k in a hash map along with the earliest index where that remainder appeared. When the same remainder appears again, check if the distance between indices is at least 2. If it is, a valid subarray exists.
The hash map stores remainder → first index. Initialize it with 0 → -1 so that a valid subarray starting from index 0 can be detected. For each element, update the running sum, compute the remainder, and check if that remainder already exists in the map. If it does and the index difference is greater than 1, return true. Otherwise store the remainder if it hasn't appeared before. This method reduces the search from checking all subarrays to a single pass using a hash table.
This technique relies on prefix sums and modular arithmetic, both common patterns when working with cumulative ranges in an array. Handling k = 0 requires checking for consecutive zeros because modulo with zero is undefined.
Recommended for interviews: Interviewers expect the prefix sum + modulo hash map solution. The brute force approach demonstrates understanding of the problem but does not scale. Recognizing the repeated remainder pattern and converting the problem into a prefix remainder lookup shows strong problem‑solving and familiarity with common interview patterns.
Approach 1: Prefix Sum with Modulo and HashMap
The idea is to use a running or cumulative sum and check the remainder when this sum is divided by k. If any two prefix sums have the same remainder, the subarray sum between these indices is divisible by k.
We maintain a hashmap to store each remainder and its index. As we iterate over the array, we update the running sum and check its remainder. If the remainder has been seen before and the subarray length is at least 2, we return true. If not, we continue. If we finish the loop without finding such a subarray, we return false.
In this C implementation, we use a dynamically allocated array to simulate a hashmap. We initialize all elements to -1, except the zero remainder, which is initialized to index 0 to handle the case where a subarray from the start has a sum that is a multiple of k.
The main loop updates the cumulative sum, calculates its modulo with k, and checks if this remainder was seen before in the hashmap, with the appropriate handling for negative mod cases. If so and the subarray has at least length 2, it returns true. Otherwise, it logs the index of this new remainder.
Complexity
Time Complexity: O(n), where n is the length of nums, since we iterate over the array only once.
Space Complexity: O(k), as we use a hashmap (or array) to store remainders which can be 0 through k-1 in the worst case.
Approach 2: Iterative Brute Force (Naive Approach)
This approach attempts every possible subarray of length at least 2, calculating the sum for each and checking if it is a multiple of k. Although not efficient, this serves as a basic solution for smaller inputs.
The process involves iterating over each possible starting point of a subarray, then for each starting point, iterating over each possible ending point to compute the sum, subsequently verifying its divisibility by k.
This brute force approach implemented in C checks all subarrays of length at least 2. It attempts every start position and iterates all feasible end positions to compute subarray sum and verify divisibility by k.
Complexity
Time Complexity: O(n²) because of the nested loop structure iterating through potential subarray limits.
Space Complexity: O(1) as no extra space apart from a few variables is used.
Approach 3: Prefix Sum + Hash Table
According to the problem description, if there exist two positions i and j (j < i) where the remainders of the prefix sums modulo k are the same, then the sum of the subarray nums[j+1..i] is a multiple of k.
Therefore, we can use a hash table to store the first occurrence of each remainder of the prefix sum modulo k. Initially, we store a key-value pair (0, -1) in the hash table, indicating that the remainder 0 of the prefix sum 0 appears at position -1.
As we iterate through the array, we calculate the current prefix sum's remainder modulo k. If the current prefix sum's remainder modulo k has not appeared in the hash table, we store the current prefix sum's remainder modulo k and its corresponding position in the hash table. Otherwise, if the current prefix sum's remainder modulo k has already appeared in the hash table at position j, then we have found a subarray nums[j+1..i] that meets the conditions, and thus return True.
After completing the iteration, if no subarray meeting the conditions is found, we return False.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix Sum with Modulo and HashMap | Time Complexity: O(n), where n is the length of nums, since we iterate over the array only once. Space Complexity: O(k), as we use a hashmap (or array) to store remainders which can be 0 through k-1 in the worst case. |
| Iterative Brute Force (Naive Approach) | Time Complexity: O(n²) because of the nested loop structure iterating through potential subarray limits. Space Complexity: O(1) as no extra space apart from a few variables is used. |
| Prefix Sum + Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Brute Force | O(n²) | O(1) | Good for understanding the problem or verifying logic on small inputs |
| Prefix Sum with Modulo + HashMap | O(n) | O(n) | Optimal approach for interviews and large arrays |
Video Solution
Continuous Subarray Sum - Leetcode 523 - Python • NeetCode • 101,262 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Continuous Subarray Sum easy or hard?
How to solve Continuous Subarray Sum in O(n)?
What is the best approach for Continuous Subarray Sum?
What data structure is used in Continuous Subarray Sum?
What is the time complexity of Continuous Subarray Sum?
Continuous Subarray Sum Python or Java solution approach?
Is Continuous Subarray Sum asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Continuous Subarray Sum with our built-in code editor and test cases.
Practice on FleetCode