Continuous Subarray Sum

MediumPrefix Sum · Hash Map (Modulo)🧩 Prefix Sum LeetCode #523 ↗Updated Oct 30, 2026

Problem

Given a non-negative integer array nums and a positive integer k, decide whether some contiguous subarray of length at least 2 has a sum that is a multiple of k (zero counts as a multiple). Return true or false.

Inputnums = [23,2,4,6,7], k = 6Outputtrue ([2,4] sums to 6)

Inputnums = [23,2,6,4,7], k = 6Outputtrue (whole array sums to 42)

Inputnums = [23,2,6,4,7], k = 13Outputfalse

1 ≤ n ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁹ · total sum ≤ 2³¹-1 · 1 ≤ k ≤ 2³¹-1

Try it yourself

Java

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A subarray (i, j] sums to a multiple of k exactly when the prefix sums at i and j leave the same remainder mod k. Remember the earliest index of each remainder and check that the gap is at least 2.

PatternPrefix Sum

Instinct Repeated range-sum queries, or "count subarrays whose sum equals / divides K" with negatives allowed? Store running totals and subtract two of them.

Memory hack Any range is two prefixes apart - sum(i..j) = P[j+1] - P[i], so remember every P you've passed.

Open the Prefix Sum guide →

Approaches

Brute ForceAll Subarrays with Running Sum

Time O(n²)Space O(1)

Fix a start index and extend the end, maintaining the running sum. As soon as a window of length ≥ 2 has sum % k == 0, we are done. A running sum avoids re-adding the window each time.

Java

public boolean checkSubarraySum(int[] nums, int k) {
    int n = nums.length;
    for (int start = 0; start < n; start++) {
        long sum = nums[start];
        for (int end = start + 1; end < n; end++) {
            sum += nums[end];
            if (sum % k == 0) return true; // length >= 2 guaranteed
        }
    }
    return false;
}

Obviously correct, but quadratic — times out at n = 10⁵.

OptimalPrefix Remainder → Earliest Index

Time O(n)Space O(min(n, k))

Walk the array keeping rem = prefixSum % k. Seed the map with remainder 0 at index -1 (the empty prefix). If the current remainder was seen at index p and i - p ≥ 2, the subarray p+1..i works. Store only the first index of each remainder so gaps are as long as possible.

Java

public boolean checkSubarraySum(int[] nums, int k) {
    Map<Long, Integer> firstSeen = new HashMap<>();
    firstSeen.put(0L, -1); // empty prefix
    long rem = 0;
    for (int i = 0; i < nums.length; i++) {
        rem = (rem + nums[i]) % k;
        Integer prev = firstSeen.get(rem);
        if (prev == null) {
            firstSeen.put(rem, i); // keep the earliest index only
        } else if (i - prev >= 2) {
            return true;
        }
    }
    return false;
}

Dry runnums = [23,2,4,6,7], k = 6

i current index changed

init
23

2

4

6

7

map {0:-1}
i=0
23
i
2

4

6

7

rem=5, map {5:0}
i=1
23

2
i
4

6

7

rem=1, map {1:1}
i=2
23

2

4
i
6

7

rem=5 seen at 0, gap 2
done
23

2

4

6

7

[2,4] → true ✔

One pass with a hash map; the standard “equal remainders” trick.

Pro tip

Never overwrite an existing remainder — a later index only shortens the gap and can hide valid answers like [0,0].

At a glance

Level	Approach	Time	Space
Brute Force	All Subarrays with Running Sum	`O(n²)`	`O(1)`
Optimal	Prefix Remainder → Earliest Index	`O(n)`	`O(min(n, k))`

Common pitfalls

Forgetting the {0: -1} seed — misses subarrays that start at index 0.
Updating the stored index on every hit — breaks the length ≥ 2 check (e.g. [5,0,0]).
Treating a single element divisible by k as valid — length must be ≥ 2.

Interview tips

Derive it: (P[j] - P[i]) % k == 0 ⇔ P[j] % k == P[i] % k.
Explain why a map (index) is needed instead of a set: the length constraint.
Mention handling negatives with ((x % k) + k) % k if inputs could be negative.

Pattern

Prefix sum + remainder map → subarray sums that must be divisible by k, with a length condition.

My notes saved in this browser