Determine if a multiple-sum subarray exists
Company: Adobe
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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?
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Determine if a multiple-sum subarray exists states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
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.
Examples
Input: ([23, 2, 4, 6, 7], 6)
Expected Output: True
Explanation: Subarray [2, 4] (indices 1..2) sums to 6, a multiple of 6.
Input: ([23, 2, 6, 4, 7], 6)
Expected Output: True
Explanation: Subarray [6, 4] sums to 10... but [2, 6, 4] sums to 12, which is a multiple of 6.
Hints
- 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).
- 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.
- 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.
- Handle k = 0 separately: track raw prefix sums instead of remainders and look for two equal prefix sums at least 2 indices apart.