Number of subarrays having sum exactly equal to K

This article would help you understand how two problems which seem so similar can have different approaches depending on the allowed input. If you are interested in learning more about the two-pointer technique and some interesting approaches along with their subtle differences then you are at the right place. For full blown solutions to these problems you can always refer LeetCode. This article intends to just “Spot the Differences”.

Problem 1

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

Binary Subarrays With Sum - LeetCode

Approach 1: Prefix sums using dictionary

This approach is similar to the approach generally taken for 2-sum problem. Go checkout 2-sum problem if you haven’t already. Let’s break down this problem first.

The problem of finding the number of subarrays with a given sum can be further divided into two problems:

• Find all the contiguous subarrays of the given array.
• Find the sum of each of the subarrays to check if it’s equal to the desired sum.

Number of subarrays formed between index i and j is equal to the number of elements between index i and j.

A subarray is defined by two indices i and j and the elements between them form the sub-array. The total number of combinations for i and j would be O(N²). Can we optimize this?

Here is the part where you need to remember the algorithm you would have used for 2-sum problem 🤓. The problem of 2-sum says, find two numbers such that they add up to a specific target.

The running sum that we maintain in a dictionary will give us the sum of a prefix array at each index . This means while iterating the array at any given time we know how many prefix arrays have a particular sum.

Look at how similar the problems are now. We now have a prefix_sum which is derived from the given array, a running_sum which is also derived from the given array and we are given the target value which is the desired subarray sum. Thus, at any given point when we have the currentrunning_sum we just have to check if the dictionary has a key i.e.prefix_sum such that

prefix_sum + desired_sum = running_sum
or to put it otherwise, running_sum — desired_sum is present in prefix sum dictionary.

By now you would have understood that we need to maintain a running sum for the array. The running sum is nothing but an ongoing sum for the array. We store this sum in a prefix_sumdictionary with keyas the sum and value as the number of times we encountered that sum.

The value corresponding to the key in the prefix_sum dictionary would basically give us the number of prefix arrays that can be removed to get the subarrays of the desired_sum.

At every index you just have to find out how many desired windows are possible. Number of desired window at each index = prefix_sum[running_sum - desired_sum] i.e. the number of prefix arrays that can be removed.

Approach 2: Sliding window approach using two pointers

Sliding window — In any sliding window based problem we have two pointers. The right pointer whose job is to expand the current window and then we have the left pointer whose job is to contract a given window. At any point in time only one of these pointers moves and the other one remains fixed.

In this case the right pointer would expand the window while the sum of the window is less or equal to the desired sum. When the sum of the window exceeds the desired sum we then can contract the window by throwing out a few elements from the left. The contraction continues while the sum is greater than the desired sum.

During this process of sliding the window using left and right pointers. Whenever we have window_sum == desired_sum it means we found a subarray with the desired sum.

And in this process, we keep counting the windows whose sum is equal to the desired sum.

Problem 2:

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Subarray Sum Equals K - LeetCode

Before looking at the differences let’s look at how similar these two problems are.

Both problems want us to find out the number of continuous subarrays with a given sum.

Woah ! This is some crazy amount of similarity.

Are these problems duplicates? What is the difference then 😱😰

The input allowed in both problems is the key here. While Problem 1 allows only binary numbers. Problem 2 deals with integers. Thus, Problem 2 not only deals with 0’s and 1’s but all the positive as well as all the negative numbers. Yes, the negative is highlighted for a reason. Let’s look at how we would have solved this.

Approach 1: Prefix sums using dictionary

This approach works in the same manner as for Problem 1. After all this approach is well adopted for 2-sum. As usual, we would save all the prefix sums and our goal is to find out if removal of any of the prefixes would help us attain the desired window sum.

And that works like a charm.

Approach 2: Sliding window approach using two pointers

If you haven’t thought of this approach already then probably you should now. After all sliding window approach fits so well when we are working with subarrays. But wait, think before you start implementing it. I am guilty of actually going ahead with this approach and later on realizing that this won’t work. And that is the motivation behind this article i.e. to show how a minor detail miss can screw up an approach.

Ideally, the right pointer would expand the window to increase the sum of the window and left pointer would contract the window to decrease the sum. Now read that again. Are you sure that statement would hold true when your array also contains negative numbers?

When sliding a window using left and right pointers we always have a well defined role for both the pointers. When we have negative numbers present in the array this role starts to fade away. When we move the right pointer the sum might increase or decrease based on the number we encounter and the same holds true for left pointer.

Do you see the difference? window_sum increased when left pointer contracted the window. That’s because the element which got kicked off from the window was a negative number.

Thus, whenwindow_sum > desired_sumcontracting the window by moving the left pointer forward does not guarantee that window_sum would decrease.

When during the expansion step window_sum became greater than desired_sum, normally we would have stopped the window expansion at this point and started window contraction to remove some extra elements from the left. This contraction step helped us to decrease thewindow_sum and have a window with sum which is less than the desired_sum so that we could start the expansion step again.

But now that we have negative elements in the array even further expansion i.e. continue moving the right pointer can result in decrease in the window_sum.

This means if we would have stopped the expansion step when window_sum got greater than the desired_window we would just miss out on this new expanded window. But then that also means we are missing the contracted window we might get at this point.
This clearly indicates just the introduction of negative numbers led to fading of the roles for left and right pointers because of the non-deterministic behavior.

Clearly the straightforward sliding window approach fails for Problem 2.

TL;DR Even though two pointer technique works for Problem 1. It won’t work for Problem 2.

Share your views in the comment section. If you have any suggestions for other spot-the-difference problems please share.
Hit the clap 👏 button if you liked the article. ❤