JavaScript: return all contiguous subarrays whose sum equals K

Question

This is a variant of this leetcode question, but instead of returning the count, we want to return the actual contiguous sub arrays. For example, if num = [1,2,4,7] k=7 the returned value should be [[1,2,4],[7]] .

I used a hashmap to store the cumulative sum up to all the indices possible along with the number of times the same sum occurs for the original question, where it asks to return the count

var subarraySum = function(nums, k) {
  let sum = 0;
  let count = 0;
  const myMap = new Map();
  myMap.set(0, 1);

  for (let num of nums) {
    sum += num;
    count += myMap.get(sum - k) || 0;
    myMap.set(sum, (myMap.get(sum) || 0) + 1);
  }
  
  return count;
}

But I cannot seem to figure out how I can adapt this solution to return the actual sub-arrays.

Anatolii · Answer 1 · 2021-04-01T21:05:20.160

Solution

To return all matching contiguous subarrays, you should use your myMap a bit differently. For each key sum, it should store indexes, rather than the frequency of sum.

Also, your ans you should contain an array of matching contiguous subarrays, and it get updated based on indexes stored in myMap.

Basically, if there are indexes for sum - k, then they're start indexes for your new matching subarrays and your current index i is the end index. Hence, you iterate through all start indexes and add new matching subarrays as below:

...
    if (myMap.has(key)) {
      indices = myMap.get(key) 
      for (const index of indices) {
        matchingSubArrayIndices.push([index, i])    
      }
    } 
...

Please find the full code below:

var subarrays = function(nums, k) {
  let sum = 0;
  const myMap = new Map();
  
  myMap.set(0, [0]);
  const matchingSubArrayIndices = new Array()

  for (var i = 0; i < nums.length; i++) {
    num = nums[i]
    sum += num;
    let key = sum - k
    if (myMap.has(key)) {
      indices = myMap.get(key) 
      for (const index of indices) {
        matchingSubArrayIndices.push([index, i])    
      }
    }
    
    array = myMap.get(sum)
    if (array == undefined) {
      array = new Array() 
    }
    array.push(i + 1)
    myMap.set(sum, array);
  }
  
  for (let indices of matchingSubArrayIndices) {
    console.log("Matching subarray")
    for (i = indices[0]; i <= indices[1]; i++) {
        console.log(nums[i] + " ")
    }
  }
}

subarrays([1,3,4], 4)

This solution works quite good for most inputs, but for an input like:

0 0 0 0
0

it will be quadratic in time and space because on each iteration the matchingSubArrayIndices will be growing linearly, and so for all iterations it will be quadratic.

Conclusion

Even though the algorithm is quadratic in the worst case, it's not a problem of the algorithm itself, but of the output. If the output is quadratic, then any solution will be at least quadratic.

score 0 · Answer 2 · answered Apr 02 '21 at 15:22

This is a naïve implementation, but it's quite simple. We simply find all contiguous (non-empty) subarrays, and then filter to find those whose sums match our target:

const sum = (ns) => ns.reduce((a, b) => a + b, 0)
const suffixes = (xs) => xs .map ((_, i) => xs .slice (i))
const prefixes = (xs) => xs .map ((_, i) => xs .slice (0, i + 1))
const subArrays = (xs) => suffixes (xs) .flatMap (prefixes)

const subArraysWithTotal = (ns, t) => subArrays (ns) .filter ((s) => sum (s) == t)

console .log (
  subArraysWithTotal ([1, 2, 4, 7], 7)
)

sum is obvious, just adding together the numbers in an array.

prefixes and suffixes are similar, and should be clear with an example:

prefixes (['w', 'x', 'y', 'z'])
//=> [['w'], ['w', 'x'], ['w', 'x', 'y'], ['w', 'x', 'y', 'z']]

suffixes (['w', 'x', 'y', 'z'])
//=> [['w', 'x', 'y', 'z'], ['x', 'y', 'z'], ['y', 'z'], ['z']]

subArrays combines these, returning all the prefixes of every suffix, which gives us all contiguous subarrays of the original:

subArrays (['w', 'x', 'y', 'z'])
//=> [['w'], ['w', 'x'], ['w', 'x', 'y'], ['w', 'x', 'y', 'z'], 
//    ['x'], ['x', 'y'], ['x', 'y', 'z'], ['y'], ['y', 'z'], ['z']]

Our main function, subArraysWithTotal simply finds all these subArrays and then filters them by calculating their sums, comparing that to our target.

As I said, this is naïve. It will be O(n^2) in space and O(n^3) in time. If we knew that all our numbers were positive, some sort of sliding window technique would definitely improve on both the speed and memory of this. With the possibility of negative numbers, there is still probably a less expensive algorithm, but it's not nearly as obvious.

But we can reduce the memory of this using generator functions. An alternate version replacing all of the above (except sum) with generators, and adding a filter function for generators, might look like this:

const sum = (ns) => ns.reduce((a, b) => a + b, 0)
function* suffixes (xs) {for (let i of xs .keys ()) yield xs .slice (i)}
function* prefixes (xs) {for (let i of xs .keys ()) yield xs .slice (0, i + 1)}
function* subs (xs) {for (let suff of suffixes (xs)) yield* prefixes (suff)}
function* filter (fn, it) {for (let x of it) {if (fn (x)) yield x}}

function* subArraysWithTotal (ns, t) {yield * filter ((s) => sum (s) == t, subs (ns))}

console .log (
  [...subArraysWithTotal ([1, 2, 4, 7], 7)]
)

Now we need only enough memory to hold the current subarray.

score -1 · Accepted Answer · answered Mar 16 '21 at 05:43

Below is an efficient solution with a minor tweak to the code your are referring to. This solution iterates over the input array once + whatever is required to add a subarray to the solution.

On the below line, you know the count if increases, you have something to add to your solution.

count += myMap.get(sum - k) || 0;

Now we need to understand at what index does sum - k exists in the map. On the below line, you are counting only the number of times the sum occurs.

myMap.set(sum, (myMap.get(sum) || 0) + 1);

Instead of just the count, you need to store the index* at which the sum occurs. Get rid of the counts throughout the code and focus only on index.

The pseudo code now looks like below:

for(int i = 0; i < nums.size(); i++):
    sum += nums[i]
    if(sum-k exists in the map):
        start_index = get the index corresponding to that sum-k
        //end_index will be the i
        add to the result set the subarray from start_index to i (or end_index)
    Set in map the sum and index i appropriately

*I hope the resultant subarrays don't overlap. Otherwise, store a list of indices instead of an index.

JavaScript: return all contiguous subarrays whose sum equals K

3 Answers3

Solution

Conclusion