# Algorithms & Data Structures - Day 2April 04, 2020

## 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) {
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``````
##### 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 cases `O(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