Preface

This is my own curated list of tips and tricks about data structures and algorithms, in Python or TypeScript.

Checklist

If you are able to bring up complexities amd implementations in mind just by looking at each topic, you are in a good shape.

Big-O and its friends

Big O cheatsheet

Everything is from bigocheatsheet.com. It’s just that I don’t visit it as often as my blog.

Mathematical definition of Big-O

$f(x) = O(g(x))$ if there exists $c$ and $k$ where $0 <= f(x) <= c * g(x)$ for some $k <= x$

Intuitive definition of Big-O

• Worst time complexity of an algorithm. Denotes an upper boundary.
• How fast a program’s runtime grows asymptotically when the size of the input increases towards infinity

Mathematical definition of Big-Omega

$f(x) = Ω(g(x))$ if there exists $c$ and $k$ where $0 <= c * g(x) <= f(x)$ for all $k <= x$

Intuitive definition of Big-Omega

Best time complexity of an algorithm. Denotes a lower boundary.

Mathematical definition of Big-Theta

$f(x) = \Omega{(g(x))}\space \text{and}\space f(x) = O(g(x)) \Rightarrow \Theta{(g(x))}$

In other words,

$c_{1} * g(x) <= f(x) <= c_{2} * g(x)$

Intuitive definition of Big-Theta

It must be the case that $f(x)$ is essentially the same function as $g(x)$ if the constants on each function are removed, if any.

Big-O computations

• If $f(x)$ is a sum of several terms, the term of the largest growth rate can be left without others because we only care about the biggest term}|
  • example: $f(x) = O(nlogn) + O(n) = O(nlogn)$
• If $f(x)$ is a product of several factors, any constants C terms in the product that do not depend on $x$ can be omitted.
  • example: $f(x) = O(5nlogn) = O(nlogn)$
• Proving Big-O often requires choosing an arbitrary $c$ and $k$:
  • example: show that $O(f(x)) = O(x^4) \space \text{where} \space f(x) = 6x^4-2x^3+5$
  • proof: $|6x^4 - 2x^3 + 5| \leq 6x^4 + 2x^4 + 5x^4 = 13x^4 \Rightarrow f(x) = O(x^4) \text{ given } c = 13 \text{ for all } 0 \leq k = 1 \leq x$

Review of exponents

Rule of power

• Rule: $(b^x)^y = b^{xy}$
• Example: $(2^3)^3 = 2^6$

Multiplying exponents

• Rule: $(b^x)(b^y) = b^{x+y}$
• Example: $(2^3)(2^3) = 2^5$

Dividing exponents

• Rule: $\frac{b^x}{b^y} = b^{x-y}$
• Example: $\frac{2^5}{2^2} = 2^3$

Rule Taking the power of two multiplied terms

• Rule: $(a * b)^x = a^{x} * b^{x}$
• Example: $(2 * 3)^3 = 216 = 2^3(3^3) = 8 * 27 = 216$

Review of Logarithms

Relationship between the logarithm and the exponent function

The logarithm is the inverse of the exponent function.

$log_{a}{b} = x \Leftrightarrow a^x = b$

example:

$log_{2}{8} = 3 \Leftrightarrow 2^3 = 8$

Log of a product

• Rule: $log_{b}{(x \times y)} = log_{b}{x} + log_{b}{y}$
• Example: $log_{2}{(4 \times 8)} = log_{2}{32} = 5 = log_{2}{4} + log_{2}{8} = 2 + 3$
• Reasoning: $(b^x)(b^y) = b^{x+y}$

Log of a fraction

• Rule: $log_{b}{\frac{x}{y}} = log_{b}{x} - log_{b}{y}$
• Example: $log_{2}{\frac{32}{4}} = log_{2}{8} = 3 = log_{2}{32} - log_{2}{4} = 5 - 2 = 3$
• Reasoning: $\frac{b^x}{b^y} = b^{x-y}$

Log of a power

• Rule: $log_{b}{x^y} = y \times log_{b}{x}$
• Example: $log_{2}{4} = 2$
• Reasoning: $(b^c)^d = b^{cd}$

A power of a log

• Rule: $x^{log_{b}{y}} = y^{log_{b}{x}}$
• Example: $4^{log_{2}{8}} = 4^3 = 4 \times 4 \times 4 = 8 \times 8 = 8^2 = 8^{log_{2}{4}}$
• Reason: $x^{log_{b}{y}} = b^{(log_{b}{x})(log_{b}{y})}$

Change of a base

• Rule: $log_{b}{x} = \frac{log_{d}{x}}{log_{d}{b}}$
• Example: $log_{4}{64} = 3 = \frac{log_{2}{64}}{log_{2}{4}} = \frac{6}{2} = 3$

Amortized analysis

Amortized analysis is a worst-case analysis of a a sequence of operations to obtain a tighter bound on the overall or average cost per operation in the sequence than is obtained by separately analyzing each operation in the sequence.

There are two prominent examples:

• Amortized $O(1)$ of array.append()
• Amortized $O(1)$ of dict[key]

Arrays

• An array can work as a replacement for hash tables if you know the range of indices that will go into the array. But sometimes it will waste spaces.
• otherwise, do use hash tables because they have O(1) amortized time complexity.
• append() or push() for arrays and strings takes O(1) amortized time. It means that on average it will take O(1) for insertion if you keep adding new elements. This is because it takes O(1) time for simple insertions with no capacity increase, but it will take O(n/2) time for insertions with capacity increase, where n is the size of next array (because usually arrays double the capacity). The insertion with capacity increase only comes when you reach n/2 elements. This is why on average the insertion would take O(1) time.

Useful code snippets

Initialize an empty array of length 10 full of 0’s:

const arr = Array(100).fill(0)

arr = [0] * 10

Be careful when you are creating a 2D array in Python:

