Jobs

Interviews

Discussions

Subarray Sum Equals K

Medium

Disney

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.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

Subarray Sum Equals K

Medium

Disney

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.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

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:

What are the possible ranges for the values within the `nums` array and for the target value `k`?
Can the `nums` array contain negative numbers, zero, or only positive integers?
What should be returned if there are no subarrays that sum to `k`?
Does the order of elements within a subarray matter? For example, is `[1, 2]` considered different from `[2, 1]`?
Can the input array `nums` be empty or null?

Brute Force Solution

Approach

The brute force method solves this by checking every possible group of numbers within the larger list. It's like trying out every possible combination to see if any adds up to the target value.

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

Start by considering the first number in the list as a group by itself.
Check if this single number is equal to the target value.
Then, consider the first and second numbers together as a group.
Check if this group's sum is equal to the target value.
Continue adding one more number at a time to this group, and check the sum each time, until you reach the end of the list.
Now, move to the second number in the original list and repeat the same process: start with just that number, then that number plus the next, and so on, until you reach the end.
Keep doing this, shifting your starting point one number further each time, until you've checked every possible group of numbers within the list.
Every time you find a group of numbers that adds up to the target value, count it.

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_subarray_sum = 0

        # Iterate through all possible end indices for each start index.
        for end_index in range(start_index, len(numbers)):
            current_subarray_sum += numbers[end_index]

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

    # Return the number of subarrays that sum to k
    return number_of_subarrays

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through each element of the input array of size n. For each element, it calculates the sum of all possible subarrays starting from that element. In the worst case, for the first element, it considers n subarrays, for the second n-1, and so on. The total number of operations approximates to n + (n-1) + (n-2) + ... + 1 which is n*(n+1)/2. This simplifies to O(n²).

Space Complexity

O(1) – The provided brute force solution iterates through all possible subarrays by maintaining a starting index and an ending index. The algorithm does not use any auxiliary data structures like lists, hash maps, or sets to store intermediate results. It only uses a few constant space variables to keep track of the current subarray's sum and the start/end indices, so the extra space remains constant regardless of the input array's size (N).

Optimal Solution

Approach

Instead of checking every single group of numbers, we'll use a trick to keep track of sums we've already seen. This allows us to quickly determine if a group adding up to the target number exists without repetitive calculations. It's like remembering past results to avoid redoing work.

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

Start by going through the numbers one by one, and keep a running total of the sum so far.
Also, keep a record of all the sums you have seen so far, and how many times you've seen each one.
As you calculate each new sum, check if the difference between this sum and the target number is in your record. If it is, it means you've found a group that adds up to the target.
Increase the count of the current sum in your record.
Continue going through the numbers. The running sum and record will help you efficiently identify groups that meet your requirement.

Code Implementation

def subarray_sum_equals_k(numbers, target_value):
    running_sum = 0
    sum_frequency = {0: 1}
    subarray_count = 0

    for number in numbers:
        running_sum += number

        #Check if there is a prefix sum equal to running_sum - target_value
        if (running_sum - target_value) in sum_frequency:

            subarray_count += sum_frequency[running_sum - target_value]

        # Store the frequency of the current running sum.
        if running_sum in sum_frequency:
            sum_frequency[running_sum] += 1
        else:
            sum_frequency[running_sum] = 1

    # Return total number of subarrays found.
    return subarray_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once to calculate the running sum. Inside the loop, it performs constant-time operations: checking for a value in the hash map and updating the hash map. The hash map operations (containsKey and put) take O(1) time on average. Therefore, the overall time complexity is dominated by the single pass through the array, resulting in O(n).

Space Complexity

