Skip to main content

Code Reference

Approaches to Computational Problem Solving​

Dynamic Programming​

Breaking a problem into smaller problems.

Memoization​

By storing information about the decisions made so that you do not recompute decisions. This technique is known as memoization.

The problem must have an optimal substructure. This means the optimal solution is constructed from the optimal solution of it's sub-problems.

These include:

  • Recursive top-down (caching)
  • Iterative bottom-up (tabulation, solution table)

Greedy​

A greedy approach makes locally optimal decisions without knowing about future decisions or remembering previous ones. It will often not be able to find the optimal solution but one which works in an efficient time and memory complexity.

1. Math Algorithms​

Greatest Common Divisor​

Finding the greatest common divisor of two integers.

Implementation​

Go Lang​

Useful breakdown of the Euclidean method

Using the Euclidean method.

  1. Check that the two numbers do not divide with a modulo of 0.
  2. If they do then the smaller number is the GCD.
  3. If not then the new values to check are the smaller number modulo the last remainder.
  4. If the result is zero then the last remainder is the GCD.
  5. If not then repeat steps 3 and 4 until the remainder is 0.
Complexity​

A nice breakdown by GeeksForGeeks of the complexity of the Euclidean GDC algorithm.

Time: O(Logmin(a,b))O(Log min(a, b))

Memory: O(Log(min(a,b)))O(Log (min(a,b)))

Annotated​
// Find the gdc of two integers
// 
// In: 2 x integers
// Out: integer which represents the greatest common divisor
// 
func gdc(a, b int) int {
    // Keep going until we meet 0, if there is no gdc
    for b != 0 {
        // store b as t
        t := b
        // check the remainder of the two numbers
        b = a % b
        // move b to a via t
        a = t
    }
    return a
}
Unannotated​
func gdc(a, b int) int {
    for b != 0 {
        t := b
        b = a % b
        a = t
    }
    return a
}

2. Sorting, Manipulation Algorithms​

Bubble Sort​

This algorithm moves through an array flipping two adjacent elements if they are in the wrong order

Implementation​

Go Lang​

Recursive implementation of a bubble sort algorithm in Go. It sorts in non-decreasing order.

This function takes in an integer array and an integer as parameters and returns a sorted array. If the array is sorted then the functions returns the array. This is the base case. If there is an element which is larger then the following element then the function is called with a new array whereby the elements found to be out of order are flipped.

Complexity​

Useful breakdown of the time and space complexity of bubble sort by GeeksForGeeks

Time: (Best) O(n)O(n) time efficiency is n i.e. the input array is already sorted. It takes one iteration of the input array to determine if the array is sorted.

Time: (Worst) O(n2)O(n^2) If the elements of the array are arranged in decreasing order then the function will call itself recursively for each element of the array, swapping two elements at a time.

Memory: O(1)O(1) Constant

Annotated​
// Recursive function for sorting integer arrays into non-decreasing order
// 
// In: array of integers
// Out: array of sorted (non-decreasing) integers
// 
func bubbleSort(nums []int) []int 
    // this is retained as true only when the whole array is in the correct order
    var sorted bool = true

    for i := 0; i < len(nums)-1; i++ {
        var elem int = nums[i]
        var nextElem int = nums[i+1]

        // if the first and next elements are not non-decreasing then the array is not sorted
        // flip the elements into the correct order
        if elem > nextElem {
            sorted = false
            nums[i] = nextElem
            nums[i+1] = elem
        }
    }

    // the array is sorted up to the point we flipped the two variables above
    // pass the partially sorted array into the function again to check the array again
    if !sorted {
        bubbleSort(nums)
    }

    // if it's iterated through the whole array then we have a sorted array
    return nums
Unannotated​
func bubbleSort(nums []int) []int {
    var sorted bool = true

    for i := 0; i < len(nums)-1; i++ {
        var elem int = nums[i]
        var nextElem int = nums[i+1]

        if elem > nextElem {
            sorted = false
            nums[i] = nextElem
            nums[i+1] = elem
        }
    }

    if !sorted {
        bubbleSort(nums)
    }

    return nums
}