doesnt_work_arr = [[0] * 10] * 10 # doesn't work
2d_arr = [[0] * 10 for _ in range(10)] # works

Creating an array of certain range of contiguous characters:

count = [0] * (ord("z") - ord("a") + 1)

# access the index corresponding to "c" (should be 2nd index)
count[ord("c") - ord("a")]

Remember that uppercase letters come first in the ASCII order (and there are some special characters in between "Z" and "a")

>>> ord("A")
65
>>> ord("Z")
90
>>> ord("a")
97
>>> ord("z")
122

Why an arraylist has $O(1)$ armortized insertion time

Basic idea

• An arraylist has:
  • $length$: the actual number of elements in the list
  • $capacity$: the size of the memory allocated for the list (always bigger than or equal to $length$)
• Appending an element to an list while its length is less than or equal to the $capacity$ is an apparent $O(1)$
• When the $capacity$ is full, $length$ (= $capacity$) elements need to be copied over to a brand new list, which is not $O(1)$

The cost of resizing

• Usually, the list will need to double in its $capacity$ (powers of 2). Therefore, list increases its $capacity$ only when $length = 2^k$ for some integer $k > 0$ (you need to resize at $2, 4, 8, 16, ...$).
• Total number of times for resizing $capacity$ is $floor(log_2(n))$. At certain $length$, the list would have been resized for $floor(log_2(n))$ times. For example, if your $length$ is $34$, that means is the list would have been resized for $floor(log_2(34)) = 5$ times.
• The total (accumulated) cost of resizing at $length$: $1 + 2 + 4 + 8 + ... + 2^{floor(log_2(length))}$
• We know $\sum_{i=0}^{k}2^k = 2^{k + 1} - 1$. For example, $k = 4 \Rightarrow \sum_{i=0}^{k}2^k = 1 + 2 + 4 + 8 + 16 = 31 = 2^{k + 1} - 1$
• Therefore, the total accumulated cost of resizing at $length$ = $2^{floor(log_2(length)) + 1} - 1 = 2^{k + 1} - 1$ where $k$ is the number of times of resizing.

The cost of $O(1)$ ops

• Up to a certain $k = 2^{floor(log_2(length))}$, the accumulative cost of $O(1)$ operations is $2^k - k + 1$. For exmaple, let $k = 5 \Rightarrow 2^5 - 5 + 1 = 28$. Other $4 (=k)$ ops are all resizing ops at 2, 4, 8, and 16 (you don’t resize at 1).
• Because we are interested in the amortized time complexity, we will have to divide the entire cost by $2^k + 1$.
• $2^k + 1$ is the general worst case, since the last operation (the $+1$ part) triggers the resizing.

Conclusion

Sliding window

• Sliding window technique is used in subarray or substring problems, like longest, shortest, or target value.
• For these problems, there is usually an apparent brute force solution that runs in O(N²), O(2^N)
• Two pointers move in the same direction in the way that they will never overtake each other (O(n))
• The key concept is you want to keep track of the previous best information you have

Intuition

FYI: Big help from this stackoverflow answer.

Sliding window can be used when you want to efficiently get the maximum sum of a subarray of length 5 in an array, for example.

[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]

The bruteforce algorithm will clearly introduce O(length_of_the_array * length_of_the_subarray) time complexity. But we can improve by ‘sliding the window’:

• The first subarray’s sum is sum(5, 7, 1, 4, 3) = 20
• The second subarray’s sum is sum(7, 1, 4, 3, 6) = 21
• … and so on

But the only numbers changing in the calculation are the first and the last number (5 and 6). So simply subtracting 5 from and adding 6 to the first subarray’s sum would deduce the second array’s sum. The same goes for the next subarrays.

This will result in O(n) time complexity because subtracting and adding ops are fixed at 2 * O(1) regardless of length of the array/subarray.

Sliding window of dynamic range

• Sometimes, the sliding window’s length is not fixed. In this case, you will need to move the start and end pointers to the array dynamically.
• Dynamic range sliding window qs often involes using a hash to store previous information and starting again from there once some condition is met

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

from collections import defaultdict
from typing import Dict

def minimum_window_substring(s: str, substr: str) -> str:
  substr_hash: Dict[str, int] = defaultdict(int)
  window_hash: Dict[str, int] = defaultdict(int)

  # for "ABCDAB", need_unique_chars_count will be 4 because A and B overlap
  # it's just len(substr_hash)
  need_unique_chars_count = 0
  for c in substr:
    if substr_hash[c] == 0: need_unique_chars_count += 1
    substr_hash[c] += 1

  have_unique_chars_count = 0
  minimum_window_bounds = [-1, -1]
  start = 0
  # initiate 'end' from the beginning of the string
  for end in range(len(s)):
    if s[end] in substr_hash:
      window_hash[s[end]] += 1
      # minimum requiremenet to create a window
      # for this char (which is s[end]) has been fulfilled
      if window_hash[s[end]] == substr_hash[s[end]]:
        have_unique_chars_count += 1
    
    # while the condition to create a valid sliding window has
    # been fulfilled
    while have_unique_chars_count == need_unique_chars_count:
      curr_window_size = end - start + 1
      # current valid window size is smaller than the existing one
      # therefore we need to replace the window
      if minimum_window_bounds[0] == -1 or curr_window_size < minimum_window_bounds[1] - minimum_window_bounds[0] + 1:
        minimum_window_bounds = [start, end]
      # keep shrinking from the leftmost character because
      # we checked everything with it
      window_hash[s[start]] -= 1
      # if you happen to take out the character
      # that was required for the minimum window,
      # decrement have_unique_chars_count by 1
      if s[start] in substr_hash and window_hash[s[start]] < substr_hash[s[start]]:
        have_unique_chars_count -= 1
      start += 1
  if minimum_window_bounds[0] == -1:
    return ""
  return s[minimum_window_bounds[0]:minimum_window_bounds[1] + 1]

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

