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.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function subarraySum(nums, n) {

  let sumsMap = { 0: 1 }; // hash of prefix sums

  let sum = 0;

  for (let num of nums) {

    sum += num; // increment current sum

    if (sumsMap[sum - n]) {

      return true;

    }

    // store sum so far in hash with truthy value

    sumsMap[sum] = true;

  }

  return false;

}

​

const arr = [1, 2, 3],

  sum = 5;

console.log(subarraySum(arr, sum));

​

try {

  assert.equal(subarraySum([1, 2, 3], 3), true);

​

  console.log('PASSED: ' + 'assert.equal(subarraySum([ 1, 2, 3 ], 3), true)');

} catch (err) {

  console.log(err);

}

​

try {

  assert.equal(subarraySum([], 3), false);

​

  console.log('PASSED: ' + 'assert.equal(subarraySum([], 3), false)');

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.