Determine if a multiple-sum subarray exists

Given an integer array nums and an integer k, determine whether there exists a contiguous subarray of length at least 2 whose sum is divisible by k; return true if such a subarray exists, otherwise false. If k = 0, interpret the requirement as finding a length ≥2 subarray with sum exactly 0. Explain your approach and analyze time and space complexity. Follow-up: how would you adapt your solution to a streaming setting where nums arrives incrementally?

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Determine if a Multiple-Sum Subarray Exists

Given an integer array nums and an integer k, determine whether there exists a contiguous subarray of length at least 2 whose sum is divisible by k. Return true if such a subarray exists, otherwise false.

Special case: if k = 0, interpret the requirement as finding a contiguous subarray of length at least 2 whose sum is exactly 0.

For the general (k != 0) case, treat k by its absolute value: a sum is "divisible by k" if sum % |k| == 0.

Examples

• nums = [23, 2, 4, 6, 7], k = 6 -> true (the subarray [2, 4] sums to 6, a multiple of 6).
• nums = [23, 2, 6, 4, 7], k = 13 -> false (no length-≥2 contiguous subarray has a sum that is a multiple of 13).
• nums = [1, -1, 3], k = 0 -> true (the subarray [1, -1] sums to exactly 0).
• nums = [0, 1, 0], k = 0 -> false (no contiguous subarray of length ≥2 sums to exactly 0).

Approach (prefix sums + hashing). Two prefix sums with the same value (k = 0 case) or the same remainder mod |k| mark a subarray whose sum is 0 / divisible by k. Store the earliest index at which each remainder (or prefix value) first appears; when the same key is seen again at an index that is at least 2 positions later, a valid subarray exists. Seed the map with {0: -1} so that a prefix itself being 0 / divisible counts. This runs in O(n) time and O(min(n, |k|)) space.

Follow-up (streaming). The same prefix-sum-mod-k hashing works incrementally: maintain the running remainder and the map of first-seen indices as each element arrives, emitting true the moment a repeated remainder is found at index distance ≥ 2. Space stays bounded by O(min(n, |k|)) remainders (or O(n) distinct prefix values when k = 0).

Constraints

• 1 <= nums.length is typical, but the function must also handle an empty array (returns false).
• Elements of nums may be negative, zero, or positive.
• k may be negative, zero, or positive; for k != 0 use |k| when testing divisibility.
• When k = 0, a single element equal to 0 does NOT qualify — the subarray must have length >= 2.

Hints

1. A subarray sum equals prefixSum[j] - prefixSum[i]. It is divisible by k exactly when prefixSum[j] and prefixSum[i] leave the same remainder mod |k| (or are equal, when k = 0).
2. Store the FIRST index at which each remainder (or prefix value) is seen, and require the gap between matching indices to be at least 2 to enforce the length-≥2 rule.
3. Seed the map with remainder 0 at index -1 so a prefix that is itself divisible by k (a subarray starting at index 0) is detected.
4. Handle k = 0 separately: track raw prefix sums instead of remainders and look for two equal prefix sums at least 2 indices apart.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Given an integer array nums and an integer k, determine whether there exists a contiguous subarray of length at least 2 whose sum is divisible by k; return true if such a subarray exists, otherwise false. If k = 0, interpret the requirement as finding a length ≥2 subarray with sum exactly 0. Explain your approach and analyze time and space complexity. Follow-up: how would you adapt your solution to a streaming setting where nums arrives incrementally?

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.