Counting Sort (non-comparison)​

Counting sort is useful algorithm which does not rely on comparison. It counts up the frequency of each element value and then sorts based on this.

This kind of algorithm is useful for sorting input arrays where the values are small compared to the number of elements that need to be sorted.

[1, 5, 2, 6, 4] // this is the kind of array which will work well with counting sort
[100, 256, 632, 94, 87] // this will not work well because m (the count array) will be max of the values in this array

The instructions used to create a counting sort algorithm

  1. Find the max value from the input array.
  2. Create a new count array which is the length of the max value found above. Set all elements to 0.
  3. Then iterate through the input array and increment the output array by one at the index of the value of the input array.
  4. We should now have an array which counts the frequency of the values.
  5. From the end of the array add the total of all the previous element values to the current element.
  6. Create an output array.
  7. Iterate through the input array and use the value as the index of the count array, the value of the element at that index is the index of the input array value in the output array.
  8. Take one from the value of the count array element which corresponded in the previous step.
  9. Keep iterating and you should produce a sorted array.

Implementation​

Go Lang​

This implementation is standard.

Complexity​

Time: O(n+m)O(n+m) Iteration through the input array and the new array is required.

Memory: O(n+m)O(n+m) Creation of the new count array makes this linear time.

Annotated​
// Short description of algorithm
// 
// In: array of integers
// Out: sorted (non-decreasing order) array
// 
func countingSort(inputArray []int) []int {
    // Declare an auxiliary array countArray[] of size max(inputArray[])+1 and initialize it with 0.
    var countArray = make([]int, max(inputArray)+1)

    // Traverse array inputArray[] and map each element of inputArray[] as an index of countArray[] array, i.e., execute countArray[inputArray[i]]++ for 0 <= i < N.
    for i := 0; i < len(inputArray); i++ {
        countArray[inputArray[i]]++
    }

    // Calculate the prefix sum at every index of array inputArray[].
    for i := 1; i < len(countArray); i++ {
        countArray[i] += countArray[i-1]
    }

    // Create an array outputArray[] of size N.
    var outputArray = make([]int, len(inputArray))

    // Traverse array inputArray[] from end and update outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i]. Also, update countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .
    for i := len(inputArray) - 1; i >= 0; i-- {
        outputArray[countArray[inputArray[i]]-1] = inputArray[i]
        countArray[inputArray[i]]--
    }

    return outputArray
}
Unnanotated​
func countingSort(inputArray []int) []int {
    var countArray = make([]int, max(inputArray)+1)

    for i := 0; i < len(inputArray); i++ {
        countArray[inputArray[i]]++
    }

    for i := 1; i < len(countArray); i++ {
        countArray[i] += countArray[i-1]
    }

    var outputArray = make([]int, len(inputArray))

    for i := len(inputArray) - 1; i >= 0; i-- {
        outputArray[countArray[inputArray[i]]-1] = inputArray[i]
        countArray[inputArray[i]]--
    }

    return outputArray
}

3. General, Manipulation Algorithms​

Removing elements from an array which match a given value​

Remove all elements from array using the array in-place to store the final array.

Implementation​

Go Lang​
Complexity​

Time: O(n)O(n) will always iterate through all elements of the input array nums.

Memory: O(1)O(1) Constant

Annotated​
// Remove all elements of an array which match a value
// really we are omitting any matches from being assigned to the array rather than removing them
// 
// In: array of integers
// In: int (value to "remove")
// Out: an array which is free from elements matching the input value "val"
// 
func removeElement(nums []int, val int) int {
    // track the last position in the nums array we have reassigned
    var k int = 0

    for i := 0; i < len(nums); i++ {
        var e = nums[i]
        if e != val {
            // the value is not a match so add it to the array
            nums[k] = e
            // a reassignment has been made so increment the k value
            k++
        }
    }

    return k
}
Unnanotated​
func removeElement(nums []int, val int) int {
    var k int = 0
    var l int = 0

    for i := 0; i < len(nums); i++ {
        var e = nums[i]
        if e != val {
            nums[l] = e
            l++
            k++
        }
    }

    return k
}

