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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Continuous Subarray Sum

Difficulty: Medium

Problem Description

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.

Key Insights

  • A subarray is a contiguous part of the array and must have at least two elements.
  • The sum of the subarray must be divisible by k.
  • We can use prefix sums and a hash map to track remainders when the prefix sums are divided by k.
  • If the same remainder occurs at two different indices with a distance of at least 2 between them, then the elements between those indices form a good subarray.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution involves using a prefix sum approach combined with a hash map to track the remainders. As we iterate through the array, we maintain a running sum and calculate the current remainder when divided by k. If the current remainder has been seen before and the distance between the two occurrences is at least two, we have found a good subarray. Additionally, we handle the case where k is zero separately.

Code Solutions

def checkSubarraySum(nums, k):
    if len(nums) < 2:
        return False

    # Dictionary to store the remainder and its index
    remainder_map = {0: -1}  # Handle case where the sum itself is a multiple of k
    current_sum = 0

    for i in range(len(nums)):
        current_sum += nums[i]
        if k != 0:
            current_sum %= k

        if current_sum in remainder_map:
            # Check the distance between indices
            if i - remainder_map[current_sum] > 1:
                return True
        else:
            remainder_map[current_sum] = i

    return False
← Back to All Questions