Continuous Subarray Sum - Video Solutions

Problem Overview: Given an integer array nums and an integer k, determine whether the array contains a continuous subarray of at least length 2 whose total sum is a multiple of k. In other words, check if there exist indices i < j such that the sum of elements from i to j is divisible by k.

Approach 1: Iterative Brute Force (Naive Approach) (Time: O(n²), Space: O(1))

Start from each index i and iteratively expand the subarray by adding elements nums[j]. Maintain a running sum while extending the window. After every extension where the subarray length is at least 2, check if sum % k == 0. This approach directly tests all possible subarrays of length ≥2. It works but quickly becomes slow for large arrays because the number of subarrays grows quadratically. It’s mainly useful for understanding the problem or validating small inputs.

Approach 2: Prefix Sum with Modulo and HashMap (Time: O(n), Space: O(n))

The key observation comes from modular arithmetic. If two prefix sums have the same remainder when divided by k, the subarray between them must sum to a multiple of k. While iterating through the array, compute a running prefix sum and store prefixSum % k in a hash map along with the earliest index where that remainder appeared. When the same remainder appears again, check if the distance between indices is at least 2. If it is, a valid subarray exists.

The hash map stores remainder → first index. Initialize it with 0 → -1 so that a valid subarray starting from index 0 can be detected. For each element, update the running sum, compute the remainder, and check if that remainder already exists in the map. If it does and the index difference is greater than 1, return true. Otherwise store the remainder if it hasn't appeared before. This method reduces the search from checking all subarrays to a single pass using a hash table.

This technique relies on prefix sums and modular arithmetic, both common patterns when working with cumulative ranges in an array. Handling k = 0 requires checking for consecutive zeros because modulo with zero is undefined.

Recommended for interviews: Interviewers expect the prefix sum + modulo hash map solution. The brute force approach demonstrates understanding of the problem but does not scale. Recognizing the repeated remainder pattern and converting the problem into a prefix remainder lookup shows strong problem‑solving and familiarity with common interview patterns.