Continuous Subarray Sum

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

O(n). The algorithm iterates through the array once, performing O(1) operations per element including hash map lookups and insertions.

Q: What pattern does Continuous Subarray Sum use?

The Pattern: Hash Maps (Prefix Sum Remainder Tracking) The Heuristic: When searching for subarrays whose sums satisfy modular conditions, track prefix sums modulo k and store their earliest occurrence indices in a hash map; repeated remainders indicate subarrays summing to multiples of k.

Medium Hash Maps

Problem

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.

1 ≤ nums.length ≤ 10⁵
−10⁹ ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ 10⁹

Example

Input: nums = [23, 2, 4, 6, 7], k = 6

Output: True

The subarray [2, 4] sums to 6, which is a multiple of 6. The algorithm maintains prefix sums modulo k and records the earliest index where each remainder occurs. When the same remainder appears again at a later index, the subarray between these indices sums to a multiple of k. Here, the remainder 0 is first seen at index -1 (initial state), and again at index 2 (prefix sum of first three elements modulo 6), indicating a subarray of length at least two that satisfies the condition.

Approach

Straightforward Solution

A brute-force approach checks all subarrays of length at least two, summing elements and checking divisibility by k. This approach is O(n^2) and too slow for large inputs.

Core Observation

If the sum of elements from index i to j is a multiple of k, then the prefix sums modulo k at indices i-1 and j are equal. This means that the difference between these prefix sums is divisible by k, revealing a subarray summing to a multiple of k.

Path to Optimal

Preview

The key recognition signals are 'continuous subarray', 'sum is multiple of k', and 'at least size two'. These indicate using prefix sums combined with a hash map to track remainders modulo k…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through nums, accumulating a prefix sum modulo k. Use a hash map to record the earliest index where each remainder appears, initializing with remainder 0 at index -1 to handle subarrays starting at index 0…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm iterates through the array once, performing O(1) operations per element including hash map lookups and insertions.

Space

O(min(n, k))

The hash map stores at most one entry per unique remainder modulo k. Since remainders range from 0 to k-1, the space is bounded by the smaller of n and k.

Pattern Spotlight

Hash Maps (Prefix Sum Remainder Tracking)

When searching for subarrays whose sums satisfy modular conditions, track prefix sums modulo k and store their earliest occurrence indices in a hash map; repeated remainders indicate subarrays summing to multiples of k.

Solution

Python

1class Solution:
2    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
3
4        first_seen = {0: -1}
5        prefix = 0
6
7        for i in range(len(nums)):
8
9            prefix += nums[i]
10            remainder = prefix % k
11
12            if remainder in first_seen:
13                if i - first_seen[remainder] > 1:
14                    return True
15            else:
16                first_seen[remainder] = i
17
18        return False

Step-by-Step Solution

Initialize Remainder Map and Prefix Sum Accumulator

4first_seen = {0: -1}
5prefix = 0

Objective

To set up a hash map to record the earliest index of each prefix sum remainder and initialize the prefix sum accumulator.

Key Insight

Storing the remainder 0 at index -1 handles the edge case where a valid subarray starts at index 0. This initialization ensures that when the prefix sum modulo k equals zero at index i, the subarray from index 0 to i sums to a multiple of k. The prefix sum accumulator tracks the cumulative sum as the iteration progresses.

Interview Quick-Check

Core Logic

Initialize the hash map with remainder 0 mapped to index -1 to correctly detect subarrays starting at the beginning.

Common Pitfalls & Bugs

Forgetting to initialize remainder 0 at index -1 causes missing valid subarrays that start at index 0.

Iterate Through Array and Track Prefix Sum Remainders

To accumulate prefix sums modulo k and detect repeated remainders indicating valid subarrays.

Return False if No Valid Subarray Found

To conclude the search by returning false when no qualifying subarray exists.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 4 Critical

first_seen = {0: -1}

Initialize a hash map to store prefix sum remainders with their earliest indices, starting with remainder 0 at index -1.

Mapping remainder 0 to index -1 handles subarrays starting at index 0, enabling detection of valid subarrays whose prefix sum modulo k is zero from the start.

Line 5 Critical

prefix = 0

Initialize the prefix sum accumulator to zero.

The prefix sum accumulator tracks the cumulative sum of elements as the array is traversed, which is essential for computing remainders modulo k.

Full line-by-line criticality + rationale for all 11 lines available on Pro.

Test Your Understanding

Why does detecting two prefix sums with the same remainder modulo k guarantee a subarray summing to a multiple of k?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Continuous Subarray Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Continuous Subarray Sum drill

or drill a free problem

1	`class Solution:`
2	`def checkSubarraySum(self, nums: List[int], k: int) -> bool:`
3
4	`first_seen = {0: -1}`
5	`prefix = 0`
6
7	`for i in range(len(nums)):`
8
9	`prefix += nums[i]`
10	`remainder = prefix % k`
11
12	`if remainder in first_seen:`
13	`if i - first_seen[remainder] > 1:`
14	`return True`
15	`else:`
16	`first_seen[remainder] = i`
17
18	`return False`