523. Continuous Subarray Sum - Detailed Explanation

Problem Statement

Given an integer array nums and an integer k, determine if there exists a continuous subarray of size at least two whose sum is a multiple of k (i.e. sum = m·k for some integer m). Return true if such a subarray exists, otherwise return false.

Examples

1. Input
   nums = [23, 2, 4, 6, 7], k = 6
   Output
   true
   Explanation
   The subarray [2, 4] sums to 6, which is 1·6

2. Input
   nums = [23, 2, 6, 4, 7], k = 6
   Output
   true
   Explanation
   [23, 2, 6, 4, 7] sums to 42 = 7·6

3. Input
   nums = [23, 2, 6, 4, 7], k = 13
   Output
   false

Constraints

• 1 ≤ nums.length ≤ 10⁵
• -10⁹ ≤ nums[i] ≤ 10⁹
• 0 ≤ k ≤ 10⁹

Hints

1. A brute‑force scan over all subarrays is O(n²) and will time out for n up to 10⁵.
2. Use prefix sums and the fact that

   if (sum[j] - sum[i]) % k == 0 
   ⇔ sum[j] % k == sum[i] % k
   

   to detect a valid subarray in O(n) time.

Approaches

Brute‑Force Subarray Check

Explanation

• Compute prefix sum array S of length n+1 where S[0]=0 and S[i]=sum(nums[0..i-1]).
• For every pair (i, j) with j - i ≥ 2, check if (S[j] - S[i]) % k == 0.
• If any pair satisfies this, return true.

Step‑by‑Step for [23,2,4,6,7], k=6

S = [0,23,25,29,35,42]
Check i=0,j=2: (S[2]-S[0])=25  → 25%6=1  ✗
i=0,j=3: 29→29%6=5  ✗
i=0,j=4: 35→35%6=5  ✗
i=0,j=5: 42→42%6=0  ✓ return true

Complexity Analysis

• Time O(n²) — double loop over i and j
• Space O(n) — prefix sums

Prefix‑Sum Modulo with HashMap

Explanation

• Maintain a running sum sum and a map modIndex from sum % k to the earliest index where this mod appeared.
• Initialize modIndex.put(0, -1) so that if sum % k == 0 at index ≥1, subarray from 0…i is valid.
• Iterate i from 0 to n-1:
  1. Update sum += nums[i].
  2. Compute mod = k == 0 ? sum : sum % k.
  3. If mod is already in modIndex and i - modIndex.get(mod) ≥ 2, return true.
  4. Otherwise, if mod not seen before, record modIndex.put(mod, i).
• At end, return false.

Handling k = 0

• If k == 0, look only for a subarray of length ≥2 with sum exactly 0. In that case, you can track running sum and check if it repeats (or track two consecutive zeros).

Step‑by‑Step for [23,2,4,6,7], k=6

modIndex = {0 → -1}
i=0: sum=23, mod=23%6=5, store 5→0
i=1: sum=25, mod=25%6=1, store 1→1
i=2: sum=29, mod=29%6=5, seen at index 0, length = 2-0 = 2 ≥2 → return true

Complexity Analysis

• Time O(n) — one pass with O(1) map operations
• Space O(min(n, k)) — map of seen mods

Python Code