Problem Description

You are given an integer array nums and an integer k. Your task is to determine whether the array contains a "good subarray."

A subarray is considered "good" if it meets both of these conditions:

• It has a length of at least 2 elements
• The sum of its elements is a multiple of k

Important points to remember:

• A subarray must be contiguous (elements must be consecutive in the original array)
• Any integer x is a multiple of k if there exists some integer n where x = n * k
• The value 0 is always considered a multiple of k

The function should return true if at least one good subarray exists in nums, and false otherwise.

For example, if nums = [23, 2, 4, 6, 7] and k = 6, the subarray [2, 4] would be a good subarray because its length is 2 and its sum (6) is a multiple of 6.

Intuition

The key insight comes from understanding how modular arithmetic works with prefix sums. When we want to find if a subarray has a sum that's a multiple of k, we can leverage the fact that if two prefix sums have the same remainder when divided by k, then the subarray between them must have a sum divisible by k.

Let's think about it step by step:

1. If we have a prefix sum up to index i as sum_i and a prefix sum up to index j as sum_j (where j < i), then the sum of the subarray from j+1 to i equals sum_i - sum_j.

2. For this subarray sum to be divisible by k, we need (sum_i - sum_j) % k = 0.

3. This happens when sum_i % k = sum_j % k. In other words, both prefix sums have the same remainder when divided by k.

So instead of checking every possible subarray (which would be inefficient), we can track the remainders of prefix sums as we go through the array. If we ever see the same remainder appearing at two different positions that are at least 2 indices apart, we know there's a good subarray between them.

Why do we need the positions to be at least 2 indices apart? Because the subarray needs to have at least 2 elements. If we find the same remainder at positions j and i where i - j > 1, then the subarray from index j+1 to i contains at least i - (j+1) + 1 = i - j elements, which is at least 2.

The hash table approach naturally falls out from this insight - we store each remainder with its first occurrence position, and when we see that remainder again, we check if enough distance has passed to form a valid subarray.

Learn more about Math and Prefix Sum patterns.

Solution Approach

We implement the solution using a prefix sum technique combined with a hash table to efficiently track remainders.

Here's how the algorithm works:

1. Initialize the hash table: We create a dictionary d with an initial entry {0: -1}. This represents that a remainder of 0 appears at position -1 (before the array starts). This handles the edge case where a valid subarray starts from index 0.

2. Track the running sum: We maintain a variable s to store the running prefix sum modulo k. We update it as s = (s + x) % k for each element x in the array.

3. Process each element: For each element at index i:

   • Calculate the new prefix sum remainder: s = (s + nums[i]) % k
   • Check if this remainder has been seen before:
     • If not seen: Store the current remainder with its position: d[s] = i
     • If seen before: Check if the distance between the current position i and the stored position d[s] is greater than 1 (meaning at least 2 elements in between). If i - d[s] > 1, we've found a valid subarray and return True.

4. Return result: If we complete the iteration without finding any valid subarray, return False.

The algorithm's efficiency comes from:

• Time Complexity: O(n) where n is the length of the array, as we traverse it only once
• Space Complexity: O(min(n, k)) for the hash table, which stores at most k different remainders

The beauty of this approach is that we don't need to explicitly calculate subarray sums. By tracking remainders and their positions, we can determine if a valid subarray exists in a single pass through the array.

Example Walkthrough

Let's walk through the algorithm with nums = [23, 2, 4, 6, 7] and k = 6.

Step-by-step execution:

Initialization:

• Hash table d = {0: -1} (remainder 0 at position -1)
• Running sum s = 0

Index 0 (value = 23):

• Calculate new sum: s = (0 + 23) % 6 = 23 % 6 = 5
• Check if remainder 5 exists in d: No
• Add to hash table: d = {0: -1, 5: 0}
• Continue

Index 1 (value = 2):

