Leetcode 523. Continuous Subarray Sum

Let's understand what we're being asked to do. We have an array like [23, 2, 4, 6, 7] and a value k = 6, and need to check if any contiguous subarray (length ≥ 2) has a sum divisible by k.

Tracing through: subarray [23, 2] has sum 25 (not divisible by 6), subarray [2, 4] has sum 6 (divisible by 6! return true).

Important constraint: The subarray must have at least 2 elements. A single element doesn't count, even if it's divisible by k.

Key insight: We're looking for any qualifying subarray, not all of them. As soon as we find one, we can return true.

Edge cases to consider: What if the array has only one element? (return false since we need length ≥ 2). What if k = 0? What if all elements are negative? What if the entire array sum is divisible by k?

The brute force approach checks every possible contiguous subarray of length ≥ 2. Use nested loops: the outer loop picks the starting index, the inner loop extends to each possible ending index, computing the sum along the way. For each subarray, check if the sum is divisible by k (i.e., sum % k == 0). If any subarray satisfies this condition, return true; otherwise, return false after checking all possibilities.

def check_subarray_sum(nums, k):
    """
    Brute force: Check every contiguous subarray of length >= 2
    to see if its sum is divisible by k.
    """
    n = len(nums)
    
    # Outer loop: starting index of subarray
    for i in range(n):
        current_sum = 0
        
        # Inner loop: ending index of subarray
        for j in range(i, n):
            # Add current element to running sum
            current_sum += nums[j]
            
            # Check if subarray length >= 2 and sum divisible by k
            if j - i >= 1 and current_sum % k == 0:
                return True
    
    # No valid subarray found
    return False

Instead of checking every possible subarray sum (which would be slow), we can use prefix sums modulo k.

If two positions have the same remainder when their prefix sums are divided by k, then the subarray between them has a sum divisible by k! For example, if prefixSum[i] % k = 3 and prefixSum[j] % k = 3, then (prefixSum[j] - prefixSum[i]) % k = 0.

This transforms the problem from checking O(n²) subarrays to tracking remainders as we scan through the array once.

When we see a remainder we've seen before (with index distance ≥ 2), we've found our answer! This is the difference between checking millions of subarrays and one pass with a lookup table.

Think about a running total as you walk through the array. At each step, compute runningSum % k to get the remainder.

If you see the same remainder twice (and they're at least 2 positions apart), it means the elements between those positions sum to a multiple of k. It's like finding two checkpoints at the same 'modulo position' - the distance traveled between them is divisible by k.

The optimal approach uses prefix sums with modulo arithmetic and a hash map to track remainders. As we iterate through the array, we maintain a running sum and compute runningSum % k. If we've seen this remainder before at an earlier index (with distance ≥ 2), we've found a subarray whose sum is divisible by k. We store each remainder with its first occurrence index in a hash map. Special case: if runningSum % k == 0 at index i ≥ 1, the subarray from start to i is divisible by k.

def check_subarray_sum(nums, k):
    """
    Check if array has a contiguous subarray of size at least 2
    whose elements sum to a multiple of k.
    """
    # Hash map to store first occurrence of each remainder
    remainder_map = {0: -1}
    running_sum = 0
    
    # Iterate through array computing prefix sums
    for i in range(len(nums)):
        # Add current element to running sum
        running_sum += nums[i]
        
        # Compute remainder when divided by k
        remainder = running_sum % k
        
        # Check if we've seen this remainder before
        if remainder in remainder_map:
            # Check if subarray length is at least 2
            if i - remainder_map[remainder] >= 2:
                return True
        else:
            # Store first occurrence of this remainder
            remainder_map[remainder] = i
    
    # No valid subarray found
    return False

• hashmap mastery: Understanding when and why to use hashmap data structure for this type of problem pattern
• Algorithm optimization: Recognizing how to achieve O(n) time complexity through efficient problem decomposition
• Implementation patterns: Learning the key coding techniques that make this solution robust and maintainable
• Problem-solving approach: Developing intuition for when to apply this algorithmic pattern to similar challenges
• Performance analysis: Understanding the time and space complexity trade-offs and why they matter in practice