50. Continuous Subarray Sum

🔗 LeetCode Problem: 523. Continuous Subarray Sum
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, Math, Prefix Sum

Problem Statement

Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.

A good subarray is a subarray where: - Its length is at least two, and - The sum of the elements of the subarray is a multiple of k.

Note: A subarray is a contiguous part of the array.

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 a continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 × 6 and 7 is an integer.

Example 3:

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

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

---

🎨 Visual Understanding

The Problem Visualized

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

Check all subarrays of length >= 2:

[23, 2] → sum = 25, 25 % 6 = 1 ✗
[23, 2, 4] → sum = 29, 29 % 6 = 5 ✗
[2, 4] → sum = 6, 6 % 6 = 0 ✓ Found!

Answer: true

Key Observation: Using Modulo Arithmetic

For a subarray from index i to j:
  sum[i:j] = prefixSum[j] - prefixSum[i-1]

We want: sum[i:j] % k = 0
Which means: (prefixSum[j] - prefixSum[i-1]) % k = 0

Mathematical property:
  (a - b) % k = 0  means  a % k = b % k

So we need:
  prefixSum[j] % k = prefixSum[i-1] % k

The Insight: Same Remainder = Valid Subarray

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

Calculate prefix sums and remainders:
Index:    -1    0    1    2    3    4
Prefix:    0   23   25   29   35   42
Mod k:     0    5    1    5    5    0

Look for repeated remainders with distance >= 2:

Remainder 5 appears at:
  - Index -1 (prefix = 0)
  - Index 0 (prefix = 23)
  - Index 2 (prefix = 29)
  - Index 3 (prefix = 35)

Index 0 and Index 2 both have remainder 5
Distance = 2 - 0 = 2 >= 2 ✓

Subarray from index 1 to 2: [2, 4]
Sum = 6, which is 6 % 6 = 0 ✓

Why This Works

If prefixSum[j] % k = prefixSum[i] % k

Then:
  prefixSum[j] = a × k + r
  prefixSum[i] = b × k + r
  (where r is the common remainder)

Subarray sum:
  prefixSum[j] - prefixSum[i]
  = (a × k + r) - (b × k + r)
  = a × k - b × k
  = (a - b) × k
  = multiple of k! ✓

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Check all subarrays of length >= 2:
1. For each starting position i
2. For each ending position j (where j - i >= 1)
3. Calculate sum of subarray [i, j]
4. Check if sum % k == 0

Implementation

public boolean checkSubarraySum(int[] nums, int k) {
    int n = nums.length;

    // Check all subarrays of length >= 2
    for (int i = 0; i < n - 1; i++) {
        int sum = nums[i];
        for (int j = i + 1; j < n; j++) {
            sum += nums[j];
            if (sum % k == 0) {
                return true;
            }
        }
    }

    return false;
}

⏰ Time: O(n²) - nested loops
💾 Space: O(1) - only variables

---

🎯 Approach 2: Prefix Sum Array with Nested Loop

Better than Brute Force 💡

Core Logic:

Build prefix sum array first, then check:

Key insight:
  If (prefixSum[j] - prefixSum[i]) % k == 0
  Then subarray from i+1 to j is divisible by k

Algorithm:
1. Build prefix sum array
2. Check all pairs (i, j) where j - i >= 2
3. For each pair, check if difference % k == 0

Visual Explanation:

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

Step 1: Build prefix sum array
  prefixSum[0] = 0
  prefixSum[1] = 0 + 23 = 23
  prefixSum[2] = 23 + 2 = 25
  prefixSum[3] = 25 + 4 = 29
  prefixSum[4] = 29 + 6 = 35
  prefixSum[5] = 35 + 7 = 42

  prefixSum = [0, 23, 25, 29, 35, 42]

Step 2: Check all valid pairs (j - i >= 2)

  i=0, j=2: (25 - 0) % 6 = 25 % 6 = 1 ✗
  i=0, j=3: (29 - 0) % 6 = 29 % 6 = 5 ✗
  i=0, j=4: (35 - 0) % 6 = 35 % 6 = 5 ✗
  i=0, j=5: (42 - 0) % 6 = 42 % 6 = 0 ✓ Found!

