Algorithm: a set of instructions for completing a specific task.
Big O helps us answer the Key Question:
🔑 If there are N data elements, how many steps will the algorithm take?
Big O is much more than just how many steps an algorithm takes. It tells the story of how the number of steps increase.
🛟 How will an algorithm's performance change as the data increases?
Why is this important?
Suppose we have two algorithms. One O(1) algo takes 100 steps, regardless of input size. The other, a linear O(N). Which is faster?
For all arrays greater than 100, the O(N) algo takes longer.
- Big O notation generally refers the worst-case scenario, unless noted otherwise.
| Big O | Pronunciation | Time Complexity | Notes |
|---|---|---|---|
| O(1) | "O of one" | Constant time | |
| O(log N) | "O of log N" | Log time | |
| O(N) | "O of N" | Linear time | O(log2 N) |
| O(N2) | "O of N squared" | Quadratic time | Typical of nested loops |
| O(N!) | "O of factorial N" | Factorial Time |
Logarithms are the inverse of exponents.
Exponent example: 23 = 2 * 2 * 2 = 8
The converse of the above exponent is: log28 = 3
We had to multiply 2 by itself three times to get 8.
We can also look at it as: 8 / 2 / 2 / 2 = 1
Put simply: O(log N) means the algorithm takes as many steps as it takes to keep halving the data elements until we remain with 1.
(see code example)
Two significant steps: comparisons and swaps.
For N elements, we make:
(N - 1) + (N - 2) + (N - 3) ... + 1 comparisons.
Given 10 elements:
Worst case: need to swap for each comparison; 20 total steps (10 swaps + 10 comparisons).
This grows at approximately O(N2)
func hasDuplicateValue(arr []int) bool {
for i := 0; i < len(arr); i++ {
for j := 0; j < len(arr); j++ {
if i != j && arr[i] == arr[j] {
return true
}
}
}
}Refactoring the above func to be linear (This has storage inefficiencies):
func hasDuplicateValue(arr []int) bool {
existingNumbers := make([]int, len(arr))
for i := 0; i < len(arr); i++ {
if existingNumbers[i] == 1 {
return true
} else {
existingNumbers[i] = 1
}
}
}How to compare two algorithms that seem to have the same efficiency?
We'll use (Selection Sort), and compare it to Bubble Sort.
Selection sort will make one or zero swaps, compared to bubble sort which will make a swap for each and every comparison
in the worst case. Given this, Selection Sort can take about half the amount of steps as Bubble Sort, or seemingly O(N2 / 2).
Why are they the same Big O speed?
👉 Big O ignores constants.
For example:
- N / 2 steps == O(N)
- N2 + 10 == O(N2)
- 2N steps == O(N)
- O(1000N) == O(N)
👉 Big O only cares about general categories of algorithm speed. This ties back to the soul of Big O. So, when two algos fall under the same category, further analysis is needed.
We count the number of all steps in algos that fall under the same category.
It's import to consider all scenarios when choosing an algorithm(worst/average/best case). As an example, well compare Insertion Sort with selection sort.
In the worst case, insertion sort is O(N2+N)
- N2 comparisons and shifts
- N - 1 removals
- N - 1 insertions
This give N2 + 2N - 2 Step, which is simplified to O(N2+N) because:
👉 Big O only takes into account the highest order of N when there are multiple orders added together.
ie: an algo with N4 + N3 + N2 + N steps is simplified to N4.
In the worst case, Selection Sort is faster than Insertion Sort. BUT, we must also consider the average case scenario.
Insertion sort recap:
- Worst-case scenario: compare and shift all data. ()
- Best-case scenario: shift none of data, making just on comparison per pass.
- For average case, we'd probably compare and shift only half the data.
| Algo | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Selection Sort | N2 / 2 | N2 / 2 | N2 / 2 |
| Insertion Sort | N | N2 / 2 | N2 |
Therefore, the better algorithm depends on the context. Both perform similarly in the average case.
If you can assume that the data will be mostly sorted, use Insertion Sort, but if you can assume it will be mostly sorted
in reverse, then use Selection Sort.
If you don't know, the average case applied, and both are equal.
To answer the question of "if there are N data elements, how many steps will the algorithm take?":
- Determining what the "N" data elements are.
- Determine how many steps the algorithm takes to process these N values.
3N + 3
O(N)
func averageOfEvenNumbers(arr []int) int {
sum := 0
count := 0
for _, num := range arr {
if num % 2 == 0 {
sum += num
count++
}
}
return sum / count
}In this example, the loop loops over each of the N elements, so it takes at least N steps.
Inside the loop, it checks if the number is even, and if so, performs two more steps (add to sum, and increment count).
Big O assumes the worst case, so we say it takes 3N steps, 3 steps for each of the N numbers. Outside the loop, there are
another 3 steps performed. Overall, the algorithm takes a total of 3N + 3. After ignoring constants, this is O(N).
3N2 + 1
O(N2)
func wordBuilder(arr []string) []string {
var collection []string
for i := 0; i < len(arr); i++ {
for j := 0; j < len(arr); j++ {
if i != j {
collection = append(collection, arr[i]+arr[j])
}
}
}
return collection
}If there were three nested loops, this would be O(N3)
O(1)
func sample(arr []int) (int, int, int) {
first := arr[0]
middle := arr[len(arr)/2]
last := arr[len(arr)-1]
return first, middle, last
}2N
O(N)
func averageCelcius(fahrenheitReading []float64) float64 {
var celciusNumbers []float64
// Convert each reading to celsius and add to array.
for _, f := range fahrenheitReading {
celsiusConversion := (f - 32) / 1.8
celciusNumbers = append(celciusNumbers, celsiusConversion)
}
// Get sum of all Celsius numbers
var sum float64
for _, c := range celciusNumbers {
sum += c
}
// Return mean average
return sum / float64(len(celciusNumbers))
}5N
O(N)
func markInventory(clothingItems []string) []string {
clothingOptions := []string{}
for _, item := range clothingItems {
for i := 1; i < 6; i++ {
clothingOptions = append(clothingOptions, fmt.Sprintf("%s Size: %d", item, i))
}
}
return clothingOptions
}O(N)
Inner loop only runs for as many numbers as there are in total.
func countOnes(outerArr [][]int) int {
count := 0
for _, innerArray := range outerArr {
for _, num := range innerArray {
if num == 1 {
count++
}
}
}
return count
}N/2 + 3
O(N)
func isPalindrome(str string) bool {
leftIndex := 0
rightIndex := len(str) - 1
// Iterate until left index reaches middle of the array.
for leftIndex < len(str)/2 {
if str[leftIndex] != str[rightIndex] {
return false
}
leftIndex++
rightIndex--
}
return true
}N2/2
O(N2)
func twoNumbers(arr []int) []int {
var products []int
for i := 0; i < len(arr); i++ {
for j := i + 1; j < len(arr); j++ {
products = append(products, arr[i]*arr[j])
}
}
return products
}O(N * M), where N is the size of one array and M is the size of the second.
O(N * M) can be thought of as in between O(N) and O(N)
func twoNumberProducts(arr1 []int, arr2 []int) []int {
var products []int
for i := 0; i < len(arr1); i++ {
for j := 0; j < len(arr2); j++ {
products = append(products, arr1[i]*arr2[j])
}
}
return products
}O(26N)
below is in ruby
def every_password(n)
(("a" * n)..("z" * n)).each do |str|
puts str
end
endAllow O(1) lookup speed of key-value pairs.
Conversion of chars into a numbers via a hash function. Lookups done in two steps:
- Hashing the key.
- Look in cell of hashmap if a value exists for the given key.
When the two keys, after hashing, have the same number. One approach to resolve this is separate chaining: Separate chaining: The value becomes an array. (because of this the worst case of a hash lookup is O(N), if all values get placed in the same key.)
Hash table efficiency depends on:
- Amount of data stored in the hash table
- How many cells are available in the hash table
- The hash function being used.
A good hash table strikes a good balance between avoiding collisions and not consuming large amounts of memory
#️⃣ For every 7 data elements stored in the hash table, it should have 10 cells
Load Factor: the ratio of data to cells.
#️⃣ Ideal load factor:0.7 = 7 elements / 10 cells
These are simply arrays with restrictions, specifically suitable for handling temporary data, with an emphasis on the order data is handled.
A LIFO data structure.
Three constraints:
- Data is inserted at the end of the stack.
- Data is deleted from the end of the stack.
- Only the last element can be read.
Pushing onto the stack: inserting data.
Popping from the stack: removing data.
Peaking: reading the last element without removal.
Stacks are abstract data types: a data structure with a theoretical set of rules revolving around some other concrete
data structure.
Abstract data structures help prevent bugs and give us mental models to work with for a problem.
A FIFO data structure.
Three constraints:
- Data is inserted at the end of the queue.
- Data is deleted from the front of the queue.
- Only the first element can be read.
Enqueue: inserting data.
Dequeue: removing data.
Peaking: reading the last element without removal.
Recursion is when a function calls itself. Arbitrary loop vs recursive comparison:
// loop
func countdown(n int) {
for i := n; i >= 0; i-- {
fmt.Println(i)
}
}
// recursion
func countdown(n int) {
fmt.Println(n)
if n == 0 { // The base case
return
}
countdown(n - 1)
}👉 Base case is the cae in which the function will not recurse. All recursive functions need a base case, or we encounter stack overflow.
- Identify the base case
- Walk through the function for the base case
- Identify the "next-to-last" case, the case just before the base case
- Repeat this process by identifying the case before the one you just analyzed, walking through the function for that case
func factorial(n int) {
// identify the base case, the number 1
if n == 1 {
return 1
}
// the next case:
return n * factorial(n - 1)
}Walking through the above example, when n = 4:
factorial(4) returns 24 == 4 * factorial(3)
factorial(3) returns 6 == 3 * factorial(2)
factorial(2) returns 2 == 2 * factorial(1)
factorial(1) returns 1 This is another way to word the base case for this func.
Simply put: ( 4 * 3 * 2 * 1) = 24
Func calls are places on the call-stack. The return value is passed up through the call stack, to the calling function.
There are a few patterns that make a problem suitable for recursion:
When the goal of an algorithm is to repeatedly execute a task. The countdown example above encompasses this.
Often, having to pass a separate default parameter is cumbersome, so some languages allow a default param.
Go doesn't allow passing default parameters, so we use an enclosure.
// doubleArray will double each element of a []int in place.
func doubleArray(arr []int) {
index := 0
var recurse func(arr []int, index int)
recurse = func(arr[]int, index int) {
if index == len(arr) {
return
}
arr[index] *= 2
index++
recurse(arr, index)
}
recurse(arr, index)
}When the goal is to make a calculation based on a sub-problem of the problem at hand.
Subproblem: the very same problem applied to a smaller input.
ex: factorials. 6! = 6 * 5 * 4 * 3 * 2 * 1. Here, we know that factorial(6) will be multiplied by whatever factorial(5) is.
So factorial(6) is the same as 6 * factorial(5).
The factorial example above exemplifies this. In that solution, we compute the result as n multiplied by the subproblem factorial(n - 1)
Requires passing extra params. Bottom up is the same strategy used for making loops or recursion; the same computational approach.
Making calculations based on the problem's subproblems. Needs recursion.
Allows us to mentally "kick the problem down the road".
We don't have to understand how the function calling works so solve the problem, as in the return n * factorial(n - 1 statement.
- Imagine the function you're writing has already been implemented before.
- Identify the subproblem of the problem.
- See what happens when you call the function on the sub-problem and go from there.
Array Sum
A func that sums all nums in an array. Given an array [1, 2, 3, 4, 5]
- Assume it has already been implemented.
- Identify the subproblem: We can say the subproblem is
[2, 3, 4, 5], all numbers except for the first. - Try to apply the sum func to our sub problem:
sum([2, 3, 4, 5] = 14. Adding the first number,1, to the result.- i.e.
return array[0] + sum(array[1:len(array)-1]),
- i.e.
- Lastly, be sure to handle the base case!
if len(array) == 1; { return array[0] }
String Reversal
Given string "abcde", the subproblem is "bcde.
Now pretend the revers() func already exists, so we can call reverse("bcde") to get "edcb".
After that, we'd just throw "a" at the end.
func reverse(s string) string {
if len(s) == 0 {
return ""
}
return reverse(s[1:]) + string(s[0])
}Counting X
Return the number of "x's" in a given string.
Given string "axbxcxd" it should return 3. Subproblem is "xbxcxd"
We call countX("xbxcxd") and get 3. We would need to add 1 if the first char was "x", or just return that if not.
func countX(str string) int {
if len(str) == 0 {
return 0
}
if str[0] == 'x' {
return 1 + countX(str[1:])
}
return countX(str[1:])
}Given a staircase of N steps, you have the ability to climb 1, 2, or 3 steps at a time. How many possible paths can someone take to reach the top?
Ex:
Two steps - Two possible paths: 1, 1, 2
Three steps - Four possible paths: 1, 1, 1, 1, 2, 2, 1, 3
Four steps - Seven possible paths: 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 2, 1, 1, 2, 2, 3, 1
You can see how this would be tough without recursion for larger numbers of steps. Top-down thinking helps.
For 11 steps, the subproblem is a 10-step staircase: Climbing 11 steps would take at least as many steps as climbing a 10-step staircase.
But we also know someone could jump to the top from stair 9 or 8 as well.
Therefore: the number of steps to the top is at least the sum of all the paths to stairs 10, 9 and 8. Beyond this, you can't jump from stair 7 to 11.
👉 numberOfPaths(n - 1) + numberOfPaths(n - 2) numberOfPaths(n - 3) is the core algorithm!
Base case for this problem is more difficult. We could hardcode it:
func numberOfPaths(n int) int {
switch {
case n <= 0:
return 0
case n == 1:
return 1
case n == 2:
return 2
case n == 3:
return 4
default:
return numberOfPaths(n -1) + numberOfPaths(n -2) + numberOfPaths(n - 3)
}
}🆒 But let's do better:
- We know that
numberOfPaths(1)should return one. Soif n == 1 { return 1 }. - We know
numberOfPaths(2)should return 2, and it will compute as:numberOfPaths(1) + numberOfPaths(0) + numberOfPaths(-1)- Here,
numberOfPaths(1)returns 1, so we tellnumberOfPaths(0)to also return 1, which gives us the desired 2. ie: if n < 0; { return 0 }if n == 1 || n == 0; { return 1 }
- We
numberOfPaths(3)should return 4. it computes as:numberOfPaths(2) + numberOfPaths(1) + numberOfPaths(0)which, per above if statement, will return 4.
func numberOfPaths(n int) int {
switch {
case n < 0: // base case
return 0
case n == 0 || n == 1: // also base case
return 1
default:
return numberOfPaths(n-1) + numberOfPaths(n-2) + numberOfPaths(n-3)
}
}Anagrams are a reordering of all chars within a string. ex: "abc", anagrams are "abc", "acb", "bac", "bca", "cab", "cba"
We could say that the subproblem of "abcd" is "abc". But how to use a func that gives us all anagrams of "abc"
to produce all of "abcd?".
func anagramsOf(str string) []string {
// Base case:
if len(str) == 1 {
return []string{string(str[0])}
}
var collection []string
substrAnagrams := anagramsOf(str[1:]) // Find all anagrams of the substring.
for _, subStrAnagram := range substrAnagrams { // Iterate over each substring.
for i := 0; i < len(subStrAnagram)+1; i++ { // Iterate over each index of the substring.
// Create a cpy of the substring, inserting the removed element once in each position
cpy := subStrAnagram[:i] + string(str[0]) + subStrAnagram[i:]
collection = append(collection, cpy)
}
}
return collection
}This introduces a new Big O Category. For three chars, a permutation starts with each of them, and each permutation picks
the middle char from one of the two remaining chars, and it's last char from the remaining chars. This is 3 * 2 * 1, 6 permutations.
For other string lengths:
4 Chars: 4 * 3 * 2 * 1 anagrams
5 Chars: 5 * 4 * 3 * 2 * 1 anagrams
6 Chars: 6 * 5 * 4 * 3 * 2 * 1 anagrams
This is a factorial pattern.
Given N data elements, how many steps does the algo take? For length of N, we create N! anagrams.
This is O(N!), aka factorial time. Very slow!
Dynamic programming is the process of optimizing recursive problems that have overlapping subproblems. There are two ways to do this:
Memoization and "going bottom up". First, we'll look at some inefficient recursive funcs.
Recursion can sometimes cause excess time complexity. Example of a poorly constructed recursive func:
O(2N)
// max finds the greates number from an arrayunc max(slice []int) int {
func maxInefficient(slice []int) int {
if len(slice) == 1 {
return slice[0]
}
// Compare first element with greatest element of the remainder slice.
if slice[0] > maxInefficient(slice[1:]) {
return slice[0]
}
return maxInefficient(slice[1:])
}Here, the recursive use of max in the if statement will cause an avalanche of recursive calls. Well break it down by analyzing the "bottom call".
Given an array [1, 2, 3, 4]:
max([4]) ---up-the-call-chain---> max(3, 4). Notice it again will call max([4]) twice because 3 is not greater than the result 4.
This get's even worse when we move further up the call chain. max([1, 2, 3, 4]) would call max a total of 15 times.
To fix this, we store the result to a variable, and call max only once.
O(N)
func max(slice []int) int {
if len(slice) == 1 {
return slice[0]
}
maxOfRemainder := max(slice[1:])
if slice[0] > maxOfRemainder {
return slice[0]
}
return maxOfRemainder
}Benchmarks:
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkMax-16 80621228 13.39 ns/op
BenchmarkMaxInefficient-16 5628093 212.1 ns/op
Fibonacci adds sequence of numbers until infinity: 0, 1, 2, 3, 5, 8, 13, 21, 34, 55...
Example of inefficient O(2N fibonacci recursion:
func fibInefficient(n int) int {
if n == 0 || n == 1 {
return n
}
return fibInefficient(n-2) + fibInefficient(n-1)
}Because we need to calculate both fib(n - 2) & fib(n - 1), we can't just store one of the values. This is an example
of a overlapping subproblem, because both fib(n - 2) & fib(n - 1) will call many of the same funcs as one another.
We can solve overlapping subproblems with Memoization.
Memoization reduces recursive calls by remembering previously computed functions.
We'll use this to store fib results in a hash table. fib(3) would get stored with the result: {3: 2}.
We do this by passing a hash table to the function.
O(2N)-1, or O(N)
// Because this is O(2N) - 1, we can set the size of the map we give:
// memo := make(map[int]int, 2*n-1)
func fibMemoization(n int, memo map[int]int) int {
if n == 0 || n == 1 {
return n
}
if _, recorded := memo[n]; !recorded {
memo[n] = fibMemoization(n-2, memo) + fibMemoization(n-1, memo)
}
return memo[n]
}NOTE: Using a closure is both more efficient and still allows input of a single integer. see code
This is simply ditching recursion and using a different approach(i.e. loop) to solve the problem. This is parts of dynamic
programming because it is still taking a problem that could be solved recursively, and ensures duplicate calls aren't
made for overlapping subproblems.
O(N)
func fibBottomUp(n int) int {
if n <= 1 {
return n
}
a, b := 0, 1
for i := 2; i <= n; i++ {
next := a + b
a = b
b = next
}
return b
}If you run benchmarks comparing these solutions, fibBottomUp is the clear winner, dramatically.
BenchmarkFibInefficient20-16 34086 34563 ns/op
BenchmarkFibMemoization20-16 976226 1028 ns/op
BenchmarkFib20-16 1000000 1107 ns/op
BenchmarkFibBottomUp20-16 100000000 11.48 ns/op
This demonstrates that bottom up is often better choice, unless recursion allows for more intuitive code and performance is not a factor.
Quicksort is an efficient sorting algorithm that many programming languages implement, it's very efficient for average scenarios and performs similarly to Insertion Sort and Selection sort in worse case scenarios. It relies on partitioning.
To take a random value from an array, called a pivot, every N < pivot is placed to the left of the pivot, and N > pivot
is placed to the right. Ex:
Given array [0, 5, 2, 1, 6, 3], we choose the rightmost value, 3 as the pivot. We assign two pointers, one to the leftmost value
and one to the rightmost value(excluding the pivot). 0 and 6 are the two pointers in this example.
- Left pointer moves right until a value >= pivot is reached.
- Right pointer moves left until a value <= pivot is reached.
- If left pointer has reached or gone beyond the right pointer, go to step 4. Otherwise, swap values that left & right pointers point to and repeat steps 1-3.
- Swap the pivot with the value that the left pointer is currently pointing too.
see partitioning.go
A combination of partitions and recursion. Conducts the following steps:
- Partition the array.
- Treat subarrays to left/right of the pivot as their own array & recursively repeat steps 1 & 2.
- If subarray has 0 or 1 elements, this is the basecase.
see partitioning.go
First, determine efficiency of a single partition:
A partition has two primary steps:
- Comparisons: compare each of the values to the pivot.
- At least N comparisons.
- Swaps: potentially swap values pointed to by left & right pointers
- Depends on how input data is sorted. At most N / 2 swaps per each partition.
- We don't always swap. Randomly sorted input data would bring about N / 4 swaps.
On average, this gives N comparisons and N / 4 swaps, about 1.25 steps per element. This is O(N) time.
This is only a single partition, and quicksort may perform many.
Quicksort has a series of partitions, and each partition takes N steps for N elements of each subarray.
For an array of 8 elements, quicksort takes about 21 steps.
| N | Quicksort steps (approx.) |
|---|---|
| 4 | 8 |
| 8 | 24 |
| 16 | 64 |
| 32 | 120 |
Looking above table, number of quicksort steps for N elements is about N * log N
| N | log N | n * log N | Quicksort Steps (approx.) |
|---|---|---|---|
| 4 | 2 | 8 | 8 |
| 8 | 3 | 24 | 24 |
| 16 | 4 | 64 | 64 |
| 32 | 5 | 160 | 160 |
This is O(N log N), because each time we partition an array, we break it down into two subarrays: there are log N
halvings, and each having has a partition on all subarrays whose elements add up to N.
NOTE: This is an approximation, as we must conduct O(N) partition on the original array as well.
Best case: when pivot ends up in the middle of the subarray after partition, which generally occurs when the array values
are adequately mixed.
The worst case is when the pivot always ends up on one side, ie if the input is already a perfectly sorted array.
O(N2) worst case time complexity.
| Best Case | Average Case | Worst Case | |
|---|---|---|---|
| Insertion Sort | O(N) | O(N2 | O(N2 |
| Quicksort | O(N log N) | O(N log N) | O(N2 |
Allows us to find certain values in an unsorted array, without sorting it. I.e.: finding the tenth-lowest value in an
array, or the fifth highest, etc.
Quickselect also uses partitioning. We can judge the location of the target value, based on the pivot index.
O(N) for average scenarios. For N elements, we need N + (N/2) + N/4) + (N/8) + ... 2 steps, which is roughly 2N steps.
see partitioning.go
Sorted arrays unlock possibilities to utilize other efficient algos. Ex: finding duplicates:
Linked lists are similar to arrays, but can be scattered throughout the computer's memory, via Nodes.
Each node contains some data and a link, the memory address of the next node in the list. A head and a tail are the first and last nodes in the list respectively.
Initially, only the head node of a linked list is available for immediate access. Linked lists have four classic operations: reading searching, insertion and deletion.
Requires following the chain of the nodes' links.
Worst case: O(N), must slower than array.
see linkedlist.go for implementation.
Also O(N) search speed, much slower than array. see linkedlist.go for implementation.
Here, linked lists have advantage over arrays in some situations.
O(1) for insertion at the beginning. Worst case of O(N)+1 to insert at end of list.
Create a new node, set it's next node to the current head, and change the linked list's head to the new node.
Insertion anywhere is just one step, but finding the node at a specific index is
see linkedlist.go for implementation.
Speeds are the same as insertion. Deleting merely requires changing a node's link to point to the node that exists
after the node targeted for deletion, or changing to nil if it's the tail.
Note that the 'deleted' node still exists in memory, until garbage collected by GC.
| Operation | Array | Linked List |
|---|---|---|
| Reading | O(1) | O(N) |
| Search | O(N) | O(N) |
| Insertion | O(N) or O(1) at end | O(N) or O(1) at beginning |
| Deletion | O(N) or O(1) at end | O(N) or O(1) at beginning |
The true power of a linked list is that the actual insertion and deletion steps are just O(1). They're highly suitable for situations when an app will comb through existing data, making insertions/deletions when needed. This is better than an array, which would have to move all the data around to fit in a contiguous memory block.
Have two links: pointing to both the node before and after. This allows O(1) insertion time for the beginning and end of the linked list.
This makes them highly suitable for a queue.
See doublyLinkedListQueue.go for implementation.
Binary search trees maintain ordering and have fast search, insertion, and deletion speeds.
A ndoe-based data structure, where each node can have links to multiple nodes. There are many kinds of tree-based data structures.
- Root: the uppermost node.
- Parent/children: The node immediately above/nodes immediately below.
- Descendants/ancestors: all the nodes above/below a given node.
- Levels: A row within a tree.
- A tree is balanced when it's nodes' subtrees have the same number of nodes in it, otherwise it is imbalanced.
Binary tree: a tree where each node has zero, one, or two children. Binary search tree: a binary tree that has the following additional conditions:
- Each node has at most one left child and one right child.
- A node's left descendants contains values less than the node itself, and its right descendants contain values only greater than itself.
see binarySearchTree.go for node implementation.
Searching within a binary search tree algorithm:
- Designate a node as "current node". (Initially, the root.)
- Inspect the value of current node.
- If found, return.
- If value is less than current node, search in its left subtree.
- if value is greater than current node, search in its right subtree.
- Repeat 1-5 until value is found or bottom of tree is reached, indicating the value isn't in the tree.
O(log N) Time Complexity in best-case scenario, for a perfectly balanced search tree.
👉Log(N) Levels If there are N nodes in a balanced binary tree, there will be about log N levels(rows).
Code implmentation: binarySearchTree.go
O(log N) + 1 steps
Insertion always takes 1 extra step beyond a search. In contrast, an ordered array takes O(N).
Code implmentation: binarySearchTree.go
Well-balanced trees are only created when input randomly sorted data. Sorted data can result in an imbalanced tree.
If it was completely-sorted, the tree would have all data on the right child, resulting in a completely linear O(N) search.
O(log N)
Deletion is the most complex operation of a binary search tree. The proper action depends on whether the node has a single, two, or no child nodes.
The complete algorith for deletion:
- If the node being deleted has no children, simply delete it.
- If the node being deleted has one child, delete the node and replace it with the child.
If the node ebing deleted has two children, replace the node with the successor node.
- The successor is the child node whose value is the least of all values that are greater than the deleted node.
- The find the successor: visit the right child of the deleted value, then keep visiting the left child of each subsequent child until there are no more left children. This bottom value is the successor node.
- If the successor node has a right child, after plugging the successor node into the deleted node's spot, take the former successor node's right child and turn it into the left child of the successor node's former parent.
Code implmentation: binarySearchTree.go
Traversing is the act of visiting every node in a data structure. There are many ways to traverse a tree,
we'll implement what is known as inorder traversal. The traverse method should have the following steps:
- Call itself recursively on the node's left child until there is no left child.
- "Visit" the node. Here, we'll print the title.
- Recursively call it's on the node's right child until there is no right child.
There are many types of tree data-structures, it's important to use the proper one for a given use case.
Priority queues are a list whose deletions and accesses are the same as a classic queue(front), but insertions work more
like an ordered array. Data remains in sorted order on insertions. (Think of a hospital room, where patients in more
critical condition will be seen first).
As an abstract data type, the underlying data structure is flexible. Using an array allows us to:
- Ensure proper ordering on inserts
- Data is removed from the end of the array(the 'front' of the array).
Two primary operations:
- Deletions; If data is array-based: O(1)
- Insertions; If data is array-based: O(N)
There is another, more efficient data structure for priority queues than a sorted array...
Many types, we'll focus on a binary heap, a kind of binary tree. Binary heaps also come in two varieties: max-heap & min-heap.
Examples here use a max-heap, but the implementing the other is a small difference.
Max-heaps have two conditions:
- Each node's value must be greater than each of its descendants, this is the heap condition.
- Contrast this is binary search tree, where the right child will be greater than the node. "A binary serach tree doth not a heap make."
- A min-heap would have the opposite condition: the node's value would be greater than all of its descendants.
- The tree must be complete, meaning if must be completely filled with nodes.
- The bottom row can have empty positions as no nodes are to the right of these empty positions.
- Heap-ordering is useless regarding searches, because we wouldn't know to look on the left or right of a node for a given value.
So, heaps are said to be weekly ordered, compared to binary search trees. They have some order(nodes greater than both children), but not enough to improve time-complexity of searching. - Root nodes in a max-heap will always have the greatest value (or the least, in a min-heap).
- Twp primary ops: inserting and deleting. Optional 'read' looks at value of root node.
- A last node is the heap's rightmost node in the bottom level.
Heap insertion involved the following algorithm: O(log N)
- Create new node with given value and insert it as the new last node. (see below)
- Compare the new node with its parent.
- If new node is greater than the parent, swap it with the parent.
- Repeat step 3, moving the node up the head until it's parent has a greater value, this process is called trickling.
The first step in the heap insertion algorithm requires that we find the last node. This is the "Problem of the Last Node" (see below)
Only the root node is ever deleted, just like a priority queue. Algorithm for heap deletions: O(log N)
- Remove the root node by moving the last node where the root node was.
- Trickle the root node down to its proper place. This is more complex than trickling up.
- Check both children of the "trickle node" to see which is larger.
- If trickle node is smaller than larger of the two child nodes, swap the trickle not with that larger node. (Otherwise, the heap condition would be violated)
- Repeat steps 1 & 2 until the trickle node has no children greater than it.
| Ordered Array | Heap | |
|---|---|---|
| Insertion | Slow | Very fast |
| Deletion | Extremely fast | Very fast |
| Even though the heap is slightly slower at deletions, it performs very well in all, so it's the better choice for priority queues. |
This addresses the problem of how we find the actual last node in a heap, for insertion & deletions. Using another node
would result in a heap that is incomplete. Completeness ensures that the heap remains well-balanced, and being well-balanced
is what helps us achieve O(log N) operations.
So, what algorithm helps us quickly find the last node of a heap? Well, we use arrays!
To solve the "Problem of the last node", heaps are usually implemented using arrays.
0
/ \
1 2
/ \ / \
3 4 5 6
The figure above demonstrates has the elements of an array can be represented as a heap.
With this implementation, the last node in the heap will always be the first element of the array, at index 0.
see heap.go for implementation.
Moving node-to-node would be simple with a linked list, how to do so with an array?
Assigning index's of the heap's nodes, as shown above, means the traits of a heap are always true:
- To find the left child, use this formula:
(index * 2) + 1 - To find the right child, use this formula:
(index * 2) + 2 - To find a node's parent, use this formula:
(index - 1) / 2Go ahead and try it out with the above example!
Heapsort is a sorting algorithm in which all values are inserted into the heap, and then popped out. A max-heap would
return values in descending order, and a min-heap would return values in ascending order.
This would give us a sort algorithm in O(N log N).
Tries: A type of tree, great for applications that deal with text/numbers, enabling features like autocorrect and autocomplete.
Name comes from the word retrieval, but is pronounced as "try". Tries aren't as well documented and have many implementations.
Unlike binary trees, trie nodes can have any amount of child nodes. We'll implement a trie nodes that contain a hash table, with English letter keys, and values that point to other nodes.
Ex: store three words: "ace", "bad", "cat" would create a node for each char in each word:
{"a": ptr "b": ptr "c": ptr}
/ | \
{"c": ptr} {"a": ptr} {"a": ptr}
| | |
{"e": ptr} {"d": ptr} {"t": ptr}
| | |
{"*": ptr} {"*": ptr} {"*": ptr}
The "*" indicates that there is a complete word that ends here. Adding the word "act" would look like:
{"a": ptr "b": ptr "c": ptr}
/ | \
{"c": ptr} {"a": ptr} {"a": ptr}
| |_________ |_________
| | |
{"e": ptr, "t": ptr} {"d": ptr} {"t": ptr}
| | | |
{"*": ptr} {"*": ptr} {"*": ptr} {"*": ptr}
If a word like "batter" was added, the node being pointed by the 't' in 'b-a-t' would look like: {"*": nil, "t": ptr}.
The classic trie operation. Two types:
- Determine whether the string is a complete word
- Determine whether the string is at least a a word prefix.(We implement this here).
The prefix-search algorithm uses the following algorithm:
- Declare a
currentNodevar, initally assigning the root node - Iterate over each char of the string
- Check if
currentNodehas a child with the same key as the current char - If not, return
nil - Otherwise, update the
currentNodeas that child. Repeat from step 2 - If the end of the string is reach, the search string has been found.
The algo takes as many steps as there are characters in the search string. However, it's not quite O(N), because N refers to the amount of data in the data structure (the number of nodes in the trie, which is usually much greater than the number of chars in the string.
O(K) is usually used to describe the time complexity of Tries. O(K) isn't constant: the string size can vary.
But, it has one important similarity to constant time: the trie itself can grow tremendously, but it won't affect the search speed.
In other words, a trie search on a string with 3 chars will always take three steps. Contrast this with non-constant algos, which are tied to the amount of data in the ds.
This means O(K) is extremely efficient.
Algo is similar to search:
- Declare a
currentNodevar, initally assigning the root node - Iterate over each char of the string
- Check if
currentNodehas a child with the same key as the current char - If so, update
currentNodeto become that child node & go back to step 2, moving on the next char. - Otherwise, create the child node with the char and update
currentNodeto point to this new node. - After inserting the final char, add a
"*"child to the last node.
Also O(K). Technically O(K+1), for the added "*" at the end.
This method will return an array of all the words in the trie, allowing us to start from any node in the trie. see trie.go
To display words that are more popular than others, a 'popularity rating' can be stored in the trie as well. In this implementation,
the "*" is perfect for this. Naturally, this would require refactoring of the acceptable value type in the underlying map.
Graphs are data structures that specialize in relationships, easily expressing how data is connected. Ex: In social networks, users are represented by nodes, with connecting lines representing a friendship.
Trees are a type of graph.
👉All trees are graphs, but not all graphs are trees.
A graph must not have cycles to be considered a tree, and all nodes must be connected.
A cycle is when nodes reference each other circularly.
Additionally, all nodes in a tree must be connected, but a graph allows nodes that may not be connected.
- Vertex: A node in a graph.
- Edges, aka vertices: The lines between nodes.
- Adjacent describes nodes that are connected to each other. Tese are known as neighbours.
- Path a specific sequence of edges from one vertex to another.
As a simple example, a hash map can be used to implement a simple graph. Here is one conveying a simpel social network:
friends := map[string][]string{
"Alice": []string{"Bob", "Diana", "Fred"},
"Bob": []string{"Alice", "Cynthia", "Diana"},
"Cynthia": []string{"Bob"},
"Diana": []string{"Alice", "Bob", "Fred"},
"Elise": []string{"Fred"},
"Fred": []string{"Alice", "Diana", "Elise"},
}A social network may allow non-mutual relationships: Alice can follow Bob, but Bob might not follow Alice.
--------ALICE-------
| |
v v
CYNTHIA -----------> BOB
^----------------|
Arrows indicate the direction of the relationship. Above, Alice follows Bob and Cynthia and no one follows Alice. Bob and Cynthia follow each other.
Expressed as a hashmap:
followees := make map[string][]string{
"Alice": []string{"Bob", "Cynthia"},
"Bob": []string{"Cynthia"},
"Cynthia": []string{"Bob"}
}
}see graph.go
Our implementation uses a slice to store neighbors. This is known as the adjacency list implementation.
Another implementation, known as adjacency matrix uses two-dimenstional arrays instead of a list.
We'll use a directed graph in our implementation. A directed graph would add vertex to a vertex's list of neighbors as so:
func (v *vertex) AddNeighbor(vertex vertex) {
v.neighbors = append(v.neighbors, vertex)
}Whereas an undirected implementation would mutually add a node to their respective list of neighbors:
// AddNeighborUndirected appends a given vertex to the calling vertex's list of neighbors.
func (v *vertex[T]) AddNeighborUndirected(vertex *vertex[T]) {
// Prevent an infinite loop.
for _, n := range v.neighbors {
if n == vertex {
return
}
}
v.neighbors = append(v.neighbors, vertex)
v.AddNeighborUndirected(v)
}Searching for a vertex is a common graph operation, and has more specific meaning.
👉 If we have access to one vertex in the graph, we must find another particular vertex that is somehow connected to this vertex.
This is so because there may be more than one path from one vertex to another.
Searching in graphs has many use-cases:
- Searching for a particular vertex within a connected graph. This can be done to find any vertex in the graph if we have access to just one vertex.
- Discovering whether two vertices are connected.
- To merely traverse the graph, alllowing use to perform an operation on every vertex.
Two well known approaches go graph searches: depth-first search & breadth-first search.
aka DFS. Very similar to Binary Tree Traversal algo.
🔑 Key to graph search algos is keeping track of which vertices have been visited so far. This is how we prevent endless cycles.
One way to do so is by using a hash table.
Algo:
- Start at any random vertex within the graph.
- Add current vertex to hash table, marked as visited.
- Iterate through the vertex's neighbors.
- Ignore neighbors that have been visited already.
- If the neighbor hasn't been visited, recursively perform a depth-first search on that vertex.
BFS doesn't use recursion, instead, it uses a queue.
Algo:
- Start from any vertex, the "starting vertex".
- Add it to the hash table, marked as visited.
- Add starting vertex to a queue.
- Start a loop that runs as long as the queue isn't empty.
- In the loop, remove the first vertex from the queue, the "current vertex".
- Iterate over all the neighbors of the current vertex.
- Ignore neighbors that have been visited already.
- If it hasn't been visited, mark it as visited and add it to the queue.
- Repeat loop (step 4) until queue is empty.
Breadth-first will go through all the calling vertex's immediate connections before spiralling out and moving
further from the caller. In contrast, depth-first immediately moves as far away as possible from the calling vertex
until being forced to return to it.
The correct choice depends on the usecase. Finding all direct connections would be perfect for breadth-first. Finding a specific
grandchild in a family tree would be served well with a depth-first search. Always ask:
Because we touch all vertices in the graph, the speed seems to be O(N), where N is the number of vertices.
But, we have to also iterate over all neighbors for each vertex that is traversed.
As an example: A graph has the following 5 vertices:
A, B, C, D, E. A has four neighbors, and the rest each have three. This would bring a total of 16 iterations + 5 visiting of each = 21 steps.
Another graph has 5 vertices: V, W, X, Y, Z. V has four neighbors, the rest have only one. This brings a total of 8 iterations + 5 visiting of each = 13 steps.
👉Determining the Big O requires that we count how many vertices are in the graph AND how many neighbors each vertex has. We'd
need two variables to describe the time complexity. This is O(V + E)
V: vertex, representing the number of vertices in the graph.
E: edge, the number of edges in the graph.
The number of steps is the number of vertices plus the number of edges. Each edge is actually touched twice, but because constants are dropped in Big O, V + 2E is simplified to O(V+E).
That said, the choice of BFS or DFS can help optimize searches in regard to the use case.
These add additional information to edges of the graph, a weight.
To use them in code, our neighbors array will be refactored to a hash table, with the key holding the vertex and the weight as the value.
Weighted graphs help when modeling many types of dataset problems. One of these is known as the Shorted Path Problem.
If we have a graph of cities with airplane ticket prices, how to create an algorithm that finds the cheapest price to get from one city to the next?
Here, the weight is a price, but it can also be a distance.
One of the most famous algos that can solve the shorted path problem, created by Edsger Dijjkstra in 1959. Using the airplane ticket price example below, we'll apply Dijkstra's algo to solve it. It has the added bonus of not only finding the cheapest price from our current city to destination city, but from our current city to all known cities.
Create a way to store chepest known prices from starting city to all other known destinations.
Cheapest Prices Table
| From ATL to: | City #1 | City #2 | City #3 | etc |
|---|---|---|---|---|
| $ | $ | $ | $ | |
We also need another table, the Cheapest Previous Stopover City Table |
| Cheapest Previous Sopover City from ATL | Boston | Chicago | Denver | El Paso |
|---|---|---|---|---|
| city | city | city | city |
Here, "city" is synonymous with "vertex".
- Visit starting city, making it the "current city".
- Check prices from current city to its neighbors.
- If price to a neighbor from starting city is cheaper than price currently in
cheapest prices table:- Update the
cheapest prices tableto reflect this cheaper price. - Update the
cheapest previous stopover city table, making the neighbor city the key and the current city its value.
- Update the
- Then visit the unvisited city that has the cheapest price from the starting city, making it the current city.
- Repeat steps 2 to 4 until every known city has been visited.
See pages 369-377 for a more detailed walk through of the algorithm.
Dijsktra's algo has many variations, as it's a general description of the approach to find the shortest path within a weighted graph.
(NOTE: Remember to implement use of a priority queue instead of a slice).
The initial implementation, using a slice, has a speed of O(V2).
Space constraints measure how much memory an algo consumes.
The key question in regards to space complexity:
🔑 If there are N data elements, how many units of memory will the algorithm consume?
Describing space complexity with Big O only counts new data that is being generated, aka auxiliary space.
Some references will include the original space being used, be aware of this. Here, we do not.
An example of an algo with space complexity O(N), because it generates an additional N data elements:
func makeUppercaseInefficient(words []string) []string {
newSlice := make([]string, len(words))
for i, word := range words {
newSlice[i] = strings.ToUpper(word)
}
return newSlice
}Let's make it more efficient and not consume additional memory with O(1):
func makeUppercase(words []string) []string {
for i, word := range words {
words[i] = strings.ToUpper(word)
}
return words
}Whether one of two algorithms is "more" efficient may depend on what matters to you most: time or space. Remember the func on line 49 that finds duplicate values:
Time Complexity: O(N2), Space Complexity: O(1)
func hasDuplicateValue(arr []int) bool {
for i := 0; i < len(arr); i++ {
for j := 0; j < len(arr); j++ {
if i != j && arr[i] == arr[j] {
return true
}
}
}
}and consider this version, which uses a hash map but is faster:
Time Complexity: O(N), Space Complexity: O(N)
func hasDuplicateValueFaster(arr []int) bool {
existingVals := make(map[int]bool, len(arr))
for _, v := range arr {
if !existingVals[v] {
existingVals[v] = true
} else {
return true
}
}
return false
}A third version, we've seen before, strikes a good balance between the two: Time Complexity: O(N log N), Space Complexity: O(log N)
func hasDuplicateValue[T constraints.Ordered](input []T) bool {
sort.Slice(input, func(i, j int) bool { return input[i] < input[j] })
for i := 0; i < len(input)-1; i++ {
if input[i] == input[i+1] {
return true
}
}
return false
}The Hidden Cost of Recursion
Even if our algo doesn't make new arrays or hash maps, it's possible we might be consuming more space, as recursive functions
keep adding to the call stack.
If each function takes up O(N) space, than a func that makes 100 recusive calls will need enough memory to store 100 func calls in the call stack.
👉 Recursive functions take up a unit of space for each recursive call it makes. Properly calculating this requires determining how large the call stack
would be at its peak.
As an example, quicksort make O(log N) recursive calls, so it has a call stack the size of log(N) at its peak.
The wordBuilder algo on line 155 has a Space Complexity of O(N2)
1️⃣ Before optimization begins: Determine the current efficiency of the code in question.
2️⃣ Come up with what you believe is the "best-imaginable" Big O, aka "best-conceivable runtime". This is the Big O you
know is absolutely impossible to beat.
3️⃣ If the best-imaginable is better than the current Big O, attempt optimization.
Remember: achieving the best imaginable Big O is not always possible.
Mental trick to think of best-imaginable Big O: "If someone said they know how to implement this amazing Big O for the problem, would I believe them?"
Ask: "If i could magically find the desired piece of data with O(1) time, would it make the algo faster?" If yes, then use a data-structure(ie hashmap) to make it happen.
Exercise: Write a func that accepts an array, returning true if any two numbers in th array add up to a given number.
O(N2
func twoSumInefficient(nums []int, target int) bool {
for i := 0; i < len(nums); i++ {
for j := 0; j < len(nums); j++ {
if i != j && nums[i]+nums[j] == target {
return true
}
}
}
return false
}Assume we give this func the input [2, 0, 4, 1, 7, 9] with a target 10. For the element at index 0, 2, the counterpart,
or the number that if added to 2 would equal the target is 8. Similarly, the counterpart to the second index,0 would be 10.
Therefore, we can calculate any number's counterpart by subtracting it from the target.
Now, we can implement an algo with better time complexity:
func twoSum[T numbers](nums []T, target T) bool {
numMap := make(map[T]struct{}, len(nums))
for _, num := range nums {
if _, ok := numMap[target-num]; ok {
return true
}
numMap[num] = struct{}{}
}
return false
}NOTE: Interesting, even though this has better Big O, benchmarks indicate that twoSumInefficient is actually faster.
Finding patterns within the problem at hand is a great strategy for code optimization/algorithm development.
Two players start with a pile of coins, each has the choice of removing one or two coins each turn. They play who removes the last coin loses.
Patterns:
If there's only one coin, the player whose turn it is loses.
If there are two coins left, the player whose turn it is can force a win.
If there are three coins remaining, the player whose turn it is can also force a win.
If there are four, the current player has a dilemma.
To write a function calculating whether we can win when presented with a coin pile of a certain size, we can use a top-down recursion approach.
see gameWinnerInefficient
Examples Examples help us detect a pattern:
| # of Coins | Winner |
|---|---|
| 1 | Them |
| 2 | You |
| 3 | You |
| 4 | Them |
| 5 | You |
| 6 | You |
| 7 | Them |
| 8 | You |
| 9 | You |
| 10 | Them |
Here, we see that starting with 1 coind, every third number gives victory to the opponent (assuming first play is you).
So, we can take the number of coins, subtract 1, and each "them" will end up on a number divisible by three, allowing us to simplify the algo to:
gameWinner
This example combines pattern recognition and magical lookups.
Write a function that accepts two int arrays. It should find one number from each array that can be swapped, allowing the
two array sums to be equal, returning the indices of the numbers or nil if it's not possible..
If we input [5, 3, 2, 9, 1] (sum of 20) and [1, 12, 5] (sum of 18), we'd need to switch 2 from the first and 1 from the second to get a sum of 19 from both.
A double-nested solution would give us speed of O(N * M).
We know we'll have to visit each number from the two arrays at least once. This would be O(N + M).
Let's find some patterns with examples:
| Before Swap | After Swap |
|---|---|
| arr1 = [5, 3, 3, 7] sum: 18 arr2 = [4, 1, 1, 6] sum: 12 |
arr1 = [5, 3, 3, 4], sum: 15 arr2 = [7, 1, 1, 6] sum: 15 |
| arr1 = [1, 2, 3, 4, 5] sum: 15 arr2 = [6, 7, 8] sum: 12 |
arr1 = [1, 2, 6, 4, 5], sum: 18 arr2 = [3, 7, 8] sum: 18 |
| arr1 = [10, 15, 20] sum: 45 arr2 = [5, 30] sum: 35 |
arr1 = [5, 5, 20], sum: 40 arr2 = [10, 30] sum: 40 |
- To achieve equal sums: the larger array needs to trade a larger number with a smaller number from the smaller array
- With a single swap, each array's sum changes by the same amount. (one array decreases by n, and the other increases by n)
- Swaps always cause the two array sums to fall exactly in the middle of where the two array sums begin.
Implementation:
- Determine how much an array sum needs to shift with this calculation:
shifteAmt := (sum1 - sum2) / 2 - Store numbers from one array in a hash table, and look it up as we iterate through the second.
see sumSwap
Greedy algorithms in each step, choose what appears to be the best option at that moment in time. Example:
func maxGreedy[T numbers](nums []T) T {
greatest := nums[0]
for _, num := range nums {
if num > greatest {
greatest = num
}
}
return greatest
}This is 'greedy' because it assumes the first number encountered so far is the greatest.
Write a function that takes an array of numbers, returning the largest sum that can be computed from any "subsection".
Here, a "subsection" represents a contiguous subsection, the numbers are in a row.
An inefficient approach, calculating every subsection, would take O(N2). We'll imagine O(N) and the best-imaginable speed.
We'll look for a positive trend in a given stock. Function takes an array of stock prices, and determines if there are
any three prices that create an upward trend.
Example: Given an array of stock prices: [22, 25, 21, 18, 19.6, 17, 16, 20.5], we can see that 18, 19.6, and 20.5 indicate an upward trend.
This could be done with three nested loops, but that doesn't scale well, and would be O(N3), very slow.
To apply a greedy mentality, we'll "grab" what is likely the lower point in a potential three-price upward trend:
- Assume the first price is the lowest point.
- For the middle price, initialize it to a number that is guaranteed to be greater than the highest stock price in the array, initially setting it to infinity.
- Run the algorithm:
- If current price is lower than lowest encountered price, this becomes the second-lowest price.
- If current price is higher than the lowest price, but lowers than the middle price, this becomes the new middle price.
- If current price is higher than the lowest and middle price, this becomes the new highest price.
See increasingTriplets for implementation.
Another optimization technique is to use a different data structure.
Write a func that compares two strings side by side, determining if they're an anagram of one another or not. If we used the anagramsOf function, but this would bring a O(N!) time. See xtraOptimizationTechniques.go for optimizations.
Assuming an array contains several different values, and we want to reorder the data so that the same values are grouped
together. ex: an array ["a", "c", "d", "b", "b", "c", "a", "d", "c", "b", "a", "d"], we want to sort it so it becomes
["c", "c", "c", "a", "a", "a", "d", "d", "d", "b", "b", "b"].
Fasted sorting algo take O(N log N), but we'll aim for O(N).