Jobs

Interviews

Discussions

Binary Subarrays With Sum

Medium

Apple

1 view

Topics:

ArraysSliding WindowsTwo Pointers

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.

A subarray is a contiguous part of the array.

For example:

nums = [1,0,1,0,1], goal = 2. The output should be 4 because the following subarrays sum to 2: [1,0,1], [1,0,1,0], [0,1,0,1], [1,0,1].
nums = [0,0,0,0,0], goal = 0. The output should be 15.

Clarifications:

What should the function return if the input array is null or empty? (Return 0).
What are the possible values of elements in nums? (0 or 1).
What is the possible range of values for goal? (0 <= goal <= nums.length).

Write a function to efficiently solve this problem.

Binary Subarrays With Sum

Medium

Apple

1 view

Topics:

ArraysSliding WindowsTwo Pointers

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.

A subarray is a contiguous part of the array.

For example:

nums = [1,0,1,0,1], goal = 2. The output should be 4 because the following subarrays sum to 2: [1,0,1], [1,0,1,0], [0,1,0,1], [1,0,1].
nums = [0,0,0,0,0], goal = 0. The output should be 15.

Clarifications:

What should the function return if the input array is null or empty? (Return 0).
What are the possible values of elements in nums? (0 or 1).
What is the possible range of values for goal? (0 <= goal <= nums.length).

Write a function to efficiently solve this problem.

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 is the expected range of values within the binary array, are we strictly dealing with 0s and 1s?
What should I return if no subarray exists with the given sum?
Is the target sum 'goal' always a non-negative integer?
Are overlapping subarrays considered distinct, or should I only count non-overlapping subarrays that meet the sum requirement?
How large can the input array 'nums' be, and what is the upper bound for the target sum 'goal'?

Brute Force Solution

Approach

Imagine you have a row of light bulbs, some on (represented by 1) and some off (represented by 0). We need to find how many sections of the row have a specific number of lights on. The brute force approach is to check every possible section, one by one.

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

Consider the first light bulb alone. Check if it is on and if it matches the required number of lights.
Then, consider the first two light bulbs. Check how many are on, and if it matches the requirement.
Continue this, considering the first three, then the first four, and so on, until you've checked the entire row from the beginning.
Next, start from the second light bulb and repeat the process: check the second light bulb alone, then the second and third, then the second, third, and fourth, and so on, checking each section's number of on lights.
Continue shifting the starting point one light bulb at a time, and repeating the process of checking all sections until you've covered every possible section of the row.
Each time you find a section that has the exact required number of lights on, count it as a valid result.
Finally, after checking every possible section, the total count of valid sections is your answer.

Code Implementation

def binary_subarrays_with_sum_brute_force(binary_array, goal):
    number_of_subarrays = 0

    # Iterate through all possible starting indices
    for start_index in range(len(binary_array)):
        current_sum = 0

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

            # Check if current subarray sum matches the goal
            if current_sum == goal:
                number_of_subarrays += 1

            # If the current sum exceeds goal, no need to continue
            elif current_sum > goal:
                break

    return number_of_subarrays

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the array using a nested loop structure. The outer loop starts at each index of the array of size n. The inner loop then iterates from that starting index to the end of the array, checking all possible subarrays. In the worst case, this involves checking approximately n*(n+1)/2 subarrays. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The provided plain English explanation describes a brute force approach involving iterating through all possible subarrays and calculating their sums. No auxiliary data structures like arrays, lists, or hash maps are used to store intermediate results or visited states. Only a few variables (loop counters, current subarray sum) are needed, and the number of these variables remains constant regardless of the size of the input array. Therefore, the space complexity is constant.

Optimal Solution

Approach

The best way to solve this is to count the number of subarrays that have *at most* the target sum, and then subtract the number of subarrays that have *at most* (target sum minus one). This difference gives you exactly the number of subarrays with the target sum. The approach involves efficiently keeping track of valid subarrays using a 'sliding window' that expands and contracts as it moves along the main sequence.

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

Create a method to count the number of subarrays with a sum that's at most a specific value.
For this method, imagine a window that can grow or shrink along the sequence of numbers.
Move the right side of the window to include more numbers until the sum inside the window is just over the target.
If the sum inside the window exceeds the target, shrink the window from the left until the sum is at most the target again.
Each time you move the right side of the window, count how many valid subarrays end at that spot. The length of the valid window gives you this count.
Repeat until the right side of the window reaches the end of the sequence.
To get your final result, calculate how many subarrays have a sum at most the target number and subtract the amount of subarrays that have a sum at most one less than the target number. This isolates the subarrays with an exact target sum.

Code Implementation

def numSubarraysWithSum(numbers, target):
    def atMost(target_sum):
        if target_sum < 0:
            return 0
        
        window_start = 0
        current_sum = 0
        count = 0

        for window_end in range(len(numbers)):
            current_sum += numbers[window_end]

            # Shrink window until sum is <= target_sum
            while current_sum > target_sum:
                current_sum -= numbers[window_start]
                window_start += 1

            # Add the number of valid subarrays ending at window_end
            count += window_end - window_start + 1

        return count

    # Get the difference to find exact target sum subarrays
    return atMost(target) - atMost(target - 1)

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the array using a sliding window approach. The right pointer of the window moves from left to right once, covering each element of the input array of size n. The left pointer may also move, but the total number of movements for the left pointer across all iterations is at most n, because it cannot go beyond the right pointer. Thus, each element in the input array is visited a maximum of two times (once by the right and once by the left), resulting in a time complexity of O(n).

