We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Continuous Subarray Sum

Number: 523

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, Yandex, Apple, TikTok

Problem Description

Given an integer array nums and an integer k, determine if there exists a continuous subarray of at least size 2 such that the subarray's sum is a multiple of k.

Key Insights

  • Use the prefix sum technique to accumulate sums.
  • Instead of storing full sums, store the remainder (mod k) when divided by k.
  • If two prefix sums have the same remainder, the subarray between these indices sums to a multiple of k.
  • Ensure that the subarray has at least two elements; thus, check that the distance between the indices is at least 2.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(min(n, k))

Solution

The approach involves using prefix sums and taking advantage of the modulo property. As you compute the cumulative sum for each element, calculate the remainder of the sum modulo k. If the same remainder has been seen before and the subarray between the two indices is of length at least 2, then the subarray's sum is a multiple of k.

We store these remainders in a hash table (dictionary/map) mapping the remainder to the earliest index where this remainder was encountered. Special care is taken to initialize the hash table with the remainder 0 mapped to index -1 to handle cases where the subarray starting at index 0 has a valid sum.

Code Solutions

# Python solution using prefix sum with modulo and a dictionary to store remainders.

def checkSubarraySum(nums, k):
    # Dictionary to store remainder and its earliest index.
    remainder_index = {0: -1}  
    cumulative_sum = 0

    # Iterate over the array elements.
    for index, num in enumerate(nums):
        cumulative_sum += num
        remainder = cumulative_sum % k
        
        # If the remainder is seen before, check the subarray length.
        if remainder in remainder_index:
            # If subarray length is at least 2 (current index - previous index)
            if index - remainder_index[remainder] > 1:
                return True
        else:
            # Store the index for this remainder the first time it is seen.
            remainder_index[remainder] = index

    return False

# Example usage:
# print(checkSubarraySum([23,2,4,6,7], 6))  # Expected output: True
← Back to All Questions