import math

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        left = 0
        subarray_sum, subarray_len = 0, math.inf
        # right pointer always increases
        for right, num in enumerate(nums):
            subarray_sum += num
            # if the subarray's sum satisfies the condition,
            # increase the left pointer until the subarray's sum
            # does not satisfy the condition anymore
            while subarray_sum >= target:
                subarray_len = min(right - left + 1, subarray_len)
                subarray_sum -= nums[left]
                left += 1
        return 0 if subarray_len == math.inf else subarray_len

Index as a hash key

• The index can be used as a hash table holding index and boolean value as key and value without forgetting about the initial value itself

  Example:

  arr = [4,1,5,2,2]
  
  for n in arr:
    if n < len(arr) and n > 0 and arr[n] > 0:
      arr[n] *= -1
  
  has_three = arr[3] < 0 # false
  has_two = arr[2] < 0 # true

Two pointers

Quite similar concept to the sliding window. Need to use two pointers each pointing at different parts of the array.

Traversing from the right

Sometimes you need to start from the back of the array.

Sorting the array

• If an array is sorted, there may be more optimal solution
• Sorting an array may simplify the problem

Precomputation

Precomutation of prefix/suffix/sum/product might be useful

Strings

• Watch out for the range of the input strings (characters): for example, a to z.

Hash table (Hash map)

A hash table stores data in a key-value pair. In a ‘good’ implementation of a hash table, the lookup by key takes amortized $O(1)$ time which can be mathematically proven.

Hash table implementation logics

• An array is a random access data structure, meaning that any index can be accessed in $O(1)$ time.
• A hash table is an abstract data structure because the underlying data structure can usually be an array. It does something called hashing, which is a translation from an arbitrary key to an integer number that behaves as an index of an array.
• The length of the array can be much smaller than the number hashcodes (output of the hash functions).
• For that reason, two different hashcodes may end up in the same array index. This is called collision.
• In a terrible hash table with bad a hash function that causes lots of collisions, the lookup may take $O(n)$.

Hash function

A hash function $h(k)$ used for a hash table, where $k$ is an integer key, $u$ is the maximum positive integer key, and $m$ is some integer that is $m << u$, can be defined as follows:

If $m << u$, $h(k)$ is not injective (one-to-one) by pigeonhole principle. In other words, $∀h\text{ }∃a,b\text{ } \text{s.t }h(a) = h(b)$. This is called collision. A method to handle this will be soon introduced.

A simple hash function can be implemented by getting a remainder which is k % m in Python, where $m$ is an appropriate prime number:

For example,

This function works the best only when keys are uniformly distributed. For example, let’s say you got $m = 11$. And what if you put the elements of the set $K = \{12, 23, 34, 45, 56\}$ into the hash table? The remainder will always be 1, and the lookup time will take $O(m)$.

Therefore, we want the performance of our data structure to be independent of the keys we choose to store.

Universal hashing

For a large enough key domain $u$, every hash function will be bad for some set of $t$ inputs. However, we can achieve good expected bounds on hash table performance by choosing our hash function randomly from a large family of hash functions.

The definition of the set of hash functions we are looking for is as follows:

Let $U$ be the set of universe keys and $H$ be a finite collection of hash functions mapping $U$ into ${0, 1, ... , m − 1}$. Then $H$ is called universal if,

In plain terms, for all $x, y$ that belong to $U$ and are distinct from each other, the cardinality of pairs of $h(x), h(y)$ that collide with each other (where $h$ belongs to $H$) is equal to the cardinality of the set of hash functions $H$ divided by $m$.

