Source: JavaScript Algorithms and Data Structures Masterclass

Frequency Counter

When counting frequency of iterable objects, avoid nested looping that results in O(n^2), by using objects or sets to collect values.

Example

Create a function named “same” that compares 2 arrays, and check if one array contains the squared values of the other, with matching frequencies

The Naive Solution

Use nested loop to check if squared value of current looping element exists.

Result: O(n^2)

Refactoring using Frequency Counter

Use multiple loops instead of nested loops, create objects of each array, with key of elements of array, and value of frequency.

Result: O(3n) === O(n)

Anagram

Create a function that validates if a string is an anagram of the other.

// My initial solution
// Use same pattern as above
const validAnagram = (str1, str2) => {
    if (str1.length !== str2.length) {
        return false;
    };

    str1Obj = {};
    str2Obj = {};

    for (s of str1) {
        str1Obj[s] = (str1Obj[s] || 0) + 1;
    };
    for (s of str2) {
        str2Obj[s] = (str2Obj[s] || 0) + 1;
    };

    for (s in str1Obj) {
        if(!str2Obj[s] || str1Obj[s] !== str2Obj[s]) {
            return false
        };
    }
    return true;
}

// Model Solution
// Create 1 object => loop over 2nd string and subtract from obj1, checking if 0

const validAnagram = (str1, str2) => {
    if(str1.length !== str2.length) {
        return false;
    }

    str1Obj = {}

    for (s of str1) {
        str1Obj[s] = (str1Obj[s] || 0) + 1;
    }

    for (c of str2) {
        if(!str1Obj[c] || str1Obj[c] === 0) {
            return false;
        } else {
            strObj[c]--;
        }
    }
    return true;
}

Multiple Pointers

When searching for a pair that meets a certain condition, use two references(pointers) and work towards the middle

Example

From a sorted Array, find the first pair of which the sum of the pair equals 0.

Naive Solution

Create a nested loop for each element of the loop, check each sum

Result: O(n^2)

Refactored with Multiple Pointer

Start with two indicators that is located on each end of the array. While the left pointer is smaller than the right pointer, if the sum of the two is positive move right pointer -1, and if negative move left pointer + 1. If this is 0, that is the answer.

const countUniqueValues = (arr) => {
    let i = 0;
    for (let j = 1; j <= arr.length; j++) {  // although j is supposed to end at length - 1, this results in one final increment of i without actually having to do so
        if (arr[i] !== arr[j]) {
            arr[++i] = arr[j]
        }
    }
    return i
}

Sliding Window

Used when dealing with a subset of data that is continuous.

Example

Create a function that accepts an array and a number. Find the largest sum of the subset with the length of the given number in the array.

Naive Solution

Using nested loop, for each element of the array, get sum of each subset, compare it to the current max value. Result: O(n^2)

Refactoring with Sliding Window

Instead of the nested loop, move the subset as a whole by subtracting the very first element and adding the upcoming element.

function maxSubarraySum(arr, num) {
	let maxSum = 0;
	let tempSum = 0;
	if (arr.length < num) return null;

    // Get sum of first subset
	for (let i = 0; i < num; i++) {
		maxSum += arr[i];
	}
	tempSum = maxSum;

    // Loop array, subtract the current first number, add next number
	for (let i = num; i < arr.length; i++) {
		tempSum = tempSum - arr[i-num] + arr[i];
		maxSum = Math.max(maxSum, tempSum);
	}
	return maxSum;
}