Log inSign up
mediumLeetCodeNot Started

Continuous Subarray Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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 defined as: 1. Its length is at least two (length >= 2), and 2. The sum of the elements of the subarray is a multiple of k (sum = n * k where n is an integer, including 0).

Example 1 · Standard Multiple of K:

Input: nums = [23, 2, 4, 6, 7], k = 6
Output: true
Explanation: [23, 2, 4] sums to 29 (not a multiple), but [2, 4] is a continuous subarray of size 2 and sums to 6, which is a multiple of 6.

Example 2 · Entire Array Multiple:

Input: nums = [23, 2, 6, 4, 7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] sums to 42, which is a multiple of 6 (6 * 7 = 42), and has length 5 >= 2.

Example 3 · No Valid Subarray of Length >= 2:

Input: nums = [23, 2, 6, 4, 7], k = 13
Output: false
Explanation: No continuous subarray of length >= 2 sums to a multiple of 13.

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109
  • 0 <= sum(nums[i]) <= 231 - 1
  • 1 <= k <= 231 - 1

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Prefix Sum fundamentals
  • Modulo arithmetic property — (a - b) % k == 0 <=> a % k == b % k
  • Hash Map lookup and storage

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the modular arithmetic property of prefix sums for divisibility.
  • Learn why storing only the earliest index is crucial for satisfying length >= 2 constraints.
  • Understand the index -1 initialization for remainder 0.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find subarray whose sum is divisible by k or equals n * k.
  • Constraint requires subarray length >= 2.
  • Input size up to 105 mandates an O(N) single-pass approach.

Algorithmic Decision Tree:

  • If problem asks for subarray sum divisible by k -> Map running prefix sum % k to first-seen index.
  • If matching remainder exists at index prev and (i - prev) >= 2 -> Return true immediately.
  • Always initialize map with remainder 0 at index -1 to catch valid prefix subarrays starting at index 0.

Connected Patterns:

Prefix Sum + Hash Map (Subarray Sum Equals K)Continuous Subarray Remainder CongruenceSliding Window with Divisibility

1. Nested Loops (Brute Force)

Intuition

Generate all subarrays of length >= 2 and check if their sum is divisible by k.

Algorithm

  1. 1. Loop i from 0 to N-2 as the starting index.
  2. 2. Initialize sum = nums[i].
  3. 3. Loop j from i+1 to N-1 as the ending index: - sum += nums[j] - if sum % k == 0, return true.
  4. 4. If no good subarray is found, return false.

Brute Force All Subarrays (Length >= 2) Modulo Scan

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [23, 2, 4, 6, 7]
Current operationSTEP 1 OF 6
Phase 1 — 25 is not a multiple of 6 Advance j to 2: Step 1: Subarray [23, 2] has sum 25
Visual state
Values and pointers at this exact step
array
S
23
2
4
6
7
0
↑ i=0 (val 23)
1
↑ j=1 (val 2)
2
3
4
Variables at this step
i
0
j
1
Length
2
Sum
25
25 % 6
1
Match
NO
Check / comparison
Subarray [23, 2] of length 2: sum = 23 + 2 = 25. 25 % 6 = 1 != 0.
Decision / next transition
25 is not a multiple of 6. Advance j to 2.
Why this step matters