Removing All Duplicates From Sorted Array​

This algorithm only accepts non-decreasing sorted arrays. It reuses the input array to assign values which are non-duplicate.

Implementation​

Go Lang​
Complexity​

Time: O(n)O(n) will always iterate through all elements of the input array nums.

Memory: O(1)O(1) Constant

Annotated​
// Iterate through an input array and return the same array where the first k elements are the original array without any duplicates.
// 
// In: array of integers
// Out: array of integers without duplicates (after the processed elements in the array it will contain elements which are residual from the algorithm)
// 
func removeDuplicates(nums []int) int {
    // k tracks the sorted elements total
    // it is 0 indexed, the first element is never a duplicate
    var k int = 1
    var s int = nums[0]

    for i := 1; i < len(nums); i++ {
        var e = nums[i]
        // if the current element is not equal to the previous one, then we have a non-duplicate
        // assign the current element to the first element in the array which has not yet been reassigned
        if e != s {
            nums[k] = e
            // increment our k counter so that the next assignment doesn't overwrite previous work
            k++
        }
        s = e
    }

    return k
}
Unnanotated​
func removeDuplicates(nums []int) int {
    var k int = 1
    var s int = nums[0]

    for i := 1; i < len(nums); i++ {
        var e = nums[i]
        if e != s {
            nums[k] = e
            k++
        }
        s = e
    }

    return k
}

Removing Some Duplicates From Sorted Array​

This algorithm only accepts non-decreasing sorted arrays. It reuses the input array to assign values which are non-duplicate. This function contains a lookback. Only if the lookback is non-duplicate will the element be removed. Because of this we can retain x duplicates in the array.

Implementation​

Go Lang​
Complexity​

Time: O(n)O(n) will always iterate through all elements of the input array nums.

Memory: O(1)O(1) Constant

Annotated​
// inspired by: db96's answer titled: O(1) Space, look back 2 and no counter - very fast!

// Iterate through an input array and return the same array where the first k elements are the original array without any duplicates.
// 
// In: array of integers
// Out: array of integers without duplicates (after the processed elements in the array it will contain elements which are residual from the algorithm)
// 
func removeDuplicates(nums []int) int {
    var nl = len(nums)

    if nl == 1 {
        return 1
    }

    var k int = 2

    for i := 2; i < nl; i++ {
        var c int = nums[i]
        var km1 int = nums[k-1]
        // this is the crux of it
        // we assign as an allowed duplicate or non-duplicate with a look behind
        // the element is both not equal the last element in the assigned portion of the array
        // and also the element before that
        if nums[i] != km1 || km1 != nums[k-2] {
            nums[k] = c
            k++
        }
    }

    return k
}
Unnanotated​
// inspired by: db96's answer titled: O(1) Space, look back 2 and no counter - very fast!

func removeDuplicates(nums []int) int {
    var nl = len(nums)

    if nl == 1 {
        return 1
    }

    var k int = 2

    for i := 2; i < nl; i++ {
        var c int = nums[i]
        var km1 int = nums[k-1]
        if nums[i] != km1 || km1 != nums[k-2] {
            nums[k] = c
            k++
        }
    }

    return k
}

Rotate array elements​

There are two ways which are memory and time efficient.

Implementation (Juggle Algorithm)​

This method involves splitting the input array into the gdc of the array and the positions of rotation. Then each index of each set is rotated.

Go Lang​

Complexity​

Time: O(n)O(n)

Memory: O(1)O(1) Constant as we perform changes in place.

