Big O of Arrays & Objects
Array and objects are built in data structures.
Objects are unordered key pair values. Objects have fast insertion & deletion, use them when order of members are unimportant
Big O of Objects
 Insertion  O(1)
 Removal  O(1)
 Access  O(1)
 Searching  O(n)
Big O of Object Methods
 Object.keys  O(N)
 Object.values  O(N)
 Object.entries  O(N)
 hasOwnProperty  O(1)
NB: Use hasOwnProperty
whenever possible.
Arrays
Arrays are ordered, indexed list.
Big O of Arrays
 Insertion  depends
 Removal  depends
 Sort  O(n)
 Access O(1)
Big O of Array Methods
 push  O(1)
 pop  O(1)
 shift  O(N)
 unshift  O(N)
 concat  O(N)
 slice  O(N)
 splice  O(N)
 sort  O(N * log N)
 forEach/map/filter/reduce/etc.  O(N)
NB: Inserting at the beginning of an array is very expensive. You can make use of data structures like queues
.
Problem solving
 Understand the problem
 Explore concreate examples
 Break it down
 Solve/Simplify
 Look back and Refactor
Understand the problem
 Restate the problem in own words
 What inputs go into the problem?
 What outputs come from the solution of the problem
 Do I have enough information to solve the problem?
 How should I label the important piece of data that are part of the problem?
NB: 2 stand alone loops are better than 2 nested loops
Common Problem Solving Patterns
A few patterns for solving algorithm problems
 Frequency Counter
 Multiple Pointers
 Sliding Window
 Divide and Conquer
 Dynamic Programming
 Greedy Algorithms
 Backtracking
