Jobs

Interviews

Discussions

Subarray Sum Equals K

Medium

Uber

0 views

Topics:

ArraysSliding Windows

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 Explanation: There are two subarrays [1, 1] that sum to 2.
nums = [1,2,3], k = 3 Output: 2 Explanation: There are two subarrays [1, 2] and [3] that sum to 3.

Clarify the following constraints and edge cases before coding:

What is the maximum size of the array?
What is the range of values that can be found inside the array?
What is the range of values that k can be?
Should I handle an empty array?
Can the array contain only negative numbers? How should the algorithm behave in this case?

Write a function that efficiently calculates the total number of subarrays that sum to k.

Subarray Sum Equals K

Medium

Uber

0 views

Topics:

ArraysSliding Windows

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 Explanation: There are two subarrays [1, 1] that sum to 2.
nums = [1,2,3], k = 3 Output: 2 Explanation: There are two subarrays [1, 2] and [3] that sum to 3.

Clarify the following constraints and edge cases before coding:

What is the maximum size of the array?
What is the range of values that can be found inside the array?
What is the range of values that k can be?
Should I handle an empty array?
Can the array contain only negative numbers? How should the algorithm behave in this case?

Write a function that efficiently calculates the total number of subarrays that sum to k.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array `nums` contain negative numbers, zeros, or only positive numbers?
What are the constraints on the size of the input array `nums` and the value of `k`?
If no subarray sums to `k`, should I return 0?
Is the order of the subarrays in the output important, or do I just need to return the total count?
Are overlapping subarrays that sum to `k` counted multiple times?

Brute Force Solution

Approach

The brute force method for this problem is all about trying every single possible group of numbers. We'll check the sum of each group to see if it matches our target value. We keep going until we've checked every single possibility.

Here's how the algorithm would work step-by-step:

First, consider the group made up of just the first number in the list. See if that equals our target value.
Next, consider the group made up of the first two numbers. Add them together and see if that equals our target value.
Then, consider the group made up of the first three numbers, and so on. Keep going until you've checked the sum of the first 'all' numbers.
Now, shift your focus. Start with the second number in the list and consider only that number. See if that equals our target value.
Then, consider the group made up of the second and third numbers, and so on.
Keep doing this, shifting the starting point one number at a time and checking all possible groups that start from that point.
Continue until you've started at the very last number in the list, and checked the sum of just that single number.

Code Implementation

def subarray_sum_equals_k_brute_force(numbers, target):
    number_of_subarrays = 0

    # Iterate through all possible start indices
    for start_index in range(len(numbers)):

        current_sum = 0
        # Iterate through all possible end indices for the current start index
        for end_index in range(start_index, len(numbers)):
            current_sum += numbers[end_index]

            # Check if the current subarray sum equals the target
            if current_sum == target:
                number_of_subarrays += 1

    return number_of_subarrays

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through all possible subarrays. For an array of size n, the outer loop iterates n times, representing the starting index of the subarray. The inner loop, for each starting index, iterates up to n times to calculate the sum of all subarrays starting from that index. Therefore, the number of operations grows proportionally to n * n, resulting in a time complexity of O(n²).

Space Complexity

O(1) – The brute force solution, as described, iterates through subarrays using nested loops, calculating the sum of each subarray on the fly. It doesn't use any auxiliary data structures like lists, dictionaries, or sets to store intermediate results or subarray sums. Only a few variables are used to track loop indices and the current sum, and the number of these variables remains constant regardless of the input array's size, N. Therefore, the space complexity is constant.

Optimal Solution

Approach

The trick is to keep track of running totals as we go. Instead of checking every possible group of numbers, we use a shortcut to find groups that add up to our target by remembering previous sums and seeing if the difference gets us to the answer.

Here's how the algorithm would work step-by-step:

Imagine you have a way to quickly look up previously seen running totals and how many times you've seen them.
Start by calculating the running total as you move through the numbers.
For each running total, check if (running total - target) exists in your record of previously seen totals.
If it does, that means we've found a group of consecutive numbers that adds up to the target. Add the number of times (running total - target) has occurred to a running count.
Record the current running total in your record of seen totals, incrementing its count.
The final count will tell you how many groups of consecutive numbers add up to the target.

Code Implementation

def subarray_sum_equals_k(numbers, target):
    running_sum = 0
    subarray_count = 0
    previous_sums = {}

    previous_sums[0] = 1

    for number in numbers:
        running_sum += number

        # Check if (running_sum - target) exists.
        if (running_sum - target) in previous_sums:
            subarray_count += previous_sums[running_sum - target]

        # Update the count of the current running sum.
        if running_sum in previous_sums:
            previous_sums[running_sum] += 1
        else:
            previous_sums[running_sum] = 1

    return subarray_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once to calculate the running total. Inside the loop, it performs a constant time operation to check if (running total - target) exists in the hash map and update the count. Inserting and retrieving values from the hash map takes constant time on average. Therefore, the overall time complexity is dominated by the single loop, resulting in O(n).

