Continuous Subarray Sum

Given an integer array nums and an integer k, determine whether the array contains a contiguous subarray that satisfies both conditions:

• The subarray contains at least two elements.

• The subarray sum is a multiple of k.

Return true when such a subarray exists. Otherwise, return false.

Brute Force Approach

The most direct method generates every contiguous subarray containing at least two elements.

For every selected range, the complete sum is calculated separately. The method returns true as soon as a range has a sum divisible by k.

Algorithm

• Store the array size in n. If n < 2, return false because a valid subarray must contain at least two elements.

• Treat every index start as a possible beginning and every index end from start + 1 to n - 1 as an ending position. Starting from start + 1 guarantees that the selected range contains at least two elements.

• For every range [start, end], initialize currentSum with 0 and add all elements from start through end to calculate its complete sum.

• If k != 0, check whether currentSum % k == 0, which means the selected sum is divisible by k.

• If k == 0, check whether currentSum == 0 instead, since modulo by zero cannot be performed.

• Return true immediately when a valid subarray is found. Return false after all possible ranges have been examined.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N³), where N represents the array size. Two loops select every starting and ending index, while another traversal calculates the sum of each selected range.

Space Complexity: O(1), because only loop indices and currentSum require auxiliary storage.

Better Approach

The Brute Force Approach recalculates every selected range from the beginning.

For one fixed starting index, the next subarray contains the previous range plus one additional element. Maintaining a running sum allows every new range to be checked with one addition.

Algorithm

• Store the array size in n. If fewer than two elements are available, return false.

• Treat every index start as the beginning of a new group of subarrays and initialize currentSum with 0.

• Move end from start to n - 1 and add nums[end] to currentSum. This extends the previous range by one element instead of recalculating its complete sum.

• Check the divisibility condition only when end - start + 1 >= 2, ensuring that single-element ranges are never accepted.

• If k != 0, return true when currentSum % k == 0. If k == 0, return true when currentSum == 0.

• Return false if every possible subarray has been processed without finding a valid one.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N²), where N represents the array size. Every starting position extends through all possible ending positions.

Space Complexity: O(1), because only loop indices and currentSum require auxiliary storage.

Optimal Approach

Consider two prefix sums ending at different indices.

When both prefix sums have the same remainder after division by k, subtracting the earlier prefix from the later prefix produces a value divisible by k. Therefore, the elements between those prefix positions form a subarray whose sum is a multiple of k.

Only the first index of each remainder should be stored. The earliest index creates the largest possible distance and provides the best chance of satisfying the required subarray length.

When k = 0, remainders cannot be calculated. In that case, repeated prefix sums indicate that the elements between those positions have a sum of 0.

Algorithm

• Store the array size in n. If n < 2, return false.

• Create a hash map firstIndex and initialize it with {0: -1}. The index -1 represents the empty prefix before the array, allowing subarrays beginning at index 0 to satisfy the length condition naturally.

• Initialize prefixSum with 0 and traverse the array from left to right, treating each current index as a possible ending position.

• Add nums[index] to prefixSum. If k != 0, use the normalized remainder of prefixSum by |k| as the key. If k == 0, use prefixSum itself because equal prefix sums indicate a zero-sum subarray.

• If the key has appeared before, check whether index - firstIndex[key] >= 2. A distance of at least 2 means the elements between the two prefix positions form a valid subarray.

• If the key has not appeared before, store its current index. Keeping only its earliest occurrence gives future indices the largest possible distance. Return false if the traversal ends without finding a valid range.

Dry Run

Solution

Complexity Analysis

Time Complexity: O(N) on average, where N represents the array size. Every element requires one hash-map lookup and, when necessary, one insertion.

Space Complexity: O(N), because the hash map may store up to N + 1 distinct remainder or prefix-sum values.

FAQs

Q1. Why do equal prefix remainders produce a sum divisible by k?

If two prefix sums have the same remainder, their difference has remainder 0. That difference represents the sum of the elements between the two prefix positions.

Q2. Why is remainder 0 initially stored at index -1?

Index -1 represents the empty prefix before the array starts. This allows a valid subarray beginning at index 0 to satisfy the length check naturally.

Q3. Why is only the first index of each remainder stored?

The earliest occurrence produces the greatest distance from future positions. Replacing it with a later index could hide a valid subarray of length at least 2.

Q4. Why must negative remainders be normalized?

Some programming languages produce negative modulo results for negative prefix sums. Normalization ensures that equivalent remainder classes use the same hash-map key.

Q5. How should k = 0 be handled?

Modulo cannot be performed with zero. A repeated prefix sum must be searched instead, because equal prefix sums mean the subarray between them has sum 0.

Q6. Can a sliding-window approach solve this problem?

A standard sliding window is not reliable when negative values are allowed. Adding or removing an element does not change the sum in a predictable direction.