Continuous Subarray Sum

1. Define the problem

Given an integer array nums and an integer k, return true if nums has a contiguous subarray of size at least 2 whose sum is a multiple of k , or false otherwise. Two prefix sums that share the same remainder mod k differ by a multiple of k. Track the first index each remainder was seen — if the same remainder shows up again at least 2 indices later, that stretch's sum is a multiple of k.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums_i ≤ 10⁹
0 ≤ sum(nums_i) ≤ 2³¹ - 1
1 ≤ k ≤ 2³¹ - 1

Example

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

Outputtrue

Explanation nums[1..2] = [2, 4] sums to 6, which is a multiple of 6, and has length 2.

2. Know the words first

In plain terms

Multiple of k: A number that k divides evenly, with no remainder — 0 counts as a multiple of every k.

3. Visualize the solution

Match remainders of the running sum modulo k

023

Statusinit

sum=23, remainder=23%6=5. New remainder, record firstIndex[5]=0.

What happens in this step

firstIndex = {0: -1}   sum = 0

i=0: sum += nums[0]=23 → sum = 23
  remainder = 23 % 6 = 5
  firstIndex has no key 5 → record firstIndex[5] = 0
  firstIndex = {0: -1, 5: 0}

Step 1 of 3

Steps to visualize

Start a hashmap with {0: -1} — a remainder of 0 was "seen" before the array begins.
Walk the array, adding each value onto a running sum, then taking that sum modulo k.
If this remainder was seen before at an index at least 2 back, return true.
If this remainder is new, record its index. Return false if the array ends with no match.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Match remainders of the running sum modulo k

023

Statusinit

sum=23, remainder=23%6=5. New remainder, record firstIndex[5]=0.

What happens in this step

firstIndex = {0: -1}   sum = 0

i=0: sum += nums[0]=23 → sum = 23
  remainder = 23 % 6 = 5
  firstIndex has no key 5 → record firstIndex[5] = 0
  firstIndex = {0: -1, 5: 0}

Step 1 of 3

5. Solution

Solution

solution.tsTypeScript

function checkSubarraySum(nums, k) {
  const firstIndex = new Map([[0, -1]]);
  let sum = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    const remainder = ((sum % k) + k) % k;

    if (firstIndex.has(remainder)) {
      if (i - firstIndex.get(remainder) >= 2) {
        return true;
      }
    } else {
      firstIndex.set(remainder, i);
    }
  }

  return false;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`nums = [23, 2, 4, 6, 7], k = 6`	`true`	example from the docstring
`nums = [23, 2, 6, 4, 7], k = 6`	`true`	only the entire array forms a valid multiple
`nums = [23, 2, 6, 4, 7], k = 13`	`false`	no remainder repeats with a gap of at least 2
`nums = [0, 0], k = 1`	`true`	zero values that are trivially a multiple of any k
`nums = [1, 2, 3], k = 7`	`false`	a k larger than any achievable remainder repeat
`nums = [7], k = 5`	`false`	array too short to form a subarray of size 2

Continuous Subarray Sum