523. Continuous Subarray Sum Solution

Q: Is Continuous Subarray Sum easy or hard?

Continuous Subarray Sum is classified as a medium difficulty problem. The brute force idea is straightforward, but identifying the prefix sum modulo pattern and implementing the hash map optimization requires familiarity with common interview techniques.

Q: How to solve Continuous Subarray Sum in O(n)?

Maintain a running prefix sum while iterating through the array. Compute the remainder of the prefix sum with k and store the first occurrence of each remainder in a hash map. When the same remainder appears again and the gap between indices is at least two, a valid subarray exists. This avoids checking every subarray explicitly.

Q: What is the best approach for Continuous Subarray Sum?

The optimal approach uses prefix sum with modulo and a hash map. While iterating through the array, store the first index where each remainder (prefixSum % k) appears. If the same remainder appears again and the index difference is at least 2, the subarray between them has a sum divisible by k. This solution runs in O(n) time with O(n) space.

Q: What data structure is used in Continuous Subarray Sum?

The optimal solution relies on a hash map to store the earliest index for each prefix sum remainder. Combined with a running prefix sum and modulo arithmetic, the hash map allows constant-time checks to determine whether a valid subarray exists.

Q: What is the time complexity of Continuous Subarray Sum?

The optimal prefix sum and hash map solution runs in O(n) time because the array is scanned once and each hash lookup is O(1) on average. Space complexity is O(n) for storing remainders. The brute force approach takes O(n²) time since it checks every possible subarray.

Q: Continuous Subarray Sum Python or Java solution approach?

Both Python and Java implementations follow the same logic: compute a running prefix sum, track prefixSum % k, and store the earliest index of each remainder in a hash map. When the same remainder reappears with an index gap of at least two, return true. The complexity remains O(n) time and O(n) space.

Q: Is Continuous Subarray Sum asked at Google, Amazon, or Meta?

Continuous Subarray Sum is a common medium-level interview problem and appears in question banks used by companies like Amazon, Google, and Meta. It tests knowledge of prefix sums, modular arithmetic, and hash maps—patterns frequently evaluated in coding interviews.

The problem

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 x is a multiple of k if there exists an integer n such that x = n * k. 0 is always 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

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
0 <= sum(nums[i]) <= 2³¹ - 1
1 <= k <= 2³¹ - 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.

Python

def check_subarray_sum(nums, k):
    rem_map = {0: -1}
    total = 0
    for i, num in enumerate(nums):
        total += num
        remainder = total % k
        if remainder < 0:
            remainder += k
        if remainder in rem_map:
            if i - rem_map[remainder] > 1:
                return True
        else:
            rem_map[remainder] = i
    return False

if __name__ == '__main__':
    nums = [23, 2, 4, 6, 7]
    k = 6
    print(check_subarray_sum(nums, k))

Java

import java.util.HashMap;

public class Solution {
    public static boolean checkSubarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int mod = sum % k;
            if (mod < 0) mod += k;
            if (map.containsKey(mod)) {
                if (i - map.get(mod) > 1) return true;
            } else {
                map.put(mod, i);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {23, 2, 4, 6, 7};
        int k = 6;
        System.out.println(checkSubarraySum(nums, k));
    }
}

C++

#include <unordered_map>
#include <vector>
#include <iostream>
using namespace std;

bool checkSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> remainderMap;
    remainderMap[0] = -1;
    int sum = 0;
    for (int i = 0; i < nums.size(); ++i) {
        sum += nums[i];
        int mod = sum % k;
        if (mod < 0) mod += k;
        if (remainderMap.count(mod)) {
            if (i - remainderMap[mod] > 1) return true;
        } else {
            remainderMap[mod] = i;
        }
    }
    return false;
}

int main() {
    vector<int> nums = {23, 2, 4, 6, 7};
    int k = 6;
    cout << (checkSubarraySum(nums, k) ? "true" : "false") << endl;
    return 0;
}

JavaScript

function checkSubarraySum(nums, k) {
    const remainderMap = new Map();
    remainderMap.set(0, -1);
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        let mod = sum % k;
        if (mod < 0) mod += k;
        if (remainderMap.has(mod)) {
            if (i - remainderMap.get(mod) > 1) return true;
        } else {
            remainderMap.set(mod, i);
        }
    }
    return false;
}

console.log(checkSubarraySum([23, 2, 4, 6, 7], 6));

#include <stdbool.h>
#include <stdio.h>

