Problem Statement

Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.

A good subarray is a subarray where:

• its length is at least two, and
• the sum of the elements of the subarray is a multiple of k.

Note: An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Additional information

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 0 <= sum(nums[i]) <= 2^31 - 1
• 1 <= k <= 2^31 - 1

Example 1:

Input: nums = [23,2,4,6,7], k = 6

Output: true

Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

Input: nums = [23,2,6,4,7], k = 6

Output: true

Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42. 42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

Input: nums = [23,2,6,4,7], k = 13

Output: false

Brute Force (Nested Loops)

Intuition

The most direct way to solve this is to simply check the sum of every single possible subarray that has a length of at least 2.

We can use a nested loop where the outer loop sets the starting index i of the subarray, and the inner loop sets the ending index j. As we expand j, we keep a running total of the subarray's sum. If that running total modulo k equals 0, we have found a valid subarray and can immediately return True.

Algorithm

1. Iterate i from 0 to the length of nums.
2. Initialize a current_sum variable to nums[i].
3. Iterate j from i + 1 to the length of nums. This guarantees our subarray will always have a length of at least 2.
4. Add nums[j] to current_sum.
5. Check if current_sum % k == 0. If it is, return True.
6. If both loops finish without finding a valid subarray, return False.

def check_subarray_sum(nums: list[int], k: int) -> bool:
    n = len(nums)
    
    # Check all subarrays of length >= 2
    for i in range(n):
        current_sum = nums[i]
        for j in range(i + 1, n):
            current_sum += nums[j]
            
            # If the sum is a multiple of k, we found a match
            if current_sum % k == 0:
                return True
                
    return False

Time & Space Complexity

• Time complexity: O(N^2)
  • Reason: We are evaluating the sum of every possible contiguous subarray. With an array length of up to 10^5, this quadratic time complexity will cause a Time Limit Exceeded (TLE) error.
• Space complexity: O(1)
  • Reason: We only use a single integer variable to track the sum, taking constant auxiliary space.

Prefix Sum Modulo with Hash Map - Optimal

Intuition

We can solve this in a single pass using the mathematical properties of remainder arithmetic.

If we keep a running "prefix sum" of the array, we can take the modulo k of that sum at every step. Here is the trick: if we encounter the exact same remainder at two different indices, it means the elements between those two indices must add up to a multiple of k!

For example, if the remainder at index 1 is 4, and the remainder later at index 5 is also 4, the sum of the elements from index 2 to 5 didn't add any extra remainder. Therefore, their sum is perfectly divisible by k. We can use a Hash Map to store the first time we see a specific remainder and its index. If we see it again, we just check if the distance between the indices is at least 2.

Algorithm

1. Initialize a dictionary remainder_map with {0: -1}. This is a crucial base case! It handles the scenario where the prefix sum itself perfectly divides by k right from the beginning of the array.
2. Initialize prefix_sum = 0.
3. Iterate i from 0 to the length of nums.
4. Add nums[i] to prefix_sum.
5. Calculate the remainder = prefix_sum % k.
6. If remainder is already a key in remainder_map:
   • Check if the subarray length is at least 2 (i - remainder_map[remainder] >= 2).
   • If it is, return True.
   • (Note: We deliberately do NOT update the index in the map if the remainder exists, because keeping the oldest index gives us the best chance of finding a length >= 2 later).
7. If remainder is NOT in the map, add it with the current index: remainder_map[remainder] = i.
8. Return False if the loop finishes.

def check_subarray_sum(nums: list[int], k: int) -> bool:
    # Initialize with 0: -1 to catch subarrays starting from index 0
    remainder_map = {0: -1}
    prefix_sum = 0
    
    for i in range(len(nums)):
        prefix_sum += nums[i]
        remainder = prefix_sum % k
        
        # If we have seen this remainder before, the subarray between them is a multiple of k
        if remainder in remainder_map:
            # Ensure the subarray length is at least 2
            if i - remainder_map[remainder] >= 2:
                return True
        else:
            # Only store the FIRST time we see a remainder to maximize length
            remainder_map[remainder] = i
            
    return False

Time & Space Complexity

• Time complexity: O(N)
  • Reason: We iterate through the array exactly one time. Hash Map lookups and insertions take O(1) time.
• Space complexity: O(K)
  • Reason: The Hash Map will store at most K distinct remainders (from 0 to K-1). If K is massive, it bounds to O(N) as we can only store up to N distinct remainders.