Frequency Counters
Using objects or sets to collect values/frequencies of values. Used to avoid the need for nested loops or O(N2) operations.
E.g: Write a function called same, which accepts 2 arrays. The function should return true
if every value in the array has it’s corresponding value squared in the second array. The frequency of the values must be the same.
same([1, 2, 3], [4, 1, 9]) // true
same([1, 2, 3], [1, 9]) // false
same([1, 2, 1], [4, 4, 1]) // false (must be same frequency)
First solution
The first solution uses a for loop and has Big O complexity of O(n2)
. It works by looping through the first array while removing matching squares of the array items from the second array.
const same = (arr1, arr2) => {
if (arr1.length !== arr2.length) {
return false
}
for (let i = 0; i < arr1.length; i++) {
let correctIndex = arr2.indexOf(arr1[i] ** 2)
if (correctIndex === 1) return false
// Remove the matching square from arr2
arr2.splice(correctIndex, 1)
}
return true
}
NB: indexOf
also runs a loop underneath.
A refactored version with Frequency Counters
This refactor makes use of 3 seperate loops. 2 standalone loops are better than 2 nested loops. This solution has a complexity of O(n)
.
const same = (arr1, arr2) => {
if (arr1.length !== arr2.length) return false
let frequencyCounter1 = {},
frequencyCounter2 = {}
for (let val of arr1) {
frequencyCounter1[val] = (frequencyCounter1[val]  0) + 1
}
for (let val of arr2) {
frequencyCounter2[val] = (frequencyCounter2[val]  0) + 1
}
for (let key in frequencyCounter1) {
if (!(key ** 2 in frequencyCounter2)) return false
if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) return false
}
return true
}
Anagrams  Another Example
An anagram is a word or phrase formed by rearranging the letters of another, e.g Cinema, formed from Iceman. Given 2 strings, write a function to determine if the second string is an anagram of the first.
Solution
const validAnagram = (first, second) => {
if (first.length !== second.length) return false
const lookup = {}
for (let i = 0; i < first.length; i++) {
let letter = first[i]
// Add character if it doesn't exist in object, or increase count if it does
lookup[letter] ? (lookup[letter] += 1) : (lookup[letter] = 1)
}
for (let i = 0; i < second.length; i++) {
let letter = second[i]
// return false if character is not in second array
if (!lookup[letter]) {
return false
} else {
// reduce count if character exists in second array
lookup[letter] = 1
}
}
return true
}
Multiple Pointers
Used for creating pointers or values that correspond to an index or position while moving towards the beginning or end or middle based on certain conditions. Very efficient for solving problems with minimal space complexity
Example
Write a function sumZero
accepting a sorted array of integers. The function should find the first pair where the sum is 0.. Return an array that includes both values that sum to zero or indefined if a pair does not exist.
sumZero([3, 2, 1, 0, 1, 2, 3]) // [3,3]
sumZero([2, 1, 0, 1, 3]) // undefined
sumZero([1, 2, 3]) // undefined
First solution
The first solution uses 2 nested loops, has a time complexity of O(N2)
and space complexity of O(1)
.
const sumZero = arr => {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === 0) {
return [arr[i], arr[j]]
}
}
}
}
Refactored solution with Multiple pointers
The refactored solution has time complexity of O(n)
and space complexity of O(1)
.
const sumZero = arr => {
// Get first and last index of arr
let left = 0,
right = arr.length  1
while (left < right) {
// Add both number
let sum = arr[left] + arr[right]
if (sum === 0) {
// Sum is 0, return array of both values
return [arr[left], arr[right]]
} else if (sum > 0) {
right
} else {
left++
}
}
}
Count Unique Values
Implement a function called countUniqueValues
which accepts a sorted array and counts the unique values in the array.
countUniqueValues([1, 1, 1, 1, 1, 1, 2]) //2
countUniqueValues([1, 2, 3, 4, 4, 4, 5, 6, 6, 12]) //7
countUniqueValues([0]) //0
Solution with Multiple pointers
const countUniqueValues = arr => {
let i = 0
for (let j = 1; j < arr.length; j++) {
if (arr[i] !== arr[j]) {
i++
arr[i] = arr[j]
}
}
}
Sliding Windows
Involves creating a window from one position to another. Very useful for keeping track of a subset of data in an array/string.
Example
Write a function called maxSubArraySum which accepts an array of integers and a number called n
. The function should calculate the maximum sum of n
consecutive elements in the array.
maxSubArraySum([1, 2, 5, 2, 8, 1, 5], 2) // 10
maxSubArraySum([1, 2, 5, 2, 8, 1, 5], 4) //17
maxSubArraySum([], 4) // null
First solution
Involves a nested loop and has Big O of O(n2)
const maxSubArraySum = (arr, num) => {
if (num > arr.length) return null
let max = Infinity
for (let i = 0; i < arr.length  num + 1; i++) {
let temp = 0
for (let j = 0; j < num; j++) {
temp += arr[i + j]
}
if (temp > max) {
max = temp
}
}
return max
}
Refactoring with Sliding Window
This solution has a Big O of O(n)
.
const maxSubArraySum = (arr, num) => {
let maxSum = 0
let tempSum = 0
if (arr.length < num) return null
for (let i = 0; i < num; i++) {
maxSum += arr[i]
}
tempSum = maxSum
for (let i = num; i < arr.length; i++) {
tempSum = tempSum  arr[i  num] + arr[i]
maxSum = Math.max(maxSum, tempSum)
}
return maxSum
}
Divide & Conquer
Involves dividing a dataset into smaller chunks and then repeating a process with a subset of data. Can tremendously decrease time complexity.
Example
Let’s say we’re asked to loop through an array and return true
if a value is a member of an array. We could loop through the array, checking every member for equality (imagine very large arrays).
Or we could divide the array into 2 and only search the part where the value is at.
;[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
suppose we’re to check if the array contains 7
, we can roughly split the array into 2 equals, discard the left part and keep spliting the right till we get to 7.
Searching Algorithms
There’s a lot of search algorithms

Linear search: Looping through an array of items and finding the index. The Big O of linear search is most commonly
O(n)
. But in some cases, the element we’re after can be the element in the first index. Common JavaScript array methods are indexOf()
 find()
 findIndex()
 includes(), etc
 Binary Search: Works by eliminating half of the array elements at a time. But only works on sorted array items. It’s a divide and conquer algorithm. The Big O of binary is
O(log n)
and in some casesO(1)
.
O(log n)
means we get one additional operation when we double the size of the array.
E.g: An array of 4 elements will have a Big O of 2
because log2(4) == 2
. If we increase the array size to 8
, Big O increases to 3
, if we increase array size to 16
, Big O increases to 4
and if we increase to 32
, Big O increases to 5
. That’s significantly better than a loop that runs 32 times.
Example of Binary Search
const binarySearch = (arr, elem) => {
let start = 0,
end = arr.length  1,
middle = Math.floor((start + end) / 2)
while (arr[middle] !== elem && start <= end) {
if (elem < arr[middle]) end = middle  1
else start = middle + 1
middle = Math.floor((start + end) / 2)
}
return arr[middle] === elem ? middle : 1
}
String Search
Imagine we need to search through a paragraph of text and return the matching phrase. We could do that with loops
const search = (text, pattern) => {
let count = 0
for (let i = 0; i < text.length; i++) {
for (let j = 0; j < pattern.length; j++) {
if (pattern[j] !== text[i + j]) break
if (j === pattern.length  1) count++
}
}
return count
}
This solution has a Big O of O(nm)
because we have a nested loop.
Tomorrow
I’ll try my hands on KMP searching algorithm tomorrow