Data Structures & Algorithms (Prefix Sum): Continuous Subarray Sum*

January 21, 2026

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.

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

Playground: Leetcode 523

Naive Approach - Nested Loops

Iterate over all possible substrings, maintain a running sum for each and return true if any of the subarray's sum is divisible by k.

Algorithm

1. Iterate over each index in "nums", treating it as the starting index for the current subarray.
    2. Initialize a variable: "currentSubarraySum" to track the cumulative sum of the current subarray.
    3. For each starting index, expand the subarray one element at a time.
        4. Add the current element to "currentSubarraySum".
        5. If the length of the current substring is greater than 1 and "currentSubarraySum" is completely 
           divisible by "k", return "true".
6. If no good subarray found, return "false".

Implementation

Sample inputs
1public boolean checkSubarraySum(int[] nums, int k) {
2
3 // 1. Iterate over each index in "nums", treating it as the starting index for the current subarray.
4 for (int i = 0; i < nums.length; i++) {
5 // 2. Initialize a variable to track the cumulative sum of the current subarray.
6 int currentSubarraySum = 0;
7 // 3. For each starting index, expand the subarray one element at a time.
8 for (int j = i; j < nums.length; j++) {
9 // 4. Add the current element to the current subarray sum.
10 currentSubarraySum += nums[j];
11 // 5. Check if the current subarray length is greater than 2 and its sum is completely divisible by "k".
12 int currentSubarrayLength = j - i + 1;
13 if (currentSubarrayLength > 1 && currentSubarraySum % k == 0) {
14 // Good subarray found.
15 return true;
16 }
17 }
18 }
19
20 // 6. If no good subarray found, return "false".
21 return false;
22
23}
k6
nums
j
j
j
j
j
23
2
4
6
7
i
i
i
i
i
0
1
2
3
4
Current subarray—
nums[i..j]
i = —
j = —
currentSubarraySum = —
currentSubarrayLength = —
sum % k = —
checkSubarraySum
—
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/18

Time Complexity

In the worst-case scenario, i.e, when no good subarray exists, we will explore all possible subarrays of nums.

The operations inside the inner loop mainly involve arithmetic calculations like addition and division, all consuming constant time, O(1). Therefore, the time complexity is primarily dependent on the number of times the inner loop is executed.

The outer loop will run n times. For every ith iteration, the inner loop will run for (n - i) times.

The total number of iterations performed will be:

(n-0) + (n-1) + (n-2) + (n-3) + ... + (n-(n-1))
= n + (n - 1) + ... 3 + 2 + 1
= [n x (n+1)] / 2

Since, the total number inner-loop executions grow proportional to n², the overall time complexity is O(n²).

Space Complexity

We only use one variable, currentSubarraySum, to keep track of the cumulative sum of the current subarray.

Since we do not use any additional data structures, the overall space complexity is O(1).

Key Observations

For a subarray (j+1 ... i) to have a sum divisible by k, (prefixSum[i] - prefixSum[j]) % k == 0.

key-optimization-1

In other words, if: prefixSum[i] % k == prefixSum[j] % k, then the subarray (j+1 ... i) has a sum divisible by k. This observation essentially changes the problem from checking every subarray to checking whether we've seen the same prefix-sum remainder before.

Suitable Approach - Prefix Sum

Iterate over nums while maintaining a map of prefix-sum-remainders. Return true if a remainder is seen again and the difference between the current index and its first occurrence is greater than 1.

Note

  1. We store the first occurrence of each prefix-sum remainder to ensure that we can find the longest possible subarray ending at the current index.

  2. To handle good subarrays that start at index 0, initialize the map with a prefix-sum-remainder of 0 at index -1.

Algorithm

1. Initialize:
    a. A map: "prefixSumRemainderMap" to track the first occurrence of every distinct 
       prefix-sum-remainder.
    b. A variable: "currentPrefixSum" to track the prefix sum observed so far.

2. Add "{0, -1}" to "prefixSumRemainderMap" to handle good subarrays that start at index `0`.

3. Iterate over each "index" in "nums".
    4. Add the current element: "nums[index]" to "currentPrefixSum".
    5. Calculate "currentPrefixSumRemainder".
    6. If "prefixSumRemainderMap" contains "currentPrefixSumRemainder" and the difference 
       between the current index and first occurence of "currentPrefixSumRemainder" is 
       greater than "1", return "true".
    7. If "prefixSumRemainderMap" does not contain "currentPrefixSumRemainder", add 
       "currentPrefixSumRemainder" and the current index as key-value pair in 
       "prefixSumRemainderMap".

8. If no good subarray found, return "false".

Implementation

Sample inputs
1public boolean checkSubarraySum(int[] nums, int k) {
2
3 /* 1. Initialize:
4 * a. A map to track the first occurrence of every distinct prefix-sum-remainder.
5 * b. A variable to track the prefix sum observed so far.
6 */
7 Map<Integer, Integer> prefixSumRemainderMap = new HashMap<>();
8 int currentPrefixSum = 0;
9
10 // 2. Add "{0, -1}" to the prefix sum remainder map to handle good subarrays that start at index 0.
11 prefixSumRemainderMap.put(0, -1);
12
13 // 3. Iterate over each index in "nums".
14 for (int i = 0; i < nums.length; i++) {
15 // 4. Add the current element to the current prefix sum.
16 currentPrefixSum += nums[i];
17 // 5. Calculate the current subarray sum remainder.
18 int prefixSumRemainder = currentPrefixSum % k;
19 // 6. Check if prefix sum remainder map contains the current prefix sum
20 if (prefixSumRemainderMap.containsKey(prefixSumRemainder)) {
21 /* Check if the difference between the current index and first occurence of the current prefix
22 * sum in prefix sum remainder map is greater than 1.
23 */
24 if (i - prefixSumRemainderMap.get(prefixSumRemainder) > 1) {
25 return true;
26 }
27 // 7. Check if prefix sum remainder map does not contain the current prefix sum
28 } else {
29 // Add the current prefix sum and the current index as key-value pair in the prefix sum remainder map.
30 prefixSumRemainderMap.put(prefixSumRemainder, i);
31 }
32 }
33
34 // 8. If no good subarray found, return "false".
35 return false;
36
37}
k6
nums
23
2
4
6
7
i
i
i
i
i
0
1
2
3
4
Candidate subarray—
nums[first + 1..i]
i = —
currentPrefixSum = —
prefixSumRemainder = —
first index = —
i − first = —
prefixSumRemainderMap
Empty
checkSubarraySum
—
Ready
Press Play or Step. Highlighted lines, including the comments, are the ones executing.
0/18

Time Complexity

For each iteration, we perform only a few arithmetic operations and validation checks, all of which take constant time, O(1). Therefore, the time complexity primarily depends on the number of iterations.

In the worst-case scenario, i.e., when no good subarray exists, the loop executes n times. Hence, the overall time complexity is O(n).

Space Complexity

We use a map to store the first occurrence of each distinct prefix-sum remainder.

In the worst case, all prefix-sum remainders are distinct, so the map will contain n key-value pairs. Hence, the overall space complexity is O(n).

Similar Problems

  1. Leetcode 974 - Subarray Sums Divisible by K