O(N) – The algorithm uses a record (likely a hash map or dictionary) to store the cumulative sums encountered so far and their frequencies. In the worst-case scenario, all N elements of the input array `nums` could have distinct cumulative sums, leading to N entries in the record. Therefore, the auxiliary space required to store this record grows linearly with the input size N. Thus the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0, as there are no subarrays in an empty array.
Array with a single element that equals k	Return 1 if the single element equals k, otherwise return 0.
Array with all zeros and k is 0	The number of subarrays summing to 0 is (n*(n+1))/2 where n is the length of the array, handled by the hashmap approach.
Array contains only negative numbers and k is positive	Return 0, since the sum of negative numbers cannot be positive.
Large array with a sum exceeding integer limits	Use a long datatype to store the cumulative sum to avoid integer overflow.
Array contains very large positive and negative numbers that cancel each other out to equal k	The hashmap correctly handles cases where the cumulative sum reaches k after a series of additions and subtractions.
k is 0 and the array contains both positive and negative numbers that cancel each other.	The hashmap accurately counts subarrays that sum to 0 even with alternating positive and negative values.
k is negative and the array consists of positive numbers	Return 0 as the sum of positive numbers can never be negative.

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:

What are the possible ranges for the values within the `nums` array and for the target value `k`?
Can the `nums` array contain negative numbers, zero, or only positive integers?
What should be returned if there are no subarrays that sum to `k`?
Does the order of elements within a subarray matter? For example, is `[1, 2]` considered different from `[2, 1]`?
Can the input array `nums` be empty or null?

Brute Force Solution

Approach

The brute force method solves this by checking every possible group of numbers within the larger list. It's like trying out every possible combination to see if any adds up to the target value.

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

Start by considering the first number in the list as a group by itself.
Check if this single number is equal to the target value.
Then, consider the first and second numbers together as a group.
Check if this group's sum is equal to the target value.
Continue adding one more number at a time to this group, and check the sum each time, until you reach the end of the list.
Now, move to the second number in the original list and repeat the same process: start with just that number, then that number plus the next, and so on, until you reach the end.
Keep doing this, shifting your starting point one number further each time, until you've checked every possible group of numbers within the list.
Every time you find a group of numbers that adds up to the target value, count it.

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_subarray_sum = 0

        # Iterate through all possible end indices for each start index.
        for end_index in range(start_index, len(numbers)):
            current_subarray_sum += numbers[end_index]

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

    # Return the number of subarrays that sum to k
    return number_of_subarrays

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by going through the numbers one by one, and keep a running total of the sum so far.
Also, keep a record of all the sums you have seen so far, and how many times you've seen each one.
As you calculate each new sum, check if the difference between this sum and the target number is in your record. If it is, it means you've found a group that adds up to the target.
Increase the count of the current sum in your record.
Continue going through the numbers. The running sum and record will help you efficiently identify groups that meet your requirement.

Code Implementation

def subarray_sum_equals_k(numbers, target_value):
    running_sum = 0
    sum_frequency = {0: 1}
    subarray_count = 0

    for number in numbers:
        running_sum += number

        #Check if there is a prefix sum equal to running_sum - target_value
        if (running_sum - target_value) in sum_frequency:

            subarray_count += sum_frequency[running_sum - target_value]

        # Store the frequency of the current running sum.
        if running_sum in sum_frequency:
            sum_frequency[running_sum] += 1
        else:
            sum_frequency[running_sum] = 1

    # Return total number of subarrays found.
    return subarray_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array (nums is null or has length 0)	Return 0, as there are no subarrays in an empty array.
Array with a single element that equals k	Return 1 if the single element equals k, otherwise return 0.
Array with all zeros and k is 0	The number of subarrays summing to 0 is (n*(n+1))/2 where n is the length of the array, handled by the hashmap approach.
Array contains only negative numbers and k is positive	Return 0, since the sum of negative numbers cannot be positive.
Large array with a sum exceeding integer limits	Use a long datatype to store the cumulative sum to avoid integer overflow.
Array contains very large positive and negative numbers that cancel each other out to equal k	The hashmap correctly handles cases where the cumulative sum reaches k after a series of additions and subtractions.
k is 0 and the array contains both positive and negative numbers that cancel each other.	The hashmap accurately counts subarrays that sum to 0 even with alternating positive and negative values.
k is negative and the array consists of positive numbers	Return 0 as the sum of positive numbers can never be negative.