bool checkSubarraySum(int* nums, int numsSize, int k) {
    int sum = 0;
    int *map = (int *)malloc((k + 1) * sizeof(int));
    for (int i = 0; i <= k; ++i) map[i] = -1;
    map[0] = 0;
    for (int i = 0; i < numsSize; ++i) {
        sum += nums[i];
        int mod = sum % k;
        if (mod < 0) mod += k; // handle negative mod
        if (map[mod] != -1) {
            if (i + 1 - map[mod] > 1) {
                free(map);
                return true;
            }
        } else {
            map[mod] = i + 1;
        }
    }
    free(map);
    return false;
}

int main() {
    int nums[] = {23, 2, 4, 6, 7};
    int k = 6;
    bool result = checkSubarraySum(nums, 5, k);
    printf("%s\n", result ? "true" : "false");
    return 0;
}

using System;
using System.Collections.Generic;

class Program {
    public static bool CheckSubarraySum(int[] nums, int k) {
        Dictionary<int, int> remainderMap = new Dictionary<int, int>();
        remainderMap.Add(0, -1);
        int sum = 0;
        for (int i = 0; i < nums.Length; i++) {
            sum += nums[i];
            int mod = sum % k;
            if (mod < 0) mod += k;
            if (remainderMap.ContainsKey(mod)) {
                if (i - remainderMap[mod] > 1) return true;
            } else {
                remainderMap[mod] = i;
            }
        }
        return false;
    }

    static void Main() {
        int[] nums = {23, 2, 4, 6, 7};
        int k = 6;
        Console.WriteLine(CheckSubarraySum(nums, k));
    }
}

This Python function operates using a dictionary that maps remainders of the sum modulo k to their indices, allowing detection of the necessary subarray efficiently. The key structure of the solution lies in the comparison of indices whenever a remainder recurs.

The function captures and accounts for negative remainder values and adjusts back into the valid range with k, ensuring accuracy in diverse numeric scenarios.

Complexity

Time Complexity: O(n), where n represents the size of nums.

Space Complexity: O(k), as the hashmap stores a bounded number of potential remainders from 0 to k.

Try this approach in the editor

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.

Python

def check_subarray_sum(nums, k):
    for start in range(len(nums) - 1):
        total = nums[start]
        for end in range(start + 1, len(nums)):
            total += nums[end]
            if total % k == 0:
                return True
    return False

if __name__ == '__main__':
    nums = [23, 2, 4, 6, 7]
    k = 6
    print(check_subarray_sum(nums, k))

Java

