Subarray Sum Equals K

Medium

Amazon

2 views

Topics:

Arrays

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

For example:

nums = [1,1,1], k = 2

Output: 2 (The subarrays [1, 1] and [1, 1] sum to 2)
nums = [1,2,3], k = 3

Output: 2 (The subarrays [1, 2] and [3] sum to 3)
nums = [1, -1, 5, -2, 3], k = 3

Output: 4 (The subarrays [1, -1, 5, -2], [5, -2], [1, -1, 3] and [3] sum to 3)

Consider the constraints:

1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

How would you approach this problem efficiently, considering both time and space complexity?

Subarray Sum Equals K

Medium

Amazon

2 views

Topics:

Arrays

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

For example:

nums = [1,1,1], k = 2

Output: 2 (The subarrays [1, 1] and [1, 1] sum to 2)
nums = [1,2,3], k = 3

Output: 2 (The subarrays [1, 2] and [3] sum to 3)
nums = [1, -1, 5, -2, 3], k = 3

Output: 4 (The subarrays [1, -1, 5, -2], [5, -2], [1, -1, 3] and [3] sum to 3)

Consider the constraints:

1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

How would you approach this problem efficiently, considering both time and space complexity?

Solution

Brute Force Solution

A naive approach to solve this problem would be to consider all possible subarrays and check if their sum equals k. This involves two nested loops: the outer loop to select the starting element of the subarray, and the inner loop to iterate through the remaining elements to form the subarray and calculate its sum.

def subarray_sum_brute_force(nums, k):
    count = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            current_sum = 0
            for l in range(i, j + 1):
                current_sum += nums[l]
            if current_sum == k:
                count += 1
    return count

Time Complexity: O(n^3), due to the three nested loops.

Space Complexity: O(1), as we only use a constant amount of extra space.

Optimized Solution

An optimized solution can be achieved using a hash map to store the prefix sums and their frequencies. We iterate through the array, calculate the cumulative sum up to each element, and check if (cumulative_sum - k) exists in the hash map. If it does, it means there is a subarray ending at the current index whose sum is k. We add the frequency of (cumulative_sum - k) to our result.

def subarray_sum_optimized(nums, k):
    prefix_sums = {0: 1}
    current_sum = 0
    count = 0

    for num in nums:
        current_sum += num
        if (current_sum - k) in prefix_sums:
            count += prefix_sums[current_sum - k]
        prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1

    return count

Time Complexity: O(n), as we iterate through the array only once.

Space Complexity: O(n), as the hash map prefix_sums can store up to n distinct prefix sums in the worst case.

Edge Cases

Empty array: If the input array is empty, the function should return 0, as there are no subarrays.
Array with one element: If the array contains only one element, the function should return 1 if the element is equal to k, and 0 otherwise.
Array with all zeros: Consider an array filled with zeros and k is also zero. The number of subarrays summing to zero would be significant and needs to be correctly counted.
Negative numbers: The array can contain negative numbers, requiring the use of a hash map to handle prefix sums effectively.

Code (Optimized Solution)

def subarray_sum(nums, k):
    prefix_sums = {0: 1}
    current_sum = 0
    count = 0

    for num in nums:
        current_sum += num
        if (current_sum - k) in prefix_sums:
            count += prefix_sums[current_sum - k]
        prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1

    return count

Solution

Brute Force Solution

def subarray_sum_brute_force(nums, k):
    count = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            current_sum = 0
            for l in range(i, j + 1):
                current_sum += nums[l]
            if current_sum == k:
                count += 1
    return count

Time Complexity: O(n^3), due to the three nested loops.

Space Complexity: O(1), as we only use a constant amount of extra space.

Optimized Solution

def subarray_sum_optimized(nums, k):
    prefix_sums = {0: 1}
    current_sum = 0
    count = 0

    for num in nums:
        current_sum += num
        if (current_sum - k) in prefix_sums:
            count += prefix_sums[current_sum - k]
        prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1

    return count

Time Complexity: O(n), as we iterate through the array only once.

Space Complexity: O(n), as the hash map prefix_sums can store up to n distinct prefix sums in the worst case.

Edge Cases

Empty array: If the input array is empty, the function should return 0, as there are no subarrays.
Array with one element: If the array contains only one element, the function should return 1 if the element is equal to k, and 0 otherwise.
Array with all zeros: Consider an array filled with zeros and k is also zero. The number of subarrays summing to zero would be significant and needs to be correctly counted.
Negative numbers: The array can contain negative numbers, requiring the use of a hash map to handle prefix sums effectively.

Code (Optimized Solution)

def subarray_sum(nums, k):
    prefix_sums = {0: 1}
    current_sum = 0
    count = 0

    for num in nums:
        current_sum += num
        if (current_sum - k) in prefix_sums:
            count += prefix_sums[current_sum - k]
        prefix_sums[current_sum] = prefix_sums.get(current_sum, 0) + 1

    return count