To put it even easier: the probability of a collision for two different keys $x$ and $y$ given a hash function randomly chosen from $H$ is $1/m$. This is can easily be seen because $\frac{\text{\# hash functions that map x and y to the same location}}{\text{total \# of hash functions}} = \frac{\frac{|H|}{m}}{|H|} = \frac{1}{m}$

Collision resolution strategies

As discussed, a collision must happen anyway when there are $m$ slots and $u$ items to insert into the slots, where $u > m$, due to the pigeonhole principle. Here are the strategies to resolve the collision.

1. Separate chaining.

• Easiest technique to resolve this problem.
• Whenever there is a collision, append the new data to a linked list (called a bucket) allocated to that specific index of the array.
• A node in the linked list would contain the original key and value.
• The hashcode will be used to iterate through a linked list that corresponds to the key.

The structure may be better described with TypeScript:

interface KeyValNode<T> {
  key: number; // hashcode
  val: T; // data to be held
  next: KeyValNode<T> | null;
  prev: KeyValNode<T> | null;
}

type HashTable<T> = LinkedList<KeyValNode<T>>[];

2. Linear probing.

• one method of open addressing
• No linked list, directly store data in the array records
• used when there are more slots in the array than the values to be stored
• If there is a collision, store the data at (index + n) % hash_table_len where n is the first nth index at which you find the array slot is empty. For example, if you wanted to insert data at index 5 but notice it’s not empty but index 6 is, simply put it at 6.
• Formally, the linear probing function can be given by $h(x, i) = (f(x) + i)\space mod\space N$ where $i = 1,2,3,...$
  • Usually, $f(x)$ would just be $f(x) = x$ in its simplest form.
  • $N$ is the length of the array

3. Quadratic probing.

• another method of open addressing
• similar to linear probing, but the interval between probes increases quadratically. Resolve collisions by examining certain cells (1,4,9, …) away from the original probe point
• therefore, it does not check all slots in the array and may not find a vacant slot in the end
• clustering
• quadratic probing function: $h_{i}(k) = (h(k) + i^2)\space mod\space N$, where
  • $h(k)$ is the original hash function (probably just $h(k) = k\space mod\space N$)
  • $h_{i}(k)$ is the hash function for each index $i$
  • $N$ is the length of the array

4. Double hashing.

• another method of open addressing
• double hashing function: $h(k, i) =(h_{1}(k) + i \times h_{2}(k))\space mod\space N$ where $h_{1}(k)$ and $h_{2}(k)$ are two ordinary hash functions.
  • For a popular case, let $h_{1}(k) = k\space mod\space N$ and $h_{2}(k) = P - (k\space mod\space P)$
    • Let $P$ a well chosen prime number less than $N$, and $N$ be the length of the array

Importance of the load factor

$\text{Load factor} = \frac{\text{\# filled slots in the array}}{\text{total \# slots in the array}}$

• As load factor increases towards 100%, it becomes increasingly difficult to find/insert a given key.
• That is why the load factor is normally limited to 70~80% at maximum and for some algorithms just 50%.
• Once the load factor exceeds the boundary, double the array size, and rehash every element again

Collision resolution strategies comparision

Strategy Separate Chaining Linear probing Quadratic probing Double hashing

Amortized $O(1)$ analysis

Hash table tips in Python

Use defaultdict in Python instead of checking for the key every time:

from collections import defaultdict

somedict = {}
print(somedict['test1']) # KeyError
# check if key exists
print('test1' in somedict)

somedict2 = defaultdict(int)
print(somedict2['test2']) # 0

# custom initialization
somedict3 = defaultdict(lambda: 3)
print(somedict3['test3']) # 3

Stack

You can easily simulate the behavior of a stack using a list in Python or array in JavaScript.

from typing import TypeVar, Generic, Union

T = TypeVar('T')

class Stack(Generic[T]):
  def __init__(self):
    self.arr = []

  def __len__(self):
    return len(self.arr)

  def pop(self) -> Union[T, None]:
    return self.arr.pop()

  def push(self, item: T) -> None:
    self.arr.append(item)

  def peek(self) -> T:
    if len(self.arr) == 0:
      raise Exception("Length is zero")

    return self.arr[-1]

Queue

Standard queue

A normal queue would work in a FIFO fashion. In most cases, you would use Python because it has a queue built into its stdlib.

from typing import Generic, TypeVar
from doubly_linked_list import DoublyLinkedList

T = TypeVar("T")

class Queue(Generic[T]):
  def __init__(self):
    self.dll = DoublyLinkedList()

  def is_empty(self):
    return len(self.dll) == 0

  def prepend(self, value: T):
    self.dll.insert_at(0, value)

  def pop(self) -> T:
    return self.dll.remove_at(len(self.dll) - 1)

q = Queue[int]()

print(q.is_empty())
q.prepend(1)
print(q.pop()) # 1
q.prepend(2) # 2 1
q.prepend(3) # 3 2 1
print(q.pop())
q.prepend(4) # 4 3 2 1
print(q.is_empty()) # false
print(q.pop()) # 1
print(q.pop()) # 2
print(q.is_empty())

Deque

A queue with two ends.

from typing import Generic, TypeVar
from doubly_linked_list import DoublyLinkedList, debug

T = TypeVar("T")

class Deque(Generic[T]):
  def __init__(self):
    self.dll = DoublyLinkedList()

  def is_empty(self):
    return len(self.dll) == 0

  def append(self, value: T):
    self.dll.insert_at(len(self.dll), value)

  def prepend(self, value: T):
    self.dll.insert_at(0, value)

  def pop(self) -> T:
    return self.dll.remove_at(len(self.dll) - 1)

  def popleft(self) -> T:
    return self.dll.remove_at(0)

q = Deque[int]()

deque = Deque()

deque.prepend(1)
deque.prepend(2)
deque.prepend(3)
deque.prepend(4)
debug(deque.dll) # 1

deque.append(5)
deque.append(6)
debug(deque.dll) # [4,3,2,1,5,6]

deque.popleft() # 4
deque.pop() # 6
debug(deque.dll) # [3,2,1,5]

Priority queue

• All elements in a priority queue need to have a priority associated with them.
• The queue will maintain a sorted order throughout its lifetime
• uses heapq (heap data structure) internally

from queue import PriorityQueue

q = PriorityQueue()

q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))

q.queue # [(1, 'eat'), (2, 'code'), (3, 'sleep')]
while not q.empty():
    next_item = q.get()
    print(next_item)

#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

from typing import Generic, Tuple, TypeVar, Union
import heapq

T = TypeVar('T')

class PriorityQueue(Generic[T]):
  def __init__(self):
    self.heap = []
  
  def put(self, item: T):
    heapq.heappush(self.heap, item)
  
  def get(self) -> Union[T, None]:
    if not self.heap:
      raise Exception("No elements in the heap")

    return heapq.heappop(self.heap)

  def __len__(self) -> None:
    return len(self.heap)

  def __bool__(self) -> bool:
    return len(self.heap) != 0
pq = PriorityQueue[Tuple[int, str]]()

pq.put((1, "one"))
pq.put((5, "five"))
pq.put((2, "two"))
pq.put((10, "ten"))

while pq:
  # (1, 'one')
  # (2, 'two')
  # (5, 'five')
  # (10, 'ten')
  print(pq.get())

Linked lists

Singly linked list implementation

from typing import Iterator, Union


class Node:
  def __init__(self, value=None, nxt=None, prev=None):
    self.value = value
    self.nxt = nxt
    self.prev = prev
  
  def __str__(self) -> str:
    return f"{{value:{self.value}}}"

class SinglyLinkedList:
  def __init__(self):
    self.head = Node()
    self.len = 0

  def __len__(self):
    return self.len

  def is_empty(self) -> bool:
    return len(self) == 0

  def connect_in_between(self, prev: Node, middle: Node, nxt: Node):
    prev.nxt = middle
    middle.nxt = nxt

  def traverse(self) -> Iterator[Node]:
    # head is a dummy pointer
    ptr = self.head.nxt

    while ptr is not None:
      yield ptr
      ptr = ptr.nxt
  
  def traverse_right_before(self, index: int) -> Node:
    ptr = self.head

    visit_count = index
    while ptr.nxt is not None and visit_count > 0:
      ptr = ptr.nxt
      visit_count -= 1

    if visit_count != 0:
      raise Exception(f"Index out of bounds: {index}")

    return ptr

  def insert_at(self, index: int, value) -> Node:
    prev = self.traverse_right_before(index)
    middle = Node(value)
    nxt = prev.nxt
    self.connect_in_between(prev, middle, nxt)

    self.len += 1
  
    return middle

  def remove_at(self, index: int) -> Node:
    prev = self.traverse_right_before(index)
    prev_nxt = prev.nxt
    two_nodes_away_node: Union[Node, None] = prev.nxt.nxt
    prev.nxt = two_nodes_away_node

    self.len -= 1
    # assert self.len >= 0

    return prev_nxt

ll = SinglyLinkedList()
def debug():
  for node in ll.traverse():
    print(node, end=" ")
  print("")
  
ll.insert_at(0, 1)
ll.insert_at(0, 2)
ll.insert_at(0, 3)
ll.insert_at(0, 4)
ll.insert_at(0, 5)
ll.insert_at(0, 6)
ll.insert_at(0, 1)
ll.insert_at(0, 3)
ll.insert_at(5, 100)
debug() 
# {value:3} {value:1} {value:6} {value:5} {value:4} {value:100} {value:3} {value:2} {value:1} 
ll.remove_at(5)
debug()
# {value:3} {value:1} {value:6} {value:5} {value:4} {value:3} {value:2} {value:1} 
ll.remove_at(0)
ll.remove_at(0)
ll.remove_at(3)
debug()
# {value:6} {value:5} {value:4} {value:2} {value:1}
ll.remove_at(0)
ll.remove_at(len(ll) - 1)
debug()
# {value:5} {value:4} {value:2} 
ll.insert_at(2, 50)
debug()
# {value:5} {value:4} {value:50} {value:2} 

Doubly linked list implementation

from typing import Iterator, Union


class Node:
  def __init__(self, value=None, nxt=None, prev=None):
    self.value = value
    self.nxt = nxt
    self.prev = prev
  
  def __str__(self) -> str:
    return f"{{value:{self.value}}}"

class DoublyLinkedList:
  def __init__(self):
    self.head = Node()
    self.tail = Node()
    self.head.nxt = self.tail
    self.tail.prev = self.head
    self.length = 0

  def __len__(self) -> int:
    return self.length

  def traverse(self) -> Iterator[Node]:
    ptr = self.head
    while ptr:
      if ptr == self.head or ptr == self.tail:
        ptr = ptr.nxt
      else:
        yield ptr
        ptr = ptr.nxt

  def traverse_from_right(self) -> Iterator[Node]:
    ptr = self.tail
    while ptr:
      if ptr == self.head or ptr == self.tail:
        ptr = ptr.prev
      else:
        yield ptr
        ptr = ptr.prev

  def connect_in_between(self, prev: Node, middle: Node, nxt: Node):
    prev.nxt = middle
    middle.prev = prev

    middle.nxt = nxt
    nxt.prev = middle

  def traverse_up_to(self, index: int):
    if len(self) < index:
      raise Exception(f"Index out of bounds at {index}")

    ptr = self.head
    
    visit_count = index
    
    while ptr.nxt is not None and visit_count > 0:
      ptr = ptr.nxt
      visit_count -= 1
    
    # should never get here, but just an exhaustive check
    if visit_count != 0:
      raise Exception(f"Index out of bounds at {index}")

    return ptr

  def insert_at(self, index: int, value):
    prev = self.traverse_up_to(index)

    nxt = prev.nxt
    middle = Node(value)
    self.connect_in_between(prev, middle, nxt)
    self.length += 1

  def at(self, index: int) -> Union[Node, None]:
    if len(self) <= index:
      raise Exception(f"Index out of bounds at {index}")

    prev = self.traverse_up_to(index)
    if prev.nxt == self.tail:
      return None
    return prev.nxt

  def remove_at(self, index: int):
    prev = self.traverse_up_to(index)
    two_nodes_away_node = prev.nxt.nxt

    prev.nxt = two_nodes_away_node
    two_nodes_away_node.prev = prev
    self.length -= 1

def debug(dll: DoublyLinkedList):
  for node in dll.traverse():
    print(node, end="")
  print("")
  for node in dll.traverse_from_right():
    print(node, end="")
  print("")

doubly_linked_list = DoublyLinkedList()
doubly_linked_list.insert_at(0, 0)
doubly_linked_list.insert_at(0, 1)
doubly_linked_list.insert_at(0, 2)
doubly_linked_list.insert_at(0, 3)
doubly_linked_list.insert_at(4, 100)
debug(doubly_linked_list)
doubly_linked_list.remove_at(0)
doubly_linked_list.remove_at(3)
doubly_linked_list.remove_at(1)
debug(doubly_linked_list)

The ‘dummy head’ technique

pointing to the actual head is useful for languages where there is a no explicit expression of a pointer (like LinkedListNode *node in C++). So it would go like this in TS:

const dummyHead: LinkedListNode = new LinkedListNode()

dummyhead.next = actualHead

Singly linked list does a lot

You can do a lot without making a singly linked list a doubly linked list.

The runner technique

it employs two pointers at the same time. For example, when you want to get the middle node of the array, you can use this.

def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
  slow = head
  fast = head
  while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      
  return slow

function middleNode(head: ListNode | null): ListNode | null {
    let slow = head
    let fast = head
    
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow!.next!
    }
    
    return slow
};

Reversing the list

function reverseList(head: ListNode | null): ListNode | null {
  let curr = head
  let prev = null
  let next = null

  while (curr) {
    next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }

  return prev
}

Reversing the list may be the alternative for a variable to store values sometimes.

Cycle detection

A variation of the runner technique. Think about it this way: there are two runners in a circular track, one at a slower speed than the other. Their speeds are fixed. Then the faster one will catch up with the slower one at least once in a while. In that sense, this technique is also called tortoise and hare algorithm.

function hasCycle(head: ListNode | null): boolean {
  let slow = head
  let fast = head

  while (fast && fast.next) {
    slow = slow?.next ?? null
    fast = fast?.next?.next ?? null

    if (slow === fast) {
      return true
    }
  }

  return false
};

Detecting the entry node to the cycle is an extension of the code above. This however requires some mathmatical reasoning:

The crux of it is the last sentence:

You need to move the head and slow nodes forward (by one node each time), and then they will meet each other at the entry point.

function detectCycle(head: ListNode | null): ListNode | null {
  let maybeNodeInLoop = hasCycle(head)

  if (!maybeNodeInLoop) return null

  while (maybeNodeInLoop != head) {
    // practically, it never becomes null because there is a cycle
    maybeNodeInLoop = maybeNodeInLoop?.next ?? null;
    head = head?.next ?? null;
  }
  return head;
};

Trees

• A tree is an undirected and connected acyclic graph
• A tree has $n$ nodes and $n - 1$ edges
• A tree is a recurisve data structure with subtrees

Terms

• Neighbor: Parent or child of a node
• Ancestor: A node reachable by traversing its parent chain
• Descendant: A node in the node’s subtree
• Degree: Number of children of a node
• Degree of a tree: Maximum degree of nodes in the tree
• Distance: Number of edges along the shortest path between two nodes
• Level/Depth: Number of edges along the unique path between a node and the root node
• Height of a node: Number of edges from the node to the deepest leaf
• Height of a tree: a height of the root
• Width: Number of nodes in a level
• Leaf: A node that does not have a child node in the tree
• Sibiling: nodes that share the same parent
• Subtree: basically subgraph

Binary tree

• A binary tree is a tree
  • where a parent node has two edges at max, each connecting to each of two nodes.
• A complete binary tree is a tree where every level of the tree is fully filled with the possible exception of the last level where the nodes must be as far left as possible. This is also a property of heap.
  • In a complete binary tree, $\text{number of nodes} = 2^{\text{height of the tree}+1} − 1 - \text{number of empty nodes in the bottomost level}$
• A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.
• A full binary tree is a binary tree in which each node has exactly zero or two children.

Binary search and binary search tree (BST)

A binary search is:

• an algorithm searches through a sorted collection by dividing the search set into two and comparing an element to the one that is larger or smaller than the element being searched for.

A binary search tree (BST) is a tree:

• where $\text{all left descendents' values} < n < \text{all right descendents' values}$ for every node’s value $n$.

def binary_search(array) -> int:
    def condition(value) -> bool:
        pass

    left, right = min(search_space), max(search_space) # could be [0, n], [1, n] etc. Depends on problem
    while left < right:
        mid = left + (right - left) // 2
        if condition(mid):
            right = mid
        else:
            left = mid + 1
    return left

def binary_search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left < right: 
        mid = left + (right - left) // 2
        if nums[mid] >= target: 
            right = mid
        else: 
            left = mid + 1
    return left if nums[left] == target else -1

def binary_tree_traversal(root: Union[Node, None]):
  if root is None:
    return
  # --
  # do what you want to do here
  # (code)
  # --
  binary_tree_traversal(root.left)
  binary_tree_traversal(root.right)

def binary_tree_traversal_iterative_dfs(root: Union[Node, None]):
  stack = [root]

  while stack:
    node = stack.pop()
    # --
    # do what you want to do here
    # (code)
    # --
    if node:
      stack.append(node.left)
      stack.append(node.right)

from queue import Queue

def binary_tree_traversal_iterative_dfs(root: Union[Node, None]):
  queue = Queue[Node]()
  queue.put(root)
  while not queue.empty():
    node = queue.get()
    # --
    # do what you want to do here
    # (code)
    # --
    if node:
      queue.put(node.left)
      queue.put(node.right)

Heap

• A min heap is a complete binary tree where the smallest value is at the top.
• A max heap is a complete binary tree where the max value is at the top. (otherwise, you could negate the key of a node in a min heap to use it as a max heap)
• A binary heap usually means min heap.
• In a min heap, every node is smaller than or equal to its children (the reverse for the max heap)
• A simple rule to remember the heap ‘order’ goes left to right, top to bottom
• Questions dealing with min/max may be relevant to heap

Min heap time complexities

$n = \text{number of nodes in the complete binary tree}$

Min heap implementation

from typing import Generic, List, TypeVar

T = TypeVar('T')

class MinHeap(Generic[T]):
  def parent_index(self, index: int) -> int:
    return (index - 1) // 2

  def left_child_index(self, index: int) -> int:
    return index * 2 + 1
  
  def right_child_index(self, index: int) -> int:
    return index * 2 + 2

  def is_index_valid(self, index: int, arr: List[T]) -> bool:
    return 0 <= index <= len(arr) - 1

  def bubble_down(self, parent_index: int, arr: List[T]) -> None:
    """
    Bubble the element down until the a node is smaller than its children
    """
    while self.is_index_valid(parent_index, arr):
      left = self.left_child_index(parent_index)
      right = self.right_child_index(parent_index)

      # find the smaller one between left and right (it may not exist)
      smaller_child_index = None
      if self.is_index_valid(left, arr) and arr[left] < arr[parent_index]:
        smaller_child_index = left
      if self.is_index_valid(right, arr) and arr[right] < arr[parent_index] and arr[right] <= arr[left]:
        smaller_child_index = right

      if smaller_child_index is not None:
        arr[smaller_child_index], arr[parent_index] = arr[parent_index], arr[smaller_child_index]
        # keep bubbling down
        parent_index = smaller_child_index
      else:
        break

  def bubble_up(self, child_index: int, arr: List[T]) -> None:
      """
      Bubble the node up until the node has all of its children bigger than itself
      """
      while self.is_index_valid(child_index, arr):
        parent_index = self.parent_index(child_index)
        # if child_index == 0
        if not self.is_index_valid(parent_index, arr):
          break
        if arr[child_index] < arr[parent_index]:
          arr[child_index], arr[parent_index] = arr[parent_index], arr[child_index]
          child_index = parent_index
        else:
          break

  def peek(self, arr: List[T]) -> T:
    return arr[0]

  def push(self, arr: List[T], new_elem: T) -> List[T]:
    """
    1. Add the node to the last indexing order of the array (rightmost, bottommost part of the tree)
    2. Bubble that node up
    """
    arr.append(new_elem)
    self.bubble_up(len(arr) - 1, arr)

    return arr

  def pop(self, arr: List[T]) -> T:
    """
    1. Remove the smallest node
    2. Move the last node in the array indexing order to the first index (to the root of the tree)
    3. Bubble that node down
    """
    smallest = arr[0]
    last = arr.pop()
    if last is not smallest:
      arr[0] = last
      self.bubble_down(0, arr)

    return smallest

  def heapify(self, arr: List[T]) -> None:
    # last level leaves don't need to be bubbled down
    for i in range(len(arr) // 2, -1, -1):
      self.bubble_down(i, arr)

Min heap implementation logics

An array can represent a heap

• Due to the ordering of the complete binary tree, an array can be used to represent a heap:

• Because of the complete binary tree’s property, the indices of a parent, left child, and right child can be identified given an index:

  ...
  
  def get_parent_idx(self, idx):
      return (idx - 1) // 2
  
  def get_left_child_idx(self, idx):
      return idx * 2 + 1
  
  def get_right_child_idx(self, idx):
      return idx * 2 + 2
  
  ...

  Notice the meaning of $* 2$ and $/ 2$. This is because the next level must have twice as many elements as the previous level in a complete binary tree.

  For example, given an index of 3:

  • its parent is 3 - 1 // 2 = 2
  • its left child is 3 * 2 + 1 = 7
  • its right child is 3 * 2 + 2 = 8

  

Insertion

1. Put the new element into the last position of the complete binary tree
2. Compare the new element with its parent, and swap with the parent if it is greater than the element.
3. Repeat 1-2. This process is called ‘bubbling up’

Removal

1. Removal only happens at the top of the heap only
2. Move the element at the last position (bottommost & rightmost) of the complete binary tree to its top
3. See if any of its children are smaller than the element
4. Swap the element with the smaller one of the children nodes
5. Repeat 3-4. This process is called ‘bubbling down’ (also known as ‘sift down’)

Heapify: How is it $O(n)$?

• We all know about the naive approach by now
• In the efficient approach:
  • start from the bottommost, rightmost node in the complete binary tree that has a child
  • bubble the node down if possible
  • repeat by going backwards in the array index order until the root is reached

• Why is bubbling down is much more efficient than bubbling up (FYI if implemented correctly, bubble_up will only need to be used to perform an insert to an existing heap)?
  • The number of operations required for bubble_down and bubble_up is proportional to the distance the node may have to move.
  • For bubble_down, it is the distance to the bottom of the tree, so bubble_down is expensive for nodes at the top of the tree.
  • With bubble_up, the work is proportional to the distance to the top of the tree, so bubble_up is expensive for nodes at the bottom of the tree.
  • The tree has smaller number of nodes at the top, and larger at the bottom
  • Intuitively, bubble_down will cost less work if every node were to be gone through

Calculation of the work: bubble_down

As you can see, the total work for bubble_down is

$\text{(bubble\_down work at the bottommost level)} + \text{(bubble\_down work at the next bottommost level)} + ... + \text{(bubble\_down work at the top level)} =$

$O(0 \times n/2) + O(1 \times n/4) + O(2 \times n/8) + ... + O(h \times 1)$

where $n = \text{number of nodes in the complete binary tree}$. Remember each work is the number of edges a node may have to go down at most in a single bubble_down operation.

The sum of the work is equal to $n$. The proof requires the knowledge of some math concepts, so it’ll be skipped here.

Calculation of the work: bubble_up

The total work for bubble_up is

$\text{(bubble\_up work at the topmost level)} + \text{(bubble\_up work at the next top level)} + ... + \text{(bubble\_up work at the bottommost level)} =$

$O(h \times n/2) + O((h-1) \times n/4) + O((h-2) \times n/8) + ... + O(0 \times 1)$

The first term, $O(h \times n/2)$, is already $O(h) * n = O(nlogn)$, so it’s obvious it requires more work than bubble_down strategy.

Python’s heapq

Applications of the heap

• When you feel like you can use a heap but can’t get any further, maybe think about using multiple heaps?

AVL tree

AVL trees

Red-black tree

Red-black trees

Trie (Prefix tree)

Trie is a special arrangement of nodes such that a prefix of each string is recursively stored up to the root node.

Complexities (where k is the length of a string and n is the number of strings stored)

• time
  • search: O(k)
  • insert: O(k)
• space: O(n * k)

A trie is useful when you need to search for matching prefix from many strings. No major languages offer this data structure in their std. Your own implementation is needed.

Note that TrieNode itself does not contain the character although from illustration of the tries above it may look like that.

class TrieNode:
    def __init__(self) -> None:
        # you can change this to self.nodes: List[TrieNode] = [None] * characters_len
        # if you know the exact set of characters you will receive
        self.nodes: dict[str, TrieNode] = {}
        # is_leaf tells if the node is the end of a word
        self.is_leaf = False

    def insert_many(self, words: list[str]) -> None:
        for word in words:
            self.insert(word)

    def insert(self, word: str) -> None:
        """
        recursively insert char by char
        """
        curr = self
        for char in word:
            if char not in curr.nodes:
                curr.nodes[char] = TrieNode()
            curr = curr.nodes[char]
        curr.is_leaf = True

    def find(self, word: str) -> bool:
        """
        recurisvely find char by char
        if one char in the middle is not in the tree,
        return false
        """
        curr = self
        for char in word:
            if char not in curr.nodes:
                return False
            curr = curr.nodes[char]
        return curr.is_leaf

    def delete(self, word: str) -> None:
        """
        Deletes a word in a Trie
        :param word: word to delete
        :return: None
        """

        def _delete(curr: TrieNode, word: str, index: int) -> bool:
            if index == len(word):
                # If word does not exist
                if not curr.is_leaf:
                    return False
                curr.is_leaf = False
                return len(curr.nodes) == 0
            char = word[index]
            char_node = curr.nodes.get(char)
            # If char not in current trie node
            if not char_node:
                return False
            # Flag to check if node can be deleted
            delete_curr = _delete(char_node, word, index + 1)
            if delete_curr:
                del curr.nodes[char]
                return len(curr.nodes) == 0
            return delete_curr

        _delete(self, word, 0)

def test_trie() -> bool:
    words = "banana bananas bandana band apple all beast".split()
    root = TrieNode()
    root.insert_many(words)
    # print_words(root, "")
    assert all(root.find(word) for word in words)
    assert root.find("banana")
    assert not root.find("bandanas")
    assert not root.find("apps")
    assert root.find("apple")
    assert root.find("all")
    root.delete("all")
    assert not root.find("all")
    root.delete("banana")
    assert not root.find("banana")
    assert root.find("bananas")
    return True

Graphs

DFS and BFS

DFS: Makes a discovery into the last found vertex (branch) first.

A DFS would usually involve passing graph and visited as a reference to the function:

def dfsWrapper(edges: List[List[int]], source: int):
  graph = defaultdict(list)
  for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])
  visited = set()
  dfs(graph, visited, source)