Space Complexity

O(N) – The primary auxiliary space usage comes from the "record of previously seen running totals," which, as described in the explanation, needs to store running totals and their counts. This record can be efficiently implemented using a hash map (or dictionary) where the running totals are keys and the counts are values. In the worst-case scenario, where all running totals are distinct, the hash map can store up to N key-value pairs, where N is the number of elements in the input array. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately since no subarray can exist with a sum.
Array with a single element equals to k	Check if the single element is equal to k, and return 1 if true, 0 otherwise.
Array with all zeros and k=0	The number of subarrays will be n*(n+1)/2; handle potential integer overflow for large n.
Array with all identical numbers and k equals a multiple of that number	Account for all possible subarrays whose length will result in sum equals k.
Array with only negative numbers and k is positive	Return 0 as no subarray sum can equal a positive k with all negative numbers.
Large array sizes and extreme values in array leading to possible Integer Overflow	Use a data type with a larger range than int to avoid integer overflow when calculating prefix sums.
k=0 and the array contains both positive and negative numbers	Correctly count subarrays that sum to zero, even with mixed positive and negative values, using a hash map to track prefix sums.
k is a very large positive number	The prefix sum can become large quickly; use appropriate data types and consider early termination if the prefix sum exceeds k significantly in the negative direction.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array `nums` contain negative numbers, zeros, or only positive numbers?
What are the constraints on the size of the input array `nums` and the value of `k`?
If no subarray sums to `k`, should I return 0?
Is the order of the subarrays in the output important, or do I just need to return the total count?
Are overlapping subarrays that sum to `k` counted multiple times?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider the group made up of just the first number in the list. See if that equals our target value.
Next, consider the group made up of the first two numbers. Add them together and see if that equals our target value.
Then, consider the group made up of the first three numbers, and so on. Keep going until you've checked the sum of the first 'all' numbers.
Now, shift your focus. Start with the second number in the list and consider only that number. See if that equals our target value.
Then, consider the group made up of the second and third numbers, and so on.
Keep doing this, shifting the starting point one number at a time and checking all possible groups that start from that point.
Continue until you've started at the very last number in the list, and checked the sum of just that single number.

Code Implementation

def subarray_sum_equals_k_brute_force(numbers, target):
    number_of_subarrays = 0

    # Iterate through all possible start indices
    for start_index in range(len(numbers)):

        current_sum = 0
        # Iterate through all possible end indices for the current start index
        for end_index in range(start_index, len(numbers)):
            current_sum += numbers[end_index]

            # Check if the current subarray sum equals the target
            if current_sum == target:
                number_of_subarrays += 1

    return number_of_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a way to quickly look up previously seen running totals and how many times you've seen them.
Start by calculating the running total as you move through the numbers.
For each running total, check if (running total - target) exists in your record of previously seen totals.
If it does, that means we've found a group of consecutive numbers that adds up to the target. Add the number of times (running total - target) has occurred to a running count.
Record the current running total in your record of seen totals, incrementing its count.
The final count will tell you how many groups of consecutive numbers add up to the target.

Code Implementation

def subarray_sum_equals_k(numbers, target):
    running_sum = 0
    subarray_count = 0
    previous_sums = {}

    previous_sums[0] = 1

    for number in numbers:
        running_sum += number

        # Check if (running_sum - target) exists.
        if (running_sum - target) in previous_sums:
            subarray_count += previous_sums[running_sum - target]

        # Update the count of the current running sum.
        if running_sum in previous_sums:
            previous_sums[running_sum] += 1
        else:
            previous_sums[running_sum] = 1

    return subarray_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately since no subarray can exist with a sum.
Array with a single element equals to k	Check if the single element is equal to k, and return 1 if true, 0 otherwise.
Array with all zeros and k=0	The number of subarrays will be n*(n+1)/2; handle potential integer overflow for large n.
Array with all identical numbers and k equals a multiple of that number	Account for all possible subarrays whose length will result in sum equals k.
Array with only negative numbers and k is positive	Return 0 as no subarray sum can equal a positive k with all negative numbers.
Large array sizes and extreme values in array leading to possible Integer Overflow	Use a data type with a larger range than int to avoid integer overflow when calculating prefix sums.
k=0 and the array contains both positive and negative numbers	Correctly count subarrays that sum to zero, even with mixed positive and negative values, using a hash map to track prefix sums.
k is a very large positive number	The prefix sum can become large quickly; use appropriate data types and consider early termination if the prefix sum exceeds k significantly in the negative direction.