Continuous Subarray Sum

You want to find a run of numbers that adds up to a multiple of k. Checking every run is slow. The interviewer wants to see if you know a remainder trick that makes it fast. That trick is the whole point of this question.

🎯 The Problem

You get an array and a number k. Say if some run of numbers sums to a multiple of k.

• A run of numbers next to each other is a subarray.
• The run must have at least two numbers.
• Its sum must be a multiple of k. So dividing it by k leaves no leftover.
• Return true if such a run exists. Otherwise false.
• A single number that happens to be a multiple of k does not count.

Say the array is [23, 2, 4, 6, 7] and k is 6. Look at 2 + 4, which is 6. That is a multiple of 6. The run has two numbers. So the answer is true.

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

Explanation: the subarray [2, 4] sums to 6, which is a multiple of 6.

Here is the array with the matching run marked.

🐢 Approach 1: Try Every Run (Brute Force)

The idea in one line: check every run and test its sum.

The idea:

• Pick a start.
• Grow the run to the right one number at a time.
• Keep a running sum and test it each step.

How it works:

• One loop picks the start position.
• A second loop adds numbers going forward.
• Test the sum each time.
• If any run of length two or more is a multiple of k, return true.

Why it is weak:

• There are about n times n runs to check.
• That is O(n²) work.
• A big array makes this slow.

Here is the brute-force code for that idea:

def check_subarray_sum(nums, k):
    for start in range(len(nums)):
        total = 0
        for end in range(start, len(nums)):
            total += nums[end]
            if end - start + 1 >= 2 and total % k == 0:
                return True

    return False


print(check_subarray_sum([23, 2, 4, 6, 7], 6))

⚡ Approach 2: Prefix Sum Mod K With a Hash Map (Best)

The idea in one line: two prefix sums with the same remainder mean the run between them is a multiple of k.

The idea:

• A prefix sum is the total from the start up to the current spot.
• The sum of a run equals the prefix sum at the end minus the prefix sum at the start.
• Store each prefix sum’s remainder mod k, not the raw sum.
• The remainder is what is left over after dividing by k.
• Equal remainders cancel out, so the run between them is a multiple of k.

How it works:

• Walk the array once, keeping a running prefix sum.
• At each step, take its remainder mod k.
• Store each remainder in a hash map with the first index where you saw it.
• A hash map looks up a key almost instantly.
• See a remainder again with a gap of at least two, and the answer is true.
• Seed the map with remainder 0 at index -1 to catch a run that starts at the very beginning.
• Keep only the first index for each remainder, so the gap stays as wide as possible.

Why it is fast:

• One pass with fast lookups. That is O(n) time.
• The map holds at most k remainders. That is O(k) space.

Here is the dry run on [23, 2, 4, 6, 7] with k = 6.

Steps to Solve

1. Create a hash map and put remainder 0 at index -1.
2. Walk the array, keeping a running prefix sum.
3. At each index, take the remainder of the prefix sum mod k.
4. If that remainder is already in the map, and the gap to the stored index is at least two, return true.
5. If the remainder is new, store it with the current index.
6. If the walk ends with no match, return false.

#include <stdio.h>
#include <string.h>

int checkSubarraySum(int nums[], int n, int k) {
    int first[1000];
    for (int i = 0; i < k; i++) first[i] = -2;  // not seen yet
    first[0] = -1;   // remainder 0 before the array starts

    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += nums[i];
        int rem = sum % k;          // remainder of prefix sum
        if (first[rem] == -2) {
            first[rem] = i;         // store the first index
        } else if (i - first[rem] >= 2) {
            return 1;               // run of length 2 or more
        }
    }
    return 0;
}

int main(void) {
    int nums[] = {23, 2, 4, 6, 7};
    printf("%s\n", checkSubarraySum(nums, 5, 6) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

bool checkSubarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> first;  // remainder -> first index
    first[0] = -1;                  // remainder 0 before start

    int sum = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        sum += nums[i];
        int rem = sum % k;          // remainder of prefix sum
        if (first.count(rem)) {
            if (i - first[rem] >= 2) return true;  // length 2+
        } else {
            first[rem] = i;         // store the first index
        }
    }
    return false;
}

int main() {
    vector<int> nums = {23, 2, 4, 6, 7};
    cout << (checkSubarraySum(nums, 6) ? "true" : "false") << endl;
    return 0;
}

true

import java.util.HashMap;
import java.util.Map;

public class ContinuousSubarraySum {
    static boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> first = new HashMap<>();  // rem -> index
        first.put(0, -1);   // remainder 0 before the array starts

        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int rem = sum % k;          // remainder of prefix sum
            if (first.containsKey(rem)) {
                if (i - first.get(rem) >= 2) return true;  // length 2+
            } else {
                first.put(rem, i);      // store the first index
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = { 23, 2, 4, 6, 7 };
        System.out.println(checkSubarraySum(nums, 6));
    }
}

true

def check_subarray_sum(nums, k):
    first = {0: -1}   # remainder 0 sits before the array starts
    total = 0
    for i, num in enumerate(nums):
        total += num
        rem = total % k            # remainder of the prefix sum
        if rem in first:
            if i - first[rem] >= 2:   # run of length 2 or more
                return True
        else:
            first[rem] = i         # store the first index for this rem
    return False


nums = [23, 2, 4, 6, 7]
print(check_subarray_sum(nums, 6))

True

function checkSubarraySum(nums, k) {
  const first = new Map(); // remainder -> first index
  first.set(0, -1); // remainder 0 before the array starts

  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    const rem = sum % k; // remainder of the prefix sum
    if (first.has(rem)) {
      if (i - first.get(rem) >= 2) return true; // length 2 or more
    } else {
      first.set(rem, i); // store the first index
    }
  }
  return false;
}

const nums = [23, 2, 4, 6, 7];
console.log(checkSubarraySum(nums, 6));

true

Let us walk through the Python version line by line. The line first = {0: -1} seeds the map with remainder 0 at index -1. This covers a run from the very start that is already a multiple of k. Without it, such a run would be missed.

The loop for i, num in enumerate(nums) walks the array with both the index and the value. The line total += num keeps the running prefix sum. So after 23 and 2 and 4, the total is 29.

The line rem = total % k takes the remainder. For total 29 and k = 6, the remainder is 5. We store remainders, not raw sums, because two equal remainders mean the run between them is a multiple of k.

The check if rem in first asks if we saw this remainder before. We saw remainder 5 earlier at index 0, after the number 23. Now we are at index 2. The line if i - first[rem] >= 2 confirms the gap is at least two, so the run has two or more numbers. The gap from 0 to 2 is 2, so we return True. If the remainder is new, the else branch stores it with the current index. We keep only the first index so the gap stays as wide as possible.

⏱️ Time and Space Complexity

The brute force checks every run, so it is O(n²). The prefix sum plus hash map walks the array one time with fast lookups, so it is O(n). The map can hold up to k different remainders, so the space is O(k).

🧩 Key Takeaways

• ✅ A run that is a multiple of k shows up as two prefix sums with the same remainder.
• ✅ Store remainders in a hash map, not the raw sums.
• ✅ Seed the map with remainder 0 at index -1 to catch a run from the start.
• ✅ Keep only the first index for each remainder so the gap stays wide.
• ✅ This turns an O(n²) search into one O(n) pass.

🚀 What’s Next?

• Maximum Swap
• Buildings With an Ocean View