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.

Continuous Subarray Sum - LeetCode Solution

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.

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

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. By storing the earliest index where each remainder occurs, the algorithm can detect subarrays with sums divisible by k in O(n) time.

Optimal Approach

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. When a remainder repeats at a later index, check if the subarray length is at least two. If so, return true immediately. If no such subarray is found, return false.

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.

Solution

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

1

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.

2

Iterate Through Array and Track Prefix Sum Remainders

7for i in range(len(nums)):
  prefix += nums[i]
  remainder = prefix % k
  if remainder in first_seen:
      if i - first_seen[remainder] > 1:
          return True
  else:
      first_seen[remainder] = i

Objective

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

Key Insight

By computing prefix sums modulo k, the algorithm reduces the problem to detecting repeated remainders. When a remainder repeats, the subarray between the previous occurrence and the current index sums to a multiple of k. Checking that the subarray length is at least two ensures the problem's size constraint is met. Adding new remainders to the map only when first seen preserves the earliest index, maximizing subarray length detection.

Interview Quick-Check

Core Logic

For each prefix sum remainder, check if it has been seen before; if yes, verify the subarray length is at least two to return true.

State & Boundaries

Only add a remainder to the map if it is not already present to keep the earliest index.

Common Pitfalls & Bugs

Failing to check subarray length > 1 can lead to false positives for single-element subarrays.

3

Return False if No Valid Subarray Found

18	`return False`

Objective

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

Key Insight

If the iteration completes without finding two prefix sums with the same remainder separated by at least one element, no valid subarray exists. Returning false signals this outcome clearly and efficiently.

Interview Quick-Check

Core Logic

Return false only after confirming no subarray of length at least two sums to a multiple of k.

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.

Line 7 Standard

for i in range(len(nums)):

Iterate through each index in the nums array.

Sequentially processing each element allows the algorithm to build prefix sums and check for repeated remainders in a single pass.

Line 9 Standard

prefix += nums[i]

Add the current element to the prefix sum accumulator.

Updating the prefix sum is necessary to compute the current remainder modulo k, which is the key to detecting valid subarrays.

Line 10 Standard

remainder = prefix % k

Compute the current prefix sum remainder modulo k.

Taking modulo k reduces the prefix sum to a remainder class, enabling detection of subarrays whose sums are multiples of k by comparing remainders.

Line 12 Standard

if remainder in first_seen:

Check if the current remainder has been seen before in the hash map.

A repeated remainder indicates that the subarray between the previous occurrence and the current index sums to a multiple of k.

Line 13 Standard

if i - first_seen[remainder] > 1:

Verify that the subarray length between repeated remainders is at least two.

Ensuring the subarray length is greater than one satisfies the problem's requirement for subarray size, preventing false positives from single elements.

Line 14 Standard

return True

Return true immediately upon finding a valid subarray.

Early termination upon detection of a qualifying subarray optimizes performance by avoiding unnecessary further computation.

Line 15 Standard

else:

If the remainder is not in the map, record its earliest occurrence index.

Storing only the earliest index for each remainder maximizes the chance of finding the longest valid subarray and prevents overwriting with later indices.

Line 16 Standard

first_seen[remainder] = i

Assign the current index as the earliest occurrence of the remainder.

This assignment preserves the earliest index where the remainder appeared, which is critical for correct subarray length calculations.

Line 18 Standard

return False

Return false if no valid subarray is found after processing all elements.

Returning false signals that no continuous subarray of size at least two sums to a multiple of k, completing the algorithm.

Test Your Understanding

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

Because the difference between these prefix sums is divisible by k, meaning the sum of the elements between their indices is a multiple of k.

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`

7	`for i in range(len(nums)):`
9	`prefix += nums[i]`
10	`remainder = prefix % k`
12	`if remainder in first_seen:`
13	`if i - first_seen[remainder] > 1:`
14	`return True`
15	`else:`
16	`first_seen[remainder] = i`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Remainder Map and Prefix Sum Accumulator

Iterate Through Array and Track Prefix Sum Remainders

Return False if No Valid Subarray Found

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.