Space Complexity

O(1) – The provided solution uses a sliding window approach, primarily involving two pointers to define the window boundaries. Regardless of the input array's size (N), the algorithm only requires a few integer variables to store the current window's sum and the left and right indices of the window. No auxiliary data structures like arrays, lists, or hash maps are created that scale with the input size. Therefore, the space complexity remains constant, independent of the input size N.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there are no subarrays.
Input array of size 1	Check if the single element equals the goal and return 1 if it does, 0 otherwise.
Input array with all zeros and a target greater than 0	Return 0, as no subarray will sum to the target.
Input array with all ones and a target greater than array length	Return 0, as the maximum possible sum is the array length.
Target equals 0 and array contains only 0s and 1s	Count the subarrays containing only zeros using the sliding window approach, considering all zero-length subarrays.
Large input array with potential integer overflow in sum calculation	Use a 64-bit integer type if necessary or check for overflow during sum calculation and handle appropriately.
Target is negative (problem states non-negative target, but consider)	The problem statement specifies non-negative numbers and target, so clarifying invalid input or if negative target is valid is necessary.
Target equals the sum of all elements in the input array	The entire array constitutes a valid subarray, handle this edge case correctly by returning the expected count using a sliding window approach.

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 is the expected range of values within the binary array, are we strictly dealing with 0s and 1s?
What should I return if no subarray exists with the given sum?
Is the target sum 'goal' always a non-negative integer?
Are overlapping subarrays considered distinct, or should I only count non-overlapping subarrays that meet the sum requirement?
How large can the input array 'nums' be, and what is the upper bound for the target sum 'goal'?

Brute Force Solution

Approach

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

Consider the first light bulb alone. Check if it is on and if it matches the required number of lights.
Then, consider the first two light bulbs. Check how many are on, and if it matches the requirement.
Continue this, considering the first three, then the first four, and so on, until you've checked the entire row from the beginning.
Next, start from the second light bulb and repeat the process: check the second light bulb alone, then the second and third, then the second, third, and fourth, and so on, checking each section's number of on lights.
Continue shifting the starting point one light bulb at a time, and repeating the process of checking all sections until you've covered every possible section of the row.
Each time you find a section that has the exact required number of lights on, count it as a valid result.
Finally, after checking every possible section, the total count of valid sections is your answer.

Code Implementation

def binary_subarrays_with_sum_brute_force(binary_array, goal):
    number_of_subarrays = 0

    # Iterate through all possible starting indices
    for start_index in range(len(binary_array)):
        current_sum = 0

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

            # Check if current subarray sum matches the goal
            if current_sum == goal:
                number_of_subarrays += 1

            # If the current sum exceeds goal, no need to continue
            elif current_sum > goal:
                break

    return number_of_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Create a method to count the number of subarrays with a sum that's at most a specific value.
For this method, imagine a window that can grow or shrink along the sequence of numbers.
Move the right side of the window to include more numbers until the sum inside the window is just over the target.
If the sum inside the window exceeds the target, shrink the window from the left until the sum is at most the target again.
Each time you move the right side of the window, count how many valid subarrays end at that spot. The length of the valid window gives you this count.
Repeat until the right side of the window reaches the end of the sequence.
To get your final result, calculate how many subarrays have a sum at most the target number and subtract the amount of subarrays that have a sum at most one less than the target number. This isolates the subarrays with an exact target sum.

Code Implementation

def numSubarraysWithSum(numbers, target):
    def atMost(target_sum):
        if target_sum < 0:
            return 0
        
        window_start = 0
        current_sum = 0
        count = 0

        for window_end in range(len(numbers)):
            current_sum += numbers[window_end]

            # Shrink window until sum is <= target_sum
            while current_sum > target_sum:
                current_sum -= numbers[window_start]
                window_start += 1

            # Add the number of valid subarrays ending at window_end
            count += window_end - window_start + 1

        return count

    # Get the difference to find exact target sum subarrays
    return atMost(target) - atMost(target - 1)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there are no subarrays.
Input array of size 1	Check if the single element equals the goal and return 1 if it does, 0 otherwise.
Input array with all zeros and a target greater than 0	Return 0, as no subarray will sum to the target.
Input array with all ones and a target greater than array length	Return 0, as the maximum possible sum is the array length.
Target equals 0 and array contains only 0s and 1s	Count the subarrays containing only zeros using the sliding window approach, considering all zero-length subarrays.
Large input array with potential integer overflow in sum calculation	Use a 64-bit integer type if necessary or check for overflow during sum calculation and handle appropriately.
Target is negative (problem states non-negative target, but consider)	The problem statement specifies non-negative numbers and target, so clarifying invalid input or if negative target is valid is necessary.
Target equals the sum of all elements in the input array	The entire array constitutes a valid subarray, handle this edge case correctly by returning the expected count using a sliding window approach.