Subarray from index 1 to 5: [2, 4, 6, 7]
Sum = 42 - 0 = 42, which is 42 % 6 = 0 ✓

Implementation

public boolean checkSubarraySum(int[] nums, int k) {
    int n = nums.length;

    // Build prefix sum array
    int[] prefixSum = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    // Check all pairs with distance >= 2
    for (int i = 0; i < n; i++) {
        for (int j = i + 2; j <= n; j++) {
            // Subarray from index i to j-1 (length >= 2)
            int subarraySum = prefixSum[j] - prefixSum[i];
            if (subarraySum % k == 0) {
                return true;
            }
        }
    }

    return false;
}

⏰ Time: O(n²) - nested loops checking all pairs
💾 Space: O(n) - prefix sum array

Why This is Better than Brute Force: - Brute Force: Recalculate sum for each subarray → O(n²) with repeated work - This Approach: Precompute sums, then O(1) to get any subarray sum → O(n²) but cleaner

---

✅ Approach 3: Prefix Sum Modulo with HashMap (Optimal)

The Ultimate Optimization 💡

Core Logic:

Use prefix sum + modulo + hashmap:

Key insight:
  If prefixSum[j] % k == prefixSum[i] % k
  Then sum[i+1:j] is divisible by k

Algorithm:
1. Track remainder of running sum modulo k
2. Store first occurrence of each remainder in hashmap
3. If same remainder seen again with distance >= 2:
   - Found valid subarray!

Visual Explanation:

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

Running sum and remainder:

Index -1: sum = 0, remainder = 0 % 6 = 0
  map = {0: -1}

Index 0: sum = 23, remainder = 23 % 6 = 5
  map = {0: -1, 5: 0}

Index 1: sum = 25, remainder = 25 % 6 = 1
  map = {0: -1, 5: 0, 1: 1}

Index 2: sum = 29, remainder = 29 % 6 = 5
  Remainder 5 seen before at index 0!
  Distance = 2 - 0 = 2 >= 2 ✓
  Found valid subarray [2, 4]!

Return true

Why Store Index -1 with Remainder 0?

Edge case: Entire prefix is divisible by k

nums = [6, 0], k = 6

Index 0: sum = 6, remainder = 0
  If we check map, remainder 0 was at index -1
  Distance = 0 - (-1) = 1... wait, that's only 1 element!

  But at index 1:
  sum = 6, remainder = 0
  Distance = 1 - (-1) = 2 >= 2 ✓
  Subarray [6, 0] is valid!

Initial map: {0: -1} handles this case

Implementation

public boolean checkSubarraySum(int[] nums, int k) {
    // Map: remainder -> first index where this remainder was seen
    Map<Integer, Integer> map = new HashMap<>();

    // Initialize: remainder 0 at index -1
    // This handles case where entire prefix is divisible by k
    map.put(0, -1);

    int sum = 0;

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

        if (map.containsKey(remainder)) {
            // Found same remainder before
            // Check if distance >= 2
            if (i - map.get(remainder) >= 2) {
                return true;
            }
        } else {
            // First time seeing this remainder
            map.put(remainder, i);
        }
    }

    return false;
}

⏰ Time: O(n) - single pass through array
💾 Space: O(min(n, k)) - hashmap stores at most k different remainders

---

🔍 Step-by-Step Execution

Approach 2: Prefix Sum Array - Example: nums = [23, 2, 4, 6, 7], k = 6

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [23, 2, 4, 6, 7]
k = 6
n = 5


Step 1: Build Prefix Sum Array
═══════════════════════════════════════════════════════════════════

prefixSum[0] = 0 (no elements before index 0)
prefixSum[1] = 0 + 23 = 23
prefixSum[2] = 23 + 2 = 25
prefixSum[3] = 25 + 4 = 29
prefixSum[4] = 29 + 6 = 35
prefixSum[5] = 35 + 7 = 42

