# Array (/docs/dsa/array)
## Overview [#overview]
Array is a data structure that lets you store multiple values in one variable. Each value in the array is called an element, and elements are accessed using their index, which starts at `0` for the first element.
| Operations | Complexity | Description |
| ------------------------ | ---------- | -------------------------------------------------------------------------------------------------------------------- |
| Access/Edit i-th element | O(1) | Arrays give direct access to elements through their index. |
| Insert/Remove | O(n) | Adding or removing an element at a specific index requires shifting all later elements to make room or fill the gap. |
| Insert/Remove at end | O(1) | Adding or removing an element at the end only needs updating the last index. |
### Background [#background]
Arrays are usually stored as contiguous memory blocks. This means all elements sit next to each other in memory with no gaps in between.
> When an array is created, the system allocates a block of memory large enough to hold all elements. The memory address of each element is based on the starting address of the array. The first element sits at the starting address, and each following element is placed at the next available address.
>
> ```c++
> int arr[5] = {3, 7, 1, 2, 3};
> ```
>
> If each integer takes 4 bytes, the memory addresses look like this:
>
> ```sh
> Address of arr[0] = starting address
> Address of arr[1] = starting address + 4
> Address of arr[2] = starting address + 8
> Address of arr[3] = starting address + 12
> Address of arr[4] = starting address + 16
> ```
>
> Because the memory is contiguous, accessing elements is efficient. The address of any element can be calculated from the starting address and the size of each element. This makes direct access possible without looping or searching.
Different languages are designed with different goals related to performance, control, and flexibility, arrays can differ with their declaration and capabilities.
* Static Arrays:
> * They have a fixed size declared ahead of time.
> * They use a set amount of memory for the entire program.
> * Trying to add more elements than the set size can lead to overflow or memory issues.
* Dynamic Arrays:
> * They do not need a fixed size in advance.
> * They can grow or shrink during runtime.
> * Some languages give them a default starting capacity. When this capacity is exceeded, the array is resized.
> * Resizing usually means creating a new larger block of memory, often 2x or 1.5x bigger, copying all existing elements into it, and freeing the old block.
> > The worst case for resizing has a time complexity of `O(n)` because all elements must be copied one by one.
> Here is a video about JavaScript arrays and how the V8 engine handles them: [https://www.youtube.com/watch?v=m9cTaYI95Zc](https://www.youtube.com/watch?v=m9cTaYI95Zc)
# Complexity (Big O) (/docs/dsa/complexity)
## Overview [#overview]
Big O notation shows how an algorithm's speed or memory use grows as the input gets bigger.
* Time Complexity: Speed
> How the amount of work changes as the input size increases.
* Space Complexity: Memory
> How the amount of memory changes as the input size increases.
Measurements:
> * `O(1)`: Constant.
> > The work stays the same no matter how big the input is.
> * `O(log n)`: Logarithmic.
> > The work shrinks by a large factor each step, often by half.
> * `O(n)`: Linear.
> > The work grows at the same rate as the input.
> * `O(n log n)`: Log Linear.
> > The input is split into smaller parts that get handled in about `log n` stages with each stage doing `O(n)` work.
> * `O(n^2)`: Quadratic.
> > The work grows with the square of the input size.
> * `O(2^n)`: Exponential.
> > The work doubles with each extra input item.
## Rules [#rules]
1. Worst Case.
> Big O describes the upper limit of how long an algorithm might take. It looks at the worst possible case so you know the running time will never be worse than that.
2. Remove Constants.
> Big O cares about how the work grows, not about fixed numbers. This means constants are removed. For example, `O(5n)` becomes `O(n)`.
3. Different Inputs, Different Variables.
> If an algorithm uses more than one input, each input should have its own variable so the complexity stays clear to accurately capture their separate impacts.
> * Sequential loops:
> * Same inputs: `O(a + a)` -> `O(2a)` -> `O(n)`
> > ```js
> > func(a) {
> > a.loop1 {}
> > a.loop2 {}
> > }
> > ```
> * Different inputs: `O(a + b)`
> > ```js
> > func(a, b) {
> > a.loop1 {}
> > b.loop2 {}
> > }
> > ```
> * Nested loops:
> * Same inputs: `O(a * a)` -> `O(a^2)`
> > ```js
> > func(a) {
> > a.loop1 {
> > a.loop2 {}
> > }
> > }
> > ```
> * Different inputs: `O(a * b)`
> > ```js
> > func(a, b) {
> > a.loop1 {
> > b.loop2 {}
> > }
> > }
> > ```
4. Drop the Non-Dominant Terms.
> Only the term that grows the fastest is kept. All smaller (non-dominant) terms are removed because they have much less effect as the input grows.
> For example, `O(n) + O(n^2)` becomes `O(n^2)`.
>
> ```js
> func(a) {
> a.loop1 {}
> a.loop2 {
> a.loop3 {}
> }
> }
> ```
# Graphs (/docs/dsa/graphs)
## Overview [#overview]
A graph is a data structure used to represent relationships between things. It is made up of `nodes` (vertices) that represent the objects you care about and `edges` that represent the connections between them.
### Types of Graphs [#types-of-graphs]
* Directed Graph:
> Edges have a direction, so a connection goes from one node to another.
> 
* Undirected Graph:
> Edges have no direction, so the connection works both ways.
> 
* Cyclic Graph:
> Contains at least one cycle, meaning you can start at a node and return to it by following edges.
> 
* Acyclic Graph:
> Has no cycles, so you cannot return to a starting node by following edges.
> 
* Unweighted Graph:
> Edges do not have values, so all connections are treated as equal.
> 
> Here, the most efficient way from `A` to `D` is `ABCD` (the shortest path).
* Weighted Graph:
> Edges have values (weights), such as distance, cost, or time.
> 
> Here, the most efficient way from `A` to `D` is `AFGBCD` (the lowest total cost).
### Code Representations [#code-representations]
There are three common ways to represent a graph in code.
> Example graph:
> 
* Edge lists.
> A graph is stored as a plain list of edges. Each edge is a pair (`from`, `to`) for unweighted graphs, or a triple (`from`, `to`, `weight`) for weighted graphs.
```js
const edgeList = [
['A', 'B'],
['B', 'C'],
['B', 'E'],
['C', 'D'],
['D', 'E'],
['D', 'F'],
];
```
* Adjacency matrices.
> A graph is stored as a 2D grid of values. The cell at (`i`, `j`) indicates whether there is an edge from node `i` to node `j` (often `0`/`1`), or stores the edge weight in weighted graphs.
```js
const adjMatrix = {
A: { A: 0, B: 1, C: 0, D: 0, E: 0, F: 0 },
B: { A: 1, B: 0, C: 1, D: 0, E: 1, F: 0 },
C: { A: 0, B: 1, C: 0, D: 1, E: 0, F: 0 },
D: { A: 0, B: 0, C: 1, D: 0, E: 1, F: 1 },
E: { A: 0, B: 1, C: 0, D: 1, E: 0, F: 0 },
F: { A: 0, B: 0, C: 0, D: 1, E: 0, F: 0 },
};
```
* Adjacency lists.
> A graph is stored as a mapping from each node to its neighbors. Each key is a node, and its value is a list of directly connected (outgoing) nodes (or pairs like (`neighbor`, `weight`) for weighted graphs).
```js
const adjList = {
A: ['B'],
B: ['A', 'C', 'E'],
C: ['B', 'D'],
D: ['C', 'E', 'F'],
E: ['B', 'D'],
F: ['D'],
};
```
# Hash Table (/docs/dsa/hash-table)
## Overview [#overview]
A hash table is a data structure that stores data as key value pairs. It uses a hashing function to map each key to a position in memory which gives fast access when storing or retrieving values by that key.
| Operations | Complexity |
| ----------- | ---------- |
| Access/Edit | O(1) |
| Insert | O(1) |
| Remove | O(1) |
JavaScript provides objects and Maps as hash table based collections.
* Using a plain object:
> ```js
> const user = {};
>
> user['age'] = 25;
> user['name'] = 'John';
>
> console.log(user); // {age: 25, name: 'John'}
> console.log(user['age']); // 25
> ```
* Using Map:
> ```js
> const user = new Map();
>
> user.set('age', 25);
> user.set('name', 'John');
>
> console.log(user); // Map(2) {'age' => 25, 'name' => 'John'}
> console.log(user.get('age')); // 25
> ```
### Background [#background]
A hash table is built on three core components:
> 1. Key: The identifier used to access stored data.
> 2. Hash Function: A process that turns the key into a numeric hash code.
> 3. Buckets: An array in memory that holds the entries.
How it works:
> 1. Input:
> > You insert the value `John` using the key `name`.
> 2. Hashing:
> > The hash function converts `name` into a number such as `417`. This example uses character code sums. Real systems may use stronger functions for better distribution.
> 3. Indexing:
> > The table reduces that number to a valid index with a modulo step such as `417 % 10` which becomes `7`. Again, real systems may use different indexing methods.
> 4. Storage:
> > The pair is stored in bucket `7`.
>
> When you request `name`, the table repeats the hash and index calculations and retrieves the entry from bucket `7` immediately `O(1)`.
Handling collisions:
> A collision happens when two different keys map to the same bucket.
>
> Solution:
>
> * Chaining:
> > Each bucket holds a small list of entries. If two keys map to bucket `7`, both are stored in that list.
> >
> > Lookups check bucket `7` in `O(1)` time then scan the small list in `O(n)` time to find the matching key.
> >
> > Keeping entries well distributed across buckets is important for performance because it keeps these lists short which reduces how often lookups fall back to `O(n)` work.
# Home (/docs/dsa)
# Linked List (/docs/dsa/linked-list)
## Overview [#overview]
A linked list is a data structure made of nodes where each node holds a value and a reference to the next node. The nodes form a chain in memory which allows the list to grow or shrink easily by adjusting references.
| Operations | Complexity | Description |
| ------------------------ | ---------- | ------------------------------------------------------- |
| Access/Edit | O(n) | Reaching a position requires sequential node traversal. |
| Access/Edit first & last | O(1) | Head and tail pointers give direct access to ends. |
| Insert | O(n) | Traversal is required to reach the insertion point. |
| Insert front & end | O(1) | Head or tail pointer is updated directly. |
| Remove | O(n) | Traversal is required to locate the node. |
| Remove first | O(1) | Head pointer is updated directly. |
### Background [#background]
Linked lists can be formed with one or two references per node, creating singly or doubly linked structures.
* Singly Linked List:
> * Value: The data stored in the node.
> * Next: A reference to the next node in the list.
>
* Doubly Linked List:
> * Value: The data stored in the node.
> * Next: A reference to the next node in the list.
> * Prev: A reference to the previous node in the list.
>
> In doubly linked lists, removing the last node is `O(1)` because its previous node is directly reachable.
## Implementation [#implementation]
```js title="Singly Linked List" lineNumbers
class ListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// Access:
get(index) {
if (index < 0 || index >= this.size) {
throw new Error('invalid index');
}
let currNode = this.head;
for (let i = 0; i < index; i++) {
currNode = currNode.next;
}
return currNode;
}
// Insert front:
prepend(value) {
const newNode = new ListNode(value);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head = newNode;
}
this.size++;
}
// Insert end:
append(value) {
const newNode = new ListNode(value);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
}
// Insert
insertAt(index, value) {
if (index <= 0) {
this.prepend(value);
} else if (index >= this.size) {
this.append(value);
} else {
const newNode = new ListNode(value);
const parent = this.get(index - 1);
newNode.next = parent.next;
parent.next = newNode;
this.size++;
}
}
// Remove:
deleteAt(index) {
if (this.head === null) {
throw new Error('list is empty');
}
if (index < 0 || index >= this.size) {
throw new Error('invalid index');
}
if (index === 0) {
this.head = this.head.next;
if (this.head === null) {
this.tail = null;
}
} else {
const parent = this.get(index - 1);
parent.next = parent.next.next;
if (index === this.size - 1) {
this.tail = parent;
}
}
this.size--;
}
// (optional) Only to make the list easier to view:
toArray() {
const list = [];
let currNode = this.head;
while (currNode !== null) {
list.push(currNode.value);
currNode = currNode.next;
}
return list;
}
}
```
> Usage:
>
> ```js
> const myList = new LinkedList();
>
> myList.append('one');
> myList.append('two');
> myList.append('three');
> myList.insertAt(1, 'four');
> console.log(myList.toArray()); // (4) ['one', 'four', 'two', 'three']
> myList.prepend('five');
> myList.deleteAt(2);
> console.log(myList.toArray()); // (4) ['five', 'one', 'two', 'three']
> ```
# Matrix (2D Arrays) (/docs/dsa/matrix)
## Overview [#overview]
A matrix in data structures usually means a 2D array: a grid of values arranged in rows and columns.
## Movements [#movements]
| Action | Row | Column |
| ------ | ---- | ------ |
| Up | `-1` | `0` |
| Down | `+1` | `0` |
| Left | `0` | `-1` |
| Right | `0` | `+1` |
> Example:
>
> Suppose we are at `Row 2`, `Col 3` and want to move two steps up.
>
> ```js
> [
> [0, 0, 0, 0, 0, 0],
> [0, 0, 0, 0, 0, 0],
> [0, 0, 0, 1, 0, 0],
> [0, 0, 0, 0, 0, 0],
> ];
> ```
>
> Apply the Up move `(-1, 0)` twice: subtract 1 from the row two times while keeping the column the same.
>
> ```js
> [
> [0, 0, 0, 1, 0, 0],
> [0, 0, 0, 0, 0, 0],
> [0, 0, 0, 0, 0, 0],
> [0, 0, 0, 0, 0, 0],
> ];
> ```
>
> The new position is `Row 0`, `Col 3`.
# Queue (/docs/dsa/queue)
## Overview [#overview]
A queue is a data structure that stores items according to the First In First Out (FIFO) principle. The item that has been in the queue the longest is the first one to be removed.
| Operations | Complexity |
| ---------------------- | ---------- |
| Enqueue (insert end) | O(1) |
| Dequeue (delete first) | O(1) |
| Peek (view first) | O(1) |
## Implementation [#implementation]
In a queue, operations occur at both ends, so using an array is not efficient since removing the first element is costly. A linked list implementation is more suitable.
```js title="Queue" lineNumbers
class QueueNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
enqueue(value) {
const newNode = new QueueNode(value);
if (this.head === null) {
this.head = newNode;
} else {
this.tail.next = newNode;
}
this.tail = newNode;
this.size++;
}
dequeue() {
if (this.head === null) {
throw new Error('queue is empty');
}
const value = this.head.value;
this.head = this.head.next;
this.size--;
if (this.head === null) {
this.tail = null;
}
return value;
}
peek() {
if (this.head === null) {
throw new Error('queue is empty');
}
return this.head.value;
}
}
```
> Usage:
>
> ```js
> const myQueue = new Queue();
>
> myQueue.enqueue('One');
> myQueue.enqueue('Two');
> myQueue.enqueue('Three');
>
> console.log(myQueue.peek()); // One
>
> console.log(myQueue.dequeue()); // One
> console.log(myQueue.dequeue()); // Two
> console.log(myQueue.dequeue()); // Three
>
> console.log(myQueue.peek()); // Error: queue is empty
> ```
# Stack (/docs/dsa/stack)
## Overview [#overview]
A stack is a data structure that stores items according to the Last In First Out (LIFO) principle. The most recently added item is the first one to be removed.
| Operations | Complexity |
| ----------------- | ---------- |
| Push (insert end) | O(1) |
| Pop (delete last) | O(1) |
| Peek (view last) | O(1) |
## Implementation [#implementation]
Stacks can be implemented using different underlying structures. The most common versions are based on arrays or linked lists.
### Array Based Stack [#array-based-stack]
```js title="Array Based Stack" lineNumbers
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.items.length == 0) {
throw new Error('stack is empty');
}
return this.items.pop();
}
peek() {
return this.items.at(-1);
}
}
```
> Usage:
>
> ```js
> const myStack = new Stack();
>
> myStack.push('One');
> myStack.push('Two');
> myStack.push('Three');
>
> console.log(myStack.peek()); // Three
>
> console.log(myStack.pop()); // Three
> console.log(myStack.pop()); // Two
> console.log(myStack.pop()); // One
>
> console.log(myStack.peek()); // undefined
> ```
### Linked List Based Stack [#linked-list-based-stack]
```js title="Linked List Based Stack" lineNumbers
class StackNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Stack {
constructor() {
this.top = null;
this.size = 0;
}
push(value) {
const newNode = new StackNode(value);
newNode.next = this.top;
this.top = newNode;
this.size++;
}
pop() {
if (this.top === null) {
throw new Error('stack is empty');
}
const value = this.top.value;
this.top = this.top.next;
this.size--;
return value;
}
peek() {
if (this.top === null) {
throw new Error('stack is empty');
}
return this.top.value;
}
}
```
> Usage:
>
> ```js
> const myStack = new Stack();
>
> myStack.push('One');
> myStack.push('Two');
> myStack.push('Three');
>
> console.log(myStack.peek()); // Three
>
> console.log(myStack.pop()); // Three
> console.log(myStack.pop()); // Two
> console.log(myStack.pop()); // One
>
> console.log(myStack.peek()); // Error: stack is empty
> ```
# Basic Data Types (/docs/go/basic-data-types)
Go has three basic data types: `boolean`, `numeric`, and `string`. Each type has a zero-value assigned when a variable is declared without initialization.
## Boolean [#boolean]
| Keyword | Values |
| ------- | ----------------- |
| `bool` | `true` or `false` |
> Zero-value: `false`.
## Numeric [#numeric]
| Keyword | Size | Values |
| -------------- | --------------- | ------------------------------------------- |
| `uint8`/`byte` | 8-bit | 0 to 255 |
| `uint16` | 16-bit | 0 to 65535 |
| `uint32` | 32-bit | 0 to 4294967295 |
| `uint64` | 64-bit | 0 to 18446744073709551615 |
| | | |
| `int8` | 8-bit | -128 to 127 |
| `int16` | 16-bit | -32768 to 32767 |
| `int32`/`rune` | 32-bit | -2147483648 to 2147483647 |
| `int64` | 64-bit | -9223372036854775808 to 9223372036854775807 |
| | | |
| `float32` | 32-bit | -3.4e+38 to 3.4e+38 |
| `float64` | 64-bit | -1.7e+308 to +1.7e+308 |
| | | |
| `uint` | 32 bit / 64 bit | `uint32` / `uint64` |
| `int` | 32 bit / 64 bit | `int32` / `int64` |
> Zero-value: `0`.
## String [#string]
| Keyword | Values |
| -------- | ---------------------------------------- |
| `string` | "text in double quotes" or \`backticks\` |
> Zero-value: `""`.
Extra:
* > * Double-quoted strings are interpreted string literals. Escape sequences like `\n`, `\t`, `\uXXXX`, and `\xNN` are processed into their byte values. They cannot span multiple lines in source code.
> * Backtick strings are raw string literals. Content is preserved exactly as written, with no escape processing. They can span multiple lines in source code.
* > Technically, a string is a read-only slice of bytes:
>
> ```go
> str := "abcd" // [97 98 99 100]
>
> fmt.Printf("str[0]: %v, type: %T\n", str[0], str[0]) // str[0]: 97, type: uint8
>
> for i, v := range str {
> fmt.Println(i, v)
> }
>
> // 0 97
> // 1 98
> // 2 99
> // 3 100
> ```
>
> However, not every character is a single byte. Some characters require more than one byte:
>
> ```go
> str := "é"
> fmt.Printf("str: %v, len: %v, bytes: %v", str, len(str), []byte(str))
> // str: é, len: 2, bytes: [195 169]
> ```
>
> > `len()` returns the byte count, not the character count.
>
> This is because Go strings are UTF-8 encoded, and UTF-8 uses variable-length encoding. A character can use 1 to 4 bytes depending on its Unicode code point:
>
> | First code point | Last code point | Byte 1 | Byte 2 | Byte 3 | Byte 4 |
> | ---------------- | --------------- | -------- | -------- | -------- | -------- |
> | 0 | 127 | 0yyyzzzz | | | |
> | 128 | 2,047 | 110xxxyy | 10yyzzzz | | |
> | 2,048 | 65,535 | 1110wwww | 10xxxxyy | 10yyzzzz | |
> | 65,536 | 1,114,111 | 11110uvv | 10vvwwww | 10xxxxyy | 10yyzzzz |
>
> Explanation:
>
> > The character `é` has Unicode code point `U+00E9` (233). Since `233` falls in the range `128-2047`, it uses two bytes in UTF-8:
> >
> > ```go
> > str := "é" // [195 169]
> >
> > fmt.Printf("str[0]: %v\n", str[0]) // str[0]: 195
> > fmt.Printf("str[1]: %v\n", str[1]) // str[1]: 169
> > ```
> >
> > Proof (decoding):
> >
> > > `195` is `11000011` and `169` is `10101001`.
> > >
> > > Matching against the second row of the table above:
> > >
> > > * First byte: `11000011` (110xxxyy) -> prefix `110`, data bits `00011`.
> > > * Second byte: `10101001` (10yyzzzz)-> prefix `10`, data bits `101001`.
> > >
> > > Combining `00011` and `101001` gives `00011101001` in binary, which equals `233` in decimal.
A string does not always hold UTF-8 encoded bytes. Strings can contain arbitrary bytes, but when created from string literals, those bytes are (almost always) UTF-8.
```go
// From raw bytes:
var1 := string([]byte{0, 1, 2, 65, 195, 255, 195, 169, 0xff, 0xfd})
fmt.Printf("var1: %v, len: %v, bytes: %v", var1, len(var1), []byte(var1))
// var1: A���, len: 10, bytes: [0 1 2 65 195 255 195 169 255 253]
// From byte-level escape sequences:
var2 := "\xbd\x20\xb2\x3d\xbc\x48"
fmt.Printf("var2: %v, len: %v, bytes: %v", var2, len(var2), []byte(var2))
// var2: � �=�H, len: 6, bytes: [189 32 178 61 188 72]
// From a regular string literal:
var3 := "Hello"
fmt.Printf("var3: %v, len: %v, bytes: %v", var3, len(var3), []byte(var3))
// var3: Hello, len: 5, bytes: [72 101 108 108 111]
```
For example, in `var1` (`[0 1 2 65 195 255 195 169 255 253]`), some bytes form valid UTF-8 sequences and render as readable characters, such as `A` and `é`:
* `A` has Unicode code point `65`, which is in the `0` to `127` range. In UTF-8, this range uses one byte, so `65` maps directly to `A`.
* `é` has Unicode code point `233`, which is in the `128` to `2047` range. In UTF-8, this uses two bytes. In `var1`, these are `195` and `169`, which together decode to `233`.
> The remaining bytes do not form valid UTF-8 sequences and are shown as replacement characters (`�`).
* > Iterating with `range`:
>
> > When iterating with `range`, Go decodes each UTF-8 character and returns its Unicode code point (not the raw byte value):
> >
> > ```go
> > str := "Héllo" // [72 195 169 108 108 111]
> >
> > for i, v := range str {
> > fmt.Println(i, v)
> > }
> >
> > // 0 72
> > // 1 233
> > // 3 108
> > // 4 108
> > // 5 111
> > ```
# Conditions (/docs/go/conditions)
## If-else Statement [#if-else-statement]
Executes a block when a condition evaluates to `true`.
```go
if condition {
// runs if condition is true
} else if anotherCondition {
// runs if it gets here and this condition is true
} else {
// runs if none of the above are true
}
```
* Variable declaration is allowed inside the `if` statement, with scope limited to the `if-else` block:
```go
s := "Hello"
if n := len(s); n == 1 {
fmt.Println("n is:", n)
} else if n >= 2 {
fmt.Println("n is:", n)
} else {
fmt.Println("Empty string", n)
}
// n is: 5
fmt.Println("n is:", n) // <-- compiler: undefined: n
```
## Switch Statement [#switch-statement]
Executes the block for the first matching case.
```go
switch expression {
case value1:
// runs if expression == value1
case value2:
// runs if expression == value2
case value3, value4:
// runs if expression == value3 or value4
default:
// runs if no case matches
}
```
> Each case ends with an implicit `break` (the keyword itself can still be used).
* `fallthrough` overrides the implicit `break` and continues into the next case:
```go
a := 2
switch a {
case 1:
fmt.Println("One")
case 2:
fmt.Println("Two")
fallthrough
case 3:
fmt.Println("Three")
case 4:
fmt.Println("Four")
default:
fmt.Println("None of above")
}
// Two
// Three
```
* Variable declaration is allowed inside the `switch` statement, with scope limited to the `switch` block:
```go
s := "hi"
switch n := len(s); n {
case 1:
fmt.Println("n is:", n)
case 2:
fmt.Println("n is:", n)
default:
fmt.Println("None of above", n)
}
// n is: 2
fmt.Println("n is:", n) // <-- compiler: undefined: n
```
* Omitting the expression makes `switch` behave like an `if-else` chain.
```go
a := 3
switch {
case a == 1:
fmt.Println("One")
case a == 2:
fmt.Println("Two")
case a == 3 || a == 4:
fmt.Println("Three or Four")
default:
fmt.Println("None of above")
}
// Three or Four
```
# Data Structures (/docs/go/data-structures)
## Arrays [#arrays]
In Go, an array is a fixed-size, ordered collection of elements of the same type.
* Declare:
```go
var arr [5]int // [0 0 0 0 0] (zero-valued)
```
> Or initialize at declaration:
>
> ```go
> arr := [5]int{1, 2, 3, 4, 5}
> ```
* Access:
```go
fmt.Println(arr[0]) // 1
```
* Modify:
```go
arr[0] = 100
fmt.Println(arr[0]) // 100
```
Array elements are stored in contiguous memory locations, placed directly next to each other in memory.
```go
func main() {
arr := [3]int{1, 2, 3}
fmt.Printf("&arr[0]: %v\n", &arr[0]) // &arr[0]: 0xc00011e000
fmt.Printf("&arr[1]: %v\n", &arr[1]) // &arr[1]: 0xc00011e008
fmt.Printf("&arr[2]: %v\n", &arr[2]) // &arr[2]: 0xc00011e010
}
```
> Here, `int` is `int64` (on a 64-bit system), so each element occupies 8 bytes. Element addresses are spaced 8 bytes apart (`0` -> `8` -> `16`).
Extra:
* Let the compiler determine the size:
```go
arr := [...]int{3, 5, 6, 2, 1} // [5]int
```
* Initialize specific indices:
> The `index: value` syntax assigns values to selected indices. Unspecified indices remain zero-valued.
```go
arr := [...]int{3, 5, 4: 6, 10: 1, 2, 1}
fmt.Println(arr) // [3 5 0 0 6 0 0 0 0 0 1 2 1]
```
* Multi-dimensional arrays:
```go
arr2d := [3][2]int{
{1, 2},
{3, 4},
{5, 6},
}
arr2d[1][1] = 9
fmt.Println(arr2d) // [[1 2] [3 9] [5 6]]
```
* Slicing an array (slice expression):
> Slicing creates a slice from a selected range of elements in an array.
>
> `arr[low:high]`
>
> * `low`: Starting index (inclusive).
> * `high`: Ending index (exclusive).
```go
arr := [5]int{0, 10, 20, 30, 40}
slice := arr[1:3]
fmt.Printf("%T, %v", slice, slice) // []int, [10 20]
```
> Variants:
>
> ```go
> slice1 := arr[2:4] // [20 30]
> slice2 := arr[:4] // [0 10 20 30]
> slice3 := arr[4:] // [40]
> slice4 := arr[:] // [0 10 20 30 40]
> ```
Slicing does not copy elements. The new slice references the same underlying array.
```go
slice[0] = 99
fmt.Printf("%T, %v", slice, slice) // []int, [99 20]
fmt.Printf("%T, %v", arr, arr) // [5]int, [0 99 20 30 40]
slice = append(slice, 100)
fmt.Printf("%T, %v", slice, slice) // []int, [99 20 100]
fmt.Printf("%T, %v", arr, arr) // [5]int, [0 99 20 100 40]
```
## Slices [#slices]
In Go, a slice is a dynamic-sized, flexible view into the elements of an array.
* Declare:
```go
var slice []int // []int(nil) // (nil slice, zero length)
```
> Or initialize at declaration:
>
> ```go
> slice := []int{} // []int{} (non-nil, zero length)
> ```
>
> ```go
> slice := []int{1, 2, 3, 4, 5} // []int{1, 2, 3, 4, 5}
> ```
> Or using `make`:
>
> ```go
> slice := make([]int, 5) // []int{0, 0, 0, 0, 0} (non-zero length but zero-valued)
> ```
Slices have a length (number of elements) and a capacity (size of the underlying array). The initial capacity defaults to the initial length.
Appending beyond the current capacity allocates a larger (2x) array and copies elements to a new memory location. This is a performance-heavy operation.
```go
var slice []int // slice is initially nil (has no underlying array).
fmt.Println(len(slice)) // 0
fmt.Println(cap(slice)) // 0
slice = append(slice, 1, 2, 3, 4)
fmt.Println(len(slice)) // len: 4
fmt.Println(cap(slice)) // cap: 4
slice = append(slice, 5, 6)
fmt.Println(len(slice)) // len: 6
fmt.Println(cap(slice)) // cap: 8
slice = append(slice, 7, 8, 9)
fmt.Println(len(slice)) // len: 9
fmt.Println(cap(slice)) // cap: 16
/*
len: 0, cap: 0 [] (nil slice)
len: 1, cap: 1 [1] (allocation)
len: 2, cap: 2 [1 2] (reallocation)
len: 3, cap: 4 [1 2 3] (reallocation)
len: 4, cap: 4 [1 2 3 4]
len: 5, cap: 8 [1 2 3 4 5] (reallocation)
len: 6, cap: 8 [1 2 3 4 5 6]
len: 7, cap: 8 [1 2 3 4 5 6 7]
len: 8, cap: 8 [1 2 3 4 5 6 7 8]
len: 9, cap: 16 [1 2 3 4 5 6 7 8 9] (reallocation)
*/
```
Predefining capacity improves performance by avoiding unnecessary reallocations.
```go
slice := make([]int, 0, 20) // the third argument specifies capacity.
fmt.Println(slice) // []
fmt.Println(len(slice)) // len: 0
fmt.Println(cap(slice)) // cap: 20
```
Predefining capacity only makes sense when you have reasonable knowledge of how the data will grow or change over time.
* Append:
```go
slice := []int{1, 2, 3}
slice = append(slice, 4, 5, 6)
fmt.Println(slice) // [1 2 3 4 5 6]
```
Never use `append` on anything other than itself.
```go
func main() {
a := make([]int, 5, 7)
fmt.Println("a:", a) // a: [0 0 0 0 0]
b := append(a, 1)
fmt.Println("b:", b) // b: [0 0 0 0 0 1]
c := append(a, 2)
fmt.Println("a:", a) // a: [0 0 0 0 0]
fmt.Println("b:", b) // b: [0 0 0 0 0 2] (b got updated because of c)
fmt.Println("c:", c) // c: [0 0 0 0 0 2]
}
```
Here, `a` has remaining capacity, `b` and `c` share the same backing array. Appending through one affects the other.
This unexpected behavior would not occur if there was not enough capacity for the new element. In that case, Go would allocate a new array and copy the existing elements to it, resulting in new addresses. But still, it is prone to go unexpected.
* Prepend:
```go
slice := []int{1, 2, 3, 4, 5}
slice = append([]int{99, 98}, slice...)
fmt.Println(slice) // [99 98 1 2 3 4 5]
```
The `...` (ellipsis/expansion) operator expands a slice into individual elements.
```go
slice := []int{2, 4, 6}
otherSlice := []int{1, 3, 5}
slice = append(slice, otherSlice...)
fmt.Println(slice) // [2 4 6 1 3 5]
```
* Remove:
> Keep only the first two:
>
> ```go
> slice = slice[:2]
> ```
> Remove the last element:
>
> ```go
> slice = slice[:len(slice)-1]
> ```
> Remove a specific index:
>
> ```go
> slice = append(slice[:2], slice[3:]...) // removes index 2
> ```
Extra:
* Multi-dimensional slices:
```go
slice2d := [][]string{
{"a", "b", "c"},
{"d", "e"},
{"f", "g"},
}
slice2d[1][1] = "x"
fmt.Println(slice2d) // [[a b c] [d x] [f g]]
```
* Full slice expression:
> With a normal slice expression (`x[low:high]`), the resulting slice inherits the remaining `cap(x)-low` capacity of the underlying array.
>
> ```go
> a := []int{1, 2, 3, 4, 5}
>
> b := a[1:2]
>
> fmt.Printf("a:%v, len:%v, cap:%v", a, len(a), cap(a)) // a:[1 2 3 4 5], len:5, cap:5
> fmt.Printf("b:%v, len:%v, cap:%v", b, len(b), cap(b)) // b:[2], len:1, cap:4
> ```
> Full slice expression (`x[low:high:max]`) allows explicit capacity control (`max-low`).
>
> ```go
> c := a[1:2:3]
>
> fmt.Printf("c:%v, len:%v, cap:%v", c, len(c), cap(c)) // c:[2], len:1, cap:2
> ```
## Maps [#maps]
Maps in Go are unordered collections of key-value pairs.
> Syntax:
>
> ```go
> map[keyType]valueType
> ```
* Initialize:
```go
m := make(map[string]int)
```
> Or
```go
m := map[string]int{}
```
> Or with values:
```go
m := map[string]int{
"one": 1,
"two": 2,
"three": 3,
}
```
Maps must be initialized first (empty or with values) to make them ready to use. Declaring a map with `var m map[string]int` and then assigning values causes a `panic: assignment to entry in nil map`.
* Access:
```go
fmt.Println(m["one"]) // 1
```
* Insert or modify:
```go
m["four"] = 4
fmt.Println(m) // map[four:4 one:1 three:3 two:2]
```
* Remove:
> Can safely be used even on a non-existent key.
```go
delete(m, "two")
fmt.Println(m) // map[one:1 three:3]
```
Extra:
* Clear all elements:
```go
clear(m)
fmt.Println(m) // map[]
```
* Check if a key exists:
> The optional second return value is a boolean indicating whether the key was found.
```go
val, ok := m["two"]
fmt.Println(ok) // true
```
Maps always return a value for a key. Accessing a missing key returns the zero-value of the map value type.
```go
m := map[string]int{
"zero": 0,
"one": 1,
"two": 2,
}
fmt.Println(m["three"]) // 0
m["x"]++
fmt.Println(m) // map[one:1 two:2 x:1 zero:0]
```
* Nested maps:
```go
m2d := make(map[string]map[string]int)
m2d["a"] = map[string]int{"first": 1}
fmt.Println(m2d) // map[a:map[first:1]]
fmt.Println(m2d["a"]["first"]) // 1
```
Inner maps must also be initialized before use.
```go
func main() {
m2d := make(map[string]map[string]int)
m2d["a"]["b"] = 1 // <-- panic: assignment to entry in nil map
m2d["a"] = make(map[string]int)
m2d["a"]["b"] = 1 // <- ok
fmt.Println(m2d["a"]["b"]) // 1
}
```
## Structs [#structs]
A struct is a collection of uniquely named fields, each with a name and a type.
* Define:
```go
type person struct {
name string
age int
}
```
* Create an instance:
```go
user := person{name: "John", age: 35}
```
Any field that is not explicitly specified receives the zero-value of its type.
> Or without field names:
>
> ```go
> user := person{"John", 35}
> ```
>
> > Values must follow declaration order and include every field.
> Or zero-valued:
>
> ```go
> var user person // { 0}
> ```
* Access:
```go
fmt.Println(user.name) // John
```
* Modify:
```go
user.age = 30
fmt.Println(user.age) // 30
```
Extra:
* Embedded and nested structs:
> * The embedded struct's fields are promoted to the outer struct and can be accessed directly as if they belong to it.
> * The nested struct remains a separate field and must be accessed through its field name.
```go
type address struct {
city string
state string
zipCode string
}
type contact struct {
phone string
email string
}
type person struct {
name string
age int
address // Embedded struct
contact contact // Nested struct
}
func main() {
user := person{
name: "John",
age: 35,
address: address{
city: "Los Angeles",
state: "California",
zipCode: "00000",
},
contact: contact{
phone: "(000) 000-0000",
email: "john@example.com",
},
}
fmt.Println(user) // {John 35 {Los Angeles California 00000} {(000) 000-0000 john@example.com}}
fmt.Println(user.city) // Los Angeles
fmt.Println(user.contact.phone) // (000) 000-0000
}
```
### Struct Tags [#struct-tags]
Struct tags are metadata attached to struct fields. They are typically used by packages like `encoding/json` to control encoding and decoding behavior.
> By default, Go encodes fields using their names. When fields must be capitalized but require different names in output formats, struct tags define the external representation.
```go
type User struct {
Id int `json:"id"` // same but lowercase
Name string `json:"full_name"` // renamed field
Email string `json:"email,omitempty"` // omitted if empty ("")
Password string `json:"-"` // ignored completely
Age int `json:"age,string,omitempty"` // encoded as string
Salary int `json:"salary,omitempty"` // omitted if 0
Score *int `json:"score,omitempty"` // nil omitted, 0 still included
}
func main() {
score := 0
myUser := User{
Id: 1, Name: "John", Email: "hello@example.com", Password: "12345", Age: 26, Salary: 0, Score: &score,
}
fmt.Printf("myUser: %+v\n", myUser) // myUser: {Id:1 Name:John Email:hello@example.com Password:12345 Age:26 Salary:0 Score:0x255956d3e048}
jUser, _ := json.Marshal(myUser) // Converting struct to JSON
fmt.Printf("jUser: %+v\n", string(jUser)) // jUser: {"id":1,"full_name":"John","email":"hello@example.com","age":"26","score":0}
}
```
The `json` package only accesses the exported fields of struct types (those that begin with an uppercase letter).
`omitempty` can hide valid values like `0` or `false`. Using a pointer with `omitempty` omits only `nil` while keeping
other values.
# Declaring Variables (/docs/go/declaring-variables)
Re-declaration of a variable in the same scope is not allowed.
## Using the `var` keyword [#using-the-var-keyword]
```go
var varName varType = value
```
> Variables declared without an explicit initial value receive their zero-value.
* Either `type`, `value`, or both must be specified:
```go
var name string = "John" // explicit type and value
var surname = "Doe" // type inferred as string
var age int16 // explicit type, zero-value (0)
```
* Multiple variables in a single line, same or different types:
```go
var name, age = "John", 30 // mixed types, inferred
var a, b, c int = 1, 2, 3 // all must match the declared type
var x, y int // both zero-value (0)
```
* Grouped declaration:
```go
var (
name string = "John"
surname = "Doe" // inferred as string
age int // zero-value (0)
)
```
## Using the `:=` syntax [#using-the--syntax]
```go
varName := value
```
This syntax is only available inside functions, not at package level.
* Multiple variables in a single line:
```go
name, age := "John", 30
```
Re-declaration of a variable in the same scope is not allowed. However, if at least one identifier on the left side is new, the syntax is allowed.
```go
x := 10
x := 20 // <-- compiler: no new variables on left side of :=
x, y := 20, 30 // allowed because y is new
fmt.Println(x, y) // 20 30
```
New identifiers are declared and existing ones are reassigned.
## Using the `const` keyword [#using-the-const-keyword]
Constants are fixed values that cannot change after declaration.
```go
const varName varType = value
```
Constants must be known at compile time. They cannot depend on variables, function calls, or any other runtime values.
Expressions the compiler can evaluate at compile time are allowed. Constants are limited to booleans, numbers, and
strings.
* A constant declaration may omit the type but must include a value:
```go
const daysInWeek int = 7 // explicit type and value
const hoursInDay = 24 // type inferred as int
```
* Grouped declaration:
```go
const (
daysInWeek = 7
hoursInDay = 24
)
```
# Functions (/docs/go/functions)
## Overview [#overview]
* Declaring a function:
```go
func add(a int, b int) int {
return a + b
}
```
* Calling a function:
```go
result := add(2, 3) // result = 5
```
Extra:
* Multiple return values:
```go
func swap(a, b int) (int, int) {
return b, a
}
x, y := 1, 2
x, y = swap(x, y) // x = 2, y = 1
```
* Ignoring return values:
```go
x, _ = getCoords()
```
* Named return values:
> The function automatically returns the named variables.
```go
func calculate(x int) (result int) {
result = x * x
return
}
```
* Variadic functions:
> Accept zero or more arguments of the same type, which are treated as a slice inside the function.
```go
func sum(numbers ...int) int {
total := 0
for _, number := range numbers {
total += number
}
return total
}
sum(2, 5, 7, 10) // 24
```
* First-class functions:
> Functions can be assigned, passed, and returned.
```go
func main() {
price := 100.00
fmt.Printf("Regular user price: $%.2f\n", applyDiscount(price, regularDiscount)) // Regular user price: $90.00
fmt.Printf("VIP user price: $%.2f\n", applyDiscount(price, vipDiscount)) // VIP user price: $80.00
}
func vipDiscount(price float64) float64 {
return price * 0.8
}
func regularDiscount(price float64) float64 {
return price * 0.9
}
func applyDiscount(price float64, strategy func(float64) float64) float64 {
return strategy(price)
}
```
* Anonymous functions:
> Anonymous functions are functions without a name.
```go
func main() {
func() {
fmt.Println("Hello, world!")
}() // immediately invoking the anonymous function
}
```
> Assigning an anonymous function to a variable:
>
> ```go
> myVar := func(a, b int) {
> fmt.Println(a + b)
> }
>
> myVar(1, 2) // 3
> ```
## Pass-by Value & Reference [#pass-by-value--reference]
All arguments in Go are passed by value. The difference is what gets copied.
* Pass-by Value:
> Pure value types copy the actual data. The function works with its own copy. Changes made inside the function stay local and do not affect the original.
```go
func increment(num int) {
num++
fmt.Println("Inside:", num) // Inside: 6
}
func main() {
num := 5
increment(num)
fmt.Println("Outside:", num) // Outside: 5
}
```
Pure Value Types (`pass-by-value`): **Booleans**, **Numerics**, **Arrays**, **Structs**.
```go
a := [3]int{2, 4, 6} // array
b := a
b[1] = 99
fmt.Println(a, b) // [2 4 6] [2 99 6]
```
* Pass-by Reference:
> Reference-containing types copy a value that references shared underlying data. Changes to that data are visible outside.
```go
func change(s []int) {
s[0] = 99
}
func main() {
nums := []int{1, 2, 3}
fmt.Println(nums) // [1 2 3]
change(nums)
fmt.Println(nums) // [99 2 3]
}
```
Reference-Containing Types (`pass-by-reference`): **Strings** (immutable), **Slices**, **Maps**, **Channels**, **Pointers** (\&x).
```go
a := []int{2, 4, 6} // slice
b := a
b[1] = 99
fmt.Println(a, b) // [2 99 6] [2 99 6]
```
Even though a value may allow modification of shared underlying data, the variable itself is still passed by value. Reassigning the parameter inside the function changes only the local copy and does not affect the original variable in the caller.
```go
func reassignSlice(s []int) {
s = []int{100, 200, 300}
s[0] = 99
}
func main() {
nums := []int{1, 2, 3}
fmt.Println("Before:", nums) // Before: [1 2 3]
reassignSlice(nums)
fmt.Println("After:", nums) // After: [1 2 3]
}
```
> another example:
```go
func addItem(s []int, v int) {
s = append(s, v)
}
func main() {
nums := []int{1, 2, 3}
fmt.Println("Before:", nums) // Before: [1 2 3]
addItem(nums, 4)
fmt.Println("After:", nums) // After: [1 2 3]
}
```
## Closures [#closures]
Closures are functions that capture and use variables from their surrounding scope, even after that scope ends.
Examples:
1. > ```go
> func sum() func(int) int {
> total := 0
>
> return func(number int) int {
> total += number
> return total
> }
> }
>
> func main() {
> add1 := sum()
> add2 := sum()
>
> fmt.Println(add1(1)) // 1
> fmt.Println(add1(2)) // 3
> fmt.Println(add1(3)) // 6
>
> fmt.Println(add2(1)) // 1
> fmt.Println(add2(2)) // 3
> fmt.Println(add2(6)) // 9
> }
> ```
>
> Each call to `sum()` returns a new closure with its own independent variables (`total`), allowing `add1` and `add2` to maintain separate internal state.
2. > ```go
> func fibonacci() func() int {
> a, b := 0, 1
>
> return func() int {
> a, b = b, a+b
> return a
> }
> }
>
> func main() {
> f := fibonacci()
>
> for range 10 {
> fmt.Println(f())
> }
> }
>
> // 1
> // 1
> // 2
> // 3
> // 5
> // 8
> // 13
> // 21
> // 34
> // 55
> ```
## The `defer` Keyword [#the-defer-keyword]
The `defer` keyword schedules a function call or statement to execute at the end of the current function's execution.
```go
func main() {
defer fmt.Println("done")
fmt.Println("work")
}
// work
// done
```
Extra:
* `defer` depends only on the surrounding function scope:
> `defer` is registered when execution reaches that line but runs when the surrounding function ends. It does not run when a block such as `if` or `for` ends, even if it appears inside them.
```go
func main() {
fmt.Println("start")
if true {
defer fmt.Println("inside if")
fmt.Println("in block")
}
fmt.Println("end of function")
}
// start
// in block
// end of function
// inside if
```
* Multiple defers:
> Multiple deferred statements are executed in last-in-first-out (LIFO) order. The most recently deferred function runs first.
```go
func main() {
defer sayBye()
fmt.Println("1")
defer fmt.Println("2")
fmt.Println("3")
fmt.Println(myFunc())
}
func myFunc() string {
defer fmt.Println("4")
return "5"
}
func sayBye() {
fmt.Println("bye")
}
// 1
// 3
// 4
// 5
// 2
// bye
```
# Generics (/docs/go/generics)
## Generic Functions [#generic-functions]
Allow a single function to operate on multiple types while keeping compile-time type safety.
> Syntax:
>
> ```go
> func functionName[T constraint](param T) returnType {
> //
> }
> ```
Extra:
* > Go does not support union types directly.
>
> ```go
> type number int | float64 // <-- syntax error
> ```
>
> Instead, define a type-set using an interface for use as a constraint:
>
> ```go
> type number interface {
> int | float64
> }
> ```
>
> > The `|` operator is only available in type constraints. It defines a set of allowed types for a type parameter.
>
> Usage:
>
> ```go
> func add[T number](a T, b T) T {
> return a + b
> }
> ```
>
> > The `|` operator can also be used inline without declaring a named constraint:
> >
> > ```go
> > func add[T int | float64](a T, b T) T {
> > return a + b
> > }
> > ```
* > To include named types whose underlying type matches a constraint, use `~`:
>
> ```go
> type number interface {
> ~int | ~float64
> }
> ```
>
> > `~int` means `int` and any named type with underlying type `int`.
>
> ```go
> type myInt int
>
> func add[T ~int | ~float64](a T, b T) T {
> return a + b
> }
>
> func main() {
> var a myInt = 5
> var b myInt = 10
>
> fmt.Println(add(a, b)) // 15
> }
> ```
>
> > Why?
> >
> > Because in Go, named types are distinct from their underlying types, even if they share the same representation.
> >
> > The `~` operator allows constraints to match based on the underlying type instead of only the exact type.
> >
> > ```go
> > type myInt int
> >
> > func main() {
> > var a myInt = 10
> > var b = 20
> >
> > a = b // <-- compiler: cannot use b (variable of type int) as myInt value in assignment
> >
> > a = myInt(b) // <- ok (compatible for type casting)
> >
> > fmt.Println(a, b) // 20 20
> > }
> > ```
Examples:
1. > ```go
> func main() {
> fmt.Println(add(1, 2)) // 3
> fmt.Println(add(1.5, 2.3)) // 3.8
> }
>
> func add[T int | float64](a T, b T) T {
> return a + b
> }
> ```
>
> > Without generics:
> >
> > ```go
> > func main() {
> > fmt.Println(addInts(1, 2)) // 3
> > fmt.Println(addFloats(1.5, 2.3)) // 3.8
> > }
> >
> > func addInts(a, b int) int {
> > return a + b
> > }
> >
> > func addFloats(a, b float64) float64 {
> > return a + b
> > }
> > ```
2. > ```go
> func main() {
> fmt.Println(swap(2.5, 5)) // 5, 2.5
> fmt.Println(swap("Hello", 99)) // 99, Hello
> }
>
> func swap[T any, U any](a T, b U) (U, T) {
> return b, a
> }
> ```
3. > ```go
> type gasEngine struct {
> hp int
> }
>
> type electricEngine struct {
> kWh int
> }
>
> type car[T gasEngine | electricEngine] struct {
> model string
> year int
> engine T
> }
>
> func main() {
> gCar := car[gasEngine]{
> model: "Audi",
> year: 2018,
> engine: gasEngine{
> hp: 385,
> },
> }
>
> eCar := car[electricEngine]{
> model: "Tesla",
> year: 2022,
> engine: electricEngine{
> kWh: 60,
> },
> }
>
> fmt.Println(gCar, eCar) // {Audi 2018 {385}} {Tesla 2022 {60}}
> }
> ```
## Generic Types [#generic-types]
Generic types define reusable structures that works with different data types.
> Syntax:
>
> ```go
> type typeName[T constraint] struct {
> fieldName T
> }
> ```
Example:
1. > ```go
> type List[T any] struct {
> next *List[T]
> val T
> }
> ```
# Home (/docs/go)
# Interfaces (/docs/go/interfaces)
## Overview [#overview]
In Go, an interface is a type that defines a set of method signatures. A type satisfies an interface by implementing all of its methods.
> Interfaces enable flexible code. Functions can operate on any type that satisfies the required methods. A type may satisfy multiple interfaces, and an interface may be satisfied by many types.
* Define:
```go
type shape interface {
area() float64
perimeter() float64
}
```
> Here, the `shape` interface defines two method signatures: `area()` and `perimeter()`. Any type that implements both methods satisfies `shape`.
* Implement:
```go
type circle struct {
radius float64
}
func (c circle) area() float64 {
return math.Pi * c.radius * c.radius
}
func (c circle) perimeter() float64 {
return 2 * math.Pi * c.radius
}
```
```go
type rect struct {
width float64
height float64
}
func (r rect) area() float64 {
return r.width * r.height
}
func (r rect) perimeter() float64 {
return 2*r.width + 2*r.height
}
```
> Both `circle` and `rect` satisfy `shape` by implementing all required methods. This happens automatically, no explicit declaration is needed.
Interface satisfaction also depends on method receivers. Methods with value receivers belong to both `T` and `*T`. Methods with pointer receivers belong only to `*T`.
```go
type speaker interface {
sayHello()
}
type person struct {
name string
}
func (d *person) sayHello() {
fmt.Println("Hello, my name is " + d.name)
}
func main() {
var s speaker
p := person{name: "John"}
// s = p // <-- compiler: cannot use p (variable of struct type person) as speaker value in assignment: person does not implement speaker (method sayHello has pointer receiver)
s = &p
s.sayHello() // Hello, my name is John
}
```
* Use:
```go
func printArea(s shape) {
fmt.Println("Area:", s.area())
fmt.Println("Perimeter:", s.perimeter())
}
func main() {
myCircle := circle{radius: 3}
printArea(myCircle)
// Area: 28.274333882308138
// Perimeter: 18.84955592153876
myRect := rect{width: 3, height: 4}
printArea(myRect)
// Area: 12
// Perimeter: 14
}
```
> Functions can accept interface types as parameters, which lets them work with any type that satisfies the interface.
Examples:
1. > Sorting a slice using [`Sort` function ↗](https://pkg.go.dev/sort#Sort) from the `sort` package.
>
> The `Sort` function accepts data that implements an interface. To pass the slice to it, we need to satisfy [that interface ↗](https://pkg.go.dev/sort#Interface). It requires us to have `Len() int`, `Less(i, j int) bool`, and `Swap(i, j int)` methods.
>
> ```go
> import (
> "fmt"
> "sort"
> )
>
> type ages []uint8
>
> func (a ages) Len() int {
> return len(a)
> }
>
> func (a ages) Swap(i, j int) {
> a[i], a[j] = a[j], a[i]
> }
>
> func (a ages) Less(i, j int) bool {
> return a[i] < a[j]
> }
>
> func main() {
> studentAges := ages{19, 18, 22, 20, 20, 18}
> sort.Sort(studentAges)
>
> fmt.Println(studentAges) // [18 18 19 20 20 22]
> }
> ```
2. > Change how `fmt` behaves for your own type.
>
> The `fmt` package checks whether a value satisfies the [`Stringer` interface ↗](https://pkg.go.dev/fmt#Stringer). This interface requires a single method, `String() string`. If a type implements that method, `fmt` uses it automatically when printing. Otherwise, it falls back to the default representation.
>
> ```go
> import (
> "fmt"
> )
>
> type ipAddr [4]byte
>
> func (i ipAddr) String() string {
> return fmt.Sprintf("is: %d.%d.%d.%d", i[0], i[1], i[2], i[3]) // prints the address as a dotted quad
> }
>
> func main() {
> hosts := map[string]ipAddr{
> "loopback": {127, 0, 0, 1},
> "googleDNS": {8, 8, 8, 8},
> }
>
> for name, ip := range hosts {
> fmt.Println(name, ip)
> }
> }
>
> // loopback is: 127.0.0.1
> // googleDNS is: 8.8.8.8
> ```
>
> As you can see from the output, `fmt` prints the map keys using the default behavior because they are plain `string` values. For the map values, it detects that they are of type `IPAddr` and automatically uses the custom `String()` method.
3. > Customize printing errors.
>
> Go programs express error state with error values. The built-in `error` type is an interface and defined like:
>
> ```go
> type error interface {
> Error() string
> }
> ```
>
> If a type implements the `Error() string` method, it satisfies the `error` interface. The `fmt` package also looks for the `error` interface when printing values, so if a value is an error, `fmt` uses its `Error()` method.
>
> ```go
> import (
> "fmt"
> )
>
> type errNegativeVal int
>
> func (e errNegativeVal) Error() string {
> return fmt.Sprintf("Number can't be negative: %v", int(e))
> }
>
> func twoTimes(x int) (int, error) {
> if x < 0 {
> return 0, errNegativeVal(x)
> }
>
> return x * 2, nil
> }
>
> func main() {
> fmt.Println(twoTimes(4)) // 8
> fmt.Println(twoTimes(2)) // 4
> fmt.Println(twoTimes(-2)) // 0 Number can't be negative: -2
> }
> ```
## Empty Interface [#empty-interface]
An empty interface (`interface{}`) defines zero methods, so all types satisfy it. The alias `any` can also be used instead of `interface{}`.
```go
func main() {
var x interface{}
x = 5
x = "hello"
x = true
fmt.Println(x) // true
}
```
### Type Assertion [#type-assertion]
A type assertion compares an interface value with a specific type and returns the underlying value if it matches.
> Syntax:
>
> ```go
> val, ok := x.(assertedType)
> ```
>
> * `assertedType`: Can be any type, including named types and pointer types.
> * `val`: The extracted value. If the assertion fails, it is the zero-value of the asserted type.
> * `ok`: A boolean indicating whether the assertion succeeded.
```go
func main() {
var x interface{} = "Hello"
val, ok := x.(string)
if ok {
fmt.Println("It's a string:", val)
} else {
fmt.Println("Not a string")
}
}
// It's a string: Hello
```
Omitting `ok` causes a panic on failure:
```go
func main() {
var i interface{} = "hello"
s1, ok1 := i.(string)
fmt.Println(s1, ok1) // hello true
s2 := i.(string)
fmt.Println(s2) // hello
f1, ok2 := i.(float64)
fmt.Println(f1, ok2) // 0 false
f2 := i.(float64) // <-- panic: interface conversion: interface {} is string, not float64
fmt.Println(f2)
}
```
> Here is an example showing usage with the `shape` interface defined above:
>
> ```go
> // ...
>
> func identifyShape(s shape) {
> val, ok := s.(circle)
> if ok {
> fmt.Println("Shape is a circle, val:", val)
> } else {
> fmt.Println("Shape is not a circle")
> // val is zero-value here
> }
> }
>
> func main() {
> // ...
>
> identifyShape(myCircle) // Shape is a circle, val: {3}
> }
> ```
### Type Switches [#type-switches]
A type switch compares an interface value against multiple types.
```go
func describe(i interface{}) {
switch v := i.(type) {
case string:
fmt.Println("A string", v)
case int:
fmt.Println("An int", v)
default:
fmt.Println("Unknown type", v)
}
}
func main() {
x := 5
describe(x) // An int 5
}
```
> Type switches also work with named types and pointer types, not just basic types.
>
> ```go
> type user struct {
> name string
> }
>
> func describe(i interface{}) {
> switch v := i.(type) {
> case *user:
> fmt.Println("Pointer to User", v.name)
> case user:
> fmt.Println("User value", v.name)
> default:
> fmt.Println("Unknown type", v)
> }
> }
>
> func main() {
> u := user{name: "John"}
> describe(u) // User value John
> describe(&u) // Pointer to user John
> }
> ```
Examples:
1. > ```go
> var m = map[string]interface{}{
> "Name": "Wednesday",
> "Age": 6,
> "Parents": []interface{}{
> "Gomez",
> "Morticia",
> },
> }
>
> func main() {
> for k, v := range m {
> switch vv := v.(type) {
> case string:
> fmt.Println(k, "is string", vv)
> case float64:
> fmt.Println(k, "is float64", vv)
> case []interface{}:
> fmt.Println(k, "is an array:")
> for i, u := range vv {
> fmt.Println(i, u)
> }
> default:
> fmt.Println(k, "is of a type I don't know how to handle")
> }
> }
> }
>
> // Name is string Wednesday
> // Age is of a type I don't know how to handle
> // Parents is an array:
> // 0 Gomez
> // 1 Morticia
> ```
## Interface Composition [#interface-composition]
Interface composition combines existing interfaces into a new one.
```go
type Reader interface {
Read(p []byte) (n int, err error)
}
type Writer interface {
Write(p []byte) (n int, err error)
}
type ReadWriter interface {
Reader
Writer
}
```
> The `ReadWriter` interface requires both `Read` and `Write` methods. Any type that implements both methods automatically satisfies the `ReadWriter` interface.
If multiple interfaces are composed and they contain methods with the same name, those methods must have identical
signatures in all interfaces.
# Loops (/docs/go/loops)
## Overview [#overview]
* Classic loop:
```go
for i := 0; i < 5; i++ {
fmt.Println(i)
}
// 0
// 1
// 2
// 3
// 4
```
* While loop:
```go
i := 0
for i < 5 {
fmt.Println(i)
i++
}
// 0
// 1
// 2
// 3
// 4
```
* Infinite loop:
```go
for {
fmt.Println("running")
}
// running
// running
// running
// running
// ... (infinite)
```
* Range loop:
> Used with integers, strings, arrays, slices, maps, and channels.
```go
for i := range 3 {
fmt.Println(i)
}
// 0
// 1
// 2
```
```go
nums := []int{10, 20, 30}
for i, v := range nums {
fmt.Println(i, v)
}
// 0 10
// 1 20
// 2 30
```
## Control Keywords [#control-keywords]
* `break`: Stops (quits) the loop.
```go
for i := 0; i < 5; i++ {
if i == 2 {
break
}
fmt.Println(i)
}
// 0
// 1
```
* `continue`: Skips to the next iteration.
```go
for i := 0; i < 5; i++ {
if i == 2 {
continue
}
fmt.Println(i)
}
// 0
// 1
// 3
// 4
```
### Labeled Loops [#labeled-loops]
A labeled loop allows `break` or `continue` to target a specific loop in nested structures.
```go
outerLoop:
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
if i == j {
continue outerLoop
}
fmt.Println(i, j)
}
}
// 1 0
// 2 0
// 2 1
```
# Methods (/docs/go/methods)
In Go, a method is a function with a receiver argument associated with a specific type. It defines behavior for instances of that type.
Methods can only be defined on named types. They cannot be defined on unnamed types such as `[]int` or `map[string]int`.
A named type is declared using the `type` keyword.
```go
type myInt int
```
```go
type person struct {
name string
age int
}
```
> Syntax:
>
> ```go
> func (receiver receiverType) methodName(parameters) returnType {
> // method body
> }
> ```
>
> * `receiver`: The variable that represents the instance the method is called on.
> * `receiverType`: The type the method is attached to.
> * `methodName`: The name of the method being defined.
> * `parameters`: The input arguments the method accepts (optional).
> * `returnType`: The value type the method returns (optional).
* Declare:
```go
type person struct {
name string
age int
}
func (p person) sayHello() {
fmt.Println("Hello, my name is " + p.name)
}
```
A method can only be declared on a receiver type defined in the same package.
* Call:
```go
user := person{name: "John", age: 35}
user.sayHello() // Hello, my name is John
```
Extra:
* Pointer receivers.
> To modify original data for types with `pass-by-value` semantics, the method must use a pointer receiver.
>
> ```go
> type myCounter int
>
> func (mc *myCounter) increment() {
> *mc++
> }
>
> func main() {
> count := myCounter(0)
>
> count.increment()
> count.increment()
>
> fmt.Printf("count: %v\n", count) // count: 2
> }
> ```
>
> Another example:
>
> ```go
> func (p *person) changeName(name string) {
> p.name = name // `(*p).name = name` is also valid, but unnecessary in Go.
> }
>
> func main() {
> user := person{name: "John", age: 35}
>
> user.sayHello() // Hello, my name is John
>
> user.changeName("Jane")
>
> user.sayHello() // Hello, my name is Jane
> }
> ```
>
> > Go automatically dereferences struct pointers (`T` to `*T`) when accessing fields. This is why `p.name = name` can be used instead of `(*p).name = name`.
The automatic `T` to `*T` conversion only happens when the value is addressable.
A value is addressable if it has a stable memory location.
```go
type person struct {
name string
}
func (p *person) sayHello() {
fmt.Println("Hello, my name is", p.name)
}
func main() {
user := person{name: "John"}
user.sayHello() // Hello, my name is John
person{name: "John"}.sayHello() // <-- compiler: cannot call pointer method sayHello on person
}
```
> `user` is a variable with a stable address. The compiler can take `&user` implicitly.
> `person{name: "John"}` is a temporary value without a stable address. The compiler cannot take its address, so the call does not compile.
>
> > To make it work, take the address explicitly:
> >
> > ```go
> > (&person{name: "John"}).sayHello() // Hello, my name is John
> > ```
* Embedded structs with methods.
> Methods from an embedded struct are also promoted to the outer struct and can be called directly.
>
> ```go
> type person struct {
> name string
> age int
> }
>
> func (p person) sayHello() {
> fmt.Println("Hello, my name is", p.name)
> }
>
> type employee struct {
> person
> company string
> }
>
> func main() {
> user := person{name: "John", age: 35}
> user.sayHello() // Hello, my name is John
>
> user2 := employee{person{name: "Jane", age: 28}, "Google"}
> user2.sayHello() // Hello, my name is Jane
> }
> ```
> If the outer struct defines a method with the same name, that method is used instead of the promoted one. The embedded method is shadowed but can still be accessed through the embedded field.
>
> ```go
> func (e employee) sayHello() {
> fmt.Println("Hello, my name is", e.name, "and I'm working at", e.company)
> }
>
> func main() {
> user := person{name: "John", age: 35}
> user.sayHello() // Hello, my name is John
>
> user2 := employee{person{name: "Jane", age: 28}, "Google"}
> user2.sayHello() // Hello, my name is Jane and I'm working at Google
>
> user2.person.sayHello() // Hello, my name is Jane
> }
> ```
# Pointers (/docs/go/pointers)
A pointer is a variable that stores the memory address of a value. It allows direct access to the original value without copying it.
```go
var p *int
```
> Zero-value: `nil`.
* `&p`: Address of `p`.
* `*p`: Value pointed to by `p` (dereferencing).
```go
func main() {
a := 10
fmt.Println(a) // 10
fmt.Printf("%T\n", a) // int
// Declare a pointer and assign it the address of `a`:
ptr := &a
fmt.Println(ptr) // 0xed92788e008
fmt.Printf("%T\n", ptr) // *int
fmt.Println(*ptr) // 10
// Change the value through the pointer:
*ptr = 20
fmt.Println(a) // 20
}
```
> Using pointers as function parameters passes a memory address instead of a value copy. This overrides Go's default `pass-by-value` behavior and allows modification of the original data.
>
> ```go
> func main() {
> num := 10
> fmt.Println(num) // 10
>
> resetVal(num)
> fmt.Println(num) // 10
>
> resetPtr(&num)
> fmt.Println(num) // 0
> }
>
> func resetVal(val int) {
> val = 0
> }
>
> func resetPtr(val *int) {
> *val = 0
> }
> ```
> Pointers as function parameters also improve efficiency for large data structures.
>
> No unnecessary copying = Better performance.
>
> * Without pointer:
>
> ```go
> func main() {
> arr := [5]int{1, 2, 3, 4, 5}
>
> fmt.Printf("mem addr (arr): %p, arr: %v\n", &arr, arr) // mem addr (arr): 0xc00011e000, arr: [1 2 3 4 5]
> myFunc(arr) // mem addr (items): 0xc00011e060, items: [1 2 3 4 5]
> }
>
> func myFunc(items [5]int) [5]int {
> fmt.Printf("mem addr (items): %p, items: %v\n", &items, items)
> return items
> }
> ```
>
> * With pointer:
>
> ```go
> func main() {
> arr := [5]int{1, 2, 3, 4, 5}
>
> fmt.Printf("mem addr (arr): %p, arr: %v\n", &arr, arr) // mem addr (arr): 0xc00011e000, arr: [1 2 3 4 5]
> myFunc(&arr) // mem addr (items): 0xc00011e000, items: [1 2 3 4 5]
> }
>
> func myFunc(items *[5]int) [5]int {
> fmt.Printf("mem addr (items): %p, items: %v\n", items, *items)
> return *items
> }
> ```
>
> Arrays are `pass-by-value` types in Go (like booleans, numerics, and structs). Passing them creates a full copy. Using pointers avoids that copying.
# References (/docs/go/references)
1. Read: [Tour of Go](https://go.dev/tour/welcome/1).
2. Watch (playlist): [Go Class by Matt KØDVB](https://www.youtube.com/watch?v=iDQAZEJK8lI\&list=PLoILbKo9rG3skRCj37Kn5Zj803hhiuRK6)
3. Read: [Effective Go](https://go.dev/doc/effective_go).
4. Watch (30:58): [GopherCon 2016: Understanding nil - Francesc Campoy](https://youtu.be/ynoY2xz-F8s).
5. Watch (22:28): [Gopherfest 2015 | Go Proverbs with Rob Pike](https://youtu.be/PAAkCSZUG1c).
6. Watch (51:26): [Google I/O 2012 - Go Concurrency Patterns](https://youtu.be/f6kdp27TYZs).
7. Read: [The Go Blog](https://go.dev/blog/).
8. Read: [The Go Programming Language Specification](https://go.dev/ref/spec).
# String Formatting (/docs/go/string-formatting)
* General:
| Placeholder | Description | Usage | Output |
| ----------- | -------------------------------------- | ---------------------------------------- | -------------------- |
| `%v` | Default variable format. | `("%v", 123)` | `123` |
| `%+v` | Struct format with field names. | `("%+v", Person{Name: "John", Age: 35})` | `{Name:John Age:35}` |
| `%#v` | Go syntax representation of the value. | `("%#v", []int{1, 2, 3})` | `[]int{1, 2, 3}` |
| `%T` | Type of the value. | `("%T", 123)` | `int` |
| `%p` | Hexadecimal memory address. | `("%p", &x)` | `0xc000098040` |
| `%%` | Literal `%` sign. | `("%%")` | `%` |
* Boolean:
| Placeholder | Description | Usage | Output |
| ----------- | -------------- | -------------- | ------ |
| `%t` | Boolean value. | `("%t", true)` | `true` |
* Integer:
| Placeholder | Description | Usage | Output |
| ----------- | ------------------------------------------ | ----------------------------- | ------------------ |
| `%d` | Integer in base 10. | `("%d", 123)`, `("%d", 'A')` | `123`, `65` |
| `%b` | Integer in base 2. | `("%b", 123)` | `1111011` |
| `%o` | Integer in base 8. | `("%o", 123)` | `173` |
| `%x` | Integer in base 16 with lowercase letters. | `("%x", 123)` | `7b` |
| `%X` | Integer in base 16 with uppercase letters. | `("%X", 123)` , `("%X", 'é')` | `7B`, `E9` |
| `%c` | Unicode code point character. | `("%c", 65)`, `("%c", 'A')` | `A`, `A` |
| `%U` | Unicode code point. | `("%U", 65)`, `("%U", 'é')` | `U+0041`, `U+00E9` |
* Floats:
| Placeholder | Description | Usage | Output |
| ----------- | ------------------------------------------ | ----------------- | -------------- |
| `%f` | Decimal format for floating-point numbers. | `("%f", 123.456)` | `123.456000` |
| `%e` | Scientific notation with lowercase e. | `("%e", 123.456)` | `1.234560e+02` |
| `%E` | Scientific notation with uppercase E. | `("%E", 123.456)` | `1.234560E+02` |
* String (slice of bytes):
| Placeholder | Description | Usage | Output |
| ----------- | -------------------------------------- | -------------------- | ---------- |
| `%s` | String (uninterpreted) without quotes. | `("%s", "hello \n")` | `hello \n` |
| `%q` | Double-quoted string. | `("%q", "hello")` | `"hello"` |
Examples:
1. > ```go
> name := "John"
> age := 35
> char := 97
> fmt.Printf("Name: %s, Age: %d, Char: %c ", name, age, char) // Name: John, Age: 35, Char: a
> ```
2. > ```go
> pi := 3.14159
> fmt.Printf("Pi: %.2f", pi) // Pi: 3.14
> ```
3. > `[n]` references the n-th argument in `fmt`, allowing reuse of the same evaluated value (optimizing).
>
> ```go
> func expensiveFunc(a int) int {
> fmt.Println("Calculated")
> return a
> }
> ```
>
> * Unoptimized:
>
> ```go
> func main() {
> fmt.Printf("%v and %v", expensiveFunc(5), expensiveFunc(5))
> }
>
> // Calculated
> // Calculated
> // 5 and 5
> ```
>
> * Optimized:
>
> ```go
> func main() {
> fmt.Printf("%[1]v and %[1]v", expensiveFunc(5))
> }
>
> // Calculated
> // 5 and 5
> ```
# Type Casting (/docs/go/type-casting)
Type casting is the explicit conversion of a value from one compatible type to another.
```go
newValue := targetType(value)
```
> Go does not allow implicit conversions. This prevents hidden bugs and keeps behavior predictable.
>
> ```go
> a := 5.6 // float64
> b := 10 // int
>
> c := a + b // <-- compiler: invalid operation: a + b (mismatched types float64 and int)
>
> c := a + float64(b) // 15.6 (float64)
> ```
* Casting from `float` to `integer` removes (cuts off) the decimal part:
```go
a := 5.6 // float64
b := int16(a) // 5 (int16)
c := float64(b) // 5 (float64)
```
* Casting between integer sizes must also be explicit:
```go
var a int64 = 100
var b int32 = 50
c := int32(a) + b // 150 (int32)
```
* Casting from `string` to `[]byte` or `[]rune` changes the representation:
```go
a := "1aé"
b := []byte(a) // [49 97 195 169] (UTF-8 bytes)
c := []rune(a) // [49 97 233] (Unicode code points)
```
* Some types cannot be cast directly if they are not compatible:
```go
a := "123"
b := int(a) // <-- compiler: cannot convert a (variable of type string) to type int
```
# Aliases (/docs/git/aliases)
Git aliases are custom shortcuts you create to make Git commands quicker and easier to type.
* Create:
```sh
git config --global alias. ''
```
> Example:
>
> ```sh
> git config --global alias.lo 'log --oneline'
> ```
* Remove:
```sh
git config --global --unset alias.
```
* List:
```sh
git config --global --list
```
> Shows all global config entries including your aliases.
# Branches (/docs/git/branches)
## Overview [#overview]
A Git branch is an independent line of development within a repository. Branches allow you to isolate changes and work on them independently.
In a Git repository, there is a default branch (usually called `main` or `master`). Beyond that, you can create other branches to develop new features, fix bugs, test ideas, or work on updates without affecting the main codebase.
What is a branch reference?
> A branch reference is a pointer in Git that refers to a specific commit.
>
> * It's a file named after the branch and stored in `.git/refs/heads/`.
> * The file contains the hash of the latest commit on that branch.
> * When you make a new commit, Git updates this file with the new commit hash.
> * Creating a new branch simply means creating a new file in `.git/refs/heads/`.
> > You can even do this manually by creating a file and writing a commit hash inside it. The file name becomes the branch name, and it starts from the commit you specified.
What is `HEAD`?
> `HEAD` is a pointer in Git that represents your current position in the repository.
>
> * It's a file named `HEAD` in `.git/` that usually points to the branch reference of the current branch.
> * When you switch branches, Git updates `HEAD` to point to the new branch reference.
> * Attached HEAD:
> > This is the normal state where `HEAD` points to a branch reference. Any new commits you make are added to that branch, and `HEAD` moves forward along with it.
> * Detached HEAD:
> > This occurs when `HEAD` points directly to a specific commit hash instead of a branch reference. In this state, new commits aren't associated with any branch, and you might need to create a new branch to save your work.
> You can also use it instead of ``:
>
> * `HEAD`: The current (latest) commit.
> * `HEAD~`: The commit `n` steps before `HEAD` (e.g., `HEAD~2`).
## Core Branching Commands [#core-branching-commands]
* `git branch`: List all existing branches.
> * `` - Create a new branch based on the current `HEAD`.
>
> * ` ` - Create a new branch from a specific commit.
>
> * `-d ` - Delete a branch if it has already been merged.
>
> > Use `-D` to force deletion even if it hasn't been merged.
>
> > You cannot delete the branch you're currently on. Switch first.
>
> * `-M ` - Rename the branch you're on.
> > Use `-m ` to rename a different branch.
>
> * `-vv` - Show local branches with their remote tracking information.
>
> * `-a` - List both local and remote branches.
>
> * `-r` - List only remote-tracking branches.
* `git switch `: Switch to the given branch.
> * `-c` - Create and switch to a new branch.
> > Use `-C` to recreate a branch if it already exists.
> Use `-` instead of a branch name to switch back to the previous branch.
When you switch branches, Git updates your project's file tree to match the state of that branch.
If you try to switch while having uncommitted changes:
* Without conflicts:
Git will carry your changes to the new branch with you.
* With conflicts:
Git will block the branch switch. You'll be asked to commit, stash, or discard your changes before switching.
## Merging Branches [#merging-branches]
Merging in Git is the process of combining changes from one branch into another. The changes from the source branch are integrated into the target branch.
* `git merge `: Merge changes from the specified branch into the current branch.
> * `--squash` - Combine all commits from the merged branch into the staging area of the current branch.
> > Allows committing all changes as a single commit to keep history clean.
> If you encounter conflicts or issues during a merge, you can use `git merge --abort` to cancel the process or resolve them.
### Fast-forward Merge [#fast-forward-merge]
This type of merge occurs when no new commits have been made on the target branch since the source branch was created.
> In such cases, Git simply moves the target branch pointer forward to the latest commit on the source branch without creating a new merge commit. This results in a linear commit history.
* `git merge --no-ff `: Always create a merge commit even when a fast-forward is possible.
### Three-way Merge [#three-way-merge]
This type of merge occurs when both branches have new commits.
> In such cases, Git compares the changes made in both branches relative to their common ancestor and tries to combine them automatically.
>
> If both branches modify the same lines, Git can't decide which version to keep. This is called a merge conflict. When conflicts occur, Git waits you to resolve them manually.
Resolving merge conflicts:
> 1. Git reports a merge conflict and shows which files are affected.
> 2. The conflicted files contain special markers showing differences between branches.
> > ```
> > <<<<<<< HEAD
> > your content on current branch
> > =======
> > incoming content from the other branch
> > >>>>>>> dev
> > ```
> 3. Edit the files to decide which changes to keep.
> > You can choose one version or combine parts of both.
> 4. Remove the conflict markers and save the files.
> 5. Stage the resolved files.
> 6. Create a commit to finish the merge.
## Cherry Picking [#cherry-picking]
Cherry-picking in Git means taking specific commits from one branch and applying them to another branch without merging the entire branch.
* `git cherry-pick ...`: Apply the changes from a specific commit (from another branch) to the current branch.
Cherry-picking creates new commits with different commit IDs. This can lead to duplicate commits if the process is not
managed carefully and the branches are merged later.
# Configuration (/docs/git/configuration)
* `git init`: Initialize a new Git repository in the current folder.
> This sets up a `.git` directory that stores all version control data and enables Git to start tracking changes in your project.
* Configure your Git identity.
> ```sh
> git config --global user.name ""
> ```
>
> ```sh
> git config --global user.email ""
> ```
>
> Without `--global`, the configuration applies only to the current repository.
> If you want to keep your email private, you can use GitHub's no-reply email (found in your GitHub email settings), e.g., `123456789+username@users.noreply.github.com`.
* `git config --list`: View your current Git configuration settings.
> * `--global` - View global settings (saved in your machine).
> * `--edit` - Open the configuration file in your default text editor for manual editing.
# Discarding Changes (/docs/git/discarding-changes)
* `git clean -f`: Remove untracked files from the working directory. 1️⃣ -> ❌
> * `-d` - Remove untracked directories too.
> * `-n` - Preview what would be removed without actually deleting anything.
* `git restore ...`: Discard unstaged changes in modified files. 1️⃣ -> ❌
> * `--staged` - Unstage files (move them from the staging area back to unstaged). 2️⃣ -> 1️⃣
> * `--source ` - Restore files to their state right after the specified commit. 3️⃣ -> ❌ -> 1️⃣
> > It doesn't matter if the given commit was related to the targeted files, it restores them exactly as they were at that point.
* `git revert `: Create a new commit that reverses the changes introduced by the specified commit.
> You may be asked to resolve conflicts. In such cases, you can use `git revert --abort` to cancel the process or resolve them.
* `git reset `: Rewind the repository to the specified commit state. 3️⃣ ->
> Updates the branch reference to point to the given commit.
> What happens to subsequent changes depends on the option used:
>
> * `--mixed` (default) - Keep changes in the working directory as unstaged modifications. -> 1️⃣
> * `--soft` - Keep changes staged. -> 2️⃣
> * `--hard` - Discard everything completely. -> ❌
This command has a rewriting or deleting effect on the repository history.
* `git checkout HEAD ...`: Discard uncommitted changes. 2️⃣, 1️⃣ -> ❌
* `git checkout `: Travel to a specific commit in the history (to the state just after the commit).
> * This puts your repository in a `detached HEAD` state.
> * Git updates your project's file tree to match the state of `HEAD`.
> What you can do here:
>
> * Explore the repository.
> * Create a new branch from here (`git switch -c `).
> > This reattaches `HEAD` and sets the new branch's starting point to the checked-out commit. It's like starting a new line of work from an earlier point in history.
> * End the process (travel back) by switching to a branch.
# Home (/docs/git)
# Rebasing (/docs/git/rebasing)
Rebasing rewrites commit history, which creates conflicts and makes collaboration harder on shared or public branches.
## Integrating Changes [#integrating-changes]
What is it?
> Let's say you start working on a new feature by creating a `feature` branch. While you're developing, your teammates merge their completed work, such as bug fixes, into the `main` branch. To keep your `feature` branch up to date and avoid working with known issues, you need to bring those changes in.
>
> Yes, you can do this just by merging the `main` branch into your `feature` branch. That's it, but...
What is the problem?
> As you keep working, more bug fixes and updates might get merged into the `main` branch that you'll want to include again in your `feature` branch. You can keep merging to stay up to date, but imagine the `main` branch is very active and gets such updates several times a day. If your feature takes a while to finish, your branch history can quickly fill up with unnecessary merge commits that don't really say anything about the actual work you're doing.
The solution:
* `git rebase `: Reapply your current branch's commits on top of the specified branch (integrate its latest changes).
> If conflicts appear, you can either resolve them or cancel the process with `git rebase --abort`. When resolving conflicts, don't commit as usual. Instead, use `git rebase --continue` to move forward.
> Git rebasing solves the problem by reapplying your changes on top of another branch.
>
> It rebuilds your work on the source branch's latest version. It's like you just created the branch again, but this time you already have your changes in place.
## Interactive Rebase (History Editing) [#interactive-rebase-history-editing]
Interactive rebase lets you modify a branch's commit history by editing, reordering, squashing, or removing commits.
* `git rebase -i `: Initialize the interactive rebase process for the history that comes after the given commit.
> Here is the full flow of the process:
>
> 1. Git opens the interactive editor showing a list of commits and their actions (the default action is `pick`).
>
> 2. Choose an action for each commit.
>
> > Choosing an action means changing the default action to something else.
>
> > Some available actions:
> >
> > * `pick` - Use the commit as is.
> > * `reword` - Edit the commit message.
> > * `edit` - Modify the commit content.
> > * `squash` - Combine this commit with the previous one and edit the message.
> > * `fixup` - Combine with the previous commit but discard this message.
> > * `drop` - Remove the commit completely.
> > * You can also reorder commits by simply moving their lines up or down.
>
> 3. Save the file and close the editor.
>
> 4. Handle the selected actions.
>
> > Each action has its own process:
> >
> > * `reword` - Opens an editor to edit the commit message.
> > * `edit` - Pauses the rebase so you can modify (add/edit/delete) the content. After making changes, stage them and run `git rebase --continue`.
> > * `squash` - Opens an editor to make a merging message.
>
> > If any conflicts occur, resolve them and continue with `git rebase --continue`, or cancel the process with `git rebase --abort`.
>
> 5. When you finish handling all the requested actions, you'll have a rewritten commit history.
# Reflogs (Accident Recovery) (/docs/git/reflogs)
Reflogs (reference logs) are Git's local history of performed actions.
> Reflogs track actions such as commits, checkouts, merges, rebases, resets, and other operations that change the position of a branch or `HEAD`.
>
> Reflogs are helpful when you have accidentally deleted or lost commits, branches, or other references after destructive actions.
* `git reflog`: List all reflog entries.
> Each entry includes a hash, reference syntax, a description of the action, and additional information about that action.
> * `show ` - List only the reflogs associated with the specified branch.
> * `--date=iso`- Display reflog entries with `ISO 8601` formatted timestamps.
> After identifying the desired action in the reflog, you can use the appropriate method described in [Discarding Changes](./discarding-changes.mdx) together with the reflog hash to perform recovery.
# Remote Repository (/docs/git/remote-repository)
A remote repository is a copy of your project that lives on a server accessible over a network. It acts as a shared location where team members can push their work and pull updates from others.
## Getting From [#getting-from]
Bringing a remote repository to your local machine.
* `git clone `: Create a local copy of a remote repository.
> * `.` - Clone directly into the current directory instead of creating a new folder.
## Setting Up [#setting-up]
Connecting your local repository to a remote.
If you cloned a repository, the remote setup is already done. The cloning operation automatically sets the default
remote as `origin`.
* `git remote`: List all available remotes.
> * `-v` - Show remotes with their URLs.
> * `add ` - Add a new remote connection.
> * `rename ` - Rename a remote.
> * `remove ` - Remove a remote.
## Applying To [#applying-to]
Sending your local work to the remote repository.
* `git push`: Upload commits from your current branch to the matching branch on the remote repository.
> If it is the first time you are pushing the branch you need to set upstream.
>
> * `-u ` - Push and set the upstream for the current branch.
> > What is an upstream?
> >
> > > An upstream is the remote branch that your local branch tracks. When it is set, Git knows where to push and pull by default.
> Situations when pushing:
>
> 1. Remote has no changes.
> > If no one has updated the remote branch since your last fetch or pull, your push will succeed without issues.
> 2. Remote has changes.
>
> > If the remote branch has updates, Git will reject your push indicating the branch has diverged.
> >
> > In this case you need to update your local branch using `git pull` or you can force push if you intend to overwrite.
> * `-f` - Forcefully push overwriting any changes on the remote branch.
> * `--force-with-lease` - Forcefully push in a safer way.
> > Checks the remote branch to be exactly the same as when you last saw it.
> >
> > * If someone else pushed meanwhile, the operation is rejected.
> > * If the changes belong to you, Git allows the overwrite.
> >
> > This is useful when you pushed something incorrect and want to immediately push a corrected version completely overwriting/removing the incorrect one.
* `git fetch`: Download updates from the remote.
> This updates your remote tracking branches, adds new ones if there are, and downloads any other data your local repository is missing. Your working directory stays unchanged while your local view of the remote becomes up to date.
> * `--prune` - Remove any local references to remote branches that no longer exist on the remote repository.
A remote tracking branch is a local reference that represents the state of a branch on the remote.
It is not the remote repository itself. It only represents what the remote looked like the last time you fetched or pulled.
* Commands like `git status` and `git log` do not contact the remote. They compare your local branch with its remote tracking branch.
* A remote tracking branch can fall behind the actual remote repository. Keeping it updated makes your comparisons accurate.
* These branches are stored locally under names such as `origin/main` and they are read only which means you can compare them with your work,
merge changes from them, or create new branches based on them but you cannot modify them directly.
* `git pull`: Download and integrate updates from the remote.
> This command combines `git fetch` and `git merge`.
>
> * `--rebase` - Apply your local changes on top of the latest remote changes instead of merging (the same logic as [Rebasing / Integrating Changes](./rebasing.mdx#integrating-changes)).
# Stashing (/docs/git/stashing)
Stashing is a feature that allows you to temporarily save changes in your working directory without committing them.
> It's useful when you need to switch to a different branch to work on something else but don't want to commit or lose your current changes.
>
> When you stash, Git removes the modified files and changes from your working directory and saves them in a separate store.
>
> The stash works like a stack (first in, last out), so you can save multiple sets of changes.
* `git stash`: Save current staged and unstaged changes (excluding untracked files).
> * `-u` - Include untracked files too.
>
> * `push -m ""` - Save changes with a custom message.
>
> * `list` - List all saved stashes.
>
> > Each entry includes its index, the branch where it was created, and an optional message.
>
> * `pop` - Apply (bring back) the most recent stash and remove it from the stash store.
>
> > Use `apply` to apply a stash without removing it from the store.
>
> > * `` - Apply a specific stash.
>
> * `drop ` - Delete a specific stash from the list.
>
> * `clear` - Remove all stashed entries.
# Understanding Git (/docs/git/understanding-git)
## Git Areas [#git-areas]
Git has three main areas/stages where your files can exist:
1. Working Directory (Unstaged Area) - 1️⃣
> This is where you create or edit files.
>
> The unstaged area can contain two types of files: untracked and modified.
>
> * Untracked files are new files that Git doesn't know about yet. They've never been part of the version control.
> * Modified files are tracked (known by version control) files with changes that haven't been recorded in version control yet.
2. Staging Area - 2️⃣
> This is where you plan which changes will become part of version control, reviewing and grouping related updates before committing them.
3. Repository (Committed Area) - 3️⃣
> This is where Git permanently stores your committed changes, with each commit representing a snapshot of your project at a specific point in time.
## Core Commands [#core-commands]
* `git status`: Show working tree status.
> Shows current branch, staged changes, unstaged changes, and untracked files.
* `git add ...`: Add selected file changes to the staging area. 1️⃣ -> 2️⃣
> * `.` - To select all changes.
* `git commit`: Commit staged changes to the repository. 2️⃣ -> 3️⃣
> Opens the default text editor to enter a multi-line commit message.
> * `-m ""` - To provide a single-line commit message directly without opening the editor.
> > Can be used multiple times for multi-line messages without opening the editor.
> * `--amend` - Modify the most recent commit.
> > Opens the default text editor to change the commit message of the last commit. If you have items in the staging area, they will be added to the commit that is being amended.
* `git rm ...`: Remove files from repository and add the removal to the staging area. 3️⃣ -> ❌ -> 2️⃣
> * `--cached` - Unstage files (move them from the staging area back to unstaged). 2️⃣ -> 1️⃣
* `git log`: Show commit history.
> Shows a list of commits in reverse order including commit ID, author, date, and message.
> * `--oneline` - Show each commit on a single line (minimized view).
> * `-` - Limit the number of commits shown.
* `git ls-files`: Show all tracked files in the repository.
* `git diff`: Compare working directory (1️⃣) with the staging area (2️⃣).
> It displays changes to files line by line, providing a clear view of what has been added, modified, or deleted.
> * `HEAD` - Compare the working directory (1️⃣) + staging area (2️⃣) with the last commit (3️⃣).
> * `--staged` - Compare staged (2️⃣) changes with the last commit (3️⃣).
> * ` ` - Compare two commits.
> * ` ` - Compare two branches.
> You can view changes only within specific files by providing the file names after any of these options.
# Worktrees (/docs/git/worktrees)
Git worktrees let you have multiple working directories attached to a single repository.
> A worktree is simply another folder connected to the same repository. It can point to any branch or commit. Each worktree is isolated in its working files, but all of them share the same Git history, and switching to a worktree is as simple as moving into that folder with `cd`. This lets you work on different branches or commits in parallel, avoid stashing or making temporary commits just to move around, and keep each task in its own separate folder.
* `git worktree`
> * `list` - Show all active worktrees.
> * `add ` - Create a worktree for an existing branch.
> * `add ` - Create a worktree at a specific commit in a `detached HEAD` state.
> * `remove ` - Remove the worktree folder and its reference.
If you create a worktree folder inside another working directory, Git treats that folder as new content.
While Git can detect that it is a worktree and reduce it to a single entry, it still appears as untracked content, which you usually do not want in your real project history.
Example approaches to structure projects when working with worktrees.
* One base and others:
> You have one main working directory and other worktree folders next to it.
>
> ```sh
> ├─ project/ # <- main working directory (the repository folder)
> ├─ feat/ # <- worktree for the feature branch
> ```
> How:
>
> Run `git worktree add ../feat feature` inside the repository folder.
* Everything is a worktree:
> There is one repository folder, but to work, you have to create a worktree.
>
> ```sh
> ├─ repo.git/ # <- the repository folder
> ├─ main/ # <- worktree for the main branch
> ├─ feat/ # <- worktree for the feature branch
> ```
> How:
>
> First, you need to run `git clone --bare ` to create a local bare copy.
>
> > A bare clone is a repository without a working directory. It contains only the `.git/` data.
>
> Then you can create worktrees from the bare clone to work in, using `git worktree add ../main main` and `git worktree add ../feat feature`.
To run the
`git worktree`
command, you need to be inside a repository folder.
# Bubble Sort (/docs/dsa/sorting/bubble-sort)
| Stable? | Time | Space |
| ------- | -------- | ------ |
| Yes | `O(n^2)` | `O(1)` |
Explanation:
> Go through the list and compare each adjacent pair. If they are in the wrong order, swap them. After one full pass, the largest element moves to the end, so the next pass can skip it and check one less element. Repeat until a full pass finishes with no swaps.
>
>
Implementation:
```js title="Bubble Sort" lineNumbers
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]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
}
const numbers = [6, 5, 3, 1, 8, 7, 2, 4];
bubbleSort(numbers);
console.log(numbers); // [1, 2, 3, 4, 5, 6, 7, 8]
```
# Counting Sort (/docs/dsa/sorting/counting-sort)
| Stable? | Time | Space |
| ------- | ---------- | ------ |
| Yes | `O(n + k)` | `O(k)` |
Explanation:
> Find the largest value, then make a "count" list big enough to cover that range. Go through the original list and count how many times each value appears (add 1 to the count for each value you see). Then rebuild the sorted list by walking through the count list from smallest to largest and writing each value back the number of times it was counted.
>
>
> * Non-negative Integers: Counting sort uses each value as an index in the count list, so the array based version only works with non-negative integers.
> * Small Key Range: It's better if the largest value isn't too big, since the count list needs one slot for every value up to that maximum. Even if there aren't many items to sort, a huge maximum means you still have to make a massive count list.
Implementation:
```js title="Counting Sort" lineNumbers
function countingSort(arr) {
const max = Math.max(...arr);
const count = new Array(max + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
const number = arr[i];
count[number]++;
}
let cursor = 0;
for (let i = 0; i < count.length; i++) {
for (let j = 0; j < count[i]; j++) {
arr[cursor] = i;
cursor++;
}
}
}
const numbers = [4, 3, 1, 2, 5, 5, 3, 4, 5, 1, 5, 1, 5, 2, 3, 3, 2];
countingSort(numbers);
console.log(numbers); // [1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 5]
```
# Sorting (/docs/dsa/sorting)
Sorting algorithms are a set of techniques used to arrange elements, with each algorithm having its own strengths and weaknesses, making it suitable for different scenarios and types of data.
| Name | Stable? | Time | Space |
| -------------------------------------------------------------------- | ------- | ------------------------------- | ----------- |
| [Bubble Sort](./bubble-sort.mdx) | Yes | `O(n^2)` | `O(1)` |
| [Selection Sort](./selection-sort.mdx) | No | `O(n^2)` | `O(1)` |
| [Insertion Sort](./insertion-sort.mdx) | Yes | `O(n^2)` | `O(1)` |
| [Merge Sort](./merge-sort.mdx) | Yes | `O(n log(n))` | `O(n)` |
| [Quick Sort](./quick-sort.mdx) | No | `O(n log(n))` (worst: `O(n^2)`) | `O(log(n))` |
| [Counting Sort](./counting-sort.mdx) | Yes | `O(n + k)` | `O(k)` |
| [Radix Sort ↗](https://www.w3schools.com/dsa/dsa_algo_radixsort.php) | Yes | `O(nk)` | `O(n + k)` |
| [Heap Sort ↗](https://en.wikipedia.org/wiki/Heapsort) | No | `O(n log(n))` | `O(1)` |
> * Stable: Equal elements keep their original order.
> * Unstable: Equal elements might not keep their original order.
# Insertion Sort (/docs/dsa/sorting/insertion-sort)
| Stable? | Time | Space |
| ------- | -------- | ------ |
| Yes | `O(n^2)` | `O(1)` |
Explanation:
> Treat the left side as sorted and scan from the second element onward. For each element, compare it backward with the sorted part, shift larger elements right, then insert it into the gap. Repeat until the entire list is sorted.
>
>
> * Nearly Sorted Data: If the list is nearly sorted, most items shift only a little, so it does fewer moves.
> * Real-time Data: When data is streamed in real time, each new item acts like the last iteration of the algorithm, which is just moving the item into its correct position among the already sorted items without re-sorting the entire list.
Implementation:
```js title="Insertion Sort" lineNumbers
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let j = i - 1;
while (j >= 0 && arr[j + 1] < arr[j]) {
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
j--;
}
}
}
const numbers = [6, 5, 3, 1, 8, 7, 2, 4];
insertionSort(numbers);
console.log(numbers); // [1, 2, 3, 4, 5, 6, 7, 8]
```
# Merge Sort (/docs/dsa/sorting/merge-sort)
| Stable? | Time | Space |
| ------- | ------------- | ------ |
| Yes | `O(n log(n))` | `O(n)` |
Explanation:
> Split the list into two halves, then keep splitting each half until you end up with single-element lists. Treat each single element as already sorted, then merge pairs back together by comparing the front elements of each list and taking the smaller one first. Keep merging the sorted pieces into bigger sorted lists until everything is merged into one fully sorted list.
>
>
> * Parallelization: Merge sort is parallel-friendly because, after splitting, the two halves can be sorted independently and concurrently across multiple CPU cores.
> * Predictable: Merge sort consistently performs well regardless of input order, providing reliable worst-case performance for large datasets.
Implementation:
```js title="Merge Sort" lineNumbers
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
// split until base case and then merge back while unfolding:
return merge(mergeSort(left), mergeSort(right));
}
// compare and merge:
function merge(left, right) {
const tmp = [];
let l = 0;
let r = 0;
while (l < left.length && r < right.length) {
if (left[l] <= right[r]) {
tmp.push(left[l]);
l++;
} else {
tmp.push(right[r]);
r++;
}
}
return [...tmp, ...left.slice(l), ...right.slice(r)];
}
const numbers = [6, 5, 3, 1, 8, 7, 2, 4];
console.log(mergeSort(numbers)); // [1, 2, 3, 4, 5, 6, 7, 8]
```
# Quick Sort (/docs/dsa/sorting/quick-sort)
| Stable? | Time | Space |
| ------- | ------------------------------- | ----------- |
| No | `O(n log(n))` (worst: `O(n^2)`) | `O(log(n))` |
Explanation:
> Pick a pivot element from the list. Go through the remaining elements and split them into two groups, ones smaller than the pivot and ones bigger than the pivot. Put the pivot between those two groups, so it ends up in its final spot. Repeat the same process (including pivot picking) on the left and right groups until all the groups are size one or empty, then the whole list is sorted.
>
>
> * Nearly Sorted Data: Quicksort minimizes unnecessary swaps, it swaps nothing if the data is already sorted.
> * Choosing Pivot: If the pivot is close to the median, the list splits into two similar-sized parts and quick sort stays fast (`O(n log(n))`). If the pivot is near the smallest or largest, almost everything goes to one side, so quick sort repeats the partition step on nearly the whole list over and over, which can make it much slower (`O(n^2)`).
Implementation:
```js title="Quick Sort" lineNumbers
function quickSort(arr, left = 0, right = arr.length - 1) {
if (left < right) {
const pivot = arr[Math.floor((left + right) / 2)]; // chosen pivot: always the middle element
const index = partition(arr, left, right, pivot);
quickSort(arr, left, index - 1);
quickSort(arr, index, right);
}
return arr;
}
function partition(arr, left, right, pivot) {
while (left <= right) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left <= right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
return left;
}
const numbers = [6, 5, 3, 1, 8, 7, 2, 4];
quickSort(numbers);
console.log(numbers); // [1, 2, 3, 4, 5, 6, 7, 8]
```
# Selection Sort (/docs/dsa/sorting/selection-sort)
| Stable? | Time | Space |
| ------- | -------- | ------ |
| No | `O(n^2)` | `O(1)` |
Explanation:
> Move from left to right through the list. For each position, scan the remaining unsorted part to find the smallest element, then swap it into the current position. Repeat until the unsorted part is empty.
>
>
Implementation:
```js title="Selection Sort" lineNumbers
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let min = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
[arr[i], arr[min]] = [arr[min], arr[i]];
}
}
const numbers = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
selectionSort(numbers);
console.log(numbers); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```
# Backtracking (/docs/dsa/techniques-and-tricks/backtracking)
## Overview [#overview]
Backtracking is a technique where you build a solution step by step, and as soon as you notice the current path can't lead to a valid answer, you undo the last step (or a few steps) and try a different choice.
It is useful when a problem has many possible choices and you need to explore different possibilities to find a valid solution (or all valid solutions).
## Examples [#examples]
1. Generate all combinations of well-formed parentheses.
```js
function generateParentheses(n) {
const result = [];
function backtrack(current, openUsed, closeUsed) {
// Save:
if (current.length >= 2 * n) {
result.push(current);
return;
}
// Add "(" if we still can:
if (openUsed < n) {
backtrack(current + '(', openUsed + 1, closeUsed);
}
// Add ")" if it stays valid:
if (closeUsed < openUsed) {
backtrack(current + ')', openUsed, closeUsed + 1);
}
}
backtrack('', 0, 0);
return result;
}
console.log(generateParentheses(1)); // ['()']
console.log(generateParentheses(2)); // ['(())', '()()']
console.log(generateParentheses(3)); // ['((()))', '(()())', '(())()', '()(())', '()()()']
```
> Explanation: `generateParenthesis(3)`
>
> ```js
> backtrack("", open=0, close=0)
> ├─ add "(" -> backtrack("(", open=1, close=0)
> │ ├─ add "(" -> backtrack("((", open=2, close=0)
> │ │ ├─ add "(" -> backtrack("(((", open=3, close=0)
> │ │ │ └─ add ")" -> backtrack("((()", open=3, close=1)
> │ │ │ └─ add ")" -> backtrack("((())", open=3, close=2)
> │ │ │ └─ add ")" -> backtrack("((()))", open=3, close=3)
> │ │ │ └─ save "((()))"
> │ │ └─ add ")" -> backtrack("(()", open=2, close=1)
> │ │ ├─ add "(" -> backtrack("(()(", open=3, close=1)
> │ │ │ └─ add ")" -> backtrack("(()()", open=3, close=2)
> │ │ │ └─ add ")" -> backtrack("(()())", open=3, close=3)
> │ │ │ └─ save "(()())"
> │ │ └─ add ")" -> backtrack("(())", open=2, close=2)
> │ │ └─ add "(" -> backtrack("(())(", open=3, close=2)
> │ │ └─ add ")" -> backtrack("(())()", open=3, close=3)
> │ │ └─ save "(())()"
> │ └─ add ")" -> backtrack("()", open=1, close=1)
> │ └─ add "(" -> backtrack("()(", open=2, close=1)
> │ ├─ add "(" -> backtrack("()((", open=3, close=1)
> │ │ └─ add ")" -> backtrack("()(()", open=3, close=2)
> │ │ └─ add ")" -> backtrack("()(())", open=3, close=3)
> │ │ └─ save "()(())"
> │ └─ add ")" -> backtrack("()()", open=2, close=2)
> │ └─ add "(" -> backtrack("()()(", open=3, close=2)
> │ └─ add ")" -> backtrack("()()()", open=3, close=3)
> │ └─ save "()()()"
> ```
2. Generate all subsets.
```js
function subsets(arr) {
const result = [];
function backtrack(i, path) {
// save
result.push([...path]);
// try
for (let j = i; j < arr.length; j++) {
path.push(arr[j]); // choose
backtrack(j + 1, path); // explore
path.pop(); // undo (backtrack)
}
}
backtrack(0, []);
return result;
}
console.log(subsets([1, 2, 3])); // [[], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3 ], [ 2 ], [ 2, 3 ], [ 3 ]]
console.log(subsets(['a', 'b', 'c'])); // [[], ['a'], ['a', 'b'], ['a', 'b', 'c'], ['a', 'c'], ['b'], ['b', 'c'], ['c']]
```
> Explanation: `subsets(['a', 'b', 'c'])`
>
> ```js
> backtrack(0), path=[]
> ADD result: []
>
> choose "a" -> path=[a]
> backtrack(1)
> ADD result: [a]
>
> choose "b" -> path=[a,b]
> backtrack(2)
> ADD result: [a,b]
>
> choose "c" -> path=[a,b,c]
> backtrack(3)
> ADD result: [a,b,c]
> undo "c" -> path=[a,b]
>
> undo "b" -> path=[a]
>
> choose "c" -> path=[a,c]
> backtrack(3)
> ADD result: [a,c]
> undo "c" -> path=[a]
>
> undo "a" -> path=[]
>
> choose "b" -> path=[b]
> backtrack(2)
> ADD result: [b]
>
> choose "c" -> path=[b,c]
> backtrack(3)
> ADD result: [b,c]
> undo "c" -> path=[b]
>
> undo "b" -> path=[]
>
> choose "c" -> path=[c]
> backtrack(3)
> ADD result: [c]
> undo "c" -> path=[]
> ```
# Dynamic Programming (/docs/dsa/techniques-and-tricks/dynamic-programming)
## Overview [#overview]
Dynamic programming in DSA is a technique where you break a problem into smaller overlapping subproblems, solve each subproblem once, and reuse those results instead of recalculating them.
Two main DP styles:
* Top-down (memoization):
> Solve the problem recursively and store the results of solved subproblems to avoid redundant calculations.
* Bottom-up (tabulation):
> Solve smaller subproblems first, store results in a table, and use them to build solutions to larger problems.
## Examples [#examples]
1. Fibonacci:
* Top-down: (time `O(n)`, space `O(n)`)
```js
function fib(n, cache = new Map()) {
if (n <= 1) return n;
if (cache.has(n)) {
return cache.get(n);
}
const result = fib(n - 1, cache) + fib(n - 2, cache);
cache.set(n, result);
return result;
}
console.log(fib(6)); // 8
console.log(fib(10)); // 55
console.log(fib(999)); // 2.686381002448534e+208
```
* Bottom-up: (time `O(n)`, space `O(1)`)
```js
function fib(n) {
if (n <= 1) return n;
const cache = [0, 1];
for (let i = 2; i <= n; i++) {
cache[i] = cache[i - 1] + cache[i - 2];
}
return cache[n];
}
console.log(fib(6)); // 8
console.log(fib(10)); // 55
console.log(fib(999)); // 2.686381002448534e+208
```
# The Gauss' Trick (/docs/dsa/techniques-and-tricks/gauss-sum)
## Overview [#overview]
A method for finding the sum of an arithmetic series in `O(1)` time.
Formula:
```js
S = (n / 2) * (i + j);
```
> * `i`: First term.
> * `j`: Last term.
> * `n`: Number of terms.
> > ```js
> > n = (j - i) / d + 1;
> > ```
> >
> > * `d`: Common difference (the step between terms).
> > > e.g., in `2, 4, 6, 8` the step is `2`, so `d = 2`.
## Examples [#examples]
1. Sum of the numbers from `0` to `10`:
```js
i = 0
j = 10
d = 1
n = (10 - 0) / 1 + 1 = 11
S = (11 / 2) * (0 + 10) = 5.5 * 10 = 55
```
2. Sum of the numbers from `-5` to `2`:
```js
i = -5
j = 2
d = 1
n = (2 - (-5)) / 1 + 1 = 8
S = (8 / 2) * ((-5) + 2) = 4 * (-3) = -12
```
3. Sum of the given numbers `[2, 4, 6, 8, 10, 12, 14]`:
```js
i = 2
j = 14
d = 2
n = (14 - 2) / 2 + 1 = 7
S = (7 / 2) * (2 + 14) = 3.5 * 16 = 56
```
# Recursion (/docs/dsa/techniques-and-tricks/recursion)
## Overview [#overview]
Recursion in programming is a technique where a function calls itself to solve a problem.
Recursion lets you break a complex problem into smaller, more manageable subproblems. Each recursive call works on a smaller part of the original problem until it reaches a base case, where the recursion stops.
Recursion is useful when you don't know in advance how many steps or iterations will be needed to find a solution. It allows you to go deeper into the problem until you reach a base case that can be easily solved.
> More detailed explanation: [https://www.youtube.com/watch?v=ngCos392W4w](https://www.youtube.com/watch?v=ngCos392W4w).
### Definitions [#definitions]
* Key points:
> 1. Base Case: The stopping condition that prevents infinite recursion.
> * Smallest valid input: The simplest case that can be solved directly without more recursion.
> * Termination condition: A condition that tells the function when to stop recursing.
> * Edge cases: Special cases that need specific handling.
> 2. Recursive Case: The part of the function that reduces the problem and moves it closer to the base case. Each call should make progress toward stopping.
> 3. Recursive Call: Calling the function from inside itself.
* Process:
> 1. Stacking (going down): Each recursive call creates a new stack frame on the call stack, which stores the parameters and local variables for that call.
> 2. Unfolding (going up): After the base case is reached, the calls return one by one. Each call returns its result to the previous stack frame until the original call returns the final result.
* Costs:
> * Space: Each recursive call adds a stack frame, so the space complexity is typically `O(recursion depth)`.
## Examples [#examples]
1. Reverse a string:
```js
function reverseStr(str) {
// Base case:
if (str.length <= 1) return str;
// Recursive case & call:
return reverseStr(str.slice(1)) + str[0];
}
console.log(reverseStr('Hello')); // "olleH"
console.log(reverseStr('abcdefg')); // "gfedcba"
```
> Explanation: `reverseStr("Hello")`
>
> ```js
> reverseStr("Hello") = reverseStr("ello") + "H"
> ├─ reverseStr("ello") = reverseStr("llo") + "e"
> │ ├─ reverseStr("llo") = reverseStr("lo") + "l"
> │ │ ├─ reverseStr("lo") = reverseStr("o") + "l"
> │ │ │ └─ reverseStr("o") = "o" // (base case)
> │ │ │ returns "o"
> │ │ returns "o" + "l" = "ol"
> │ returns "ol" + "l" = "oll"
> returns "oll" + "e" = "olle"
> returns "olle" + "H" = "olleH"
> ```
2. Factorial:
```js
function factorial(num) {
// Base case:
if (num === 0 || num === 1) {
return 1;
}
// Recursive case & call:
return num * factorial(num - 1);
}
console.log(factorial(5)); // 120
```
> Explanation:
>
> ```js
> factorial(5) = 5 * factorial(4)
> ├─ factorial(4) = 4 * factorial(3)
> │ ├─ factorial(3) = 3 * factorial(2)
> │ │ ├─ factorial(2) = 2 * factorial(1)
> │ │ │ └─ factorial(1) = 1 // (base case)
> │ │ │ returns 1
> │ │ returns 2 * 1 = 2
> │ returns 3 * 2 = 6
> returns 4 * 6 = 24
> returns 5 * 24 = 120
> ```
3. Fibonacci:
```js
function fib(n) {
// Base cases:
if (n === 0) return 0;
if (n === 1) return 1;
// Recursive case & call:
return fib(n - 1) + fib(n - 2);
}
console.log(fib(6)); // 8
console.log(fib(10)); // 55
console.log(fib(5)); // 5
```
> Explanation: `fib(6)`
>
> ```js
> fib(6) = fib(5) + fib(4)
> ├─ fib(5) = fib(4) + fib(3)
> │ ├─ fib(4) = fib(3) + fib(2)
> │ │ ├─ fib(3) = fib(2) + fib(1)
> │ │ │ ├─ fib(2) = fib(1) + fib(0)
> │ │ │ │ ├─ fib(1) = 1 // (base case)
> │ │ │ │ └─ fib(0) = 0 // (base case)
> │ │ │ │ returns 1
> │ │ │ └─ fib(1) = 1 // (base case)
> │ │ │ returns 2
> │ │ └─ fib(2) = fib(1) + fib(0)
> │ │ ├─ fib(1) = 1 // (base case)
> │ │ └─ fib(0) = 0 // (base case)
> │ │ returns 1
> │ │ returns 3
> │ └─ fib(3) = fib(2) + fib(1)
> │ ├─ fib(2) = fib(1) + fib(0)
> │ │ ├─ fib(1) = 1 // (base case)
> │ │ └─ fib(0) = 0 // (base case)
> │ │ returns 1
> │ └─ fib(1) = 1 // (base case)
> │ returns 2
> │ returns 5
> └─ fib(4) = fib(3) + fib(2)
> ├─ fib(3) = fib(2) + fib(1)
> │ ├─ fib(2) = fib(1) + fib(0)
> │ │ ├─ fib(1) = 1 // (base case)
> │ │ └─ fib(0) = 0 // (base case)
> │ │ returns 1
> │ └─ fib(1) = 1 // (base case)
> │ returns 2
> └─ fib(2) = fib(1) + fib(0)
> ├─ fib(1) = 1 // (base case)
> └─ fib(0) = 0 // (base case)
> returns 1
> returns 3
>
> returns 5 + 3 = 8
> ```
4. Count how many items are in a nested array:
```js
function countItems(value) {
// Base case:
if (!Array.isArray(value)) return 1;
let total = 0;
// Recursive case & call:
for (const item of value) {
total += countItems(item);
}
return total;
}
console.log(countItems(['a', ['b', 'c'], [['d', ['e', 'f']], 'g']])); // 7
console.log(countItems([])); // 0
console.log(countItems(['a', [[]]])); // 1
```
> Explanation: `countItems(['a', ['b', 'c'], [['d', ['e', 'f']], 'g']])`
>
> ```js
> countItems(['a', ['b','c'], [['d',['e','f']], 'g']]) = 1 + 2 + 4 = 7
> ├─ countItems('a') = 1
> ├─ countItems(['b','c']) = 1 + 1 = 2
> │ ├─ countItems('b') = 1
> │ └─ countItems('c') = 1
> └─ countItems([['d',['e','f']], 'g']) = 3 + 1 = 4
> ├─ countItems(['d',['e','f']]) = 1 + 2 = 3
> │ ├─ countItems('d') = 1
> │ └─ countItems(['e','f']) = 1 + 1 = 2
> │ ├─ countItems('e') = 1
> │ └─ countItems('f') = 1
> └─ countItems('g') = 1
> ```
# Breadth First Search (BFS) (/docs/dsa/searching/bfs)
## Overview [#overview]
Visits nodes level by level in a graph or tree, starting from the closest nodes to the start point.
| Time | Space |
| ------ | ------ |
| `O(n)` | `O(n)` |
## Tree BFS [#tree-bfs]
> Example Tree:
>
>
Implementation:
> Go to [Binary Search Tree](../trees/binary-search-tree) for the complete BST implementation.
> This implementation uses a [Queue](../queue) data structure, so you must implement it beforehand.
```js title="Binray Search Tree" lineNumbers
class BinarySearchTree {
...
BFS() {
if (this.root === null) return null;
const list = [];
const queue = new Queue();
queue.enqueue(this.root);
while (queue.size > 0) {
const currNode = queue.peek();
list.push(currNode.value);
if (currNode.left) {
queue.enqueue(currNode.left);
}
if (currNode.right) {
queue.enqueue(currNode.right);
}
queue.dequeue();
}
return list;
}
}
```
> Usage:
>
> ```js
> const tree = new BinarySearchTree();
>
> ...
>
> console.log(tree.BFS()); // [60, 59, 77, 28, 60, 125, 23, 28, 76, 35]
> ```
## Graph BFS [#graph-bfs]
> Example Graph:
>
>
### Adjacency Matrix [#adjacency-matrix]
Implementation:
> This implementation uses a [Queue](../queue) data structure, so you must implement it beforehand.
```js title="Graph BFS (adjacency matrix)" lineNumbers
const adjacencyMatrix = {
A: { A: 0, B: 1, C: 0, D: 0, E: 0, F: 0 },
B: { A: 1, B: 0, C: 1, D: 0, E: 1, F: 0 },
C: { A: 0, B: 1, C: 0, D: 1, E: 0, F: 0 },
D: { A: 0, B: 0, C: 1, D: 0, E: 1, F: 1 },
E: { A: 0, B: 1, C: 0, D: 1, E: 0, F: 0 },
F: { A: 0, B: 0, C: 0, D: 1, E: 0, F: 0 },
};
function adjMatrixBFS(start, graph) {
const seen = {};
const queue = new Queue();
queue.enqueue(start);
const values = [];
while (queue.size > 0) {
const node = queue.dequeue();
if (seen[node]) continue;
values.push(node);
seen[node] = true;
const connections = graph[node];
for (const key in connections) {
if (connections[key] > 0 && !seen[key]) {
queue.enqueue(key);
}
}
}
return values;
}
```
> Usage:
>
> ```js
> console.log(adjMatrixBFS('C', adjacencyMatrix)); // ['C', 'B', 'D', 'A', 'E', 'F']
> console.log(adjMatrixBFS('A', adjacencyMatrix)); // ['A', 'B', 'C', 'E', 'D', 'F']
> console.log(adjMatrixBFS('B', adjacencyMatrix)); // ['B', 'A', 'C', 'E', 'D', 'F']
> ```
### Adjacency List [#adjacency-list]
Implementation:
> This implementation uses a [Queue](../queue) data structure, so you must implement it beforehand.
```js title="Graph BFS (adjacency list)" lineNumbers
const adjList = {
A: ['B'],
B: ['A', 'C', 'E'],
C: ['B', 'D'],
D: ['C', 'E', 'F'],
E: ['B', 'D'],
F: ['D'],
};
function adjListBFS(start, graph) {
const seen = {};
const queue = new Queue();
queue.enqueue(start);
const values = [];
while (queue.size > 0) {
const node = queue.dequeue();
if (seen[node]) continue;
values.push(node);
seen[node] = true;
const connections = graph[node];
for (const key of connections) {
if (!seen[key]) {
queue.enqueue(key);
}
}
}
return values;
}
```
> Usage:
>
> ```js
> console.log(adjListBFS('C', adjList)); // ['C', 'B', 'D', 'A', 'E', 'F']
> console.log(adjListBFS('A', adjList)); // ['A', 'B', 'C', 'E', 'D', 'F']
> console.log(adjListBFS('B', adjList)); // ['B', 'A', 'C', 'E', 'D', 'F']
> ```
## Matrix (2D Array) BFS [#matrix-2d-array-bfs]
> Example 2D Array:
>
>
> > The red line shows the search flow starting from points `row: 2` and `col: 2` (green numbers show the same in a simpler format).
Implementation:
> This implementation uses a [Queue](../queue) data structure, so you must implement it beforehand.
```js title="Matrix BFS" lineNumbers
const arr2d = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
];
const directions = [
[-1, 0], // up
[0, 1], // right
[1, 0], // down
[0, -1], // left
];
function matrixBFS(matrix, row, col) {
const seen = new Set();
const queue = new Queue();
queue.enqueue([row, col]);
const values = [];
while (queue.size > 0) {
const [row, col] = queue.dequeue();
if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length || seen.has(`${row}${col}`)) {
continue;
}
seen.add(`${row}${col}`);
values.push(matrix[row][col]);
for (let i = 0; i < directions.length; i++) {
const currDir = directions[i];
queue.enqueue([row + currDir[0], col + currDir[1]]);
}
}
return values;
}
```
> Usage:
>
> ```js
> console.log(matrixBFS(arr2d, 2, 2)); // [13, 8, 14, 18, 12, 3, 9, 7, 15, 19, 17, 11, 4, 2, 10, 6, 20, 16, 5, 1]
> console.log(matrixBFS(arr2d, 0, 0)); // [1, 2, 6, 3, 7, 11, 4, 8, 12, 16, 5, 9, 13, 17, 10, 14, 18, 15, 19, 20]
> console.log(matrixBFS(arr2d, 1, 0)); // [6, 1, 7, 11, 2, 8, 12, 16, 3, 9, 13, 17, 4, 10, 14, 18, 5, 15, 19, 20]
> console.log(matrixBFS(arr2d, 2, 3)); // [14, 9, 15, 19, 13, 4, 10, 8, 20, 18, 12, 5, 3, 7, 17, 11, 2, 6, 16, 1]
> ```
# Binary Search (/docs/dsa/searching/binary-search)
## Overview [#overview]
Searches sorted data by comparing with the middle element and reducing the search range each step.
| Time | Space |
| ----------- | ------ |
| `O(log(n))` | `O(1)` |
Binary Search only works when the data is sorted.
## Implementation [#implementation]
* Iterative:
```js title="Iterative Binary Search" lineNumbers
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] < target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid - 1;
} else {
return mid;
}
}
return false;
}
console.log(binarySearch([-6, -2, 0, 2, 3, 3, 5, 7, 12], 5)); // 6
```
* Recursive:
```js title="Recursive Binary Search" lineNumbers
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
if (left > right) {
return false;
}
const mid = Math.floor((left + right) / 2);
if (arr[mid] < target) {
return binarySearch(arr, target, mid + 1, right);
} else if (arr[mid] > target) {
return binarySearch(arr, target, left, mid - 1);
} else {
return mid;
}
}
console.log(binarySearch([-6, -2, 0, 2, 3, 3, 5, 7, 12], 5)); // 6
```
# Depth-First Search (DFS) (/docs/dsa/searching/dfs)
## Overview [#overview]
Explores one path fully in a graph or tree before returning to try other paths.
| Time | Space |
| ------ | ------ |
| `O(n)` | `O(h)` |
## Tree DFS [#tree-dfs]
> Example Tree:
>
>
Order of searching:
> * Pre-order: `Node -> Left -> Right`.
> > \[60, 59, 28, 23, 28, 35, 77, 60, 76, 125]
> * In-order: `Left -> Node -> Right`.
> > \[23, 28, 28, 35, 59, 60, 60, 76, 77, 125]
> * Post-order: `Left -> Right -> Node`.
> > \[23, 35, 28, 28, 59, 76, 60, 125, 77, 60]
>
> The order of visiting children can be changed, such as visiting the right child before the left. To do this, simply swap the code for the left and right child traversals (use right before left) in the implementation below.
Implementation:
> Go to [Binary Search Tree](../trees/binary-search-tree) for the complete BST implementation.
```js title="Binray Search Tree" lineNumbers
class BinarySearchTree {
...
preOrderDFS() { ... } // [!code highlight]
inOrderDFS() { ... } // [!code highlight]
postOrderDFS() { ... } // [!code highlight]
}
```
> Usage:
>
> ```js
> const tree = new BinarySearchTree();
>
> ...
>
> console.log(tree.preOrderDFS()); // [60, 59, 28, 23, 28, 35, 77, 60, 76, 125]
> console.log(tree.inOrderDFS()); // [23, 28, 28, 35, 59, 60, 60, 76, 77, 125]
> console.log(tree.postOrderDFS()); // [23, 35, 28, 28, 59, 76, 60, 125, 77, 60]
> ```
* Pre-order:
```js
preOrderDFS() {
const traversePreOrder = (node, list) => {
if (node === null) return null;
// node:
list.push(node.value);
// left:
if (node.left) {
traversePreOrder(node.left, list);
}
// right:
if (node.right) {
traversePreOrder(node.right, list);
}
return list;
}
return traversePreOrder(this.root, []);
}
```
* In-order:
```js
inOrderDFS() {
const traverseInOrder = (node, list) => {
if (node === null) return null;
// left:
if (node.left) {
traverseInOrder(node.left, list);
}
// node:
list.push(node.value);
// right:
if (node.right) {
traverseInOrder(node.right, list);
}
return list;
}
return traverseInOrder(this.root, []);
}
```
* Post-order:
```js
postOrderDFS() {
const traversePostOrder = (node, list) => {
if (node === null) return null;
// left:
if (node.left) {
traversePostOrder(node.left, list);
}
// right:
if (node.right) {
traversePostOrder(node.right, list);
}
// node:
list.push(node.value);
return list;
};
return traversePostOrder(this.root, []);
}
```
## Graph DFS [#graph-dfs]
> Example Graph:
>
>
### Adjacency Matrix [#adjacency-matrix]
Implementation:
```js title="Graph DFS (adjacency matrix)" lineNumbers
const adjMatrix = {
A: { A: 0, B: 1, C: 0, D: 0, E: 0, F: 0 },
B: { A: 1, B: 0, C: 1, D: 0, E: 1, F: 0 },
C: { A: 0, B: 1, C: 0, D: 1, E: 0, F: 0 },
D: { A: 0, B: 0, C: 1, D: 0, E: 1, F: 1 },
E: { A: 0, B: 1, C: 0, D: 1, E: 0, F: 0 },
F: { A: 0, B: 0, C: 0, D: 1, E: 0, F: 0 },
};
function adjMatrixDFS(node, graph, values, seen) {
values.push(node);
seen[node] = true;
const connections = graph[node];
for (const key in connections) {
if (connections[key] > 0 && !seen[key]) {
adjMatrixDFS(key, graph, values, seen);
}
}
return values;
}
```
> Usage:
>
> ```js
> console.log(adjMatrixDFS('C', adjMatrix, [], {})); // ['C', 'B', 'A', 'E', 'D', 'F']
> console.log(adjMatrixDFS('A', adjMatrix, [], {})); // ['A', 'B', 'C', 'D', 'E', 'F']
> console.log(adjMatrixDFS('B', adjMatrix, [], {})); // ['B', 'A', 'C', 'D', 'E', 'F']
> ```
### Adjacency List [#adjacency-list]
Implementation:
```js title="Graph DFS (adjacency list)" lineNumbers
const adjList = {
A: ['B'],
B: ['A', 'C', 'E'],
C: ['B', 'D'],
D: ['C', 'E', 'F'],
E: ['B', 'D'],
F: ['D'],
};
function adjListDFS(node, graph, values, seen) {
values.push(node);
seen[node] = true;
const connections = graph[node];
for (let i = 0; i < connections.length; i++) {
const key = connections[i];
if (!seen[key]) {
adjListDFS(key, graph, values, seen);
}
}
return values;
}
```
> Usage:
>
> ```js
> console.log(adjListDFS('C', adjList, [], {})); // ['C', 'B', 'A', 'E', 'D', 'F']
> console.log(adjListDFS('A', adjList, [], {})); // ['A', 'B', 'C', 'D', 'E', 'F']
> console.log(adjListDFS('B', adjList, [], {})); // ['B', 'A', 'C', 'D', 'E', 'F']
> ```
## Matrix (2D Array) DFS [#matrix-2d-array-dfs]
> Example 2D Array:
>
>
> > The red line shows the search flow starting from points `row: 0` and `col: 0`.
Implementation:
```js title="Matrix DFS" lineNumbers
const arr2d = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
];
const directions = [
[-1, 0], // up
[0, 1], // right
[1, 0], // down
[0, -1], // left
];
function matrixDFS(matrix, row, col, seen, values) {
if (row < 0 || col < 0 || row >= matrix.length || col >= matrix[0].length || seen.has(`${row}${col}`)) {
return;
}
values.push(matrix[row][col]);
seen.add(`${row}${col}`);
for (let i = 0; i < directions.length; i++) {
const currDir = directions[i];
matrixDFS(matrix, row + currDir[0], col + currDir[1], seen, values);
}
return values;
}
```
> Usage:
>
> ```js
> console.log(matrixDFS(arr2d, 0, 0, new Set(), [])); // [1, 2, 3, 4, 5, 10, 15, 20, 19, 14, 9, 8, 13, 18, 17, 12, 7, 6, 11, 16]
> console.log(matrixDFS(arr2d, 1, 0, new Set(), [])); // [6, 1, 2, 3, 4, 5, 10, 15, 20, 19, 14, 9, 8, 13, 18, 17, 12, 7, 11, 16]
> console.log(matrixDFS(arr2d, 2, 3, new Set(), [])); // [14, 9, 4, 5, 10, 15, 20, 19, 18, 13, 8, 3, 2, 7, 12, 17, 16, 11, 6, 1]
> ```
# Searching (/docs/dsa/searching)
Searching algorithms are methods used to find a specific item in a set of data.
| Name | Time | Space | Overview |
| --------------------------------------- | ----------- | ------ | ------------------------------------------- |
| [Linear Search](./linear-search.mdx) | `O(n)` | `O(1)` | Checks each element one by one. |
| [Binary Search](./binary-search.mdx) | `O(log(n))` | `O(1)` | Searches sorted data by halving range. |
| [Depth-First Search (DFS)](./dfs.mdx) | `O(n)` | `O(h)` | Explores tree/graph one path before others. |
| [Breadth-First Search (BFS)](./bfs.mdx) | `O(n)` | `O(n)` | Explores tree/graph level by level. |
# Linear Search (/docs/dsa/searching/linear-search)
## Overview [#overview]
Scans each element in order until the target is found or all elements are checked.
| Time | Space |
| ------ | ------ |
| `O(n)` | `O(1)` |
## Implementation [#implementation]
```js title="Linear Search" lineNumbers
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}
const numbers = [9, 1, 9, 3, -4, 0, 3, 5, 6, 5];
// 0 1 2 3 4 5 6 7 8 9
console.log(linearSearch(numbers, 5)); // 7
```
# Channels (/docs/go/concurrency/channels)
## Overview [#overview]
Channels in Go provide a way for goroutines to communicate by sending and receiving values.
* Declare:
```go
ch := make(chan int)
```
> The channel type defines what kind of data it can carry. It can be any type, including named types.
* Send:
```go
ch <- 10
```
* Receive:
```go
value := <-ch
```
* Close:
```go
close(ch)
```
Closing a closed channel causes a panic.
Channel synchronization coordinates communication between goroutines. It ensures data is not lost and preserves the correct order.
* Send operation: Blocks the current goroutine until another goroutine (the other side) is ready to receive.
* Receive operation: Blocks the current goroutine until a value is available (from the other side).
Whoever comes first has to wait for the other one.
> Example:
>
> ```go
> func main() {
> ch := make(chan string)
>
> go expensiveFunc("Hello", ch)
>
> fmt.Println("Main")
>
> for range 4 {
> fmt.Println(<-ch)
> }
>
> fmt.Println("End")
> }
>
> func expensiveFunc(text string, ch chan string) {
> for i := range 4 {
> time.Sleep(500 * time.Millisecond)
> ch <- text + " " + fmt.Sprint(i)
> }
> }
>
> // Main
> // Hello 0
> // Hello 1
> // Hello 2
> // Hello 3
> // End
> ```
>
> No extra mechanism is required in `main` to wait for the goroutine. The `<-ch` operation blocks until a value is available. This behavior synchronizes `main` with `expensiveFunc`. Each loop iteration in `main` waits for a send from `expensiveFunc`. The loop is used only as an example, calling `fmt.Println(<-ch)` 4 times back to back would do the same.
> In the example above, closing the channel is not required because `main` receives a fixed number of messages (4) before exiting. Closing is only necessary when the receiver must be told there are no more values coming, such as to terminate a `range` loop.
>
> Here is a modified version that requires the channel to be closed explicitly:
>
> ```go
> func main() {
> ch := make(chan string)
>
> go expensiveFunc("Hello", ch)
>
> fmt.Println("Main")
>
> for msg := range ch {
> fmt.Println(msg)
> }
>
> fmt.Println("Done.")
> }
>
> func expensiveFunc(text string, ch chan string) {
> defer close(ch)
>
> for i := range 4 {
> time.Sleep(500 * time.Millisecond)
> ch <- text + " " + fmt.Sprint(i)
> }
> }
>
> // Main
> // Hello 0
> // Hello 1
> // Hello 2
> // Hello 3
> // Done.
> ```
>
> > The `for msg := range ch { ... }` syntax performs `msg := <-ch` internally, where blocking occurs.
>
> `range` does not know how many values a channel will receive, it may be infinite. To stop the loop, close the channel to signal that no more values will be sent.
Receiving from a closed unbuffered channel returns the zero-value immediately.
## Buffered Channels [#buffered-channels]
Buffered channels in Go have a defined capacity. They can hold a certain number of values before blocking.
> * A buffered channel blocks on send only when the buffer is full.
> * Receiving removes a value from the buffer. If the buffer is empty, it blocks until a value is available.
> * After closing, remaining buffered values can still be received.
* Declare:
```go
ch := make(chan int, 3)
```
> Example:
>
> ```go
> func main() {
> ch := make(chan string, 4)
>
> go myFunc("Hello", ch)
>
> fmt.Println("Main")
>
> for range 8 {
> time.Sleep(1000 * time.Millisecond)
> fmt.Println(<-ch)
> }
>
> fmt.Println("End")
> }
>
> func myFunc(text string, ch chan string) {
> for i := range 8 {
> ch <- text + " " + fmt.Sprint(i)
> fmt.Println("myFunc loop.", i)
> }
>
> close(ch)
>
> fmt.Println("myFunc End")
> }
>
> // Main
> // myFunc loop. 0
> // myFunc loop. 1
> // myFunc loop. 2
> // myFunc loop. 3
> // Hello 0
> // myFunc loop. 4
> // Hello 1
> // myFunc loop. 5
> // Hello 2
> // myFunc loop. 6
> // Hello 3
> // myFunc loop. 7
> // myFunc End
> // Hello 4
> // Hello 5
> // Hello 6
> // Hello 7
> // End
> ```
## Channel Status [#channel-status]
A receiver can check a channel's status using the second return value of a receive operation.
```go
val, ok := <-ch
```
> The second return value (`ok`) is a boolean that indicates whether the receive operation obtained a value from an open channel.
>
> * `true`: A value was successfully received. The channel is still open.
> * `false`: The channel is closed and empty, so no more values can be received.
> Example:
>
> ```go
> func main() {
> ch := make(chan int)
>
> go func(ch chan int) {
> ch <- 1
> ch <- 2
> close(ch)
> fmt.Println("Closed.")
> }(ch)
>
> for {
> val, ok := <-ch
> if !ok {
> fmt.Println("Channel is closed. Received (zero-value):", val)
> break
> }
> fmt.Println("Received:", val)
> }
> }
>
> // Received: 1
> // Received: 2
> // Closed.
> // Channel is closed. Received (zero-value): 0
> ```
Sending on a closed channel causes a panic.
## The `select` Statement [#the-select-statement]
The `select` statement is a control structure for working with multiple channels simultaneously. It is similar to `switch` statement, but designed for channel operations.
> How it works:
>
> * `select` listens on multiple channels.
> * It executes the first ready case.
> * If multiple cases are ready, one is chosen randomly.
> * Without a `default`, it blocks until a case is ready.
> * With a `default`, it executes the `default` itself immediately if no cases are ready.
> Example:
>
> ```go
> func main() {
> // Preparation:
> ch1 := make(chan int)
> ch2 := make(chan int)
> ch3 := make(chan int)
>
> go func(ch chan int) {
> time.Sleep(time.Second)
> ch <- 1
> }(ch1)
>
> go func(ch chan int) {
> time.Sleep(time.Second * 3)
> ch <- 2
> }(ch2)
>
> go func(ch chan int) {
> time.Sleep(time.Second * 2)
> ch <- 3
> }(ch3)
>
> time.Sleep(time.Second * 5)
>
> // Usage:
> select {
> case val1 := <-ch1:
> fmt.Println(val1)
> case val2 := <-ch2:
> fmt.Println(val2)
> case val3 := <-ch3:
> fmt.Println(val3)
> default:
> fmt.Println("No channels are ready.")
> }
>
> fmt.Println("Done.")
> }
>
> // 2
> // Done.
> ```
A
`select`
statement is not a loop, it executes one case even if multiple are ready and then exits.
In the example above, two goroutines remain blocked after `select` receives from one channel because the other two
channels are never received. In a short-lived program like this, it is not noticeable because the program exits
immediately afterward. However, in a long-running program, those blocked goroutines never terminate, causing a
goroutine leak that also keeps their memory allocated.
This can be avoided using any cancellation mechanism.
## Read-Only & Write-Only Channels [#read-only--write-only-channels]
Channels can be restricted to `read-only` or `write-only`. This defines communication direction and improves safety and clarity.
> * Read-Only (`<-chan chanType`): Can only receive values. Sending is not allowed.
> * Write-Only (`chan<- chanType`): Can only send values. Receiving is not allowed.
```go
func sendData(ch chan<- int) { // ch is write-only
ch <- 42
// can't do: <-ch
close(ch)
}
func receiveData(ch <-chan int) { // ch is read-only
fmt.Println(<-ch)
// can't do: ch <- 24
}
func main() {
ch := make(chan int)
go sendData(ch)
receiveData(ch)
}
```
## Concurrency Patterns [#concurrency-patterns]
### Done Channel [#done-channel]
The Done Channel pattern signals cancellation or completion in goroutines. It uses a separate shared channel, which is closed to notify them to stop execution.
* Without a Done Channel:
```go
func myFunc() {
for {
fmt.Println("Working...")
}
}
func main() {
go myFunc()
time.Sleep(1 * time.Hour)
}
```
> The `myFunc` goroutine prints "Working..." continuously until the program exits.
* With a Done Channel:
```go
func myFunc(doneCh <-chan struct{}) {
for {
select {
case <-doneCh:
return
default:
fmt.Println("Working...")
time.Sleep(time.Second)
}
}
}
func main() {
doneCh := make(chan struct{})
go myFunc(doneCh)
time.Sleep(5 * time.Second)
close(doneCh)
time.Sleep(1 * time.Hour)
}
```
> The `myFunc` goroutine prints "Working..." for 5 seconds and then returns, even though the main program continues to run for an hour.
The `struct{}` type represents an empty struct in Go. It consumes zero bytes of memory, making it ideal for
signaling and control purposes without causing any memory overhead.
### Fan-In [#fan-in]
The Fan-In pattern combines multiple input channels into a single output channel so one consumer can read from all sources.
```
ch1 ----\
\
---> merge ---> out
/
ch2 ----/
```
> Example:
>
> ```go
> func merge(chs ...<-chan string) <-chan string {
> out := make(chan string)
>
> var wg sync.WaitGroup
> wg.Add(len(chs))
>
> for _, ch := range chs {
> go func(ch <-chan string) {
> defer wg.Done()
>
> for v := range ch {
> out <- v
> }
> }(ch)
> }
>
> go func() {
> wg.Wait()
> close(out)
> }()
>
> return out
> }
>
> func myFunc(nums ...int) <-chan string {
> ch := make(chan string)
>
> go func() {
> defer close(ch)
>
> // Example business logic that writes output to the channel:
> for _, n := range nums {
> ch <- fmt.Sprintf("Hi %v!", n)
> }
> }()
>
> return ch
> }
>
> func main() {
> a := myFunc(1, 3, 5)
> b := myFunc(2, 4, 6)
>
> for v := range merge(a, b) {
> fmt.Println(v)
> }
> }
>
> // Hi 1!
> // Hi 2!
> // Hi 4!
> // Hi 3!
> // Hi 6!
> // Hi 5!
> ```
>
> Output order is not guaranteed because values are forwarded as soon as they arrive from either channel.
## Context [#context]
In Go, a context is a mechanism for propagating cancellation signals, deadlines, timeouts, and request-scoped values through function calls and goroutines.
> The hierarchy:
>
> * Contexts form an immutable tree structure (we do not modify a context, we add subtrees to a context).
> * Child contexts inherit cancellation, deadlines, and values from their parent.
> * Cancelling a parent cancels all of its descendants.
> * A child cannot cancel its parent or its siblings.
> How it works:
>
> * `WithCancel()` (or one of the other variants) creates a child context and returns a cancellation function.
> * Every context provides a Done channel (`ctx.Done()`).
> * Calling `cancel()` (or when a timeout expires or a deadline is reached) closes the `ctx.Done()` channel.
> * Anyone depending on that context is immediately notified through the `ctx.Done()` channel.
>
> `ctx.Err()` returns the reason the context ended (`nil` if it hasn't ended yet).
Context only signals cancellation by closing the `ctx.Done()` channel. It does not stop your code automatically. Every
function or goroutine that accepts a context is responsible for checking `ctx.Done()` and implementing its own
cancellation or cleanup logic.
* Creating Contexts:
> The root context, the starting point for creating child contexts.
>
> ```go
> ctx := context.Background()
> ```
* > Cancellation:
>
> ```go
> ctx, cancel := context.WithCancel(ctx)
> ```
* > Timeout:
>
> ```go
> ctx, cancel := context.WithTimeout(ctx, 5*time.Second)
> ```
* > Deadline:
>
> ```go
> ctx, cancel := context.WithDeadline(ctx, time.Now().Add(5*time.Second))
> ```
* > Value:
>
> ```go
> ctx := context.WithValue(ctx, key, value)
> ```
Always call the returned `cancel()` function when a context is no longer needed. Calling `cancel()` multiple times is
safe.
Examples:
1. > ```go
> func myFunc(ctx context.Context) {
> for {
> select {
> case <-ctx.Done():
> return
> default:
> fmt.Println("Working...")
> time.Sleep(time.Second)
> }
> }
> }
>
> func main() {
> ctx := context.Background()
> ctx, cancel := context.WithTimeout(ctx, 3*time.Second)
> defer cancel()
>
> myFunc(ctx)
>
> fmt.Println(ctx.Err())
> }
>
> // Working...
> // Working...
> // Working...
> // Working...
> // context deadline exceeded
> ```
# Goroutines (/docs/go/concurrency/goroutines)
## Overview [#overview]
Goroutines are lightweight units of execution managed by the Go runtime scheduler to run functions concurrently.
> In general, program execution can be divided into two types of routines:
>
> * Main Routine: The first goroutine started by a Go program. It executes the `main()` function in the `main` package and defines the lifetime of the program. When the main routine finishes, the program exits immediately, even if other goroutines are still running.
> * Child Routine: Any goroutine started from another routine using the `go` keyword. It runs concurrently with the parent routine and performs work independently. It does not block the parent unless synchronization is explicitly implemented. It completes when its function returns or when the program terminates.
```go
func main() {
go expensiveFunc("Hello") // Run expensiveFunc concurrently (don't wait for it)
fmt.Println("Main")
time.Sleep(1700 * time.Millisecond)
}
func expensiveFunc(text string) {
for i := 0; i < 4; i++ {
time.Sleep(500 * time.Millisecond)
fmt.Println(text, i)
}
}
// Main
// Hello 0
// Hello 1
// Hello 2
```
> The `time.Sleep` in the `main` function is used only to give the goroutine enough time to run before the main routine exits. Without it, the program would terminate as soon as the main routine completes.
>
> The output shows only 3 iterations even though the loop is set for 4 iterations. This is because `time.Sleep` of `1700 ms` is less than the `4 * 500 ms` required for all iterations of `expensiveFunc`. Meaning only the first 3 iterations had enough time to complete before the program exited.
## WaitGroup [#waitgroup]
In Go, a `WaitGroup` from the `sync` package is used to wait for a collection of goroutines to complete before continuing execution in the main routine.
> How it works:
>
> * `Add(n)` increments the counter by `n` before starting the goroutines.
> * Each goroutine calls `Done()` when it completes. This decrements the counter by 1.
> * `Wait()` blocks the parent routine until the counter reaches zero.
```go
func main() {
var wg sync.WaitGroup
wg.Add(1)
go expensiveFunc("Hello", &wg)
fmt.Println("Main")
wg.Wait()
fmt.Println("End")
}
func expensiveFunc(text string, wg *sync.WaitGroup) {
defer wg.Done()
for i := range 4 {
time.Sleep(500 * time.Millisecond)
fmt.Println(text, i)
}
}
// Main
// Hello 0
// Hello 1
// Hello 2
// Hello 3
// End
```
> The business logic can be wrapped inside an anonymous function to keep it isolated:
>
> ```go
> func main() {
> var wg sync.WaitGroup
>
> wg.Add(1)
> go func(wg *sync.WaitGroup) {
> defer wg.Done()
> expensiveFunc("Hello")
> }(&wg)
>
> fmt.Println("Main")
>
> wg.Wait()
>
> fmt.Println("End")
> }
>
> func expensiveFunc(text string) {
> for i := range 4 {
> time.Sleep(500 * time.Millisecond)
> fmt.Println(text, i)
> }
> }
> ```
>
> This approach keeps `expensiveFunc` function clean and focused on its logic, while goroutine management remains separate.
## Mutexes [#mutexes]
In Go, a Mutex (Mutual Exclusion) from the `sync` package is a locking mechanism that allows only one goroutine at a time to read or modify shared data, forcing others to wait until it is free. This prevents race conditions and keeps the data consistent.
> How it works:
>
> * `Lock()` attempts to acquire the mutex.
> * If the mutex is free, the goroutine acquires it and continues.
> * If the mutex is locked, the goroutine is blocked until it becomes available.
> * `Unlock()` releases the mutex and allows one waiting goroutine to acquire it.
>
> Only one goroutine can hold the lock at a time. The mutex is not tied to any specific goroutine. Any goroutine can compete to acquire it when it becomes available.
Calling
`Unlock()`
on an
**unlocked**
mutex causes a panic.
# Binary Heaps (/docs/dsa/trees/binary-heaps)
## Overview [#overview]
A binary heap is a tree-shaped data structure, usually stored in an array, that keeps elements arranged so the highest-priority item is always at the root.
| Operations | Complexity | Description |
| ---------- | ---------- | --------------------------------------------------------- |
| Peek | O(1) | The top element is always at the root. |
| Insert | O(log n) | The tree needs to be adjusted to keep the heap structure. |
| Remove Top | O(log n) | The tree needs to be adjusted to keep the heap structure. |
### Structure [#structure]
Binary heaps are complete binary trees, meaning they stay compact by filling levels from left to right.
* Min-heap:
> Every parent is smaller than or equal to its children, so the minimum value is at the top.
>
> `[10, 15, 20, 30, 45, 50, 25, 75, 100]`
>
* Max-heap:
> Every parent is greater than or equal to its children, so the maximum value is at the top.
>
> `[100, 75, 50, 30, 45, 20, 25, 15, 10]`
>
### Relationships [#relationships]
In an array-based heap, parent and child positions are found using simple index formulas.
> Example heap: `[100, 75, 50, 30, 45, 20, 25, 15, 10]`
* Parent index:
```js
const parentIdx = Math.floor((i - 1) / 2);
```
> The parent index of `45` (at index 4) is `Math.floor((4 - 1) / 2)` = `Math.floor(1.5)` = `1`, which is `75`.
* Left child index:
```js
const leftChildIdx = i * 2 + 1;
```
> The left child index of 75 (at index 1) is `1 * 2 + 1` = `3`, which is `30`.
* Right child index:
```js
const rightChildIdx = i * 2 + 2;
```
> The right child index of 75 (at index 1) is `1 * 2 + 2` = `4`, which is `45`.
## Implementation [#implementation]
```js title="Binary Heap (PriorityQueue)" lineNumbers
class PriorityQueue {
constructor(compare) {
this.compare = compare;
this.heap = [];
}
peek() {
return this.heap[0];
}
insert(value) { ... } // [!code highlight]
remove() { ... } // [!code highlight]
#getParentIdx(i) {
return Math.floor((i - 1) / 2);
}
#getLeftChildIdx(i) {
return i * 2 + 1;
}
#getRightChildIdx(i) {
return i * 2 + 2;
}
#swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
#percolateUp(i) {
while (i > 0) {
const parentIdx = this.#getParentIdx(i);
if (this.compare(this.heap[i], this.heap[parentIdx]) >= 0) {
break;
}
this.#swap(i, parentIdx);
i = parentIdx;
}
}
#percolateDown(i) {
const len = this.heap.length;
while (true) {
const leftIdx = this.#getLeftChildIdx(i);
const rightIdx = this.#getRightChildIdx(i);
let best = i;
if (leftIdx < len && this.compare(this.heap[leftIdx], this.heap[best]) < 0) {
best = leftIdx;
}
if (rightIdx < len && this.compare(this.heap[rightIdx], this.heap[best]) < 0) {
best = rightIdx;
}
if (best === i) {
break;
}
this.#swap(i, best);
i = best;
}
}
}
```
> Usage:
>
> > The initial compare function decides what "higher priority" means, so it determines whether the heap behaves like a `min-heap` or a `max-heap`.
>
> ```js
> // Min-heap (numbers)
> const pq1 = new PriorityQueue((a, b) => a - b);
> pq1.insert(5);
> pq1.insert(2);
> pq1.insert(6);
> pq1.insert(10);
> console.log(pq1.remove()); // 2
> console.log(pq1.peek()); // 5
>
> // Max-heap (numbers)
> const pq2 = new PriorityQueue((a, b) => b - a);
> pq2.insert(5);
> pq2.insert(2);
> pq2.insert(6);
> pq2.insert(10);
> console.log(pq2.remove()); // 10
> console.log(pq2.peek()); // 6
>
> // Objects by field (min-heap)
> const tasks = new PriorityQueue((a, b) => a.priority - b.priority);
> tasks.insert({ id: 'a', priority: 10 });
> tasks.insert({ id: 'b', priority: 1 });
> console.log(tasks.remove()); // { id: "b", priority: 1 }
> ```
* Insert:
> The insert method appends the new value to the end of the array, then percolates up from that last index.
>
> > Percolating up:
> >
> > Repeatedly compare the current value with its parent. If the current value has higher priority according to `compare` (meaning `compare(child, parent) < 0`), swap them.
```js
insert(value) {
this.heap.push(value);
this.#percolateUp(this.heap.length - 1);
}
```
* Remove:
> The remove method first handles small cases. If the heap is empty, it returns `undefined`. If it has one item, it pops and returns it.
>
> Otherwise, it stores the top value (at index 0), replaces the root with the last element (using `pop()`), then percolates down from the root.
>
> > Percolating down:
> >
> > Repeatedly compare the current node with its children. Choose the child with higher priority according to `compare` (the one that should be closer to the top), and swap if that child should come before the current node. When done, return the stored top value.
```js
remove() {
const len = this.heap.length;
if (len === 0) {
return undefined;
}
if (len === 1) {
return this.heap.pop();
}
const top = this.heap[0];
this.heap[0] = this.heap.pop();
this.#percolateDown(0);
return top;
}
```
* Heapify (Optional): Turn a random array into a Binary Heap.
> It copies the array into the internal heap, then works bottom-up from the last parent to the root. At each parent index, it percolates down to fix that subtree. Once it reaches index 0, the whole array satisfies the heap structure.
>
> Inserting items one by one takes `O(n log n)`, but heapify builds the heap in `O(n)`.
```js
heapify(arr) {
this.heap = arr.slice();
const lastParentIdx = this.#getParentIdx(this.heap.length - 1);
for (let i = lastParentIdx; i >= 0; i--) {
this.#percolateDown(i);
}
}
```
> Usage:
>
> ```js
> const myArr = [6, 8, 3, 4, 5, 2, 0, 1, 7, 11, 18, 17, 16, 15, 14, 20, -1, -10, 30];
>
> // Min-heap:
> const pq1 = new PriorityQueue((a, b) => a - b);
> pq1.heapify(myArr);
> console.log(pq1.peek()); // -10
>
> // Max-heap:
> const pq2 = new PriorityQueue((a, b) => b - a);
> pq2.heapify(myArr);
> console.log(pq2.peek()); // 30
> ```
# Binary Search Tree (/docs/dsa/trees/binary-search-tree)
## Overview [#overview]
A Binary Search Tree (BST) is a type of binary tree that stores elements in a specific order. This order makes searching, inserting, and deleting efficient.
| Operations | Complexity | Description |
| ---------- | ---------- | ------------------------------------------------------------------- |
| Search | O(log n) | The value is found by moving left or right. |
| Insert | O(log n) | Need to move through the tree to find where the new item should go. |
| Remove | O(log n) | Need to move through the tree to find the item you want to remove. |
> * Nodes in the left subtree are smaller than the current node.
> * Nodes in the right subtree are greater than or equal to the current node.
## Implementation [#implementation]
```js title="Binray Search Tree" lineNumbers
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
search(value) { ... } // [!code highlight]
insert(value) { ... } // [!code highlight]
remove(value) { ... } // [!code highlight]
}
```
> Usage:
>
> ```js
> const tree = new BinarySearchTree();
>
> tree.insert(60);
> tree.insert(59);
> tree.insert(28);
> tree.insert(23);
> tree.insert(28);
> tree.insert(35);
> tree.insert(77);
> tree.insert(60);
> tree.insert(125);
> tree.insert(76);
>
> console.log(tree.search(59)); // TreeNode {value: 59, left: TreeNode, right: null}
>
> tree.remove(77);
> ```
* Search:
> The search starts at the root, compares the target value with the current node, moves left when the value is smaller, moves right when it is greater, and repeats this process until the value is found or there are no more nodes to visit.
```js
search(value) {
let current = this.root;
while (current) {
if (value < current.value) {
current = current.left;
} else if (value > current.value) {
current = current.right;
} else {
return current;
}
}
return null;
}
```
* Insert:
> The insert starts by creating a new node, sets it as the root if the tree is empty, otherwise walks down from the root, compares values, moves left when the value is smaller, moves right when it is greater or equal, and inserts the new node at the first empty child found.
```js
insert(value) {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
return;
}
let current = this.root;
while (current) {
// left:
if (value < current.value) {
if (current.left === null) {
current.left = newNode;
return;
}
current = current.left;
}
// right:
else {
if (current.right === null) {
current.right = newNode;
return;
}
current = current.right;
}
}
}
```
* Remove:
> The remove method first searches down the tree to find the node with the target value while also keeping track of its parent. If the value is not found, it stops.
>
> If the node has zero or one child, it removes the node by linking its parent directly to that child (or updating the root if the node is the root).
>
> If the node has two children, it finds the inorder successor (the smallest value in the right subtree), copies that successor value into the node being removed, and then deletes the successor node. That successor is guaranteed to have no left child (because it is the leftmost node of the right subtree), so removing it becomes the simple zero or one child case: you reconnect the successor's parent to the successor's right child.
```js
remove(value) {
let parent = null;
let current = this.root;
// move to the point:
while (current !== null && current.value !== value) {
parent = current;
if (value < current.value) {
current = current.left;
} else {
current = current.right;
}
}
// not found:
if (current === null) {
return;
}
// case 1: node has 0 or 1 child
if (current.left === null || current.right === null) {
const child = current.left !== null ? current.left : current.right;
if (parent === null) {
this.root = child;
} else if (parent.left === current) {
parent.left = child;
} else {
parent.right = child;
}
return;
}
// case 2: node has 2 children
let successorParent = current;
let successor = current.right;
while (successor.left !== null) {
successorParent = successor;
successor = successor.left;
}
current.value = successor.value;
if (successorParent.left === successor) {
successorParent.left = successor.right;
} else {
successorParent.right = successor.right;
}
}
```
# Binary Trees (/docs/dsa/trees/binary-trees)
## Overview [#overview]
A binary tree is a tree structure where each node can have up to two children, known as left and right children. It is called a "binary" tree because the branching factor of each node is limited to two.
### Types of Binary Trees [#types-of-binary-trees]
* Full Binary Tree:
> A full binary tree is a binary tree in which every node has either zero or two children.
>
* Perfect Binary Tree:
> A perfect binary tree is a binary tree in which every level is completely filled and all leaf nodes are on the same level.
>
>
> * Node count in each level: `2^curr_level`
> * Last level node count: `nodes_in_all_previous_levels + 1`
> * Total node count: `2^(height + 1) - 1`
* Complete Binary Tree:
> A complete binary tree is a binary tree in which all levels are filled except possibly the last level. The last level is filled from left to right.
>
* Balanced Binary Tree:
> A balanced binary tree is a binary tree in which the heights of the left and right subtrees of any node differ by at most one.
>
>
>
> The tree can become unbalanced depending on inserted and deleted items. In an unbalanced tree, lookup, insert, and delete operations can take `O(h)` time because the tree starts to behave like a linked list. To address the issue there are structures like [AVL Trees ↗](https://medium.com/basecs/the-little-avl-tree-that-could-86a3cae410c7) or [Red Black Trees ↗](https://medium.com/basecs/painting-nodes-black-with-red-black-trees-60eacb2be9a5). These structures perform extra rotations after insert or delete operations to keep the tree balanced.
# Trees (/docs/dsa/trees)
A tree is a hierarchical structure made of nodes that connect through parent and child links, starting from a single root at the top and spreading downward into branches. Each node holds data and links to its children, and the structure never forms cycles, which keeps every path clear and direct.
> Terminology:
>
> * `Root`: The top node that starts the tree and has no parent.
> * `Parent`: A node that has one or more children. Each child has one parent.
> * `Child`: A node directly linked to a parent. A parent can have many children.
> * `Sibling`: Nodes that share the same parent and sit on the same level.
> * `Leaf`: A node with no children.
> * `Edge`: A link that connects two nodes.
> * `Path`: A sequence of nodes connected by edges.
> * `Depth`: The number of edges from the root to a node. The root has depth 0.
> * `Height`: The number of edges on the longest path from the root to a leaf.
> * `Subtree`: A smaller tree inside a larger one.
> * `Ancestor`: Any node on the path from a node to the root.
> * `Descendant`: Any node below a given node.
>
# Radix Tree (Compressed Trie) (/docs/dsa/trees/radix-tree)
## Overview [#overview]
A Radix Tree is an optimized version of a [Trie (Prefix Tree)](./trie.mdx) that stores strings by combining chains of single-child nodes. Basically, each node can represent a sequence of characters instead of just one.
> Use cases: Autocomplete, IP routing tables, file system paths, dictionary storage, search indexing.
> Trie example for the following words: `bar`, `bark`, `bear`, `bell`, `bet`, `car`, `start`, `state`, `stop`, `key`.
>
# Trie (Prefix Tree) (/docs/dsa/trees/trie)
## Overview [#overview]
A trie is a tree based data structure that stores strings character by character. Each node represents a character, and paths from the root to marked nodes represent complete words. Words with the same prefix share the same path.
> Use cases: Autocomplete, spell checking, dictionary or word lookup, search suggestions.
| Operations | Complexity |
| -------------------- | ---------------- |
| Insert (word) | O(word length) |
| Search (word) | O(word length) |
| Starts With (prefix) | O(prefix length) |
> Trie example for the following words: `bar`, `bark`, `bear`, `bell`, `bet`, `car`, `start`, `state`, `stop`, `key`.
>
## Implementation [#implementation]
```js title="Trie (Prefix Tree)" lineNumbers
class TrieNode {
constructor() {
this.children = new Map();
this.isWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) { ... } // [!code highlight]
search(word) { ... } // [!code highlight]
startsWith(prefix) { ... } // [!code highlight]
#walk(str) {
let node = this.root;
for (const ch of str) {
const next = node.children.get(ch);
if (!next) return null;
node = next;
}
return node;
}
}
```
> Usage:
>
> ```js
> const trie = new Trie();
>
> trie.insert('stop');
> trie.insert('bark');
> trie.insert('bet');
> trie.insert('bar');
> trie.insert('car');
> trie.insert('bear');
> trie.insert('bell');
> trie.insert('start');
> trie.insert('key');
> trie.insert('state');
>
> console.log(trie.search('star')); // false
> console.log(trie.search('start')); // true
> console.log(trie.startsWith('st')); // true
> ```
* Insert:
> The insert method starts at the root, then loops through the characters of the word.
>
> For each character, it checks if the current node already has that character in its `children`. If it does not, it creates a new `TrieNode` and saves it under that character. Then it moves node to that child and keeps going.
>
> Once it has processed all characters of the word, it marks the last node with `isWord = true` so the trie knows a complete word ends there.
```js
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node.children.has(ch)) {
node.children.set(ch, new TrieNode());
}
node = node.children.get(ch);
}
node.isWord = true;
}
```
* Search:
> The search method starts from the root and follows the trie through the word's characters. If at any point a character is missing, the search fails right away and returns `false`.
>
> If it successfully reaches the node for the last character, it still needs one more check: `isWord` must be `true`, because the trie might contain the same path as a prefix without the full word being inserted.
```js
search(word) {
const node = this.#walk(word);
return !!node && node.isWord;
}
```
* Search Prefix:
> Same as search, but it does not require `isWord` to be `true`, because a prefix does not need to be a complete word.
```js
startsWith(prefix) {
return !!this.#walk(prefix);
}
```
* Suggestions (Optional): Get words that start with a given prefix.
> First, it follows the trie using the prefix characters to reach the node where the prefix ends (if the prefix path does not exist, it returns `[]`).
>
> From that node, it explores all possible next letters below it using a recursive search.
>
> > Recursive search: It keeps going down one path, building a longer string `(path + ch)`. When it cannot go further, it backtracks and tries the next path.
>
> Whenever it reaches a node where `isWord` is `true`, it means the built string is a complete stored word, so it adds it to the results.
>
> The search also stops early once it has already found enough suggestions.
```js
suggestions(prefix, limit = Infinity) {
const start = this.#walk(prefix);
if (!start) return [];
const out = [];
const dfs = (node, path) => {
if (out.length >= limit) return;
if (node.isWord) out.push(path);
for (const [ch, child] of node.children) {
dfs(child, path + ch);
if (out.length >= limit) return;
}
};
dfs(start, prefix);
return out;
}
```
> Usage:
>
> ```js
> console.log(trie.suggestions('st')); // ['start', 'state', 'stop']
> ```