523. Continuous Subarray Sum

mediumAsked at Meta

Given an array and integer k, return true if there's a contiguous subarray of size at least 2 whose sum is a multiple of k. Meta asks this to test whether you reach for prefix sums + mod and articulate the 'same remainder means divisible difference' trick.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Meta loops.

Glassdoor (2026-Q1)— Meta E4 onsite reports cite this as a recurring prefix-sum problem.
Blind (2025-10)— Recurring Meta interview problem.

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. An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Constraints

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= sum(nums[i]) <= 2^31 - 1
1 <= k <= 2^31 - 1

Examples

Example 1

Input

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

Output

true

Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2

Input

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

Output

true

Explanation: [23, 2, 6, 4, 7] is an array of size 5 whose elements sum up to 42 = 7 * 6.

Example 3

Input

nums = [23,2,6,4,7], k = 13

Output

false

Approaches

1. Brute-force prefix sums

Compute prefix sums. For each (i, j) with j - i >= 2, check (prefix[j] - prefix[i]) % k === 0.

Time: O(n^2)
Space: O(n)

function checkSubarraySumBrute(nums, k) {
  const prefix = [0];
  for (const x of nums) prefix.push(prefix[prefix.length - 1] + x);
  for (let i = 0; i < prefix.length; i++) {
    for (let j = i + 2; j < prefix.length; j++) {
      if ((prefix[j] - prefix[i]) % k === 0) return true;
    }
  }
  return false;
}

Tradeoff: Quadratic — fails at the upper bound. Mention only to anchor the optimal.

2. Hash map of prefix sums mod k (optimal)

If two prefix sums have the same value mod k, the subarray between them is a multiple of k. Track first-seen index per residue.

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

function checkSubarraySum(nums, k) {
  const seen = new Map();
  seen.set(0, -1); // empty prefix at index -1
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    const r = sum % k;
    if (seen.has(r)) {
      if (i - seen.get(r) >= 2) return true;
    } else {
      seen.set(r, i);
    }
  }
  return false;
}

Tradeoff: Linear. The trick: (prefix[j] - prefix[i]) % k = 0 iff prefix[j] % k === prefix[i] % k. So tracking residues and their first occurrence gives O(n).

Meta-specific tips

Meta interviewers want the residue-equality trick articulated. State out loud: 'If two prefix sums have the same remainder mod k, the subarray between them is divisible by k. So I track the first index where each remainder appears.' The length >= 2 constraint is handled by checking i - seenIdx >= 2.

Common mistakes

Forgetting to seed seen[0] = -1 (otherwise misses subarrays starting at index 0).
Updating seen[r] every time instead of only on first occurrence — overwrites the early index.
Forgetting the length >= 2 check — single-element subarrays don't qualify.
Not handling k = 0 if the problem allowed it (here k >= 1).

Follow-up questions

An interviewer at Meta may pivot to one of these next:

What if we wanted to count all such subarrays, not just check existence?
Contiguous Array (LC 525) — same prefix-sum trick on 0/1 arrays.
Subarray Sum Equals K (LC 560) — prefix sums without the mod.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does residue equality imply divisibility of the difference?

If a ≡ b (mod k), then a - b ≡ 0 (mod k). So (prefix[j] - prefix[i]) % k == 0 ↔ prefix[j] % k == prefix[i] % k.

Why store first occurrence, not last?

We want the longest possible subarray ending at i for a given residue. Storing the first occurrence maximizes the gap, making the length >= 2 check more likely to pass.

Practice these live with InterviewChamp.AI

Drill Continuous Subarray Sum and other Meta interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →