Mastering Subarray Sum: Finding All Subarrays with a Given Sum in Python • Llego.dev

Given an array of integers and a target sum k, the subarray sum problem involves finding the total count of contiguous subarrays having a sum equal to the given target sum. This is a common interview question asked during technical interviews for software engineering or data science roles.

Whether you are preparing for an interview, enhancing your knowledge of array manipulation in Python, or just interested in learning a new algorithm, this article will give you an in-depth look at all aspects of solving the subarray sum problem.

Formal Problem Statement

Given an unsorted array nums of n integers and a target sum k, return the total count of continuous subarrays that have a sum equal to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2
Explanation: The subarrays [1,1] and [1,1] have a sum of 2.

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2
Explanation: The subarrays [1,2] and [3] have a sum of 3.

Brute Force Approach

The most straightforward technique is using a brute force approach - check the sum of all possible subarrays to see if any of them equal k.

Here are the steps:

Use two for loops to generate all subarrays:
- Outer loop picks the starting index i, from 0 to n-1
- Inner loop picks ending index j, from i to n-1 (inclusive, to consider single element subarrays)
For each subarray [i...j], calculate the sum and compare it with target k
If the sum equals k, increment the count
Return the final count

Python Implementation:

def subarray_sum_bruteforce(nums, k):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i, n):
            # Generate subarray
            subarray = nums[i:j+1]

            # Calculate sum of subarray
            sub_sum = sum(subarray)

            # Compare sum with target
            if sub_sum == k:
                count += 1
    return count

This brute force technique works by generating all subarrays one by one and checking if any of them have the desired sum k.

Time Complexity - O(N^2) since we have nested loops iterating through potential subarrays.

Space Complexity - O(1) since only constant extra space is used. Note that the slicing operation nums[i:j+1] might create a copy, but in terms of auxiliary space used by the algorithm itself, it’s considered O(1).

The brute force method is simple to implement but inefficient for large inputs. We need a more optimal approach.

Optimized Solution - Sliding Window (Applicable for Positive Integers)

We can sometimes optimize this using the sliding window technique. However, it’s important to note that the standard sliding window approach is best suited for arrays with non-negative numbers. If the array contains negative numbers, shrinking the window might skip valid subarrays.

For arrays with positive integers, the steps are:

Initialize a variable window_sum to keep track of the current window’s sum.
Initialize left and right pointers l and r at index 0.
Initialize a count variable to 0.
Loop through the array with the right pointer r:
- Add the current element nums[r] to window_sum.
- While window_sum is greater than k and l <= r:
  - Subtract the leftmost element nums[l] from window_sum.
  - Increment the left pointer l.
- If window_sum equals k:
  - Increment count.
Return the final count.

This ensures that the window size is adjusted efficiently, reducing redundant calculations.

Python Implementation (Suitable for Positive Integers):

def subarray_sum_slidingwindow(nums, k):
    count = 0
    window_sum = 0
    l = 0
    for r in range(len(nums)):
        window_sum += nums[r]
        while window_sum > k and l <= r:
            window_sum -= nums[l]
            l += 1
        if window_sum == k:
            count += 1
    return count

The sliding window approach, when applicable, optimizes this to O(N) time complexity since we iterate through the array with the left and right pointers at most once.

Space complexity is O(1) as well. However, remember this implementation has limitations with negative numbers.

Prefix Sum Approach (Handles Negative Integers)

The prefix sum technique is a more robust method that works correctly even with negative numbers. The steps are:

Initialize a count variable to 0.
Initialize a variable current_sum to 0.
Use a hash map (dictionary in Python) prefix_sums to store the frequency of each prefix sum encountered so far. Initialize it with {0: 1} because a prefix sum of 0 occurs before iterating through the array.
Iterate through the nums array:
- Add the current element to current_sum.
- Calculate the required_sum needed to reach k: required_sum = current_sum - k.
- If required_sum exists as a key in prefix_sums, it means there was a previous prefix sum such that the subarray between that point and the current point sums to k. Add the frequency of required_sum from prefix_sums to count.
- Update the frequency of the current_sum in the prefix_sums map.
Return the final count.

This works because if a subarray [i...j] has sum k, then prefix_sum[j] - prefix_sum[i-1] = k. Therefore, prefix_sum[i-1] = prefix_sum[j] - k. We are essentially checking if we’ve seen a prefix sum that, when subtracted from the current prefix sum, equals k.

Python Implementation:

def subarray_sum_prefixsum(nums, k):
    count = 0
    current_sum = 0
    prefix_sums = {0: 1}  # Initialize with 0:1

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

This prefix sum method has O(N) time complexity since we traverse the nums array only once.

Space complexity is O(N) in the worst case, where all prefix sums are unique and need to be stored in the prefix_sums hash map.

Analysis

Let’s summarize the time and space complexities of the approaches discussed:

Algorithm	Time Complexity	Space Complexity	Handles Negative Numbers
Brute Force	O(N^2)	O(1)	Yes
Sliding Window	O(N)	O(1)	No (Standard Form)
Prefix Sum	O(N)	O(N)	Yes

The prefix sum technique provides the most generally applicable and efficient solution for this problem, especially when dealing with arrays that might contain negative numbers. While the sliding window is efficient for arrays with positive numbers, the prefix sum approach offers broader utility.

Practical Examples

Here are some examples of how this subarray sum algorithm can be useful:

Expense Tracking: Find periods where total expenses equaled a certain budget.
Sales Analysis: Identify periods with specific revenue targets based on subarray sums.
Signal Processing: Detect patterns or segments in a signal that match a particular sum.
Bioinformatics: Find subsequences in a genetic sequence with a specific property represented by a sum.

Developers can adapt this algorithm to various applications involving array or sequence analysis.

Summary

In this comprehensive guide, we looked at different techniques to find the count of subarrays with a given sum k in Python:

Brute force is simple but inefficient with O(N^2) time complexity.
The standard sliding window algorithm provides an optimal O(N) time and O(1) space solution but is primarily suitable for arrays with non-negative numbers.
The prefix sum algorithm is a robust and efficient O(N) time and O(N) space approach that correctly handles arrays with both positive and negative numbers.
The prefix sum approach is generally preferred due to its ability to handle negative numbers.

By mastering these algorithms, you can confidently tackle subarray problems in interviews and programming projects. The concepts of sliding windows and prefix sums are also broadly applicable in various problem-solving scenarios.

Hopefully, this step-by-step article provided clear explanations of the logic and Python code needed to find subarrays with a given sum. Let us know if you have any other questions!