def dfs(graph: Dict[int, List[int]], visited: Set[int], source: int):
  visited.add(source)

  for neighbor in graph[source]:
    if not neighbor in visited:
      dfs(graph, visited, neighbor)

A DFS could also be achieved using a stack, without a recursion:

def dfs(self, graph: List[List[int]]):
    stack = [0]
    seen = set(stack)
    while stack:
        i = stack.pop()
        for j in graph[i]:
            if j not in seen:
                stack.append(j)
                seen.add(j)

BFS: Makes a discovery into the neighbors of a vertex first before going into any other vertices.

A BFS would normally use a queue or deque which is not included in JavaScript’s native API, so other languages like Python needs to be used. This is the normal BFS with an adjacency list (edges) as an input.

from collections import defaultdict
from queue import Queue
from typing import List

def BFS(edges: List[List[int]], source: int) -> bool:
  graph = defaultdict(list)

  # O(2E) time
  for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])
  
  visited = defaultdict(bool)
  queue = Queue()
  queue.put(source)
  visited[source] = True
  # O(V) time
  while not queue.empty():
    vertex: int = queue.get()
    for v in graph[vertex]:
      if not visited[v]:
        visited[v] = True
        queue.put(v)

As you can see, a BFS has an O(2E + V) time complexity, which is essentially O(E + V). BFS may be more useful than DFS in general if you are looking for the shortest path.