Unannotated​
// Rotate the input array by a number of places to the right
// 
// In: the original array
// Out: the number of positions of rotation (to the right)
// 
func rotate(nums []int, k int) {
    var l int = len(nums)

    k = k % l
    k = l - k // we are left rotating which is equal to right rotation of k = k - n

    // this is the number by which we split the array into subsets
    var cycles int = gdc(l, k)

    // for each cycle which is the number of subsets
    for i := 0; i < cycles; i++ {
        // store the first value as we will overwrite it with the following loop
        var start_e int = nums[i]
        var cur_i int = i

        for true {
            // move through each subset by the same index of each
            var next_i int = (cur_i + k) % l

            // if the next index is the first element of the cycle we have looped so exit
            if next_i == i {
                break
            }

            // assign the current index value to the next subset
            nums[cur_i] = nums[next_i]
            // keep track of where we are by writing our next index
            cur_i = next_i
        }
        // once we have broken from the loop assign the stored element to the current index
        nums[cur_i] = start_e
    }
}
Annotated​
func rotate(nums []int, k int) {
    var l int = len(nums)

    k = k % l
    k = l - k // we are left rotating which is equal to right rotation of k = k - n

    var cycles int = gdc(l, k)

    for i := 0; i < cycles; i++ {
        var start_e int = nums[i]
        var cur_i int = i

        for true {
            var next_i int = (cur_i + k) % l

            if next_i == i {
                break
            }

            nums[cur_i] = nums[next_i]
            cur_i = next_i
        }
        nums[cur_i] = start_e
    }
}

Implementation (Partial Reverse Algorithm)​

It tripped me up for a while trying to work out why this method is O(n) because I assumed that reverse was iterating through each slice of the array equal to the size of the slice. But it's doing half as many iterations as there are array elements. so subset reversals use O(n/2) and the reverse on the whole array uses O(n/2), together they are O(n). I believe this is the correct understanding.

To left rotate we flip the order of the reversals.

Go Lang​

Complexity​

Time: O(n)O(n) Each reversal of the whole array is half of n. There are in total two whole reverals of the array, so it's n for the time complexity.

Memory: O(1)O(1) Constant as we perform changes in place.

Unannotated​
// Move the input array 
// 
// In: the original array
// Out: the number of positions of rotation (to the right)
// 
func rotate(nums []int, k int) {
    // return if we don't have any rotations to do
    if k == 0 {
        return
    }

    var l int = len(nums)
    // we don't need to rotate more than the total length of the array
    // only rotate the remainder
    k = k % l 

    // reverse the whole array
    reverse(nums, 0, l-1)
    // reverse the start of the array up to the index which is the number of rotations
    reverse(nums, 0, k-1)
    // reverse the rest of the array after the index of the number of rotations
    reverse(nums, k, l-1)
}
Annotated​
func rotate(nums []int, k int) {
    if k == 0 {
        return
    }

    var l int = len(nums)
    k = k % l

    reverse(nums, 0, l-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, l-1)
}

Reverse array elements​

Simply take an array and return the reverse of the array.

Implementation​

This implementation is nice as it take s

Go Lang​

Complexity​

Time: O(n/2)O(n/2) The number of operations is the floor of n/2.

Memory: O(1)O(1) No extra memory is used if the assignments are performed on the array in place.

Unannotated​
// Reverse a slice of the input array
// 
// In: input array
// In: two integers representing the start and end position of the slice being reversed
// Out: a reversed array
// 
func reverse(nums []int, s int, e int) {
    // whilst the start is less than the end we perform swaps
    for s < e {
        // swap elements from outside inwards
        nums[s], nums[e] = nums[e], nums[s]
        // increment the start and end position moving our way inwards
        s++
        e--
    }
}
Annotated​
func reverse(nums []int, s int, e int) {
    for s < e {
        nums[s], nums[e] = nums[e], nums[s]
        s++
        e--
    }
}

4. Analysis Algorithms​

Boyer–Moore majority vote algorithm​

This is specifically useful for finding majorities, where there IS a majority in the array. If there is not majority the algorithm will not find anything.

As the array is traversed we have a counter. If that counter if the counter is above zero then we have more than one of that vote. If another element has another value that counter is decremented. If the decrement gets to 0 then the presumed majority vote is switched to the current element.

Because we only traverse the elements once it's complexity in time is low and we do not need to store any information about all of the elements so the space complexity is low aswell.

This algorithm is awesome. So clean and simple and efficient. But is very specific.

Implementation​

Go Lang​
Complexity​

Time: O(n)O(n) will always iterate through all elements of the input array nums.

Memory: O(1)O(1) Constant

Annotated​
// Using the Boyer-Moore majority voting algorithm
// 
// In: array of integers
// Out: the value of the majority vote
// 
func majorityElement(nums []int) int {
    var n int = len(nums)

    // no need to process an array of length 1 it's always going to be first element
    if n == 1 {
        return nums[0]
    }

    // this is our tracker for guesses, start with the first element
    var av int = nums[0] 
    // this is out voting, the first element exists so it's got a single vote
    var ao int = 1

    // look through the rest of the elements
    for i := 1; i < len(nums); i++ {
        if nums[i] == av {
            // get's another vote because it's come up again
            ao++
        } else {
            // reduces the vote because another vote is in the array
            ao--
            if ao == 0 {
                // too many down votes we no longer think that the guess is good
                // update the guess to be the current element
                av = nums[i]
                ao = 1
            }
        }
    }

    return av
}
Unnanotated​
func majorityElement(nums []int) int {
    var n int = len(nums)

    if n == 1 {
        return nums[0]
    }

    var av int = nums[0]
    var ao int = 1

    for i := 1; i < len(nums); i++ {
        if nums[i] == av {
            ao++
        } else {
            ao--
            if ao == 0 {
                av = nums[i]
                ao = 1
            }
        }
    }

    return av
}

Two-pointer example (finding best stock trades)​

Two pointers is a more general technique where you have two pointers which are placed somewhere along an array. These two pointers are compared and if by some criteria they are found to be correct, then they are returned, if not the values they point to are changed in some way.

Implementation​

Go Lang​

This implementation is made to find the maximum profit from an array which represents prices as the values and the index as days.

Complexity​

Time: O(n)O(n) will always iterate through all elements of the input array nums.

Memory: O(1)O(1) Constant, you only need two pointers and maybe more for the problems specific needs.

Annotated​
// Using the Boyer-Moore majority voting algorithm
// 
// In: array of integers (prices)
// Out: the value of the maximum profit
// 
func maxProfit(prices []int) int {
    if len(prices) <= 1 {
        return 0
    }

    // these are out so called two points
    var left int = 0
    var right int = 1

    // to track the profit which we will return
    var profit_max int = 0

    // iterate through the whole array - 1 because each iteration we look forward one element
    for i := 0; i < len(prices)-1; i++ {
        // if the left price is smaller than the right this is a buy sell strategy
        // you cannot sell stocks in the past before you buy them
        if prices[left] < prices[right] {
            // get the current profit of the current pointers
            var profit int = prices[right] - prices[left]
            // if the profit is bigger than our current max then store it 
            if profit > profit_max {
                profit_max = profit
            }
        } else {
            // the left price is not smaller than the right so we bring the left value up to the right
            left = right
        }
        right += 1
    }

    return profit_max
}
Unnanotated​
func maxProfit(prices []int) int {
    if len(prices) <= 1 {
        return 0
    }

    var left int = 0
    var right int = 1
    var profit_max int = 0

    for i := 0; i < len(prices)-1; i++ {
        if prices[left] < prices[right] {
            var profit int = prices[right] - prices[left]
            if profit > profit_max {
                profit_max = profit
            }
        } else {
            left = right
        }
        right += 1
    }

    return profit_max
}

Greedy Algorithms​

Greedy algorithms are simple. They aim to find a possible answer to a problem and keep doing so one decision after another until the problem is solved. It does not find the optimal solution to problems.

You have a global optimum, which is the answer or desired outcome. Then at each iteration the algorithm makes a decision based on what it thinks is the best local choice. It does not make this choice based on the current information for the choice. It does not make assumptions of future choices or reflect on previous ones.

Implementation​

Go Lang​

This implementation is for the Leecode problem 55 Jump Game. It walks backwards through an array and tries to find a possible path left to right but going from the end. It is greedy because it does not change previous decisions based on new information or predict decisions in the future based on what has happened. It returns a boolean based on if it thinks there is a path, no information about what possible paths there are will be made available.

Complexity​

Time: O(n)O(n) Once through the input array.

Memory: O(1)O(1) Takes no extra memory.

Annotated​
// Short description of algorithm
// 
// In: 
// Out: 
// 
func canJump(nums []int) bool {
    // we can say that a path exists if there is only the final
    if len(nums) == 1 {
        return true
    }

    // only track how many steps are needed between the last position and the next element
    var needs int = 1
    // start from the end of the array and one element in
    for i := len(nums) - 2; i >= 0; i-- {
        // if the value of the current element satisfies the needed steps then
        // we still only need 1 step
        if nums[i] >= needs {
            needs = 1
        } else {
            // if the value doesn't satisfy then we need to increase the step size
            needs++
        }
    }

    // if the final step is greater than what we need the path is possible
    return nums[0] >= needs
}
Unnanotated​
func canJump(nums []int) bool {
    if len(nums) == 1 {
        return true
    }

    var needs int = 1
    for i := len(nums) - 2; i >= 0; i-- {
        if nums[i] >= needs {
            needs = 1
        } else {
            needs++
        }
    }

    return nums[0] >= needs
}

5. Data Structures​

GetRandom - Hashmap to track indexes of list values​

This data structure was used to solve the GetRandom number from list with O(n) constant time.

A hashmap is used to keep track of the index of each value in a list and the stored as the value. The hashmap keys are the element values themselves.

The list is used to have a set of values from which we can pull a random index.

Deletion happens by swapping the the element you want to delete with the last element in the list and pop'ing the end of the list in O(1) time. You also need to update the hashmap to respect the current state of the list.

Insertion happens easily by putting the info in the hashmap and adding the new value to the end of the list.

Implementation​

Go Lang​
Complexity​

Time: O(1)O(1)

Memory: O(n)O(n)

Unnanotated​

Data Structure is a list which can change size and a hashmap which maps the values within the array to their indices.

type RandomizedSet struct {
    set map[int]int
    num []int
}

func Constructor() RandomizedSet {
    return RandomizedSet{
        set: make(map[int]int),
        num: make([]int, 0),
    }
}

func (this *RandomizedSet) Insert(val int) bool {
    _, ok := this.set[val]
    if !ok {
        this.set[val] = len(this.num)
        this.num = append(this.num, val)
        return true
    }
    return false
}

func (this *RandomizedSet) Remove(val int) bool {
    idx_val, ok := this.set[val]
    if ok {
        var lnum int = len(this.num)
        if idx_val != lnum-1 {
            this.num[idx_val], this.num[lnum-1] = this.num[lnum-1], this.num[idx_val]
            this.set[this.num[idx_val]] = idx_val
        }
        this.num = this.num[:lnum-1]
        delete(this.set, val)
        return true
    }
    return false
}

func (this *RandomizedSet) GetRandom() int {
    return this.num[rand.Intn(len(this.num))]
}

Title Example​

A general description of the algo + more detailed explanations in further paragraphs.

Implementation​

Go Lang​

What makes this implementation different?

Complexity​

Time: O()O()

Memory: O()O()

Annotated​
// Short description of algorithm
// 
// In: 
// Out: 
//

Unnanotated​