In this blog, I follow up on my earlier post: Managing Big O Notation and give it a shot at explaining a technique to improve some algorithms.
I will be looking specifically at eliminating nested loops through memoization so these examples go from O(n^2) to O(n). In an upcoming blog, I will take a look at improving some recursion solutions.
Memoization
This technique involves using an Object in javascript or any other data structure with key-value pairs (in other languages) to temporarily store some data while the algorithm is being executed. A key-value pair data structure is used because keys are unique so the same key won't be generated more than once. So if certain data has to be accessed multiple times, it can be stored in only one run in the form of key value pairs and then it can be accessed multiple times without the need of regenerating it. When this technique is not used, identical data is created over and over again which makes the algorithm slower.
This approach also allows to add some logic that helps get the solution at the same time we access the data of the object; as we will see in the following example.
Two Sum
A basic example of using a memoization object (in javascript) is Two Sum which is Leetcode problem #1. Two Sum takes an array of integers and a target sum and asks to find any two numbers from the array that add to the target, but we return their indexes. The brute force solution is:
const twoSumSlow = (numbers, sum) => {// O(n^2) big o complexity
for(let i = 0; i<numbers.length; i++){
for(let j = i+1; j<numbers.length; j++){// nested loop j = i+1 to avoid adding same element
if(numbers[i] + numbers[j] === sum){
return [i, j]; // return index of elements that sum to target
}
}
}
};
const numbers = [1,2,7,8,9]
const sum = 10
twoSumSlow(numbers, sum)
// returns => [0,4] which are the indexes of the correct numbers
// because 1 + 9 = 10
This solution uses a nested loop (numbers[i] vs numbers[j]) to check every combination of numbers in the array to see if they add to the required sum.
However, what makes this solution slow is that every number is visited more than once by the nested loop so when the size of the array increases, the amount of visits by the parent and child loop to each number, grows exponentially, which makes the solution expensive.
Taking a look at the memoization object solution:
const twoSumFast = (numbers, sum) => {// O(n) big O time complexity
const dataObject = {}
for(let i =0; i< numbers.length; i++){
dataObject[numbers[i]] = i // create memo object
}
for(let i =0; i< numbers.length; i++){
const missingNumber = sum - numbers[i]
if(dataObject[missingNumber] && dataObject[missingNumber] !== i){
return [dataObject[missingNumber], i] // return missing number's index and current index
}
}
}
const numbers = [1,2,7,8,9]
const sum = 10
twoSumFast(numbers, sum)
// returns => [0,4] which are the indexes of the correct numbers
// because 1 + 9 = 10
We implement memoization by creating a dataObject with the array of numbers as keys of the object and the index of each number in the array as the corresponding value.
dataobject = {
1: 0,
2: 1,
7: 2,
8: 3,
9: 4
}
This way, we can add a second loop (which is not nested) that checks for the missingNumber that adds out to our desired value.
Generating the 'memoization object' dataObject allows us to store all the numbers as unique keys that can be accessed as dataObject[missingNumber] to retrieve the index of the missing number for the 'two sum'.
The added/unique logic in this example comes from using an indirect way of checking for the sum through the missing number, which is found by subtracting the current number from the sum.
const missingNumber = sum - numbers[i]
Then we can add this logic when accessing the object key with dataObject[missingNumber]. And so we kill two birds with one store by generating the missingNumber and also seeing if it exists as a key of the object.
if(dataObject[missingNumber] && dataObject[missingNumber] !== i){
return [dataObject[missingNumber], i]
}
In the nested loop example, we set the sum logic equality in the nested loop which increases the time complexity.
//nested loop w/ i and j
if(numbers[i] + numbers[j] === sum){
return [i, j];
}
Counting Duplicates
This next example is an adaptation from Aaron Martin (AJMANNTECH) video on youtube. This algorithm takes a list of numbers and counts the duplicates.
const countDuplicatesSlow = (numbers) => { // O(n^2) big o complexity
let result = []
for(let i = 0; i<numbers.length; i++){
let count = 0
for(let j = 0; j<numbers.length; j++){
if(numbers[i] === numbers[j]){ // if we find a duplicate as we compare all numbers to all numbers
count++
}
}
result.push(`Found a total of: (${count}) number ${numbers[i]}s`)
}
return [...new Set(result)]) // only unique
}
In this example, we use a nested loop to evaluate every item (outer for loop) against the rest of the items (inner for loop) and start to count how many duplicates we have on the array.
const duplicateNumbers = [1,2,3,2,1,2]
countDuplicatesSlow(duplicateNumbers)
// returns => [Found a total of: (2) number 1s,
// Found a total of: (3) number 2s,
// Found a total of: (1) number 3s]
So first we create a loop to save the unique elements as keys to the object with an empty array as value and then we do a second loop to count the duplicates to the corresponding keys.
const countDuplicates = (numbers) => { // O(n) big o complexity
let result = {}
for(let i = 0; i<numbers.length; i++){
if(!result[numbers[i]]){ // if key does not exist the value has not been accounted for
let count = 1;
result[numbers[i]] = numbers[i] //initialize key
result[numbers[i]] = count // initialize value
} else {
result[numbers[i]]++ //increase count if key already exists
}
}
return result
}
Not having a nested loop allows for the algorithm to be O(n) instead of O(n^2).
Top comments (0)