prefixSum = [0, 23, 25, 29, 35, 42]


Step 2: Check All Valid Pairs (distance >= 2)
═══════════════════════════════════════════════════════════════════

i=0: Check all j where j >= i+2 (i.e., j >= 2)
───────────────────────────────────────────────────────────────────
  j=2: sum = prefixSum[2] - prefixSum[0] = 25 - 0 = 25
       25 % 6 = 1 ✗

  j=3: sum = prefixSum[3] - prefixSum[0] = 29 - 0 = 29
       29 % 6 = 5 ✗

  j=4: sum = prefixSum[4] - prefixSum[0] = 35 - 0 = 35
       35 % 6 = 5 ✗

  j=5: sum = prefixSum[5] - prefixSum[0] = 42 - 0 = 42
       42 % 6 = 0 ✓ FOUND!

       Subarray: indices 1 to 5 → [2, 4, 6, 7]
       Sum: 42

       Return true


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: true (found early, didn't need to check i=1,2,3)
═══════════════════════════════════════════════════════════════════

Note: Could also find it earlier if we checked:
  i=0, j=2: [23, 2] → sum = 25, 25 % 6 = 1 ✗
  i=1, j=3: [2, 4] → sum = 29-23 = 6, 6 % 6 = 0 ✓

Approach 3: HashMap - Example: nums = [23, 2, 4, 6, 7], k = 6

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [23, 2, 4, 6, 7]
k = 6
map = {0: -1}
sum = 0


Index 0: nums[0] = 23
═══════════════════════════════════════════════════════════════════
sum = 0 + 23 = 23
remainder = 23 % 6 = 5

Check map for remainder 5: NOT found

Add to map:
  map = {0: -1, 5: 0}


Index 1: nums[1] = 2
═══════════════════════════════════════════════════════════════════
sum = 23 + 2 = 25
remainder = 25 % 6 = 1

Check map for remainder 1: NOT found

Add to map:
  map = {0: -1, 5: 0, 1: 1}


Index 2: nums[2] = 4
═══════════════════════════════════════════════════════════════════
sum = 25 + 4 = 29
remainder = 29 % 6 = 5

Check map for remainder 5: FOUND at index 0!

Distance check:
  i - map.get(5) = 2 - 0 = 2
  Is 2 >= 2? YES ✓

Found valid subarray!

Subarray: indices 1 to 2 → [2, 4]
Sum: 2 + 4 = 6
6 % 6 = 0 ✓

Return true


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: true
═══════════════════════════════════════════════════════════════════

Explanation:
  prefixSum[0] = 23, 23 % 6 = 5
  prefixSum[2] = 29, 29 % 6 = 5

  Same remainder means:
    sum(index 1 to 2) = 29 - 23 = 6
    6 % 6 = 0 ✓

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

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [23, 2, 6, 4, 7]
k = 13
map = {0: -1}
sum = 0


Index 0: nums[0] = 23
═══════════════════════════════════════════════════════════════════
sum = 23
remainder = 23 % 13 = 10

map = {0: -1, 10: 0}


Index 1: nums[1] = 2
═══════════════════════════════════════════════════════════════════
sum = 25
remainder = 25 % 13 = 12

map = {0: -1, 10: 0, 12: 1}


Index 2: nums[2] = 6
═══════════════════════════════════════════════════════════════════
sum = 31
remainder = 31 % 13 = 5

map = {0: -1, 10: 0, 12: 1, 5: 2}


Index 3: nums[3] = 4
═══════════════════════════════════════════════════════════════════
sum = 35
remainder = 35 % 13 = 9

map = {0: -1, 10: 0, 12: 1, 5: 2, 9: 3}


Index 4: nums[4] = 7
═══════════════════════════════════════════════════════════════════
sum = 42
remainder = 42 % 13 = 3

map = {0: -1, 10: 0, 12: 1, 5: 2, 9: 3, 3: 4}


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: false
═══════════════════════════════════════════════════════════════════

No repeated remainders with distance >= 2 found.
All remainders are unique!

Example 3: nums = [0, 0], k = 1

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [0, 0]
k = 1
map = {0: -1}
sum = 0


Index 0: nums[0] = 0
═══════════════════════════════════════════════════════════════════
sum = 0
remainder = 0 % 1 = 0

Check map for remainder 0: FOUND at index -1!

Distance check:
  i - map.get(0) = 0 - (-1) = 1
  Is 1 >= 2? NO ✗

Don't update map (keep first occurrence):
  map = {0: -1}


Index 1: nums[1] = 0
═══════════════════════════════════════════════════════════════════
sum = 0
remainder = 0 % 1 = 0

Check map for remainder 0: FOUND at index -1!

Distance check:
  i - map.get(0) = 1 - (-1) = 2
  Is 2 >= 2? YES ✓

Found valid subarray!

Subarray: indices 0 to 1 → [0, 0]
Sum: 0
0 % 1 = 0 ✓

Return true


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: true
═══════════════════════════════════════════════════════════════════

---

🔍 Edge Cases

Case 1: Two zeros
Input: nums = [0, 0], k = 1
Output: true
Explanation: [0, 0] has sum 0, which is 0 % 1 = 0

Case 2: Single element (too short)
Input: nums = [5], k = 5
Output: false
Explanation: Need at least 2 elements

Case 3: Entire array is valid
Input: nums = [1, 2, 3], k = 6
Output: true
Explanation: 1+2+3 = 6, which is 6 % 6 = 0

Case 4: No valid subarray
Input: nums = [23, 2, 6, 4, 7], k = 13
Output: false

Case 5: k = 1 (any sum >= 2 elements is valid)
Input: nums = [1, 2, 3], k = 1
Output: true
Explanation: Any number % 1 = 0

Case 6: Zeros in array
Input: nums = [5, 0, 0], k = 3
Output: true
Explanation: [0, 0] has sum 0, 0 % 3 = 0

Case 7: Large sum but valid
Input: nums = [23, 2, 4, 6, 6], k = 7
Output: true
Explanation: [2, 4, 6, 6] has sum 18, 18 % 7 = 4, but [23, 2, 4, 6] = 35, 35 % 7 = 0

Case 8: Negative remainders (not in this problem but good to know)
Note: In Java, -5 % 3 = -2 (not 1)
We don't have this issue here since nums[i] >= 0

---

Common Mistakes

Mistake 1: Not initializing map with {0: -1}
❌ Wrong: 
    Map<Integer, Integer> map = new HashMap<>();
    // Missing initialization
✓ Right: 
    map.put(0, -1);
Reason: Handles case where entire prefix is divisible by k

Mistake 2: Not checking distance >= 2
❌ Wrong: 
    if (map.containsKey(remainder)) {
        return true;  // Missing distance check
    }
✓ Right: 
    if (map.containsKey(remainder)) {
        if (i - map.get(remainder) >= 2) {
            return true;
        }
    }
Reason: Need at least 2 elements in subarray

Mistake 3: Updating existing remainder in map
❌ Wrong: 
    map.put(remainder, i);  // Always update
✓ Right: 
    if (!map.containsKey(remainder)) {
        map.put(remainder, i);  // Only add if new
    }
Reason: Want earliest occurrence to maximize distance

Mistake 4: Using division instead of modulo
❌ Wrong: 
    if (sum / k == 0) {  // Wrong operation
    }
✓ Right: 
    if (sum % k == 0) {  // Modulo
    }
Reason: We need remainder, not quotient

Mistake 5: Checking length == 2 instead of >= 2
❌ Wrong: 
    if (i - map.get(remainder) == 2) {
        // Only accepts exactly 2 elements
    }
✓ Right: 
    if (i - map.get(remainder) >= 2) {
        // Accepts 2 or more elements
    }
Reason: Subarray can be any length >= 2

Mistake 6: Not handling k = 0 (though problem says k >= 1)
❌ Wrong: 
    int remainder = sum % k;  // Division by zero if k = 0
✓ Right: 
    // Problem guarantees k >= 1, but good to validate
    if (k == 0) return false;
Reason: Good defensive programming

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(1)
  Use: Only for understanding

  Recalculates sum for each subarray from scratch

Approach 2: Prefix Sum Array
  Time: O(n²)
  Space: O(n)
  Use: Better than brute force, easier to understand

  Precomputes prefix sums, then checks all pairs
  Each subarray sum calculated in O(1)
  Good stepping stone to understand Approach 3

Approach 3: Prefix Sum Modulo + HashMap (RECOMMENDED)
  Time: O(n)
  Space: O(min(n, k))
  Use: Optimal solution

  Uses mathematical insight about remainders
  Single pass with hashmap for duplicate detection

🔑 The Core Insight

Mathematical Property:
═══════════════════════════════════════════════════════════════

(a - b) % k = 0  ⟺  a % k = b % k

Applied to prefix sums:
  If prefixSum[j] % k == prefixSum[i] % k
  Then (prefixSum[j] - prefixSum[i]) % k == 0
  Which means sum[i+1:j] is divisible by k!

Algorithm Pattern:
═══════════════════════════════════════════════════════════════

Track running sum modulo k:
1. Initialize map with {0: -1}
2. For each element:
   a. Add to running sum
   b. Calculate remainder = sum % k
   c. If remainder seen before:
      - Check if distance >= 2
      - If yes: found valid subarray!
   d. If remainder not seen: store it

Why Map Remainders?
═══════════════════════════════════════════════════════════════

Instead of storing all prefix sums (could be large),
store remainders (only k possible values: 0 to k-1).

Space: O(k) instead of O(n)

Why Index -1 for Remainder 0?
═══════════════════════════════════════════════════════════════

Handles case where prefix itself is divisible by k:

nums = [6, 0], k = 6

At index 0: sum = 6, remainder = 0
  Remainder 0 already in map at index -1
  Distance = 0 - (-1) = 1 < 2 ✗

At index 1: sum = 6, remainder = 0
  Remainder 0 in map at index -1
  Distance = 1 - (-1) = 2 >= 2 ✓

Works perfectly!

The Distance Check:
═══════════════════════════════════════════════════════════════

i - map.get(remainder) >= 2

Why >= 2, not >= 1?

Because we want SUBARRAY of length >= 2:
- If distance is 1: only 1 element
- If distance is 2: 2 elements ✓
- If distance is 3: 3 elements ✓

Example:
  Remainder seen at index 0
  Same remainder at index 2
  Distance = 2 - 0 = 2
  Subarray: indices 1 to 2 (length 2) ✓

Time Complexity:
═══════════════════════════════════════════════════════════════

Single pass: O(n)
HashMap operations: O(1) average

Total: O(n)

Space Complexity:
═══════════════════════════════════════════════════════════════

HashMap stores remainders: O(min(n, k))
- At most n different positions
- At most k different remainders (0 to k-1)

Whichever is smaller!

🎯 Pattern Recognition

Problem Type: Subarray Sum with Divisibility Constraint
Core Pattern: Prefix Sum + Modulo + HashMap

When to Apply:
✓ Subarray sum divisible by k
✓ Need continuous/contiguous elements
✓ Find if exists (not count)
✓ Length constraint (>= 2)

Recognition Keywords:
- "Continuous subarray"
- "Multiple of k"
- "Divisible by"
- "At least length"

Similar Problems:
- Subarray Sum Equals K (LC 560) - Without modulo
- Subarray Sums Divisible by K (LC 974) - Count instead of boolean
- Make Sum Divisible by P (LC 1590)

Key Difference from Other Prefix Sum Problems:
┌────────────────────────────────────────────┐
│ #46: Range query → Store prefix sums      │
│ #47: Balance point → Running sum          │
│ #48: Product → Prefix products            │
│ #49: 2D range → 2D prefix sums            │
│ #50: Divisibility → Prefix sum MODULO     │
└────────────────────────────────────────────┘

The modulo operation is the key difference!

🧠 Interview Strategy

Step 1: "Find continuous subarray sum divisible by k"
Step 2: "Use prefix sum concept"
Step 3: "Key insight: (a-b) % k = 0 means a%k = b%k"
Step 4: "Track remainders instead of full sums"
Step 5: "Use hashmap to find matching remainders"
Step 6: "Check distance >= 2 for valid subarray"
Step 7: "Initialize with {0: -1} for edge cases"

Key Points to Mention:
- Recognize modulo property
- Prefix sum with remainder tracking
- HashMap stores remainder -> index
- Distance check for length >= 2
- Initialize {0: -1} for edge cases
- Only store first occurrence (maximize distance)
- Time: O(n), Space: O(min(n, k))
- Single pass solution

Why Modulo?
"Instead of checking if (prefixSum[j] - prefixSum[i]) % k == 0
for all pairs, I use the property that if two prefix sums
have the same remainder when divided by k, their difference
is divisible by k. This reduces the problem to finding
duplicate remainders in a single pass."

Why HashMap?
"The hashmap lets me check in O(1) if I've seen this
remainder before, storing the earliest index to maximize
the chance of meeting the length >= 2 constraint."

This is a clever prefix sum variant! 🏆

---

📝 Quick Revision Notes

🎯 Core Concept:

Same remainder = valid subarray! If prefixSum[j] % k == prefixSum[i] % k, then sum(i+1 to j) % k == 0. Three approaches: Brute Force O(n²), Prefix Array O(n²) with O(n) space, HashMap O(n) with O(min(n,k)) space (optimal).

⚡ Quick Implementation (Approach 2 - Prefix Sum Array):

public boolean checkSubarraySum(int[] nums, int k) {
    int n = nums.length;
    int[] prefixSum = new int[n + 1];

    // Build prefix sum
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    // Check all pairs with distance >= 2
    for (int i = 0; i < n; i++) {
        for (int j = i + 2; j <= n; j++) {
            if ((prefixSum[j] - prefixSum[i]) % k == 0) {
                return true;
            }
        }
    }

    return false;
}

⚡ Quick Implementation (Approach 3 - Optimal HashMap):

import java.util.HashMap;

class Test {
  public boolean checkSubarraySum(int[] a, int k) {
    int len = a.length;
    // // Approach 1 - little optimized brute force - O(N2)
    // for (int i = 0; i < len; i++) {
    // int sum = a[i];
    // for (int j = i + 1; j < len; j++) {
    // sum = sum + a[j];

    // if (sum % k == 0) {
    // return true;
    // }
    // }
    // }

    // Approach 2 - using prefixsum concept
    // calculate prefix sum array for O(1) way of getting sum at any
    // desired range. But, overall still O(N2). Actually, no diff.
    // For example, sum (i, j) = prefix(j+1) - prefix(i)
    // int[] prefixsum = new int[len + 1];
    // for (int i = 1; i <= len; i++) {
    // prefixsum[i] = prefixsum[i - 1] + a[i - 1];
    // }
    // for (int i = 0; i < len; i++) {
    // for (int j = i + 1; j < len; j++) {
    // if ((prefixsum[j + 1] - prefixsum[i]) % k == 0) {
    // return true;
    // }
    // }
    // }

    // Approach 3 - prefixsum + hashmap
    // Need to find (prefixsum[j + 1] - prefixsum[i]) % k == 0?
    // prefixsum[j + 1] % k - prefixsum[i] % k = 0
    // prefixsum[j + 1] % k = prefixsum[i] % k
    // Foget j+1 and i, just see that for any prefixsum % k, if same value exists
    // before (but with a size of 2), we are good.
    // We do not need prefixsum overhead also. runningsum is enough because we just
    // need to track the reminders if they came before for any sum (which is
    // prefixsum also)
    // To find, if they are of size 2, we need HashMap. Else, HashSet is enough.
    HashMap<Integer, Integer> map = new HashMap<>();
    // Initialize: remainder 0 at index -1
    // This handles case where entire prefix is divisible by k
    map.put(0, -1);

    int sum = 0;
    for (int i = 0; i < len; i++) {
      sum = sum + a[i];
      int remainder = sum % k;

      if (!map.containsKey(remainder)) {
        map.put(remainder, i); // track the reminders with indices
      } else {
        // check the gap of indices which is asked in question to be >= 2
        if (i - map.get(remainder) >= 2) {
          return true;
        }
      }
    }

    return false;
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.checkSubarraySum(new int[] { 23, 2, 4, 6, 7 }, 6));
    System.out.println(t.checkSubarraySum(new int[] { 23, 2, 6, 4, 7 }, 6));
    System.out.println(t.checkSubarraySum(new int[] { 23, 2, 6, 4, 7 }, 13));
    System.out.println(t.checkSubarraySum(new int[] { 23, 2, 4, 6, 6 }, 7));
    System.out.println(t.checkSubarraySum(new int[] { 0 }, 1));
  }
}

