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) {
    // 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 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