• Calculate new sum: s = (5 + 2) % 6 = 7 % 6 = 1
• Check if remainder 1 exists in d: No
• Add to hash table: d = {0: -1, 5: 0, 1: 1}
• Continue

Index 2 (value = 4):

• Calculate new sum: s = (1 + 4) % 6 = 5 % 6 = 5
• Check if remainder 5 exists in d: Yes! It was stored at index 0
• Check distance: 2 - 0 = 2 > 1 ✓
• Found a valid subarray!

The algorithm returns True because we found that the subarray from index 1 to index 2 (elements [2, 4]) has a sum of 6, which is divisible by 6.

Why this works: When we saw remainder 5 at index 0 and again at index 2, it means:

• Prefix sum up to index 0: 23 has remainder 5
• Prefix sum up to index 2: 23 + 2 + 4 = 29 has remainder 5
• Therefore, the subarray sum between them: 29 - 23 = 6 is divisible by 6 (remainder 0)

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array exactly once using a single for loop with enumerate(nums). Within each iteration, all operations performed are constant time: computing the modulo ((s + x) % k), dictionary lookup (s not in d), dictionary insertion (d[s] = i), and arithmetic comparison (i - d[s] > 1).

The space complexity is O(min(n, k)), which can be simplified to O(n) in the worst case. The dictionary d stores remainder values as keys. Since we're taking modulo k, there can be at most k distinct remainders (from 0 to k-1). However, in the worst case where all elements produce different remainders and k ≥ n, we could store up to n entries in the dictionary. Therefore, the space complexity is bounded by the minimum of n and k, but asymptotically we consider it as O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling the Minimum Length Requirement Correctly

The Pitfall: A common mistake is checking index - remainder_to_index[running_sum] >= 1 instead of > 1. This would incorrectly accept subarrays of length 1.

Why it happens: The distance calculation can be confusing. If the same remainder appears at indices i and j, the subarray between them is nums[i+1:j+1], which has length j - i.

Example:

• If nums = [5, 0, 0, 0] and k = 3
• At index 0: remainder is 2, store {2: 0}
• At index 1: remainder is still 2, distance is 1 - 0 = 1
• Using >= 1 would incorrectly return True for a single-element subarray

Solution: Always use strict inequality > 1 to ensure at least 2 elements in the subarray.

2. Updating the Hash Table Too Early

The Pitfall: Updating remainder_to_index[running_sum] = index before checking if the remainder already exists would overwrite the first occurrence, making it impossible to find the longest valid subarray starting from an earlier position.

Incorrect approach:

# WRONG: This overwrites the first occurrence
running_sum = (running_sum + num) % k
remainder_to_index[running_sum] = index  # Updates immediately
if index - remainder_to_index[running_sum] > 1:  # Always false!
    return True

Solution: Only update the hash table when the remainder hasn't been seen before:

# CORRECT: Preserve the first occurrence
if running_sum not in remainder_to_index:
    remainder_to_index[running_sum] = index
elif index - remainder_to_index[running_sum] > 1:
    return True

3. Forgetting the Initial Hash Table Entry

The Pitfall: Not initializing the hash table with {0: -1} causes the algorithm to miss valid subarrays that start from index 0.

Example:

• If nums = [6, 3, 5, 2] and k = 9
• The subarray [6, 3] has sum 9, which is divisible by 9
• Without {0: -1}, at index 1 we have remainder 0, but no previous occurrence to compare with

Solution: Always initialize with remainder_to_index = {0: -1} to handle prefix sums that are themselves multiples of k.

4. Not Handling Negative Numbers Properly

The Pitfall: In some programming languages, the modulo operation with negative numbers can produce negative remainders, which breaks the algorithm's logic.

Example in some languages:

• -5 % 3 might return -2 instead of 1

Solution: Ensure positive remainders by using:

running_sum = ((running_sum + num) % k + k) % k

Or in Python, which handles this correctly by default, the standard modulo operation works fine.