🔑 Key Insights:

• Pattern: Prefix sum with modulo arithmetic
• Key formula: (a - b) % k = 0 ⟺ a % k = b % k
• Three approaches:
• Approach 1: Brute force - recalculate each sum O(n²)
• Approach 2: Prefix array - precompute, check pairs O(n²) with O(n) space
• Approach 3: HashMap - track remainders O(n) with O(min(n,k)) space
• Approach 2 insight: Build prefix sum once, query any range in O(1)
• Approach 3 insight: Same remainder = divisible difference
• HashMap: Maps remainder → first index seen
• Initialize: {0: -1} handles prefix divisible by k
• Distance check: i - map.get(remainder) >= 2 (Approach 3 only)
• Store once: Only first occurrence maximizes distance
• Why modulo: Only k possible remainders (0 to k-1)
• Time comparison: O(n²) vs O(n²) vs O(n)
• Space comparison: O(1) vs O(n) vs O(min(n, k))

🎪 Memory Aid:

Approach 2: "Build prefix array, check ALL pairs with modulo!"
Approach 3: "Same REMAINDER = divisible! HashMap finds DUPLICATES!"
Think: "Prefix % k, map remainder, check distance!"

💡 The Mathematical Insight:

prefixSum[j] = a × k + r
prefixSum[i] = b × k + r  (same remainder r)

Difference:
  prefixSum[j] - prefixSum[i]
  = (a × k + r) - (b × k + r)
  = (a - b) × k
  = multiple of k! ✓

🔥 Why Initialize {0: -1}:

nums = [6], k = 6

Index 0: sum = 6, remainder = 0
  Found at index -1!
  Distance = 0 - (-1) = 1 < 2 ✗

nums = [6, 0], k = 6

Index 1: sum = 6, remainder = 0
  Found at index -1!
  Distance = 1 - (-1) = 2 >= 2 ✓

Handles entire prefix divisible by k!

⚠️ Critical Details:

1. Initialize: map.put(0, -1)
2. Check distance: i - map.get(remainder) >= 2
3. Store only first: if (!map.containsKey(remainder))
4. Modulo operation: sum % k
5. Edge case: k = 1 (any sum is valid)

🎯 The Pattern:

Prefix Sum Problems Evolution:

#46: Store sums → Range queries
#47: Running sum → Balance point
#48: Products → Left × Right
#49: 2D sums → Matrix ranges
#50: Sum % k → Divisibility check

All use cumulative concept, different applications!

---

Related Patterns

• Subarray Sum Equals K (LC 560) - Without modulo
• Subarray Sums Divisible by K (LC 974) - Count subarrays
• Make Sum Divisible by P (LC 1590)
• Two Sum (LC 1) - Similar hashmap pattern

---

Happy practicing! 🎯