public class Solution {
    public static boolean checkSubarraySum(int[] nums, int k) {
        for (int start = 0; start < nums.length - 1; ++start) {
            int sum = nums[start];
            for (int end = start + 1; end < nums.length; ++end) {
                sum += nums[end];
                if (sum % k == 0) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {23, 2, 4, 6, 7};
        int k = 6;
        System.out.println(checkSubarraySum(nums, k));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

bool checkSubarraySum(vector<int>& nums, int k) {
    for (int start = 0; start < nums.size() - 1; ++start) {
        int sum = nums[start];
        for (int end = start + 1; end < nums.size(); ++end) {
            sum += nums[end];
            if (sum % k == 0) return true;
        }
    }
    return false;
}

int main() {
    vector<int> nums = {23, 2, 4, 6, 7};
    int k = 6;
    cout << (checkSubarraySum(nums, k) ? "true" : "false") << endl;
    return 0;
}

JavaScript

function checkSubarraySum(nums, k) {
    for (let start = 0; start < nums.length - 1; ++start) {
        let sum = nums[start];
        for (let end = start + 1; end < nums.length; ++end) {
            sum += nums[end];
            if (sum % k === 0) return true;
        }
    }
    return false;
}

console.log(checkSubarraySum([23, 2, 4, 6, 7], 6));

#include <stdbool.h>
#include <stdio.h>

bool checkSubarraySum(int* nums, int numsSize, int k) {
    for (int start = 0; start < numsSize - 1; ++start) {
        int sum = nums[start];
        for (int end = start + 1; end < numsSize; ++end) {
            sum += nums[end];
            if (sum % k == 0) return true;
        }
    }
    return false;
}

int main() {
    int nums[] = {23, 2, 4, 6, 7};
    int k = 6;
    bool result = checkSubarraySum(nums, 5, k);
    printf("%s\n", result ? "true" : "false");
    return 0;
}

using System;

class Program {
    public static bool CheckSubarraySum(int[] nums, int k) {
        for (int start = 0; start < nums.Length - 1; ++start) {
            int sum = nums[start];
            for (int end = start + 1; end < nums.Length; ++end) {
                sum += nums[end];
                if (sum % k == 0) return true;
            }
        }
        return false;
    }

    static void Main() {
        int[] nums = {23, 2, 4, 6, 7};
        int k = 6;
        Console.WriteLine(CheckSubarraySum(nums, k));
    }
}

The Python implementation follows a brute force strategy, iterating through all pairs of start and end points for subarrays to deduce their sums and ascertain if divisible by k.

While comprehensive, this solution is notably slow on larger input scales.

Complexity

Time Complexity: O(n²), stemming from each subarray's reassessment of sum via double loops.

Space Complexity: O(1), because only a constant amount of auxiliary integers are engaged.

Try this approach in the editor

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.

TypeScript

function checkSubarraySum(nums: number[], k: number): boolean {
    const d: Record<number, number> = { 0: -1 };
    let s = 0;
    for (let i = 0; i < nums.length; ++i) {
        s = (s + nums[i]) % k;
        if (!d.hasOwnProperty(s)) {
            d[s] = i;
        } else if (i - d[s] > 1) {
            return true;
        }
    }
    return false;
}

func checkSubarraySum(nums []int, k int) bool {
	d := map[int]int{0: -1}
	s := 0
	for i, x := range nums {
		s = (s + x) % k
		if _, ok := d[s]; !ok {
			d[s] = i
		} else if i-d[s] > 1 {
			return true
		}
	}
	return false
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Prefix Sum with Modulo and HashMap	Time Complexity: O(n), where n represents the size of nums. Space Complexity: O(k), as the hashmap stores a bounded number of potential remainders from 0 to k.
Iterative Brute Force (Naive Approach)	Time Complexity: O(n²), stemming from each subarray's reassessment of sum via double loops. Space Complexity: O(1), because only a constant amount of auxiliary integers are engaged.
Prefix Sum + Hash Table	–

Approach

Complexity

Prefix Sum with Modulo and HashMap

Time Complexity: O(n), where n represents the size of nums.

Space Complexity: O(k), as the hashmap stores a bounded number of potential remainders from 0 to k.

Iterative Brute Force (Naive Approach)

Time Complexity: O(n²), stemming from each subarray's reassessment of sum via double loops.

Space Complexity: O(1), because only a constant amount of auxiliary integers are engaged.

Prefix Sum + Hash Table

–

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

Frequently asked questions

Is Continuous Subarray Sum easy or hard?

Continuous Subarray Sum is classified as a medium difficulty problem. The brute force idea is straightforward, but identifying the prefix sum modulo pattern and implementing the hash map optimization requires familiarity with common interview techniques.

How to solve Continuous Subarray Sum in O(n)?

Maintain a running prefix sum while iterating through the array. Compute the remainder of the prefix sum with k and store the first occurrence of each remainder in a hash map. When the same remainder appears again and the gap between indices is at least two, a valid subarray exists. This avoids checking every subarray explicitly.

What is the best approach for Continuous Subarray Sum?

The optimal approach uses prefix sum with modulo and a hash map. While iterating through the array, store the first index where each remainder (prefixSum % k) appears. If the same remainder appears again and the index difference is at least 2, the subarray between them has a sum divisible by k. This solution runs in O(n) time with O(n) space.

What data structure is used in Continuous Subarray Sum?

The optimal solution relies on a hash map to store the earliest index for each prefix sum remainder. Combined with a running prefix sum and modulo arithmetic, the hash map allows constant-time checks to determine whether a valid subarray exists.

What is the time complexity of Continuous Subarray Sum?

The optimal prefix sum and hash map solution runs in O(n) time because the array is scanned once and each hash lookup is O(1) on average. Space complexity is O(n) for storing remainders. The brute force approach takes O(n²) time since it checks every possible subarray.

Continuous Subarray Sum Python or Java solution approach?

Both Python and Java implementations follow the same logic: compute a running prefix sum, track prefixSum % k, and store the earliest index of each remainder in a hash map. When the same remainder reappears with an index gap of at least two, return true. The complexity remains O(n) time and O(n) space.

Is Continuous Subarray Sum asked at Google, Amazon, or Meta?

Continuous Subarray Sum is a common medium-level interview problem and appears in question banks used by companies like Amazon, Google, and Meta. It tests knowledge of prefix sums, modular arithmetic, and hash maps—patterns frequently evaluated in coding interviews.

Continuous Subarray Sum solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum with Modulo and HashMap

Approach 2: Iterative Brute Force (Naive Approach)

Approach 3: Prefix Sum + Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Continuous Subarray Sum solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum with Modulo and HashMap

Approach 2: Iterative Brute Force (Naive Approach)

Approach 3: Prefix Sum + Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems