LeetCode 523 Continuous Subarray Sum - Example and Complexity Analysis

Trace nums = [23, 2, 6, 4, 7] with k = 6.

Initialize: prefixSum = 0, seen = {0: -1}.

i = 0: prefixSum = 23. Remainder = 23 % 6 = 5. Not in map. Store {0: -1, 5: 0}.

i = 1: prefixSum = 25. Remainder = 25 % 6 = 1. Not in map. Store {..., 1: 1}.

i = 2: prefixSum = 31. Remainder = 31 % 6 = 1. Found at index 1! Gap = 2 - 1 = 1. Not enough (need $\ge 2$).

i = 3: prefixSum = 35. Remainder = 35 % 6 = 5. Found at index 0! Gap = 3 - 0 = 3 \ge 2. Return true.

The subarray from index 1 to 3 is [2, 6, 4], sum = 12, divisible by 6.

One pass through $n$ elements. $O(n)$ time. Map stores at most $k$ remainders. $O(\min(n, k))$ space.