Dealing with the adjacency list

To turn it into a graph, you may want to use not only dict but also array as long as the vertices are labeled from 0 to n:

def create_graph(edges: List[List[int]]):
  graph = [[] for _ in range(len(edges))]
  for e in edges:
    # undirected graph stored in an array
    graph[e[0]].append(e[1])
    graph[e[1]].append(e[0])

def create_graph(edges: List[List[int]]):
  graph = defaultdict(list)
  for e in edges:
    # undirected graph stored in a dict
    graph[e[0]].append(e[1])
    graph[e[1]].append(e[0])

The same goes for visited dict. In some cases, it may be better use a fixed length array to achieve it.

Preorder, inorder, postoreder traversal

In DFS for binary trees, there are multiple ways of traversal:

• Preoreder: Root -> Left subtree -> Right subtree
• Inorder: Left subtree -> Root -> Right subtree
• Postorder: Left subtree -> Right subtree -> Root

def preorder(node):
  if node is None:
    return
  # do something with node here
  do_something_with(node)
  preorder(node.left)
  preorder(node.right)

def preorder_iterative(root):
  stack = [root]
  while stack:
    curr_node = stack.pop() 
    do_something_with(curr_node)
    if curr_node.right is not None: 
      stack.push(curr_node.right)
    # first, traverse all the way down to the leftmost bottom node
    if curr_node.left is not None: 
      stack.push(curr_node.left)

def inorder(node):
  if node is None:
    return
  inorder(node.left)
  # do something with node here
  # the first node to be reached is the leftmost node at the bottom
  do_something_with(node)
  inorder(node.right)

def inorder_iterative(root):
  stack = []
  curr_node = root
  while stack or curr_node:
    # go all the way to left first
    if curr_node is not None:
      stack.append(curr_node)
      curr_node = curr_node.left
    # and then, take turns to inspect right and left nodes
    else:
      curr_node = stack.pop()
      do_something_with(curr_node)
      curr_node = curr_node.right