Data Structure & Algorithm Notes
Fundamental
Time and Space Complexity
Big O notation is a way to describe how fast the algorithm runs. It meeasures growth of the operations with respect to the input size. While time compexity measures how fast the algorithm runs, space complexity measures how much space the algorithm uses.
Example 1:
Suppose we have a list of numbers and want to find the maximum number. If the list is of size n, then the time complexity is O(n). The space complexity is O(1) since we can use a single variable to store the maximum number.
Example 2:
The code below computes the sum of the first n natural numbers. The operation grow linearly with respect to the input size. The time complexity is O(n). The space complexity is O(n) since we need to store the sum of the first n in every recursive call.
function sum(n) {
if (n == 0) {
return 0
}
return n + sum(n - 1)
}However, the space complexity of code below is O(1). The sum is stored in a single variable.
function pairSumSequence(n) {
let sum = 0
for (let i = 0; i < n; i++) {
sum += pairSum(i, i + 1)
}
return sum
}
function pairSum(a, b) {
return a + b
}Example 3:
function sum(list) {
sum = 0
product = 1
for (let i = 0; i < list.length; i++) {
sum += list[i]
}
for (let i = 0; i < list.length; i++) {
product *= list[i]
}
return `sum: ${sum}, product: ${product}`
}The code above has two loops. The time complexity is O(n) even though there are two loops. The space complexity is O(1) since the sum and product are stored in a single variable.
Example 4:
function sum(list) {
sum = 0
for (let i = 0; i < list.length; i++) {
for (let j = 0; j < list.length; j++) {
sum += list[i] + list[j]
}
}
return sum
}In this example, we have nested loops. The inner loop has O(n) time complexity, so the function has O(n^2) time complexity. The space complexity is O(1) since the sum is stored in a single variable.
Arrays and Strings
Array stores a collection of elements while string is a sequence of characters. Both are itterable. However, array is mutable while string is immutable.
Hash Tables
A hash table is a data structure that maps keys to values for highly efficient lookup. It uses a hash function to convert a key into index where the value is stored.
// Using Map as Hash Table
let map = new Map()
// Insert
map.set("apple", 10)
map.set("banana", 20)
// Search
console.log(map.get("apple")) // 10
// Delete
map.delete("banana")
console.log(map.has("banana")) // falseA set is like a special hash table that only stores unique values.
let set = new Set()
// Insert
set.add("apple")
set.add("banana")
// Search
console.log(set.has("apple")) // true
// Delete
set.delete("apple")
console.log(set.has("apple")) // falseLinked List
Linked list is a data structure that stores a collection of nodes. Each node has a value and a reference to the next node. the elements are not stored in adjecent memory locations.
Imagine a long train. Each train car is a single block or node that is connected to the next block. The first block is the head and the last block is the tail. Each block has a value and a reference to the next block. If we want to a certain block, we have to walk through every single car in order.
How linked list is different from array?
- Linked list is dynamic while array is static.
- In Array, we can access any element without walking through the whole array.
When a linked list is better?
- Adding or Removing items: Whe can add or remove items in constant time without shifting items.
When an array is better?
- Finding an item: We can find an item in constant time without shifting items.
Code Implementation:
class Node {
constructor(value) {
this.value = value
this.next = null
}
}
class LinkedList {
constructor() {
this.head = null
this.size = 0
}
add(data) {
const newNode = new Node(data)
if (this.head === null) {
this.head = newNode
} else {
let currentNode = this.head
while (currentNode.next) {
currentNode = currentNode.next
}
currentNode.next = newNode
}
this.size++
}
find(data) {
let current = this.head
while (current) {
if (current.value === data) {
return true
}
current = current.next
}
return false
}
}Recursion
Recursion is a technique in which a function calls itself. It is a way to solve a problem by decomposing it into smaller subproblems. It must have two parts:
- The Base Case: The base case is the condition when the function stops calling itself.
- The Recursive Case: The recursive case is the condition when the function calls itself.
Example:
function sum(n) {
if (n == 0) {
return 0
}
return n + sum(n - 1)
}Data Structure
Data structure is a way of organizing and storing information in a computer. It is a way to represent data in a way that is efficient and easy to use.
Stacks and Queues
Stack is precisely what is sounds like. It is a collection of elements that are added to the top and removed from the top. This follows the "Last In First Out" (LIFO) principle. The simplest example of a stack is a stack of plates. The plates are added to the top and removed from the top. In code implementation, we can use push and pop methods.
class Stack {
constructor() {
this.items = []
}
push(element) {
this.items.push(element)
}
pop() {
return this.items.pop()
}
peek() {
return this.items[this.items.length - 1]
}
isEmpty() {
return this.items.length === 0
}
size() {
return this.items.length
}
}Queue is a collection of elements that are added to the back and removed from the front. This follows the "First In First Out" (FIFO) principle. The simplest example of a queue is a line of people. The people are added to the back of the line and removed from the front of the line. In code implementation, we can use push and shift methods.
class Queue {
constructor() {
this.items = []
}
enqueue(element) {
this.items.push(element)
}
dequeue() {
return this.items.shift()
}
isEmpty() {
return this.items.length === 0
}
size() {
return this.items.length
}
}Tree
Tree is a data structure that is used to store data in a hierarchical way. It is a collection of nodes that are connected to each other. Each node has a value and a reference to the parent node. The root node is the top of the tree and the leaf nodes are the bottom of the tree. The easiest way to understand a tree is to think of a family tree where we have an oldest ancestor at the top and all the descendants branch out below them.
A Tree purpose is to strike a balance between the fast look-up of a sorted array and the flexible insertions and deletions of a linked list.
Tree Types
Binary Tree:
Binary tree is a tree where each node has at most two children. The left child is called the left child and the right child is called the right child. Not all trees are binary trees.
(A)
/ \
(B) (C)
/ \ \
(D) (E) (F)Binary Search Tree: Special binary tree where all left child < parent < all right child. The right image is not a binary search tree because the right child is greater than the parent, which is the 8. Use cases: Sorting, Searching
Balanced Binary Trees:
Balanced binary tree is a binary tree where the height of the left and right subtree differ by at most 1. It keeps its height as small as possible so operations remain efficient.
Complete Binary Trees:
Complete binary tree is a binary tree where all levels are completely filled except the last level.
Full Binary Trees: Full binary tree is a binary tree where all nodes have either 0 or 2 children.
Perfect Binary Trees:
Perfect binary tree is a binary tree where all leaves are at the same level.
Binary Tree Traversal
Traversal is a way to visit all the nodes in a tree. There are two big category of Binary Tree Traversal:
Depth First Traversal (DFS)
This traversal starts from the root and goes down to the leaves. In DFS we go deep down a path before backtracking. In code impmlementation, we use stack.
A
/ \
B C
/ \
D E
Visit order: A -> B -> D -> E -> C
// iterative
function DFS(root) {
if (root == null) {
return
}
const stack = []
stack.push(root)
while (stack.length > 0) {
const current = stack.pop()
console.log(current.value)
if (current.right) {
stack.push(current.right)
}
if (current.left) {
stack.push(current.left)
}
}
}
// recursive
function DFS(root) {
if (root == null) {
return
}
console.log(root.value)
DFS(root.left)
DFS(root.right)
}Breadth First Traversal (BFS)
This traversal starts from the root and goes level by level. In BFS we go level by level before going deep down a path. In code impmlementation, we use queue.
A
/ \
B C
/ \
D E
Visit order: A -> B -> C -> D -> E
// iterative
function BFS(root) {
if (root == null) {
return
}
const queue = []
queue.push(root)
while (queue.length > 0) {
const current = queue.shift()
console.log(current.value)
if (current.left) {
queue.push(current.left)
}
if (current.right) {
queue.push(current.right)
}
}
}Binary Heaps
Heaps are specialized structure for efficient retrieval of the minimum or maximum element, and they shine when the problem involves dynamic data with frequent inserts and removals. Binary heaps main operations are insert, get min/max, extract min/max, update, build.
Min Heap
Min heap is a complete binary tree where every parent node is less than or equal to its child nodes. The analogy of min heap is like chepest ticket queue. The person with lowest number is always at the front.
5
/ \
10 20
/ \ \
30 45 5Max Heap
Max heap is a complete binary tree where every parent node is greater than or equal to its child nodes. The analogy of max heap is like most expensive ticket queue. The person with highest number is always at the front.
50
/ \
30 20
/ \ \
10 15 5Tries
A Trie is a tree-like data structure that stores a dynamic set of strings, typically for fast prefix searches.
Key points:
- Each node represents a single character.
- The path from root to a node represents a prefix or a full string.
- The root node is empty children represents leters of stored words.
- Special nodes indicate end of a word
class TrieNode {
constructor() {
this.children = {} // key = char, value = TrieNode
this.isEndOfWord = false
}
}
class Trie {
constructor() {
this.root = new TrieNode()
}
insert(word) {
let node = this.root
for (let char of word) {
if (!node.children[char]) node.children[char] = new TrieNode()
node = node.children[char]
}
node.isEndOfWord = true
}
search(word) {
let node = this.root
for (let char of word) {
if (!node.children[char]) return false
node = node.children[char]
}
return node.isEndOfWord
}
startsWith(prefix) {
let node = this.root
for (let char of prefix) {
if (!node.children[char]) return false
node = node.children[char]
}
return true
}
}
// Example usage
let trie = new Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("cart")
trie.insert("dog")
trie.insert("lion")
console.log(trie.search("car")) // true
console.log(trie.search("cart")) // true
console.log(trie.search("cap")) // false
console.log(trie.startsWith("ca")) // true
console.log(trie.startsWith("do")) // trueGraphs
A graph is simply a collection of nodes and edges. Each node is a vertex and each edge is a connection between two vertices. A tree is actually a type of graph, but not all graphs are trees.
Directed graph has direction from one vertex to another (like one-way street). Undirected graph has no direction from one vertex to another (like two-way street).
There are two common ways to represent a graph:
-
Adjacency List Every vertex or node stores a list of its adjecent(neighbour) nodes. we can use hash table to store the adjacency list.
{ "A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": ["B"], "F": ["D"] } -
Adjacency Matrix An adjecency matrix is an NxN boolean matrix where N is the number of nodes in the graph. If there is an edge between two nodes, the matrix is set to true. If there is no edge between two nodes, the matrix is set to false.
adjacencyMatrix = [ [0, 1, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0], [0, 1, 0, 1, 1, 0], [0, 0, 1, 0, 1, 1], [0, 0, 1, 1, 0, 1], [1, 0, 0, 1, 1, 0], ]
Algorithms
Algorithm is a set of instructions for accomplishing a task. The goal is to find the optimal solution to a particular problem.
Sorting Algorithm
Bubble Sort
Bubble sort compare adjacent elements and swap if they are in the wrong order. It repeats this process until the entire array is sorted. Like bubbles rising in water, the largest element "bubbles up" to the end in each pass. The time complexity is O(n^2) and the space complexity is O(1).
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
}Selection Sort
Selection sort works by repeteadly selecting the smallest or largest element from the unsorted portion of array and placing it in the sorted portion. The time complexity is O(n^2) and the space complexity is O(1).
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minVal = arr[i]
let minIndex = i
for (let j = i; j < arr.length; j++) {
if (arr[j] < minVal) {
minVal = arr[j]
minIndex = j
}
}
const temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
}Quick Sort
Quick sort is devide and conquer algorithm, a problem solving strategy that breaks a big problem into smaller and easier one. First, pick a pivot, split into left and right. Then, recursively sort left & right. Imagine a list of people that we want to sort by height, we will pick one person as pivot and devide the group into shorter and taller than the pivot. Reapeat the process for left and right groups. To pick the pivot we can use first element, last element, middle alement or random. Choosing the last or first element as pivot is the simples method. Time complexity is O(n^2) and space complexity is O(log n).
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
// Partition the array and get pivot position
let pi = partition(arr, low, high)
// Recursively sort left and right subarrays
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
}
return arr
}
function partition(arr, low, high) {
// 🔥 Pivot is the last element
let pivot = arr[high]
let i = low - 1
for (let j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++
;[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
// Place pivot in its correct position
;[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]
return i + 1
}Merge Sort
Insead of trying to sort the whole array at once, merge sort split the array into halves, keep dividing until each part has 1 element then sort each half recursively. It's like sorting cards. Instead of splitting them all at once we split into smaller piles then merge it togehter. Time complexity is O n(log n) while space compexity is O(n).
function mergeSort(arr) {
if (arr.length <= 1) return arr // Base case
// 1. Divide
const mid = Math.floor(arr.length / 2)
const left = mergeSort(arr.slice(0, mid))
const right = mergeSort(arr.slice(mid))
// 2. Conquer (merge sorted halves)
return merge(left, right)
}
function merge(left, right) {
let result = []
let i = 0,
j = 0
// Compare and merge
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i])
i++
} else {
result.push(right[j])
j++
}
}
// Add leftovers
return result.concat(left.slice(i)).concat(right.slice(j))
}Searching Algorithm
Linear Search
Linear search means checking every element one by one. It has O(n) time complexity and O(1) space complexity.
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i // Found
}
}
return -1 // Not found
}Binary Search
It works by repeatedly deviding the search space in half until target is found. The data should be sorted first. The time complexity is O(log n) and space complexity is O(1)
function binarySearch(arr, target) {
let low = 0,
high = arr.length - 1
while (low <= high) {
let mid = Math.floor((low + high) / 2)
if (arr[mid] === target) {
return mid // Found, return index
}
if (arr[mid] < target) {
low = mid + 1 // Search right half
} else {
high = mid - 1 // Search left half
}
}
return -1 // Not found
}
// Example usage
let nums = [1, 3, 5, 7, 9, 11]
console.log(binarySearch(nums, 7)) // Output: 3
console.log(binarySearch(nums, 4)) // Output: -1Breadth First Search (Graph)
BFS is a searching algorithm used to traverse or search in data structures like a tree or a graph. The algorithm start with a root node and visits the nodes in a level by level manner. BFS use queue data structure to store nodes not yet visited. We need to check before nodes are put in the queue to ensure same nod is not visited twice.
Depth First Search (Graph)
DFS will explore as far as possible along each branch before backtracking. it uses stack to store nodes.
Example 1 - Has Path: The graph is no cycle, meaning it doesn't has any cycle path.
const graph = {
f: ["g", "i"],
g: ["h"],
h: [],
i: ["g", "k"],
j: ["i"],
k: [],
}
function hasPathBfs(graph, src, dst) {
if (src === dst) return true
const queue = [src]
while (queue.length > 0) {
const current = queue.shift()
for (item of graph[current]) {
if (item === dst) return true
queue.push(item)
}
}
return false
}
function hasPathDfs(graph, src, dst) {
if (src === dst) return true
const stack = [src]
while (stack.length > 0) {
const current = stack.pop()
for (item of graph[current]) {
if (item === dst) return true
stack.push(item)
}
}
return false
}Example 2 - Count Island: The graph here is cyclic or undirected path.
const edges = [
["i", "j"],
["k", "i"],
["m", "k"],
["k", "l"],
["o", "n"],
]
function createGraph(edges) {
const graph = {}
for (let edge of edges) {
const [a, b] = edge
if (!graph[a]) graph[a] = []
if (!graph[b]) graph[b] = []
graph[a].push(b)
graph[b].push(a)
}
return graph
}
const graphData = createGraph(edges)
function countIsland(graph) {
const visitedNode = new Set()
let count = 0
for (let item in graph) {
if (explore(graph, item, visitedNode)) {
count++
}
}
return count
}
function explore(graph, current, visitedNode) {
if (visitedNode.has(current)) return false
visitedNode.add(current)
for (let neighbor of graph[current]) {
explore(graph, neighbor, visitedNode)
}
return true
}
console.log(countIsland(graphData))Sliding Window
Sliding window is a technique where instead of recalculating results over and over for overlapping parts of data, we resuse previous calcuations by maintaining a window (subarray or substring) that slides over the input. Think of this like moving a maginfying glas over the string.
Example 1 - Longest Substring:
function longestUniqueSubstring(s) {
let set = new Set()
let left = 0,
maxLen = 0
for (let right = 0; right < s.length; right++) {
while (set.has(s[right])) {
set.delete(s[left])
left++
}
set.add(s[right])
maxLen = Math.max(maxLen, right - left + 1)
}
return maxLen
}