Continuous Subarray Sum

Master this topic with zero to advance depth.

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 $\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)$ with $j-i \ge 1$ and check if $(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] \pmod k)$ is the same as $(prefixSum[j] \pmod k)$ , then the subarray sum from $i+1$ to $j$ is a multiple of $k$ . 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}

rem=5. Map: {0:-1, 5:0}
rem=(5+2)%6=1. Map: {0:-1, 5:0, 1:1}
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;
    }
}

← Previous QuestionIsomorphic Strings

Next Question →Container With Most Water

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.