Contiguous Subarray Sum

Given an array of numbers, return true if there is a subarray that sums up to a certain number n.

A subarray is a contiguous subset of the array. For example the subarray of [1,2,3,4,5] is [1,2,3] or [3,4,5] or [2,3,4] etc.

const arr = [1, 2, 3], sum = 5
subarraySum(arr, sum)
// true
// [2, 3] sum up to 5

const arr = [11, 21, 4], sum = 9
subarraySum(arr, sum)
// false
// no subarrays sums up to 9

In the above examples, [2, 3] sum up to 5 so we return true. On the other hand, no subarray in [11, 21, 4] can sum up to 9.

Can you create a function subarraySum that accomplishes this?

Constraints

• Length of the array <= 100000
• The values in the array will be between 0 and 1000000000
• The target sum n will be between 0 and 1000000000
• The array can be empty
• Expected time complexity : O(n)
• Expected space complexity : O(n)

```js
function subarraySum(nums, n) {
  // hash of prefix sums

  // Fill in this method
  return nums;
}

const arr = [1, 2, 3],
  sum = 5;
console.log(subarraySum(arr, sum));
```

Let's take another example. If the input was [3, 2, 5, 1] and our target number was 6, we'd witness the following if we did tried the brute force solution by hand:

```
// the left side are the subsets we're trying

3 & 2        // curr_sum is 5, < 6, continue
3 & 2 & 5    // too big, skip
2 & 5        // curr_sum is 7, skip
5 & 1        // match!
```

With arrays, we can iteratively generate and run through every subarray within the array. Thus, the easiest brute force solution may be to simply test every subarray sum against n.

```js
function subarraySum(nums, sum) {
	let currSum, i, j;
	for (i = 0; i < nums.length; i += 1) {
		currSum = nums[i];
		j = i + 1;
		while (j <= nums.length) {
			if (currSum == sum) {
				return true;
			}
			if (currSum > sum || j == nums) {
				break;
			}
			currSum = currSum + nums[j];
			j += 1;
		}
	}
	return false;
}

console.log(subarraySum([1, 2, 3], 5));
```
```py
def subarray_sum(nums, sum):
	curr_sum, i, j = None, None, None
	for i in range(len(nums)):
		curr_sum = nums[i]
		j = i + 1
		while j <= len(nums):
			if curr_sum == sum:
				return True

			if curr_sum > sum or j == nums:
				break

			curr_sum = curr_sum + nums[j]
			j += 1

	return False

print(subarray_sum([1, 2, 3], 5))
```

Which of these could be a valid brute force solution?

We Can Do Better

The above code will complete a scan of every subarray possible. It does so by iterating through every element in the array. Then, at each loop, it tests every subarray with that starting index.

This works but is wildly inefficient. What if there were millions or billions of elements in each array? This caveat can also be understood by the time complexity of the brute force approach. As we are iterative through the array for each given n elements, the time complexity is O(n^2). So for a million elements in the array, there will be 10^12 operations which is huge. Perhaps we don't need to test each possible subarray -- so what if we didn't?

To make the brute force more efficient, we will be using a very popular data structure named: Hash Table.

A hash table keeps a key-value pair in a table using a hash function. As the hash function directly returns the memory address of the value given a key, its search, insert, and delete operations are in constant O(1) time.

We will be using a hash table to store the cumulative sum of the array as a key and its ending elements index as the value.

A hash table supports the search, insert, and delete operations in constant O(1) time.

We can only find a contiguous subarray summing to a certain number in O(n^2) time complexity or greater.

What could be the right order for the contiguous subarray sum algorithm?

Notice that most of the subarrays overlap in some way. In [3, 2, 5, 1], [3, 2] is part of [3, 2, 5]. It seems there's an opportunity to keep track of just one thing for now.

The final solution has us using a hash map/dict to store previous subarray sums.

One Pager Cheat Sheet

• Create a function subarraySum that returns true if a contiguous subarray sums up to a certain number n with a time complexity of O(n) and a space complexity of O(n).
• By brute force, we can manually check possible combinations of elements from the array [3, 2, 5, 1] to identify if they add up to the target number of 6.
• We can iteratively test every subarray of the array to find the brute force solution to the problem.
• A brute force solution involves exhaustively searching through all possible solutions to find the desired result.
• We can do better than O(n^2) time complexity by avoiding testing each possible subarray.
• We will be using a Hash Table to store the cumulative sum of the array as a key and its ending elements index as the value in order to improve the efficiency of the brute force algorithm.
• A hash table uses a hash function to store the key-value pairs in a table, enabling search, insert, and delete operations to be executed in constant O(1) time.
• A hash table enables constant time operations for search, insert, and delete, whereas finding a contiguous subarray summing to a certain number requires O(n^2) or greater time complexity due to the need for a brute-force approach involving iterating through all possible subarrays.
• We can calculate and store the running sum in a hash, allowing us to check if a subarray sum matches the target in O(n^2) time complexity or greater.
• We can use a hash map to store previous subarray sums and track only one thing, since most subarrays overlap in some way.