Phase 1 — 25 is not a multiple of 6 Advance j to 2: Step 1: Subarray [23, 2] has sum 25. 25 % 6 = 1. No match.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Brute Force Approach: Check all subarrays of length >= 2
6bool checkSubarraySum(const vector<int>& nums, int k) {
7 int n = nums.size();
8 for (int i = 0; i < n - 1; i++) {
9 long long sum = nums[i];
10 for (int j = i + 1; j < n; j++) {
11 sum += nums[j];
12 if (sum % k == 0) {
13 return true;
14 }
15 }
16 }
17 return false;
18}
19
20int main() {
21 vector<int> nums = {23, 2, 4, 6, 7};
22 int k = 6;
23 bool result = checkSubarraySum(nums, k);
24 cout << "Output: " << (result ? "true" : "false") << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(N^2) — Two nested loops generate N*(N-1)/2 subarrays. Each takes O(1) arithmetic operations.
  • Space complexity: O(1) — Only constant extra variables (i, j, sum) are used.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Prefix Sum Array Lookups (Better)

Intuition

Precompute prefix sum table to compute any range sum in O(1) time.

Algorithm

  1. 1. Construct prefix array of size N+1 where prefix[0] = 0.
  2. 2. Fill prefix[i] = prefix[i-1] + nums[i-1].
  3. 3. Loop i from 0 to N-2 and j from i+2 to N: - If (prefix[j] - prefix[i]) % k == 0, return true.
  4. 4. Return false if no match found.

Prefix Sum Array Modulo Scanner

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [23, 2, 4, 6, 7]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1: Precompute running prefix sums
Visual state
Values and pointers at this exact step
array
S
23
2
4
6
7
0
↑ Build Prefixes
1
2
3
4
Variables at this step
pref
[0, 23, 25, 29, 35, 42]
Check / comparison
Build prefix array: pref = [0, 23, 25, 29, 35, 42].
Decision / next transition
pref[r] - pref[l] gives sum of nums[l..r-1] in O(1).
Why this step matters

Phase 1 — Step 1: Step 1: Precompute running prefix sums. Any subarray sum can now be queried in O(1) time.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Better Approach: Prefix Sum Table
6bool checkSubarraySum(const vector<int>& nums, int k) {
7 int n = nums.size();
8 vector<long long> prefix(n + 1, 0);
9 for (int i = 0; i < n; i++) {
10 prefix[i + 1] = prefix[i] + nums[i];
11 }
12 for (int i = 0; i <= n - 2; i++) {
13 for (int j = i + 2; j <= n; j++) {
14 if ((prefix[j] - prefix[i]) % k == 0) {
15 return true;
16 }
17 }
18 }
19 return false;
20}
21
22int main() {
23 vector<int> nums = {23, 2, 4, 6, 7};
24 int k = 6;
25 bool result = checkSubarraySum(nums, k);
26 cout << "Output: " << (result ? "true" : "false") << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N^2) — Prefix array creation takes O(N). Examining all valid pairs takes N*(N-1)/2 iterations = O(N2).
  • Space complexity: O(N) — Prefix sum array requires O(N) extra space.

3. Prefix Sum Modulo Hash Map (Optimal)

Intuition

Track the earliest index where each running sum % k remainder appeared in O(N) time.

Algorithm

  1. 1. Create hash map remainderMap, initialize with {0: -1}.
  2. 2. Maintain runningSum = 0.
  3. 3. Loop i from 0 to N-1: - runningSum = (runningSum + nums[i]) % k - If remainderMap contains runningSum: - if i - remainderMap[runningSum] >= 2, return true - Else: - remainderMap[runningSum] = i.
  4. 4. If loop completes, return false.

Prefix Sum Modulo Hash Map (Earliest Index Lookup)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [23, 2, 4, 6, 7]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1: If two running prefix sums have the same remainder modulo k, their difference is divisible by k
Visual state
Values and pointers at this exact step
array
S
23
2
4
6
7
0
↑ Init Map
1
2
3
4
Variables at this step
map
{ 0: -1 }
runningSum
0
Check / comparison
Aha! Invariant: If prefixSum[j] % k == prefixSum[i] % k, then sum(nums[i+1..j]) is a multiple of k!
Decision / next transition
Initialize map = { 0: -1 } to handle subarrays starting at index 0. sum = 0.
Why this step matters

Phase 1 — Step 1: Step 1: If two running prefix sums have the same remainder modulo k, their difference is divisible by k! Initialize map = { 0: -1 }.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6// Optimal Approach: Prefix Modulo Remainder Map
7bool checkSubarraySum(const vector<int>& nums, int k) {
8 unordered_map<int, int> remainderMap;
9 remainderMap[0] = -1; // Base case for prefix starting from index 0
10 int runningSum = 0;
11
12 for (int i = 0; i < nums.size(); i++) {
13 runningSum = (runningSum + nums[i]) % k;
14 if (remainderMap.find(runningSum) != remainderMap.end()) {
15 if (i - remainderMap[runningSum] >= 2) {
16 return true;
17 }
18 } else {
19 remainderMap[runningSum] = i;
20 }
21 }
22 return false;
23}
24
25int main() {
26 vector<int> nums = {23, 2, 4, 6, 7};
27 int k = 6;
28 bool result = checkSubarraySum(nums, k);
29 cout << "Output: " << (result ? "true" : "false") << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass of size N with O(1) hash map operations.
  • Space complexity: O(min(N, K)) — Hash map contains at most min(N, K) distinct remainder entries.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute ForceO(N^2)O(1)Check every possible subarray of length >= 2 and test if sum % k == 0.Recomputing subarray sums across O(N2) pairs.
2.Better — Prefix Sum ArrayO(N^2)O(N)Precompute prefix sum array, evaluate all (i, j) subarray sums in O(1).Examining every pair takes quadratic operations.
3.Optimal — Prefix Remainder MapOptimalO(N)O(min(N, K))Store first occurrence of (runningSum % k) in a hash map. Match found with index delta >= 2 confirms solution.None; optimal single-pass solution.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Overwriting the remainder's first occurrence when seen again (which reduces the calculated subarray length).

Pitfall 2:

Forgetting the {0: -1} initialization, which misses valid subarrays starting at index 0.

Pitfall 3:

Returning true on a single element matching k (e.g. nums = [6], k = 6) because the length >= 2 constraint was ignored.

Crucial Edge Cases to Validate:

  • Subarray of zeroes: nums = [0, 0], k = 1 -> sum is 0, which is a multiple of 1 (0 * 1 = 0), returns true.
  • Single element array: nums = [6], k = 6 -> length is 1 (< 2), must return false.
  • Remainder 0 starting from index 0: nums = [5, 1], k = 6 -> (5+1)=6 % 6 == 0, distance 1 - (-1) = 2 >= 2, returns true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the mathematical property (A - B) % K == 0 <=> A % K == B % K explicitly to the interviewer.
  2. Explain why we only update the hash map on the FIRST encounter of a remainder: to maximize length (j - i).
  3. Clarify whether negative numbers or k = 0 are possible according to problem constraints.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Continuous Subarray Sum?

2.Why is the brute force approach suboptimal for large inputs in Continuous Subarray Sum?

3.Which data structure or technique enables the optimal solution for Continuous Subarray Sum?

Back to DSA Sheet