Course4all

Continuous Subarray Sum

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Arrays & Hashing.

Continuous Subarray Sum

Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.

Visual Representation

nums = [23, 2, 4, 6, 7], k = 6 Prefix Sum Modulo k: - 23 % 6 = 5 - (23+2) % 6 = 25 % 6 = 1 - (25+4) % 6 = 29 % 6 = 5 (FOUND EXISTING REMAINDER!) Subarray from index 1 to 2 has sum (2+4)=6 (multiple of 6). Size = 2 (Valid)
Medium

Examples

Input: nums = [23,2,4,6,7], k = 6
Output: true
Approach 1

Level I: Brute Force (All Subarrays)

Intuition

Iterate through all possible subarrays and calculate their sum. If any sum is a multiple of k and length is ≥2\ge 2, return true.
⏱ O(N²)💾 O(1)

Detailed Dry Run

i=0, j=1: sum=23+2=25 (Not multiple of 6) i=1, j=2: sum=2+4=6 (Multiple of 6!) return true
java
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (sum % k == 0) return true;
            }
        }
        return false;
    }
}
Approach 2

Level II: Better Solution (Prefix Sum O(N²))

Intuition

Use a prefix sum array to calculate the sum of any subarray in O(1). Iterate through all pairs (i,j)(i, j) with j−i≥1j-i \ge 1 and check if (prefix[j+1]−prefix[i])(modk)==0(prefix[j+1] - prefix[i]) \pmod k == 0.
⏱ O(N²)💾 O(N)

Detailed Dry Run

nums=[23, 2, 4], prefix=[0, 23, 25, 29] i=0, j=1: (25-0)%6 = 1 i=1, j=2: (29-23)%6 = 0 (Match!)
java
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + nums[i];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int sum = prefix[j+1] - prefix[i];
                if (sum % k == 0) return true;
            }
        }
        return false;
    }
}
Approach 3

Level III: Prefix Sum + Modulo Hashing

Intuition

If the remainder of (prefixSum[i](modk))(prefixSum[i] \pmod k) is the same as (prefixSum[j](modk))(prefixSum[j] \pmod k), then the subarray sum from i+1i+1 to jj is a multiple of kk. We use a HashMap to store remainder -> first_seen_index and check if current_index - first_seen_index >= 2.
⏱ O(N)💾 O(min(N, k))

Detailed Dry Run

nums=[23, 2, 4], k=6. Map: {0: -1}
  1. rem=5. Map: {0:-1, 5:0}
  2. rem=(5+2)%6=1. Map: {0:-1, 5:0, 1:1}
  3. rem=(1+4)%6=5. Key 5 exists at idx 0. Diff 2-0=2. return true.
java
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int rem = k == 0 ? sum : sum % k;
            if (map.containsKey(rem)) {
                if (i - map.get(rem) >= 2) return true;
            } else {
                map.put(rem, i);
            }
        }
        return false;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionIsomorphic Strings
Next Question →Container With Most Water