← DSA Atlas
Dedicated problem page · #523

Continuous Subarray Sum

MediumPrefix Sum and Difference ArrayPrefix sum remainder with hash mapHash map of prefix-sum remainders modulo k
Solve on LeetCode ↗
523
MediumPrefix Sum and Difference ArrayHash map of prefix-sum remainders modulo kPrefix sum remainder with hash map

Continuous Subarray Sum

Given an integer array nums and an integer k, return true if nums has a continuous subarray of length at least 2 whose elements sum to a multiple of k (that is, the sum equals n*k for some integer n, including 0). Otherwise return false.

Open official problem prompt ↗
In plain English

Decide whether some window of at least two consecutive elements sums to a multiple of k.

Picture it like this

Picture a clock with k hours. Each element advances the hand. If the hand returns to a position it held before, the elapsed hours between those moments is a whole number of full laps, that is, a multiple of k.

Example
Input
nums = [23, 2, 4, 6, 7], k = 6
Output
true
Why
The subarray [2, 4] has length 2 and sums to 6, which is 1 * 6
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^90 <= sum(nums) <= 2^31 - 11 <= k <= 2^31 - 1
Pattern lesson

See the pattern, then code

Prefix sum remainder with hash map
Recognition clue

Asking about a subarray sum divisible by k points to tracking prefix-sum remainders modulo k, because two prefixes with the same remainder bound a divisible subarray.

↗
Prefix Sum and Difference Array

Repeated range queries, subarray totals, balanced counts, or batched range updates.. If two prefix sums leave the same remainder mod k, the subarray between them has a sum divisible by k. Store the earliest index for each remainder so the between-length can reach at least 2.

New words, made simpleKnow these before the algorithm
Remainder
total % k, the position on the mod-k clock after adding elements.
Earliest index
The first place a remainder appeared, kept so the subarray between it and a later match is as long as possible.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Check every subarray

With n up to 10^5 the quadratic pass times out.

Try all start/end pairs of length >= 2 and test divisibility.

Time O(n^2)Space O(1)
Best choiceRemainder hash map

One pass, and the length-2 rule falls out of only recording first occurrences.

Store the first index of each prefix-sum remainder; a repeat with a gap of at least 2 proves a divisible subarray exists.

Time O(n)Space O(min(n, k))
The rule we keep true

Invariant

first_seen[r] holds the smallest index at which prefix sum had remainder r, so any later index with the same remainder maximizes the enclosed subarray length.

Why this is correct

Reasoning

If prefix[i] and prefix[j] (i < j) share a remainder mod k, then prefix[j] - prefix[i] is divisible by k, and that difference is exactly the sum of nums[i+1..j]. Seeding {0:-1} lets a prefix that is itself divisible count from the array's start.

The algorithm in three movesSay these aloud before coding
1Keep a map from remainder to earliest index, seeded with {0: -1}

rem={0:-1}

2Track the running sum and reduce it mod k each step

i0 r=23%6=5 -> {5:0}

3If the remainder was seen before and the index gap is at least 2, return true

i1 r=25%6=1 -> {1:1}

4Otherwise record the remainder's first occurrence only if new

i2 r=29%6=5 seen@0, 2-0>=2 => true

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
230
21
42
63
74
1 · Readbefore loop
2 · AskBaseline remainder?
3 · Update statefirst_seen = {0: -1}
4 · ResultEmpty prefix recorded
Key takeaway

Remainder 5 recurs at index 2 (seen at 0); the subarray between them, [2,4], is divisible by 6.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Seed and running sum

    {0:-1} makes a prefix that is already a multiple of k valid from the very start; total accumulates the running sum.

  2. 2
    Lines 7-11Match remainders with a length guard

    Only compare when the remainder recurs, and only record first occurrences so the index gap can reach 2.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A subarray of exactly length 2 is the minimum accepted
  • Two consecutive zeros sum to 0, a multiple of every k, so return true
  • A single element equal to k does not count because length must be at least 2
!

Common beginner mistakes

  • Overwriting first_seen[r] on later sightings, which shrinks the achievable gap and misses valid answers
  • Forgetting the length-at-least-2 check and accepting a zero-length or single-element window
  • Omitting the {0:-1} seed, which misses subarrays starting at index 0
Check your understanding

Why must we store only the first index for each remainder and never update it?

More in Prefix Sum and Difference Array

#303Range Sum Query – ImmutablePrecomputed prefix sums#304Range Sum Query 2D – Immutable2D precomputed prefix sums#724Find Pivot IndexRunning prefix versus suffix balance#930Binary Subarrays With SumPrefix sum counts with hash map#1094Car PoolingDifference array over positions#1109Corporate Flight BookingsRange-update via difference array