DEV Community: Emmanuel Ayinde

Understanding Pointers in Go; The Two Runes (& and *) of Go

Emmanuel Ayinde — Fri, 01 May 2026 07:02:02 +0000

A thorough guide to addresses, pointers, and the elegant dance between them - grounded in how your computer's RAM actually works, with real examples, and an honest look at the trade-offs.

Let's Start with a Story
How RAM Actually Works
- RAM is a flat, indexed array of bytes
- How the CPU reads and writes memory
- What a "variable" actually is at runtime
- Memory alignment
The Stack and The Heap
- The Stack
- The Heap
- Escape analysis: Go decides for you
From RAM to Pointers - The Bridge
The & Operator
- What can & be applied to?
- The composite literal shortcut
The * Operator
- The full picture together
Pointer Types
nil Pointers
Pointers in Functions
- The problem: pass by value
- The solution: pass the address
- Performance: avoiding large copies
Pointers & Structs
- Linked list - the canonical pointer use case
Pointer Receivers
The new() Function
Advantages of Pointers in Go
- Mutation across function boundaries
- Avoiding expensive copies
- Expressing optional values
- Shared mutable state
- Recursive data structures
- Interface satisfaction and polymorphism
Disadvantages & Risks of Pointers in Go
- Nil pointer dereferences - runtime panics
- Heap allocations increase GC pressure
- Pointer indirection degrades cache performance
- Pointer aliasing makes code harder to reason about
- Ambiguous data ownership
- Increased cognitive overhead
When to Use Pointers
- Use a pointer when…
- Avoid a pointer when…
Common Gotchas
- Loop variable capture
- Returning a pointer to a local variable - safe in Go
- Pointer comparison
- Don't over-pointer
Quick Reference Cheat Sheet

Let's Start with a Story

Before we dive into the technical details, let's set the stage with a simple story. This isn't just a metaphor - it's a direct analogy to how pointers work in Go and how they relate to RAM.

🏠 The Address Story

Imagine your town has thousands of houses. Every house has a unique address - say, "42 Elm Street" - and each house contains a value: a family, furniture, secrets.

Now suppose your friend Alice wants to give you her house key. She has two choices: she could photocopy everything inside her house and hand you the copy - expensive, bulky, and changes to your copy don't affect hers. Or she could just write her address on a piece of paper and hand it to you. You now hold a pointer - a small slip of paper that tells you where the real house is. Walk to that address, and you can reach in and change the actual furniture.

In Go, & gives you the address. * lets you walk through the door.

Every Go developer eventually faces the & and * operators. They look cryptic at first - sometimes right next to each other on the same line - but once you understand what they represent at the hardware level, they become second nature. This post is a complete guide: from how RAM actually works, through every nuanced use of these operators, to an honest accounting of their trade-offs.

How RAM Actually Works

Before pointers make complete sense, you need a clear mental model of what RAM is and how your program interacts with it. This isn't hand-wavy background - it's the actual foundation that pointers are built on.

RAM is a flat, indexed array of bytes

Your computer's RAM (Random Access Memory) is, at the hardware level, an enormous contiguous array of bytes. Each byte has a unique numeric index - that index is its memory address. On a modern 64-bit system, addresses are 64-bit integers, giving you a theoretical address space of 2^64 bytes (~18 exabytes). In practice, your OS and hardware limit how much of that space maps to physical chips.

Physical RAM (conceptually)

Address    Byte value
──────────────────────
0x0000     0x00
0x0001     0x4A
0x0002     0x1F
0x0003     0x00
...        ...
0xFFFF...  0x00

When you declare var age int = 42 in Go, the runtime doesn't invent some abstract "variable" - it picks a location in this byte array, writes the binary representation of 42 into it (8 bytes for an int on 64-bit), and associates the name age with that address. The name exists only in your source code and debug symbols. At runtime, it's all addresses and bytes.

How the CPU reads and writes memory

The CPU communicates with RAM through a memory bus. A read: CPU puts an address on the bus, RAM returns the bytes at that location. A write: CPU puts an address and a value on the bus, RAM stores them. This takes nanoseconds - fast, but significantly slower than reading from CPU registers or cache.

This is why CPUs have L1, L2, and L3 caches - small, extremely fast memory banks between the CPU cores and main RAM. When you access an address, the CPU checks its caches first. A cache hit costs ~1–4 cycles. A cache miss - reaching all the way to RAM - costs ~100–300 cycles. That gap is enormous at scale, and it has real implications for how you structure data in Go.

CPU Access Latency (approximate)

Register          ~1 cycle
L1 Cache          ~4 cycles        (32–64 KB per core)
L2 Cache          ~12 cycles       (256 KB – 1 MB per core)
L3 Cache          ~40 cycles       (shared, 4–32 MB)
RAM               ~100–300 cycles  (GBs)
SSD               ~100,000 cycles
HDD               ~40,000,000 cycles

What a "variable" actually is at runtime

When the Go compiler processes your source code, every named variable gets an address assignment - either a stack offset or a heap address. By the time your code runs, the name age is just a shorthand. The emitted machine code uses addresses directly:

// Go source
age := 42
age = age + 1

// Rough equivalent in machine terms
MOV [0xc000014080], 42     // write 42 to address 0xc000014080
MOV RAX, [0xc000014080]    // load from that address into register RAX
ADD RAX, 1                 // add 1
MOV [0xc000014080], RAX    // write result back

This is the key insight: a pointer is simply a variable whose stored value is one of these numeric addresses. There is no magic. It's an integer that the runtime interprets as a location in RAM.

Memory alignment

The CPU doesn't read arbitrary single bytes from RAM in isolation - it reads words (8 bytes on 64-bit, aligned to natural boundaries). A float64 at address 0xc000014000 is one bus transaction. The same value at 0xc000014001 (misaligned) requires two. Go's compiler handles alignment automatically, inserting invisible padding bytes between struct fields where necessary.

type Bad struct {
    A bool    // 1 byte
              // 7 bytes padding (Go inserts this)
    B float64 // 8 bytes - must be 8-byte aligned
    C bool    // 1 byte
              // 7 bytes padding
}
// Total size: 24 bytes - holds only 10 bytes of real data

type Good struct {
    B float64 // 8 bytes
    A bool    // 1 byte
    C bool    // 1 byte
              // 6 bytes padding
}
// Total size: 16 bytes - same data, better layout

Field ordering matters. This is a real micro-optimisation in memory-bound Go programs.

The Stack and The Heap

Your Go program doesn't use RAM as one undifferentiated pool. It carves it into two primary regions with very different characteristics. Knowing which one your data lives in is essential for reasoning about pointer behaviour and performance.

The Stack

The stack is a contiguous block of memory managed in LIFO (last-in, first-out) order. Every goroutine gets its own stack - starting at 2KB in Go, growing dynamically as needed. When a function is called, Go pushes a stack frame onto it: a region holding the function's local variables, arguments, and return values. When the function returns, that entire frame is popped in one operation - the stack pointer register simply moves back.

Stack (grows downward)

High address
┌─────────────────────┐
│  main() frame       │
│    x = 5            │  ← stack pointer before double() call
├─────────────────────┤
│  double() frame     │
│    n = 5 (copy)     │  ← stack pointer during double()
└─────────────────────┘
Low address

When double() returns, its frame is gone instantly.
Stack pointer moves back. No GC. No bookkeeping.

Stack allocation is extremely fast - it's just arithmetic on the stack pointer register. Stack variables are also cache-friendly because they're packed tightly in a small region.

The constraint: the stack frame is temporary. Once a function returns, its frame is gone. If you return the address of a variable that lived on the stack... that address is now dangling. In C, this is undefined behaviour. Go handles it with escape analysis.

The Heap

The heap is a large region of memory managed dynamically. Allocations on the heap persist beyond the function that created them. Go's runtime manages a heap allocator and a garbage collector (GC) that periodically scans for unreferenced objects and reclaims them.

Heap allocation is slower than stack allocation: the allocator must find a free block, update metadata, and potentially trigger GC. Heap objects are also scattered across a large address range - more likely to cause cache misses compared to tightly-packed stack variables.

Memory Layout of a Running Go Program

┌─────────────────────┐  High addresses
│      Stack(s)       │  - one per goroutine, grows downward
│  goroutine 1 ↓      │  - fast, LIFO, automatically freed
│  goroutine 2 ↓      │
├─────────────────────┤
│   (unmapped gap)    │
├─────────────────────┤
│       Heap          │  - grows upward
│  [obj1][obj2]...    │  - GC-managed, persistent
├─────────────────────┤
│   BSS Segment       │  - zero-initialized globals
├─────────────────────┤
│   Data Segment      │  - initialized globals
├─────────────────────┤
│   Text Segment      │  - compiled machine code (read-only)
└─────────────────────┘  Low addresses

Escape analysis: Go decides for you

In Go, you don't call malloc or free. The compiler runs escape analysis - a static pass that determines whether a variable's lifetime can be confined to a stack frame, or whether it needs to "escape" to the heap.

The rules are intuitive:

If a variable's address is returned from a function, it escapes (the stack frame will be gone).
If a variable is stored in a data structure that outlives the current function, it escapes.
If a variable is too large for the stack, it escapes.

func stackAlloc() int {
    x := 42       // stays on stack - doesn't escape
    return x      // value is copied out, address is never exposed
}

func heapAlloc() *int {
    x := 42       // escapes to heap - address is returned
    return &x     // safe in Go - compiler promotes x to heap
}

You can inspect escape decisions yourself:

go build -gcflags="-m" ./...
# Output: ./main.go:6:2: x escapes to heap
#         ./main.go:2:2: x does not escape

Senior engineers use this to find and reduce unnecessary heap allocations in hot paths.

From RAM to Pointers - The Bridge

Now the picture snaps together. You have:

RAM: a flat byte array, every location has a numeric address.
Stack: fast, temporary, cleaned up automatically when a function returns.
Heap: persistent, GC-managed, slower to allocate.
Variables: names the compiler associates with specific RAM addresses.

A pointer is exactly what it sounds like: a variable whose stored value is an address in RAM. It points at another location in memory. That's the entire concept.

RAM (partial view of a running Go program)

Address        Value                What it is
──────────────────────────────────────────────────────────────
0xc000014070   [42, 0, 0, 0,        age int = 42
                0,  0, 0, 0]         (8 bytes, little-endian)

0xc000014078   [0x70, 0x40, 0x01,   ptr *int = &age
                0x00, 0xc0, 0x00,    (8 bytes storing address
                0x00, 0x00]           0xc000014070)

Reading age: go to 0xc000014070, read 8 bytes, interpret as int → 42
Reading ptr: go to 0xc000014078, read 8 bytes, interpret as address → 0xc000014070
Reading *ptr: go to 0xc000014078, get 0xc000014070, then go there, read 8 bytes → 42

Two memory reads instead of one. That's dereferencing - and that cost is real, though usually trivial in isolation. It compounds in tight loops.

The `&` Operator - "Give me the address"

The & symbol placed before a variable is the address-of operator. It evaluates to the memory address of its operand - not the value stored there, but the location in RAM where the value lives.

&x asks: "Where in RAM does x live?"

package main

import "fmt"

func main() {
    age := 42

    fmt.Println(age)   // 42           - the value
    fmt.Println(&age)  // 0xc000014080 - the RAM address

    // & produces a *int (pointer to int)
    var ptr *int = &age
    fmt.Println(ptr)   // 0xc000014080 - same address
}

The type of &age is *int - a pointer to an int. & can be applied to any addressable value: variables, struct fields, array/slice elements, and more.

What can `&` be applied to?

type Person struct {
    Name string
    Age  int
}

func main() {
    // ✅ Variable
    x := 10
    _ = &x

    // ✅ Struct field
    p := Person{Name: "Alice", Age: 30}
    _ = &p.Age   // *int pointing into the struct's RAM location

    // ✅ Slice element
    nums := []int{1, 2, 3}
    _ = &nums[0]  // *int pointing at first element of backing array

    // ✅ Composite literal - Go heap-allocates it and gives you the pointer
    pp := &Person{Name: "Bob", Age: 25}  // *Person
    _ = pp

    // ❌ NOT addressable - compile error
    // _ = &42         (literal - no stable RAM location)
    // _ = &len(nums)  (function return value - temporary register value)
}

⚠️ Literals like 42 are typically inlined into machine instructions - they don't live at a stable, named RAM address. Taking their address is a compile-time error.

The composite literal shortcut

// Verbose
p := Person{Name: "Alice", Age: 30}
ptr := &p      // *Person

// Idiomatic - allocates on heap, returns pointer immediately
ptr2 := &Person{Name: "Alice", Age: 30}  // *Person

// Seen everywhere in real Go codebases:
resp := &http.Response{StatusCode: 200}
node := &ListNode{Val: 42, Next: nil}

The `*` Operator - "Go to that address"

The * symbol has two distinct jobs in Go. Conflating them is the most common source of pointer confusion.

Job	Context	Meaning
Type declaration	Type position	`*T` means "a pointer to T"
Dereference	Expression position	`*ptr` means "follow this pointer into RAM and give me the value"

**ptr says: "Follow the address. Read what's in RAM at that location."*

func main() {
    score := 100

    // & → give me the RAM address   (* in TYPE position)
    var ptr *int = &score

    fmt.Println(ptr)   // 0xc000014080  (a RAM address)

    // * → go to that RAM address    (* in EXPRESSION position)
    fmt.Println(*ptr)  // 100           (the value at that address)

    // Modify through the pointer - writes directly to score's RAM location
    *ptr = 200
    fmt.Println(score) // 200 - score itself changed
}

The full picture together

Step 1: score := 100
  ┌──────────────────────────┐
  │ score  @0xc000014080     │
  │        value = 100       │
  └──────────────────────────┘

Step 2: ptr := &score
  ┌──────────────────────────┐      ┌────────────────────────────┐
  │ score  @0xc000014080     │◄─────│ ptr    @0xc000014088       │
  │        value = 100       │      │        value = 0xc000014080│
  └──────────────────────────┘      └────────────────────────────┘

Step 3: *ptr = 200
  ┌──────────────────────────┐      ┌────────────────────────────┐
  │ score  @0xc000014080     │◄─────│ ptr    @0xc000014088       │
  │        value = 200 ✏️    │      │        value = 0xc000014080│
  └──────────────────────────┘      └────────────────────────────┘

Pointer Types Are Strongly Typed

A *int is a completely different type from a *string or a *Person. The compiler enforces this strictly - no implicit casting between pointer types.

name   := "Alice"
age    := 30
active := true

var pName   *string  = &name    // ✅
var pAge    *int     = &age     // ✅
var pActive *bool    = &active  // ✅

// ❌ Type mismatch - compile error
// pAge = &name   // cannot use *string as *int

// Dereferencing gives back the original type
var n string = *pName   // "Alice"
var a int    = *pAge    // 30

Variable Type	Pointer Type	Dereference Type
`int`	`*int`	`int`
`string`	`*string`	`string`
`bool`	`*bool`	`bool`
`float64`	`*float64`	`float64`
`Person` (struct)	`*Person`	`Person`
`[]int` (slice)	`*[]int`	`[]int`
`*int` (pointer)	`**int`	`*int`

💡 **int is valid - a pointer to a pointer to an int. You rarely need more than one level of indirection in practice.

`nil` - The Zero Value of Pointers

A pointer that hasn't been assigned holds the zero value nil - numerically, address 0x0. The OS deliberately leaves address 0 unmapped. Any dereference of a nil pointer causes a segmentation fault, which Go catches and converts into a runtime panic.

🚪 The Phantom Address

A nil pointer is a slip of paper with no address written on it. Your car starts, you pull out of the driveway, and there's nowhere to go. Go terminates the program: runtime: invalid memory address or nil pointer dereference.

func main() {
    var ptr *int        // nil - holds address 0x0
    fmt.Println(ptr)   // <nil>

    // ❌ Panics at runtime - dereferences address 0x0
    // fmt.Println(*ptr)

    // ✅ Always check before dereferencing
    if ptr != nil {
        fmt.Println(*ptr)
    } else {
        fmt.Println("pointer is nil - nothing to read")
    }
}

// Idiomatic Go: return nil to signal "not found"
func findUser(id int) *User {
    if id <= 0 {
        return nil
    }
    return &User{ID: id, Name: "Alice"}
}

⚠️ Returning *T with a possible nil is a contract. The caller is obligated to check. Forgetting to nil-check before dereferencing is one of the most common sources of production panics in Go.

Pointers in Functions

In Go, function arguments are passed by value - the callee receives a copy, allocated in its own stack frame. Modifying it has no effect on the original.

The problem: pass by value

func double(n int) {
    n = n * 2    // modifies the stack copy, not the original
}

func main() {
    x := 5
    double(x)
    fmt.Println(x)  // 5 - unchanged
}

The solution: pass the address

func double(n *int) {
    *n = *n * 2   // follows the pointer into the caller's stack frame
}

func main() {
    x := 5
    double(&x)
    fmt.Println(x)  // 10
}

📮 The Photocopy vs. House Key

double(x) hands the function a photocopy of 5. It scribbles on the copy and throws it away. Your original is untouched. double(&x) hands it your house key - the function walks to the actual RAM location and changes what's there.

Performance: avoiding large copies

type BigReport struct {
    Title   string
    Data    [10000]float64  // ~80KB
    Summary string
}

// ❌ Copies ~80KB on every call
func processReport(r BigReport) { ... }

// ✅ Copies only 8 bytes (the pointer)
func processReport(r *BigReport) { ... }

In hot paths - data pipelines, request handlers, game loops - this difference is measurable. Benchmarks regularly show 2–5x throughput improvement for moderately sized structs.

Pointers & Structs

When you have a pointer to a struct, Go auto-dereferences on dot access - p.Name and (*p).Name are identical. This is pure syntactic sugar.

type Person struct {
    Name string
    Age  int
}

func main() {
    p := &Person{Name: "Alice", Age: 30}

    fmt.Println((*p).Name)  // "Alice" - explicit dereference
    fmt.Println(p.Name)     // "Alice" - identical, idiomatic

    p.Age = 31  // modifies the heap-allocated Person directly
}

Linked list - the canonical pointer use case

type Node struct {
    Value int
    Next  *Node  // pointer to next node - 8 bytes
}

func main() {
    head := &Node{Value: 1}
    head.Next = &Node{Value: 2}
    head.Next.Next = &Node{Value: 3}

    for curr := head; curr != nil; curr = curr.Next {
        fmt.Println(curr.Value)
    }
    // Output: 1, 2, 3
}

A Node value cannot contain another Node value - that would be infinite size at compile time. A *Node is just 8 bytes. This is why recursive data structures require pointers.

Pointer Receivers vs Value Receivers

type Counter struct {
    count int
}

// Value receiver - operates on a copy
func (c Counter) Value() int {
    return c.count
}

// Pointer receiver - operates on the original in RAM
func (c *Counter) Increment() {
    c.count++
}

func (c *Counter) Reset() {
    c.count = 0
}

func main() {
    c := Counter{}
    c.Increment()  // Go auto-takes address: (&c).Increment()
    c.Increment()
    fmt.Println(c.Value())  // 2
    c.Reset()
    fmt.Println(c.Value())  // 0
}

Situation	Use
Method needs to modify the receiver	Pointer receiver `*T`
Struct is large (avoid copying)	Pointer receiver `*T`
Method is read-only, struct is small	Value receiver `T`
Any method on type uses `*T` - be consistent	Pointer receiver `*T`

💡 Mixed receiver sets cause subtle interface satisfaction bugs. If any method uses a pointer receiver, use pointer receivers throughout.

The `new()` Function

new(T) heap-allocates zeroed storage for type T and returns a *T. It's equivalent to &T{} for most cases.

func main() {
    p := new(int)      // *int pointing to 0 on the heap
    fmt.Println(*p)    // 0
    *p = 42
    fmt.Println(*p)    // 42

    s1 := new(Person)  // *Person, all fields zeroed
    s2 := &Person{}    // identical
    _ = s1; _ = s2

    flag := new(bool)  // most natural use - primitive zero-value pointer
    *flag = true
}

💡 Prefer &T{} for structs (allows field initialization). new() is cleaner for primitives.

Advantages of Pointers in Go

Pointers are not just a feature - in the right contexts, they're the correct tool. Here's a precise breakdown of what they buy you.

1. Mutation across function boundaries

The primary reason pointers exist. Go's pass-by-value semantics mean a function cannot modify its caller's data without a pointer. Pointer parameters are an explicit, visible contract: this function will modify the value at this address.

func normalise(v *Vector3) {
    mag := math.Sqrt(v.X*v.X + v.Y*v.Y + v.Z*v.Z)
    v.X /= mag
    v.Y /= mag
    v.Z /= mag
}

The caller sees the mutation. The function signature makes it visible and deliberate.

2. Avoiding expensive copies

For structs beyond a few dozen bytes, passing by pointer is meaningfully faster. The function call overhead drops from O(struct size) to O(8 bytes), and the stack frame is smaller.

// Copies 256 bytes on every call
func render(m Matrix4x4) { ... }

// Copies 8 bytes
func render(m *Matrix4x4) { ... }

In tight loops or hot paths, benchmarks regularly show 2–5x throughput improvements for moderately sized structs.

3. Expressing optional values

A *T can be nil, giving you a clean way to represent the absence of a value - without a separate boolean flag or a magic sentinel.

type Config struct {
    Timeout  *time.Duration  // nil means "use the default"
    MaxRetry *int            // nil means "unlimited"
}

Immediately readable: if the pointer is nil, the field was not set.

4. Shared mutable state

When multiple parts of your code operate on the same data - a cache, a connection pool, an in-memory store - pointers give all of them a reference to the same RAM location.

type Cache struct {
    mu    sync.RWMutex
    store map[string]string
}

func NewCache() *Cache {
    return &Cache{store: make(map[string]string)}
}

// Every caller holding *Cache operates on the same object in RAM

Without pointers, every assignment would copy the cache - updates in one copy would be invisible to others.

5. Recursive data structures

Trees, linked lists, graphs, tries - any structure where a node references a same-type node requires a pointer. A Node value cannot contain a Node value. A *Node is 8 bytes.

6. Interface satisfaction and polymorphism

Pointer receivers expand the method set of a type. An interface satisfied by *T cannot be satisfied by T alone. Pointer types and interfaces together form Go's core abstraction mechanism for dependency injection and plugin architectures.

Disadvantages & Risks of Pointers in Go

Every advantage has a corresponding cost. Experienced engineers weigh these deliberately.

1. Nil pointer dereferences - runtime panics

The most immediate risk. A *T can be nil, and any dereference panics at runtime. Unlike type errors, there's no static guarantee that a pointer is non-nil. Go does not have non-nullable pointer types. Every *T is implicitly nullable.

func processUser(u *User) {
    fmt.Println(u.Name)  // panics if u is nil - no compiler warning
}

In large codebases, nil checks become tedious and are frequently omitted. Consider whether a *T parameter is truly necessary, or whether a T value would remove the problem entirely.

2. Heap allocations increase GC pressure

Every time a value escapes to the heap, Go's GC is responsible for eventually reclaiming it. In systems with millions of small, short-lived pointer allocations - a common pattern in naively written Go HTTP servers - GC overhead becomes significant. Even Go's low-latency concurrent GC adds latency jitter that's hard to eliminate without rethinking allocation patterns.

// Allocates a new *Response on the heap for every request
func handleRequest(r *http.Request) *Response {
    return &Response{...}
}

// In hot paths, sync.Pool amortises allocations
var pool = sync.Pool{New: func() any { return &Response{} }}

Profile with go tool pprof and check allocs/op in benchmarks. Stack allocations cost nothing to GC - they're freed when the function returns.

3. Pointer indirection degrades cache performance

Modern CPUs are optimised for sequential memory access. When data is laid out contiguously in RAM ([]struct{}), the CPU prefetcher pulls entire cache lines ahead of your loop. When data is a slice of pointers ([]*struct{}), each element is a random jump somewhere in the heap - a potential cache miss on every access.

// Cache-friendly - all Particle data is contiguous in RAM
particles := make([]Particle, 100_000)
for i := range particles {
    particles[i].X += particles[i].VX
}

// Cache-hostile - each pointer is a separate heap allocation
particles := make([]*Particle, 100_000)
for _, p := range particles {
    p.X += p.VX  // potential cache miss on every iteration
}

For large datasets, the throughput difference can be 10x or more. This is why Go's standard library and high-performance Go code strongly prefer value slices over pointer slices.

4. Pointer aliasing makes code harder to reason about

When two pointers point to the same address, a write through one silently changes what the other sees. The compiler cannot assume pointer parameters are distinct, which limits certain optimizations and makes code harder to audit.

func add(a, b, result *int) {
    *result = *a + *b
}

x := 5
add(&x, &x, &x)  // all three alias the same address
// result = 5 + 5, then written to x - order matters here

In concurrent code, aliasing combined with unsynchronized writes produces data races - some of the hardest bugs to reproduce and diagnose.

5. Ambiguous data ownership

With value semantics, ownership is clear: each copy is independent. With pointers, multiple parts of the code may hold a reference to the same object - and it's not always obvious who owns it, who can mutate it, or when it's safe to discard.

Go's GC removes the memory-safety aspect (no use-after-free), but logical ownership ambiguity remains. In complex systems, poorly managed pointer sharing leads to subtle state corruption.

// Who owns cfg? Can handleFoo mutate it? Can handleBar?
// If both do concurrently, do they race?
func setup(cfg *Config) {
    go handleFoo(cfg)
    go handleBar(cfg)
}

Rust's borrow checker enforces ownership at compile time. Go leaves it to convention, documentation, and sync primitives.

6. Increased cognitive overhead

Code passing and returning pointers requires the reader to track multiple levels of indirection. p.Name looks like a value access, but if p is a *Person, it's a dereference followed by a field read. In deeply nested pointer chains, this becomes genuinely difficult to follow, and mutation bugs are non-obvious.

Summary table

	Value (`T`)	Pointer (`*T`)
Allocation	Stack (usually)	Heap (usually)
GC pressure	None	Yes - GC must track and reclaim
Nil risk	None	Runtime panic if nil
Mutation semantics	Copy - caller unaffected	Shared - caller sees changes
Cache behaviour	Contiguous, prefetcher-friendly	Scattered, potential cache misses
Ownership clarity	Clear - independent copies	Requires explicit discipline
Copy cost on call	O(size of T)	O(8 bytes) always

When to Use Pointers

Go's philosophy is that you should reach for a pointer deliberately, not reflexively.

✅ Use a pointer when…

You need to mutate the original value inside a function or method.
The struct is large enough that copying is measurably wasteful (~64–128 bytes as a rough heuristic - benchmark to be sure).
You want to express optionality - a nil-able *T instead of a zero value.
You're building recursive data structures (trees, linked lists, graphs).
You're implementing interfaces where pointer receivers are required.
You need shared mutable state across goroutines (with appropriate synchronization).

❌ Avoid a pointer when…

The value is small (int, float64, bool, small struct) and doesn't need mutation.
You want to signal immutability - a value parameter tells the caller "this function won't touch your data."
The type is already a reference type: slices, maps, channels, and interfaces contain internal pointers. Wrapping them in an additional * is almost never necessary.
You're iterating over a large dataset - value slices are dramatically more cache-friendly than pointer slices.

⚠️ Slices and maps already have pointer semantics for element mutation. You only need *[]int if the function needs to affect the caller's slice header (e.g. an append that must be visible to the caller).

func modifyElement(s []int) {
    s[0] = 999  // ✅ modifies backing array - visible to caller
}

func appendToSlice(s *[]int) {
    *s = append(*s, 42)  // ✅ caller sees new length
}

func appendWrong(s []int) {
    s = append(s, 42)  // ❌ modifies local copy of slice header only
}

ommon Gotchas

1. Loop variable capture

// ❌ Classic bug - all pointers point to the same loop variable
ptrs := make([]*int, 3)
for i := 0; i < 3; i++ {
    ptrs[i] = &i   // &i is the same address every iteration
}
// After loop, i == 3. All three ptrs point to it.
fmt.Println(*ptrs[0], *ptrs[1], *ptrs[2])  // 3 3 3

// ✅ Fix - new variable per iteration
for i := 0; i < 3; i++ {
    v := i
    ptrs[i] = &v
}
fmt.Println(*ptrs[0], *ptrs[1], *ptrs[2])  // 0 1 2

// Note: Go 1.22+ changed loop variable semantics - per-iteration by default

2. Returning a pointer to a local variable - safe in Go

In C, returning &localVar is undefined behaviour - the stack frame is gone. In Go, escape analysis detects this and promotes x to the heap automatically.

func newInt(v int) *int {
    x := v    // compiler promotes x to heap
    return &x // ✅ perfectly safe
}

Run go build -gcflags="-m" to confirm which variables escape.

3. Pointer comparison

a := 42
b := 42
pa, pb := &a, &b

fmt.Println(pa == pb)    // false - different RAM addresses
fmt.Println(pa == &a)    // true  - same address
fmt.Println(*pa == *pb)  // true  - same value at different addresses

Pointer equality checks address identity, not value equality. A frequent source of bugs when engineers expect == to compare pointed-to values.

4. Don't over-pointer

Scattering * everywhere "for performance" backfires: unnecessary heap allocations increase GC pressure, pointer indirection causes cache misses, and nil checks add noise throughout the codebase. Use pointers when you have a concrete reason: mutation, large size, optionality, or shared state.

Quick Reference Cheat Sheet

Expression	Reads as	Result Type	What it does
`&x`	"address of x"	`*T`	Returns the RAM address of variable x
`*p`	"value at p"	`T`	Reads the value at the RAM address in p
`*p = v`	"write v to p"	-	Writes v into RAM at the address in p
`var p *T`	"p is a pointer to T"	`*T`	Declares p as a pointer (zero value: nil / 0x0)
`new(T)`	"allocate a T"	`*T`	Heap-allocates zero-value T, returns pointer
`&T{...}`	"new T literal"	`*T`	Heap-allocates initialised T, returns pointer
`p == nil`	"is p nil?"	`bool`	True if p holds 0x0 - points nowhere
`p.Field`	"field via pointer"	field type	Auto-dereferences; identical to `(*p).Field`

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth
discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data
structures and algorithms, and other exciting tech topics, follow me on:

Emmanuel Ayinde Follow

Lead Full-Stack Software Engineer | Backend & AI Systems | Building Scalable, Production-Ready Products

Stay tuned and happy coding 👨‍💻🚀

[Boost]

Emmanuel Ayinde — Thu, 01 Jan 2026 11:26:06 +0000

Gergely Orosz

Dec 1 '20

Six Principles Your Resume Should Follow - So Recruiters Will Read It

#books #career #beginners #resume

322

Comments 10

9 min read

Cracking Quick Sort algorithm: From Theory to Practice in Minutes

Emmanuel Ayinde — Wed, 06 Nov 2024 21:23:05 +0000

Quicksort is one of the fastest sorting algorithms. It takes an array of values, chooses one of the values as the 'pivot' element, and moves the other values so that lower values are on the left of the pivot element, and higher values are on the right of it.

Quick Sort stands as one of the most elegant and efficient sorting algorithms in the world of algorithms. Unlike simpler algorithms like Bubble Sort or Selection Sort, Quick Sort employs a sophisticated divide-and-conquer strategy that makes it significantly faster in practice. While Merge Sort also uses divide-and-conquer, Quick Sort's unique partitioning approach often leads to better performance and memory usage.

Average Time Complexity: O(n log n)

Worst Case Time Complexity: O(n²)

Space Complexity: O(log n)

What is quick sort algorithm
How does quick sort work
- Time Complexity
- Space Complexity
JavaScript Implementation
Conclusion

What is Quick Sort Algorithm

Quick Sort is a highly efficient sorting algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot. Unlike Merge Sort, which divides first and combines later, Quick Sort does its sorting during the partitioning process.

Consider this comparison with other sorting algorithms:

Algorithm	Time Complexity (Average)	Space Complexity	In-Place?
Quick Sort	O(n log n)	O(log n)	Yes
Merge Sort	O(n log n)	O(n)	No
Bubble Sort	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(1)	Yes
Heap Sort	O(n log n)	O(1)	Yes

How does quick sort work?

Before we dive into the JavaScript implementation of quick sort algorithms, let's take a step-by-step approach to understand how the algorithm works by manually sorting a simple array of numbers with just four simple steps.

Quick sort can be broken down into four simple steps:

Choose a pivot element from the array. This element could be the first, the last, the middle or even a random element from the list/array.

Rearrange the array so that all elements less than the pivot are on the left, and all elements greater are on the right.

Swap the pivot element with the first element of the greater values, so that the pivot is in the middle.

Recursively apply the same operations to the sub-arrays on the left and right of the pivot.

Let's apply these steps to a real array. Shall we?

Initial Array: [3, 6, 2, 7, 1]

Step 1: Choose a Pivot

We choose the last element as the pivot for simplicity.
Pivot = 1

Step 2: Rearrange Array Around Pivot

Rearrange so that all elements less than the pivot (1) are on the left and all elements greater are on the right.
As we go through each element:
- 3 (greater than 1) → stays on the right.
- 6 (greater than 1) → stays on the right.
- 2 (greater than 1) → stays on the right.
- 7 (greater than 1) → stays on the right.
Rearranged Array: [1, 6, 2, 7, 3]

Step 3: Swap Pivot to its Correct Position

Swap the pivot (1) with the first element greater than it, which is 6.
Array after swapping: [1, 3, 2, 7, 6]
Now, 1 is in the correct position (index 0).

Step 4: Recursive Quick Sort on Sub-arrays

Left Sub-array: [] (no elements left of 1, so nothing to sort here)
Right Sub-array: [3, 2, 7, 6]

Sorting the Right Sub-array `[3, 2, 7, 6]` recursively

Step 1: Choose a Pivot

Pivot = 6 (last element)

Step 2: Rearrange Array Around Pivot

Arrange elements less than 6 to the left and greater ones to the right:
- 3 (less than 6) → stays on the left.
- 2 (less than 6) → stays on the left.
- 7 (greater than 6) → stays on the right.
Rearranged Array: [3, 2, 6, 7]

Step 3: Swap Pivot to Its Correct Position

6 is already in the correct position (index 2).
Array: [1, 3, 2, 6, 7]

Step 4: Recursive Quick Sort on Sub-arrays

Left Sub-array: [3, 2]
Right Sub-array: [7] (single element, no sorting needed)

Sorting the Left Sub-array `[3, 2]`

Step 1: Choose a Pivot

Pivot = 2 (last element)

Step 2: Rearrange Array Around Pivot

Rearrange so elements less than 2 are on the left:
- 3 (greater than 2) → stays on the right.
Rearranged Array: [2, 3]

Step 3: Swap Pivot to Its Correct Position

2 is already in the correct position (index 1).
Array: [1, 2, 3, 6, 7]

Step 4: Recursive Quick Sort on Sub-arrays

Left Sub-array: [] (no elements)
Right Sub-array: [3] (single element, no sorting needed)

Final Sorted Array

After sorting all the sub-arrays, we get the final sorted array:

Sorted Array: [1, 2, 3, 6, 7]

Below is the best illustration of how this works in real life:

Time Complexity

Quick Sort's time complexity varies based on pivot selection:

Best Case (O(n log n)):
- Occurs when the pivot always divides the array into equal halves
- Similar to Merge Sort's performance
Average Case (O(n log n)):
- Most practical scenarios
- Better than Merge Sort due to better cache utilization
Worst Case (O(n²)):
- Occurs with already sorted arrays and poor pivot selection
- Can be avoided with good pivot selection strategies

Space Complexity

Quick Sort's space complexity is O(log n) due to:

Recursive call stack depth
In-place partitioning (unlike Merge Sort's O(n) extra space)
Better memory efficiency compared to Merge Sort

JavaScript Implementation

function quickSort(arr) {
  // Base case: arrays with length 0 or 1 are already sorted
  if (arr.length <= 1) return arr;

  // Helper function to swap elements
  const swap = (i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  };

  // Partition function using Lomuto's partition scheme
  function partition(low, high) {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        swap(i, j);
      }
    }
    swap(i + 1, high);
    return i + 1;
  }

  // Main quickSort function implementation
  function quickSortHelper(low, high) {
    if (low < high) {
      const pivotIndex = partition(low, high);
      quickSortHelper(low, pivotIndex - 1); // Sort left side
      quickSortHelper(pivotIndex + 1, high); // Sort right side
    }
  }

  quickSortHelper(0, arr.length - 1);
  return arr;
}

Conclusion

Quick Sort is a popular choice due to its efficiency and in-place sorting. It outperforms simpler algorithms like Bubble Sort and Selection Sort with its O(n log n) average-case performance and low space complexity.

Key takeaways:

Choose pivot selection strategy carefully
Consider input characteristics when deciding between Quick Sort and other algorithms
Use randomized pivot selection for better average-case performance

Stay Updated and Connected

Emmanuel Ayinde Follow

Lead Full-Stack Software Engineer | Backend & AI Systems | Building Scalable, Production-Ready Products

Stay tuned and happy coding 👨‍💻🚀

Understanding merge sort algorithm: Beginner's guide to mastering sorting algorithm

Emmanuel Ayinde — Mon, 04 Nov 2024 22:42:08 +0000

In our previous articles, we've learned about quite a number of sorting algorithms like Bubble Sort, Selection Sort as well as Insertion Sort. We've learned that while these sorting algorithms are very easy to implement, they are not efficient for large datasets, which means we need a more efficient algorithm to handle sorting large datasets, hence merge sort. In this series, we'll go through how merge sort works and how it can be implemented in JavaScript. You ready?

What is Merge Sort Algorithm?
How Merge Sort Algorithms Works
- Time Complexity
- Space Complexity
Implementation in JavaScript
Conclusion

What is Merge Sort Algorithm?

Merge Sort Algorithm is an excellent sorting algorithm that follows the divide-and-conquer principle. Unlike simpler algorithms like Selection Sort and Bubble Sort that make multiple passes through the array comparing adjacent elements, Merge Sort takes a more strategic approach:

Divide: firstly, merge sort split the array into two halves
Conquer: secondly, it recursively sort each half
Combine: lastly, it merges the sorted halves back together

This approach consistently outperforms simpler O(n²) algorithms like Selection Sort and Bubble Sort when dealing with larger datasets.

How Merge Sort Algorithms Works

We've seen that merge sort works by using the popular divide-and-conquer approach. Below is a visual representation of how it works.

Now that we'v seen the magic, let's walk through how merge sort algorithm works by manually sorting this array: [38, 27, 43, 3, 9, 82, 10] using the approach mentioned above.

Step 1: Dividing

The first step in merge sort is dividing the array into subarrays, and then dividing each subarray into subarrays, and the subarray into subarrays until we have just one item left in all the subarrays.

Step 2: Merging Back (Conquering)

The second step is to start sorting those subarrays from the ground up.

Time Complexity

Merge Sort achieves O(n log n) time complexity in all cases (best, average, and worst), making it more efficient than O(n²) algorithms for larger datasets.

Here's why:

Dividing: The array is divided log n times (each division cuts the size in half)
Merging: Each level of merging requires n operations
Total: n operations × log n levels = O(n log n)

Compare this to:

Bubble Sort: O(n²)
Selection Sort: O(n²)
Merge Sort: O(n log n)

For an array of 1,000 elements:

O(n²) ≈ 1,000,000 operations
O(n log n) ≈ 10,000 operations

Space Complexity

Merge Sort requires O(n) additional space to store the temporary arrays during merging. While this is more than the O(1) space needed by Bubble Sort or Selection Sort, the time efficiency usually makes this trade-off worthwhile in practice.

Implementation in JavaScript

// The Merge Helper Function
function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

Breaking Down the Merge Function:

Function Setup:

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

Creates an empty array to store merged results
Initializes pointers for both input arrays
Think of these pointers like fingers keeping track of where we are in each array

Main Merging Logic:

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

Compares elements from both arrays
Takes the smaller element and adds it to result
Moves the pointer forward in the array we took from
Like choosing the smaller of two cards when sorting a deck

Cleanup Phase:

   while (leftIndex < left.length) {
     result.push(left[leftIndex]);
     leftIndex++;
   }

Adds any remaining elements
Necessary because one array might be longer than the other
Like gathering the remaining cards after comparing

The Main Merge Sort Function

function mergeSort(arr) {
  // Base case
  if (arr.length <= 1) {
    return arr;
  }

  // Divide
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  // Conquer and Combine
  return merge(mergeSort(left), mergeSort(right));
}

Breaking Down MergeSort:

Base Case:

   if (arr.length <= 1) {
     return arr;
   }

Handles arrays of length 0 or 1
These are already sorted by definition
Acts as our recursion stopping point

Division Phase:

   const middle = Math.floor(arr.length / 2);
   const left = arr.slice(0, middle);
   const right = arr.slice(middle);

Splits array into two halves
slice() creates new arrays without modifying original
Like cutting a deck of cards in half

Recursive Sorting and Merging:

   return merge(mergeSort(left), mergeSort(right));

Recursively sorts each half
Combines sorted halves using merge function
Like sorting smaller piles of cards before combining them

Example Walkthrough

Let's see how it sorts [38, 27, 43, 3]:

First Split:

   [38, 27, 43, 3]
   ↙           ↘
   [38, 27]    [43, 3]

Second Split:

   [38, 27]    [43, 3]
   ↙    ↘      ↙    ↘
   [38] [27]   [43] [3]

Merge Back:

   [38] [27]   [43] [3]
      ↘↙          ↘↙
   [27, 38]    [3, 43]
       ↘        ↙
    [3, 27, 38, 43]

Conclusion

Merge Sort stands out as a highly efficient sorting algorithm that consistently performs well on large datasets. While it requires additional space compared to simpler sorting algorithms, its O(n log n) time complexity makes it a go-to choice for many real-world applications where performance is crucial.

Key takeaways:

Uses divide-and-conquer strategy
O(n log n) time complexity in all cases
Requires O(n) additional space
Stable sorting algorithm
Excellent for large datasets

Stay Updated and Connected

Emmanuel Ayinde Follow

Lead Full-Stack Software Engineer | Backend & AI Systems | Building Scalable, Production-Ready Products

Stay tuned and happy coding 👨‍💻🚀

Mastering Selection Sort Algorithm like a PRO

Emmanuel Ayinde — Fri, 18 Oct 2024 22:53:34 +0000

As we've been talking about different sorting algorithms, today we'll be learning about the selection sort algorithm. A sorting algorithm that allows for the possible minimum amount of swaps in a memory-constrained environment.

Introduction
What is Selection Sort Algorithm?
How does selection sort work?
- Time Complexity
- Space Complexity
Implementation in JavaScript
Solving LeetCode Problems
Conclusion

Introduction

Selection sort is a simple yet effective sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the beginning (or end) of the sorted portion. This process is repeated until the entire list is sorted. In this article, we will delve into the details of the selection sort algorithm, its implementation in JavaScript, and its applications in solving real-world problems.

What is Selection Sort Algorithm?

Selection Sort algorithm is an in-place comparison sorting algorithm. It divides the input list into two parts:

The sorted portion at the left end
The unsorted portion at the right end

The algorithm repeatedly selects the smallest element from the unsorted portion and swaps it with the leftmost unsorted element, moving the boundary between the sorted and unsorted portions one element to the right.

How does selection sort work?

Let's walk through an example using the array [64, 25, 12, 22, 11]:

Initial array: [64, 25, 12, 22, 11]

Sorted portion: []
Unsorted portion: [64, 25, 12, 22, 11]

First pass:

Find minimum in unsorted portion: 11
Swap 11 with first unsorted element (64)
Result: [11, 25, 12, 22, 64]
Sorted portion: [11]
Unsorted portion: [25, 12, 22, 64]

Second pass:

Find minimum in unsorted portion: 12
Swap 12 with first unsorted element (25)
Result: [11, 12, 25, 22, 64]
Sorted portion: [11, 12]
Unsorted portion: [25, 22, 64]

Third pass:

Find minimum in unsorted portion: 22
Swap 22 with first unsorted element (25)
Result: [11, 12, 22, 25, 64]
Sorted portion: [11, 12, 22]
Unsorted portion: [25, 64]

Fourth pass:

Find minimum in unsorted portion: 25
25 is already in the correct position
Result: [11, 12, 22, 25, 64]
Sorted portion: [11, 12, 22, 25]
Unsorted portion: [64]

Final pass:
- Only one element left, it's automatically in the correct position
- Final result: [11, 12, 22, 25, 64]

The array is now fully sorted.

Time Complexity

Selection Sort has a time complexity of O(n^2) in all cases (best, average, and worst), where n is the number of elements in the array. This is because:

The outer loop runs n-1 times
For each iteration of the outer loop, the inner loop runs n-i-1 times (where i is the current iteration of the outer loop)

This results in approximately (n^2)/2 comparisons and n swaps, which simplifies to O(n^2).

Due to this quadratic time complexity, Selection Sort is not efficient for large datasets. However, its simplicity and the fact that it makes the minimum possible number of swaps can make it useful in certain situations, especially when auxiliary memory is limited.

Space Complexity

Selection Sort has a space complexity of O(1) because it sorts the array in-place. It only requires a constant amount of additional memory space regardless of the input size. This makes it memory-efficient, which can be advantageous in memory-constrained environments.

Implementation in JavaScript

Here's a JavaScript implementation of Selection Sort Algorithm:

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Find the minimum element in the unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));

Let's break down the code:

We define a function selectionSort that takes an array as input.
We iterate through the array with the outer loop (i), which represents the boundary between the sorted and unsorted portions.
For each iteration, we assume the first unsorted element is the minimum and store its index.
We then use an inner loop (j) to find the actual minimum element in the unsorted portion.
If we find a smaller element, we update minIndex.
After finding the minimum, we swap it with the first unsorted element if necessary.
We repeat this process until the entire array is sorted.

Solving LeetCode Problems

Let'solve one leetcode algorithm problem using selection sort algorithm. Shall we?

Problem: Sort An Array `[Medium]`

Problem: Given an array of integers nums, sort the array in ascending order and return it. You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Approach:: To solve this problem, we can directly apply the Selection Sort algorithm. This involves iterating through the array, finding the smallest element in the unsorted portion, and swapping it with the first unsorted element. We repeat this process until the entire array is sorted.

Solution:

// This function sorts an array of integers in ascending order using the Selection Sort algorithm.
const sortArray = function (nums) {
  // Get the length of the input array.
  const n = nums.length;

  // Iterate through the array, starting from the first element.
  for (let i = 0; i < n - 1; i++) {
    // Initialize the index of the minimum element to the current element.
    let minIndex = i;

    // Find the minimum element in the unsorted portion of the array.
    for (let j = i + 1; j < n; j++) {
      if (nums[j] < nums[minIndex]) {
        // Update the minimum index if a smaller element is found.
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element if necessary.
    if (minIndex !== i) {
      [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
    }
  }

  // Return the sorted array.
  return nums;
};

This solution directly applies the Selection Sort algorithm we implemented earlier. While it correctly solves the problem, it's worth noting that this solution may exceed the time limit for large inputs on LeetCode due to the O(n^2) time complexity of Selection Sort. The image below shows that the solution is correct but not efficient.

Conclusion

In conclusion, Selection Sort is a simple and intuitive sorting algorithm that serves as an excellent introduction to the world of sorting techniques. Its simplicity makes it easy to understand and implement, making it a valuable learning tool for beginners. However, due to its quadratic time complexity O(n^2), it is not efficient for large datasets. For larger datasets or performance-critical applications, more efficient algorithms like QuickSort, MergeSort, or built-in sorting functions are preferred.

Stay Updated and Connected

Emmanuel Ayinde Follow

Lead Full-Stack Software Engineer | Backend & AI Systems | Building Scalable, Production-Ready Products

Stay tuned and happy coding 👨‍💻🚀

Understanding insertion sort algorithm: Beginner's guide with leetcode problems

Emmanuel Ayinde — Thu, 17 Oct 2024 11:01:00 +0000

There are many sorting algorithms 🧮, and each has its own strengths and weaknesses. Some are more efficient for large datasets 📊, while others are simpler and easier to understand 🤓. In this article, we'll explore one of the simplest sorting algorithms, Insertion Sort 📥. We'll look at how it works, its algorithm complexity, and how to implement it in JavaScript and finally solve some LeetCode problems using Insertion Sort 🏆.

I hope you are ready for this? Are you?

Introduction
What is an Insertion Sort Algorithm?
How does Insertion Sort work?
- Time Complexity
- Space Complexity
Implementation of Insertion Sort
Solving LeetCode Problems
Conclusion
References

Introduction

Insertion Sort algorithm is a comparison-based sorting algorithm that builds a sorted array one element at a time. It is one of the simplest sorting algorithms and is also known as a stable sort algorithm. It can be used for sorting small data sets or for educational purposes and can be implemented with just a few lines of code.

What is an Insertion Sort Algorithm?

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it has advantages such as simple implementation, efficient for small data sets, stable sort, and in-place sorting algorithm.

How does Insertion Sort work?

Imagine we have an array [5, 3, 8, 4, 2] that we want to sort in ascending order using Insertion Sort. Here's how we'll go about it:

Start with [5] (first element is considered sorted)
Take 3: [5, 3] → [3, 5] (3 is smaller than 5, so we swap them)
Take 8: [3, 5, 8] (8 is already in the correct position)
Take 4: [3, 5, 8, 4] → [3, 4, 5, 8] (4 is smaller than 8, so we swap them)
Take 2: [3, 4, 5, 8, 2] → [2, 3, 4, 5, 8] (2 is smaller than 8, so we swap them)

Final sorted array: [2, 3, 4, 5, 8]

Time Complexity

Best-case scenario: O(n)
- Occurs when the array is already sorted
- The algorithm only needs to do n-1 comparisons
Average-case scenario: O(n^2)
- On average, each element must be compared with about half of the previous elements
Worst-case scenario: O(n^2)
- Occurs when the array is sorted in reverse order (that is, the array is in descending order and we want to sort it in ascending order)
- Each element must be compared with all previous elements

Space Complexity

Insertion Sort has a space complexity of O(1) because it sorts the array in-place. It only requires a constant amount of additional memory space regardless of the input size.

Implementation of Insertion Sort

Having understood how Insertion Sort works, let's implement it in JavaScript:

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i]; // current element
    let j = i - 1; // index of previous element

    // Move elements of arr[0...i-1] that are greater than key
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
  return arr;
}

console.log(insertionSort([5, 3, 8, 4, 2])); // Output: [2, 3, 4, 5, 8]

Let's break down the code:

We start with the second element (index 1 from our for-loop) because we consider the first element as already sorted.
We store the current element as key.
We compare key with the elements before it, moving elements that are greater than key one position ahead.
We place key in its correct position in the sorted portion of the array.
We repeat this process for all elements in the array.

It is important to note that Insertion Sort is already optimal for small data sets and mostly sorted arrays. However, it becomes inefficient for large, unsorted arrays. In such cases, more advanced algorithms like QuickSort or MergeSort are preferred.

Solving LeetCode Problems

Let's look at a LeetCode problem that can be solved using Insertion Sort:

Problem 1: Sort an Array `[Easy]`

Problem: You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Approach: We can use a for-loop to traverse the array and insert each element into the correct position in the sorted portion. This is a direct application of insertion sort.

Solution:

function merge(nums1, m, nums2, n) {
  // Step 1: Copy elements from nums2 into nums1
  for (let i = 0; i < n; i++) {
    nums1[m + i] = nums2[i];
  }
  // Step 2: Apply Insertion Sort on the merged nums1 array
  for (let i = 1; i < m + n; i++) {
    let key = nums1[i];
    let j = i - 1;

    // Shift elements of nums1[0..i-1] that are greater than key to one position ahead
    while (j >= 0 && nums1[j] > key) {
      nums1[j + 1] = nums1[j];
      j--;
    }
    nums1[j + 1] = key; // Insert key at the correct position
  }
}

Problem 2: Insertion Sort List `[Medium]`

Problem: Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

Approach: This problem is a direct application of insertion sort. We can use a dummy node to keep track of the sorted portion of the list and insert each node into the correct position in the sorted portion. We can use a pointer to traverse the list and insert each node into the correct position in the sorted portion.

Solution:

// Function to perform insertion sort on a linked list
const insertionSortList = function (head) {
  // Create a dummy node to simplify insertion at the beginning
  let dummy = new ListNode(0);
  let current = head;

  // Iterate through each node in the original list
  while (current) {
    // Start from the dummy node to find the correct position
    let prev = dummy;

    // Move prev until we find the right position to insert current
    while (prev.next && prev.next.val < current.val) {
      prev = prev.next;
    }

    // Store the next node to process
    let next = current.next;

    // Insert current node into the sorted portion
    current.next = prev.next;
    prev.next = current;

    // Move to the next unsorted node
    current = next;
  }

  // Return the head of the sorted list (excluding dummy node)
  return dummy.next;
};

Noticed how we used while-loop to traverse the list and insert each node into the correct position in the sorted portion. Unlike the array implementation of insertion sort where we used for-loop to traverse the array and insert each element into the correct position in the sorted portion. This is because our data structure is a linked list and not the regular array.

Conclusion

Insertion Sort is a very simple and straightforward sorting algorithm that's especially effective for small arrays or arrays that are already mostly sorted. While it may not be the most efficient choice for large, unsorted datasets, its simplicity makes it a great starting point for understanding sorting algorithms.

Key takeaways:

Insertion Sort builds the final sorted array one item at a time.
It's efficient for small datasets and nearly-sorted arrays.
It has a best-case time complexity of O(n) and a worst-case of O(n^2).
It sorts in-place, requiring only O(1) additional memory.

Understanding Insertion Sort provides a solid foundation for learning more complex sorting algorithms and helps in solving various coding problems efficiently.

References

Stay Updated and Connected

Emmanuel Ayinde Follow

Lead Full-Stack Software Engineer | Backend & AI Systems | Building Scalable, Production-Ready Products

Stay tuned and happy coding 👨‍💻🚀

Understanding bubble sort algorithm: Beginner's guide with leetcode problems

Emmanuel Ayinde — Wed, 16 Oct 2024 07:33:23 +0000

In the world of programming, sorting algorithms are fundamental. They're used in various applications, from organizing data in databases to optimizing search functions. Bubble Sort, with its straightforward approach, serves as a stepping stone to understanding more advanced sorting techniques.

Introduction
What is Bubble Sort?
How does Bubble Sort work?
- Time Complexity
- Space Complexity
Implementation of Bubble Sort
Optimizing Bubble Sort
Solving LeetCode Bubble Sort Problems
Conclusion

Introduction

Bubble Sort is one of the simplest sorting algorithms, making it an excellent starting point for our journey in sorting techniques. While it may not be the most efficient for large datasets, understanding Bubble Sort lays a solid foundation for understanding more complex sorting algorithms.

What is Bubble Sort?

Bubble Sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Bubble sort sort elements basically by comparing each pair of elements in the array and swapping them if they are in the wrong order. It is an in-place sorting algorithm, meaning it sorts the elements within the array itself without needing additional memory.

The algorithm gets its name from the way smaller elements "bubble" to the top of the list with each iteration, similar to air bubbles rising in a liquid.

How does Bubble Sort work?

Before we start writing code, let's walk through how Bubble Sort works using an example array: [5, 3, 8, 4, 2]. Assume we have this array [5, 3, 8, 4, 2] and we want to sort it in ascending order using Bubble Sort.

First pass:

Compare 5 and 3: Swap → [3, 5, 8, 4, 2]
Compare 5 and 8: No swap
Compare 8 and 4: Swap → [3, 5, 4, 8, 2]
Compare 8 and 2: Swap → [3, 5, 4, 2, 8]

Second pass:

Compare 3 and 5: No swap
Compare 5 and 4: Swap → [3, 4, 5, 2, 8]
Compare 5 and 2: Swap → [3, 4, 2, 5, 8]
Compare 5 and 8: No swap

Third pass:

Compare 3 and 4: No swap
Compare 4 and 2: Swap → [3, 2, 4, 5, 8]
Compare 4 and 5: No swap
Compare 5 and 8: No swap

Fourth pass:

Compare 3 and 2: Swap → [2, 3, 4, 5, 8]
Compare 3 and 4: No swap
Compare 4 and 5: No swap
Compare 5 and 8: No swap

Fifth pass:
- No swaps needed, the array is sorted

After each pass, the largest unsorted element "bubbles up" to its correct position at the end of the array. Notice how the number of total passes is 5 which is the length of the array but the last pass has no swap whatsoever, meaning if we had used 5 - 1 = 4 as the total number of passes, we'd have gotten the correct result. This is because the last element is already in its correct position after the fourth pass.

Time and Space Complexity of Bubble Sort

It is important to note that Bubble Sort is not the most efficient sorting algorithm for large datasets due to its quadratic time complexity O(n^2). However, it is still a good algorithm for small datasets or for educational purposes.

Time Complexity

The time complexity of Bubble Sort can be analyzed in three scenarios:

Worst-case scenario: O(n^2)

This occurs when the array is in reverse order (meaning the array is already sorted in descending order and we want to sort it in ascending order), requiring the maximum number of swaps.
For each of the n elements, we potentially need to do n-1 comparisons.

Best-case scenario: O(n)

This occurs when the array is already sorted.
With optimization (stopping early if no swaps are made), we only need to do one pass through the array.

Average-case scenario: O(n^2)
- On average, we can expect quadratic time complexity.

Here, n represents the number of elements in the array.

Space Complexity

Bubble Sort has a space complexity of O(1), which means it uses constant extra space.

This is because Bubble Sort is an in-place sorting algorithm. It doesn't require any extra array or data structure for sorting. The swaps are done within the original array, using only a constant amount of extra memory for variables (like loop counters and temporary variables for swapping).

Implementation of Bubble Sort

We've seen how Bubble Sort works and how to analyze its time and space complexity, let's now implement it in JavaScript.

Here's a basic implementation of Bubble Sort in JavaScript:

function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    // <--- Outer loop runs n-1 times (O(n))
    for (let j = 0; j < n - i - 1; j++) {
      // <--- Inner loop runs n-1 times (O(n))
      if (arr[j] > arr[j + 1]) {
        // Swap elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

// Example usage:
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log("Unsorted array:", unsortedArray); // [64, 34, 25, 12, 22, 11, 90]
console.log("Sorted array:", bubbleSort(unsortedArray)); // [11, 12, 22, 25, 34, 64, 90]

Let's break down the code:

The outer loop for (let i = 0; i < n - 1; i++) runs n-1 times, where n is the length of the array. This is because the last element is already in its correct position after the (n-1)th pass.
The inner loop for (let j = 0; j < n - i - 1; j++) compares adjacent elements (arr[j] and arr[j + 1]). Notice how the loop decreases as we progress through the array (i.e n - i - 1). This expression means that after you've looped through a number of elements from the first loop (i.e i from the outer loop), the number of comparisons decreases by i, so in our inner loop, we'd be comparing n - i - 1 elements not n - 1.
If an element is greater than the next one, they are swapped using destructuring assignment.
This process continues until no more swaps are needed.

Optimizing Bubble Sort

We can optimize Bubble Sort by adding a flag to check if any swaps were made in a pass. If no swaps were made, it means the array is already sorted, and we can stop the algorithm early.

Here's the optimized version:

function optimizedBubbleSort(arr) {
  const n = arr.length;
  let swapped;

  for (let i = 0; i < n - 1; i++) {
    swapped = false; // We initialize swapped to false

    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true; // We set swapped to true to indicate that a swap occurred
      }
    }

    // If no swapping occurred, this means the array is sorted
    if (!swapped) break; // We break out of the loop if no swaps occurred
  }

  return arr;
}

// Example usage:
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log("Unsorted array:", unsortedArray); // [64, 34, 25, 12, 22, 11, 90]
console.log("Sorted array:", optimizedBubbleSort(unsortedArray)); // [11, 12, 22, 25, 34, 64, 90]

This optimization improves the best-case time complexity to O(n) when the array is already sorted or nearly sorted.

Solving LeetCode Bubble Sort Problems

Having studied how bubble sort works and how to implement it, let's solve some LeetCode problems using bubble sort to solidify our understanding.

Problem 1: Maximum Product of Two Elements in an Array `[Easy]`

Problem: Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).

Approach: This problem is a direct application of bubble sort. We can sort the array in ascending order and return the product of the last two elements, which are the two largest elements in the array.

Solution:

const maxProduct = function (nums) {
  // Implement bubble sort
  for (let i = 0; i < nums.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < nums.length - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        // Swap elements
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
        swapped = true;
      }
    }
    // If no swapping occurred, array is sorted
    if (!swapped) break;
  }

  // Return the product of the last two elements (largest two)
  return (nums[nums.length - 1] - 1) * (nums[nums.length - 2] - 1);
};

Problem 2: Sort Colors `[Medium]`

Problem: Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function.

Approach: We can use bubble sort to solve this problem efficiently. Since we only have three distinct values (0, 1, and 2), we can sort the array in-place using bubble sort. The algorithm will compare adjacent elements and swap them if they are in the wrong order. After each pass, the largest unsorted element will "bubble up" to its correct position. We'll repeat this process until the entire array is sorted, resulting in all red elements (0) at the beginning, followed by white elements (1), and then blue elements (2) at the end.

Solution:

const sortColors = function (nums) {
  var len = nums.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        // Swap nums[j] and nums[j + 1]
        var temp = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = temp;
      }
    }
  }
  return nums;
};

Conclusion

Bubble Sort is a simple and intuitive sorting algorithm that serves as an excellent introduction to the world of sorting techniques. Its simplicity makes it easy to understand and implement, making it a valuable learning tool for beginners.

Key points to remember about Bubble Sort:

It repeatedly steps through the list, comparing adjacent elements and swapping them if they're in the wrong order.
The algorithm gets its name from the way smaller elements "bubble" to the top of the list with each iteration.
Time complexity: Worst and Average case O(n^2), Best case O(n) with optimization.
Space complexity: O(1) as it sorts in-place.
It can be optimized to stop early if the list becomes sorted before all passes are complete.

While Bubble Sort is not efficient for large datasets due to its quadratic time complexity O(n^2), understanding it provides a solid foundation for learning more advanced sorting algorithms. In practice, for larger datasets or performance-critical applications, more efficient algorithms like QuickSort, MergeSort, or built-in sorting functions are preferred.

In our next article, we'll be learning about another sorting algorithm called Selection Sort.

Stay Updated and Connected

Emmanuel Ayinde Follow

Lead Full-Stack Software Engineer | Backend & AI Systems | Building Scalable, Production-Ready Products

Stay tuned and happy coding 👨‍💻🚀

Mastering Time and Space Complexity: A Beginner's Guide to Big O Notation

Emmanuel Ayinde — Mon, 14 Oct 2024 20:58:10 +0000

In your journey to becoming a proficient software or data engineer, understanding algorithm complexity is crucial. It helps you make informed decisions about the efficiency of your code and ensures that your applications perform well even as the data grows.

In this article, we'll explore the concept of algorithm complexity, specifically focusing on time and space complexity and how to calculate them using Big O notation.

Introduction
What is Algorithm Complexity?
- Time Complexity
- Space Complexity
Asymptotic Notation
How to Calculate Complexity
- How to Calculate Time Complexity
- How to Calculate Space Complexity
Common Runtime Complexities
Conclusion

Introduction

If you've ever been tasked with optimizing code, you've likely encountered the concept of algorithm complexity. At its core, complexity deals with the efficiency of an algorithm, focusing on how much time and space it requires to run as the input size grows.

What is Algorithm Complexity?

Algorithm complexity refers to the amount of time and space required by an algorithm to complete its execution. It helps us understand how efficient an algorithm is and how it scales with the size of the input data.

Time Complexity

Time complexity measures how the runtime of an algorithm increases with the size of the input. It answers the question: "As we add more data, how much longer will our algorithm take?"

It is a measure of how much time an algorithm takes to complete its execution as a function of the input size. It helps us understand the performance of an algorithm in terms of time.

Space Complexity

Space complexity measures how much additional memory an algorithm needs as the input size grows. It answers the question: "As we add more data, how much more memory will our algorithm use?"

It is a measure of how much memory an algorithm uses as a function of the input size. It helps us understand the performance of an algorithm in terms of memory.

Sometimes, you might prioritize one over the other. For instance:

In a mobile app with limited memory, you might prioritize space efficiency.
In a real-time system where quick responses are crucial, time efficiency might be more important.

Asymptotic Notation## Asymptotic Notation

When discussing algorithmic complexity, we use asymptotic notation to describe how the runtime or space usage grows as the input size approaches infinity. There are three main notations:

Big O Notation (O)

Represents the upper bound or worst-case scenario
Example: O(n) means the algorithm will never be slower than linear time

Big Omega Notation (Ω)

Represents the lower bound or best-case scenario
Example: Ω(log n) means the algorithm will never be faster than logarithmic time

Big Theta Notation (Θ)
- Represents both upper and lower bounds or average-case scenario
- Example: Θ(n) means the algorithm is always linear time

How to Calculate Complexity

Calculating complexity involves analyzing how the number of operations grows with the input size. It involves counting the number of operations and expressing them in terms of the input size (usually n).

How to calculate time complexity

To calculate the time complexity, we can follow these steps:

Count the number of operations (primitive operations)
Express the number of operations in terms of the input size (usually n)
Keep only the highest order term (the term with the largest growth rate)
Drop constants

NOTE 🔥

The steps above can also be applied to space complexity excepts we are dealing with memory which means we are counting the number of variables and the size of the input data instead of the number of operations.

Take for example we have the following function:

function sumArray(arr) {
  let sum = 0; // 1 operation
  for (let i = 0; i < arr.length; i++) {
    // n operations (where n is the array length)
    sum += arr[i]; // n operations (where n is the array length)
  }
  return sum; // 1 operation
}

In this example, the function sumArray takes an array arr as input and returns the sum of its elements. Let's analyze the complexity following the steps we mentioned earlier:

Step 1: Count the number of operations

Initialization: let sum = 0; - 1 operation
Loop: for (let i = 0; i < arr.length; i++) - n operations (where n is the length of the array, i.e n = arr.length)
Summation: sum += arr[i]; - n operations
Return: return sum; - 1 operation

So, the total number of operations is 1 + n + n + 1 = 2n + 2.

Step 2: Express the number of operations in terms of the input size (usually n)

The total number of operations is 2n + 2.

Step 3: Keep only the highest order term (the term with the largest growth rate)
From our expression 2n + 2, the highest order term is 2n. So we keep 2n.

Step 4: Drop constants
From 2n, we drop the constant 2. So we are left with n.

So, the time complexity of the sumArray function is O(n).

NOTE: As n approaches infinity (meaning, as n gets larger and larger says 1000, 10000, 100000, etc.), the constant 2 becomes insignificant, so we can simplify the complexity to O(n).

How to calculate space complexity

When it comes to space complexity, we are interested in the amount of memory used by the algorithm as a function of the input size.

We usually use this formular to calculate space complexity:

Space Complexity Formular

Space Complexity = Auxiliary space + Input size

NOTE 🔥

Auxiliary space is the extra or temporary space (excluding input size) used by the algorithm while Input size is the space taken by the input data.

For any algorithm, memory is required for the following:

To store program instructions
To store constant values
To store variables
To handle function calls, jumping statements, etc.

Let's look at an example to understand this better.

function sumArray(arr) {
  let sum = 0; // i unit of space
  for (let i = 0; i < arr.length; i++) {
    // n operations (where n is the array length)
    sum += arr[i]; // n operations (where n is the array length)
  }
  return sum; // 1 operation
}

from the above function, we have the following:

Auxiliary space: 0
Input size: n

So, the space complexity is O(n).

In the context of algorithm complexity, primitive operations refer to the basic operations that a computer can perform in a single step. These operations are typically simple and fundamental, such as:

Arithmetic operations: Addition, subtraction, multiplication, and division.

Variable assignments: Assigning a value to a variable.

Comparisons: Checking if one value is greater than, less than, or equal to another.

Logical operations: Operations like AND (&&), OR (||), and NOT (!).

Array access: Accessing an element in an array by its index.

When analyzing the time complexity of an algorithm, we count these primitive operations to estimate how the runtime of the algorithm grows as the size of the input increases. This helps in understanding the efficiency of the algorithm.

Common Runtime Complexities

Finally before we go, let's look at some common runtime complexities with their respective code implementations:

Common Runtimes

Here are some common time complexities you'll encounter:

1. Constant time - O(1)

Runtime doesn't increase with input size
Example: Accessing an array element by index

Code Implementation

function getFirstElement(arr) {
  return arr[0];
}

Illustration

2. Logarithmic time - O(log n)

Runtime increases logarithmically with input size
Example: Binary search

Code Implementation

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Illustration

3. Linear time - O(n)

Runtime increases linearly with input size
Example: Linear search

Code Implementation

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

Illustration

4. Polynomial time - O(n^k)

Runtime is a polynomial function of input size
Example: Nested loops

Code Implementation

function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

5. Exponential time - O(2^n)

Runtime doubles with each addition to the input
Example: Recursive Fibonacci

Code Implementation

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

6. Factorial time - O(n!)

Runtime grows factorial with input size
Example: Generating all permutations

Code Implementation

function generatePermutations(arr) {
  if (arr.length <= 1) return [arr];
  let result = [];
  for (let i = 0; i < arr.length; i++) {
    let rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    let perms = generatePermutations(rest);
    result.push(...perms.map((perm) => [arr[i], ...perm]));
  }
  return result;
}

Conclusion

In this article, we've explored the concept of algorithm complexity, specifically focusing on time and space complexity and how to calculate them using Big O notation. We've also looked at how to calculate the space complexity of an algorithm.

In our next article, we'll be focusing on sorting algorithms, their implementations and their complexities.Until then,

Stay Updated and Connected

Stay tuned and happy coding 👨‍💻🚀

Hash Tables Demystified: The Ultimate Guide with JavaScript Implementation

Emmanuel Ayinde — Sat, 12 Oct 2024 22:36:49 +0000

Imagine you're in a vast library with millions of books 📚. How do you find the exact book you're looking for without spending hours searching through every shelf? 🕵️‍♀️ The answer lies in the library's catalog system - a powerful tool that allows you to locate any book in seconds ⚡. This is precisely the real-world analogy of a Hash Table, a fundamental data structure that enables lightning-fast data storage and retrieval 🚀.

Hi 👋, welcome to this article on Hash Tables! In this article, we'll be demystifying Hash Tables 🧩, exploring their inner workings and implementing them in JavaScript.

Before we move on, let's take a look at what we'll be covering in this article:

Introduction
What is a Hash Table?
Common Terminologies Used in Hash Tables
How Hash Tables Work
Implementing a Hash Table in JavaScript
- Creating the Hash Table
- Adding Values to the Hash Table
- Retrieving Values from the Hash Table
- Removing Values from the Hash Table
- Checking if a Value exists in the Hash Table
Conclusion

Introduction

The importance of Hash Tables in the world of programming cannot be overstated. They are the backbone of many real-world applications, from database indexing to caching systems, and from compilers to blockchain technology. Moreover, Hash Tables are a favorite topic in coding interviews, making them an essential skill for any aspiring software developer.

You might be wondering why we need a Hash Table in the first place. A Hash Table is a data structure designed to be fast to work with.

The reason Hash Tables are sometimes preferred instead of arrays or linked lists is because searching for, adding, and deleting data can be done really quickly, even for large amounts of data.

In a Linked List, finding a person "Esther" takes time because we would have to go from one node to the next, checking each node, until the node with "Esther" is found.

And finding "Esther" in an Array could be fast if we knew the index, but when we only know the name "Esther", we need to compare each element (like with Linked Lists), and that takes time.

With a Hash Table however, finding "Esther" is done really fast because there is a way to go directly to where "Esther" is stored, using something called a hash function.

In this comprehensive article, we'll demystify Hash Tables, explore their inner workings, implement them in JavaScript, and solve popular LeetCode problems. By the end of this journey, you'll have a solid understanding of Hash Tables and be well-equipped to optimize your code and ace your next coding interview.

That being said, let's dive into the world of Hash Tables!

What is a Hash Table?

A hash table is a data structure that allows you to store data in key-value pairs and quickly access it using a key. Think of it like a dictionary or a phone book, where you can look up information (value) by a name (key). A hash table is a data structure that stores values using keys. It uses a hash function to compute an index into an array in which an element will be stored.

Common Terminologies Used in Hash Tables

Term	Definition
Key	The identifier used to store or retrieve a value in the hash table.
Value	The actual data associated with the key.
Hash Function	A function that converts the key into a unique hash code used to store the value.
Bucket / Slot	A location in the hash table where a value is stored, indexed by the hash code.
Collision	When two different keys produce the same hash code and are assigned to the same bucket.
Chaining	A method for handling collisions by storing multiple values in a list within a bucket.
Rehashing	Resizing the hash table and recalculating hash codes to redistribute the keys.
Hash Code	The result of the hash function used as the index to store or retrieve values.

How Hash Tables Work

Again, let use the analogy of a vast library of books to get key insight into how Hash Table works. Think of a hash table like a library where you want to store books on shelves, but instead of just throwing them anywhere, you use a clever way of organizing them.

Here’s how it works step-by-step:

Step 1: Hashing is Like Labeling the Book
When you have a book, you need to figure out where to place it in the library. You don’t just choose a random shelf. Instead, you calculate the shelf number based on the book’s title.

This is where the hash function comes in. A hash function is like a special librarian that looks at the title of a book (like the key in a hash table) and decides which shelf the book should go on (like the index in an array). For example:

Title: "Alice in Wonderland"
The librarian (hash function) checks the title and decides: "Put it on Shelf 3." It calculates a shelf number based on the title in a consistent way, so every time you bring "Alice in Wonderland," it will always tell you to use Shelf 3.

Step 2: Storing the Book (Key-Value Pair)
In a hash table, each shelf is actually a bucket. When you know the shelf number (from the hash function), you place the book (value) on that shelf.

You store the book (value) along with its title (key) on the shelf.
This key-value relationship ensures that you can easily find the book later.
For example:
Shelf 3 (bucket) now contains:
- "Alice in Wonderland" → 555-1234 (phone number)

Step 3: Retrieving a Book (Getting a Value)
Let’s say you want to find the phone number for "Alice in Wonderland". The hash table process works as follows:

You go to the librarian (hash function) and ask, "Where is 'Alice in Wonderland'?"
The librarian calculates the same shelf number: Shelf 3.
You walk over to Shelf 3 and find the book, which has the phone number 555-1234. This is the efficiency of a hash table: It doesn't need to search every shelf; it knows exactly where to look!

Step 4: Handling Collisions (Multiple Books on One Shelf)
Sometimes, two books may end up on the same shelf (because of the way the hash function works). This is called a collision.

For example:

"Alice in Wonderland" and "Anna Karenina" might both be placed on Shelf 3. When you retrieve a book from Shelf 3, you might have multiple books there, so you just look through the few that are on that shelf. This is why buckets sometimes contain more than one key-value pair.

This structure is highly efficient and is used for fast data retrieval in many applications, such as dictionaries and databases.

Implementing a Hash Table in JavaScript

Let's roll up our sleeves and implement a simple Hash Table in JavaScript. We'll go through this process step-by-step, explaining each part of the implementation.

When it comes to implementing a Hash Table, the first thing we need to do is to create a hash function. This hash function will take a key and return an index in the array where the value should be stored. To implement this, we'll use a simple algorithm that involves multiplying by a prime number and taking the modulo with the array length.

A hash map uses a simple array (or a list of buckets) to store data. The data is accessed by using a key and the hash function maps that key to an index in the array.

Hash Map: We'll represent the hash map as an array.
Hash Function: This will take a string key, convert it into a hash code (an index in the array), and return that index. The hash function needs to ensure that keys are mapped to valid indices within the array bounds.

Let's start by creating our Hash Map class and the hash function:

Creating the Hash Table

// Hash Map class
class HashTable {
  constructor(size) {
    this.size = size; // size of the hash map (number of buckets)
    this.buckets = new Array(size); // create an array of the given size (buckets)
  }

  // Hash function to generate an index based on the key
  _hash(key) {
    let hashValue = 0;
    for (let i = 0; i < key.length; i++) {
      hashValue += key.charCodeAt(i); // get the ASCII value () of each character and sum it
    }
    return hashValue % this.size; // ensure the index is within the bounds of the array
  }
}

// Create a hash map of size 10 and test the hash function
let myHashTable = new HashTable(10);
console.log(myHashTable._hash("Alice")); // This will return the index for "Alice"
console.log(myHashTable._hash("Bob")); // This will return the index for "Bob"

Explanation:

We created a HashTable class with a size and an array of buckets (empty spots).
The hash function (_hash) takes a key, sums up the ASCII values of the characters, and modulo the result by the size of the array to ensure the result stays within the array’s bounds.
This function is private (indicated by _) because we don't want it to be directly accessible outside the class.

ASCII, which stands for American Standard Code for Information Interchange, is a character encoding standard used to represent text in computers and other devices that use text. It is a 7-bit code, meaning it uses seven bits to represent a character, allowing for 128 possible characters (0-127). The ASCII table includes control characters (0-31 and 127), printable characters (32-126), and extended ASCII characters (128-255).

Now that we can generate an index from a key, the next step is to insert values into the hash table. We'll create a function called set that:

Adding Values to the Hash Table

Now that we can generate an index from a key, the next step is to insert values into the hash map. We'll create a function called set that:

Takes a key-value pair.
Uses the hash function to find the index (bucket) where the value should be stored.
Adds the key-value pair into that bucket. We will use chaining (a list at each bucket) to handle potential collisions (when two keys map to the same bucket).

// Add values to the hash map

set(key, value) {
  const index = this._hash(key); // Get the index for the key

  // Initialize the bucket if it's empty
  if (!this.buckets[index]) {
    this.buckets[index] = []; // Use an array to handle multiple values (chaining)
  }

  // Add the key-value pair to the bucket
  this.buckets[index].push([key, value]);
  console.log(`Set ${key}: ${value} at index ${index}`);
}

// Example of adding values
myHashMap.set("Alice", "555-1234");
myHashMap.set("Bob", "555-5678");
myHashTable.set("Charlie", "555-9999");

Explanation:

The set method uses the hash function to find the correct index.
If the bucket at that index is empty, it initializes an empty list.
The key-value pair is then pushed into that bucket.
This implementation handles collisions by chaining—storing multiple key-value pairs in a list if two keys map to the same bucket.

Retrieving Values from the Hash Table

Once we've inserted values, the next logical step is to retrieve values. We'll create a function get that:

Takes a key.
Uses the hash function to find the index (bucket) where the value should be stored.
Searches the bucket for the key and returns the value if found.

// Retrieve values from the hash map

get(key) {
  const index = this._hash(key); // Get the index for the key

  // Check if the bucket at that index exists
  if (!this.buckets[index]) {
    return null; // If the bucket is empty, return null (key not found)
  }

  // Search through the bucket for the key
  for (let i = 0; i < this.buckets[index].length; i++) {
    const pair = this.buckets[index][i];
    if (pair[0] === key) {
      return pair[1]; // Return the value if the key is found
    }
  }

  return null; // Return null if the key is not found in the bucket
}

// Example of retrieving values
console.log(myHashMap.get("Alice"));   // Should print "555-1234"
console.log(myHashMap.get("Bob"));     // Should print "555-5678"
console.log(myHashMap.get("Charlie")); // Should print "555-9999"
console.log(myHashMap.get("Dave"));    // Should print null (not found)

Explanation:

The get function finds the index for the key using the hash function.
If the bucket at that index is empty, it returns null because the key doesn't exist.
If there are multiple entries in that bucket (due to collisions), the function searches through the list to find the correct key and returns its value.

Removing Values from the Hash Table

To complete the basic operations of a hash table, we'll add a method to remove a key-value pair. This function will:

Take a key.
Use the hash function to find the bucket.
Remove the key-value pair if found.

// Remove values from the hash map

// Remove values from the hash map
remove(key) {
  const index = this._hash(key); // Get the index for the key

  // Check if the bucket exists
  if (!this.buckets[index]) {
    return null; // If the bucket is empty, return null (key not found)
  }

  // Search through the bucket for the key
  for (let i = 0; i < this.buckets[index].length; i++) {
    const pair = this.buckets[index][i];
    if (pair[0] === key) {
      this.buckets[index].splice(i, 1); // Remove the key-value pair from the bucket
      return pair[1]; // Return the removed value
    }
  }

  return null; // Return null if the key is not found in the bucket
}

// Example of removing values
console.log(myHashMap.remove("Alice"));   // Should print "555-1234"
console.log(myHashMap.get("Alice"));      // Should now print null (not found)

Explanation:

The remove function searches for the key in the appropriate bucket and removes the key-value pair if found.
After removal, it returns the value that was removed.
If the key doesn't exist, it returns null.

Checking if a Value exists in the Hash Table

The contains function will:

Loop through all the buckets in the hash map.
Check each key-value pair in the bucket.
Return true if the value is found, and false if it's not.

// Check if the hash map contains a specific value
contains(value) {
  // Loop through all the buckets
  for (let i = 0; i < this.size; i++) {
    const bucket = this.buckets[i];

    // If the bucket exists, search through its key-value pairs
    if (bucket) {
      for (let j = 0; j < bucket.length; j++) {
        const pair = bucket[j];
        if (pair[1] === value) { // Check if the value matches
          return true; // Return true if the value is found
        }
      }
    }
  }

  return false; // Return false if the value is not found in any bucket
}

// Example of checking for values
console.log(myHashMap.contains("555-1234")); // Should return false (because Alice was removed)
console.log(myHashMap.contains("555-5678")); // Should return true (Bob's number)
console.log(myHashMap.contains("555-9999")); // Should return true (Charlie's number)
console.log(myHashMap.contains("555-8888")); // Should return false (not found)

Explanation:

The contains function loops through each bucket in the hash map.
If the bucket exists (i.e., it contains some key-value pairs), it checks whether any value in that bucket matches the value we are looking for.
If it finds a match, it returns true; otherwise, after searching all buckets, it returns false.

Conclusion

Hash Tables are a powerful and versatile data structure that offer efficient data storage and retrieval. Through this guide, we've explored their inner workings, implemented them in JavaScript, and solved several LeetCode problems that leverage their strengths.

In our next article, we'll be solving some LeetCode problems that use Hash Tables. Until then, happy coding!

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

Stay tuned and happy coding 👨‍💻🚀

Cracking Stack and Queue LeetCode Problems: A Step-by-Step Guide to Solving LeetCode Challenges

Emmanuel Ayinde — Thu, 10 Oct 2024 22:30:12 +0000

Learning how to use stacks and queues effectively is an important skill for any developer, and it's a common topic in coding interviews 🎯. In this article, we'll go over some LeetCode problems that involve the use of stacks and queues, and we'll solve them using JavaScript 💻.

Welcome back to this new article in the DSA series 📚! If you've been following my articles up till last article, you'll notice that I've been going over the basic concepts of stacks and queues, how they work and the terminologies used when talking about them 🧠.

Introduction
Problem 1: Implement Stack using Queues
Problem 2: Implement Queue using Stacks
Problem 3: Valid Parentheses
Problem 4: Decode String
Conclusion

Introduction

In the last two articles, we've gone over the basic concepts of stacks and queues 📚, how they work and the terminologies used when talking about them as well as their implementations in JavaScript. In this article, we'll be solving some problems on LeetCode that involves the use of stacks and queues using our implementations. Get ready to put your knowledge to the test and level up your coding skills! 🚀

Before we start cracking some problems, let's quickly remind ourselves the basic of queue and stack.

Stack: Think of a stack as a pile of books. You can only add or remove books from the top. Last In, First Out (LIFO).

For more information on stack, check out my previous article.

Understanding Stack Data Structure: A Step-by-Step Guide to Implementing Stack in JavaScript

Emmanuel Ayinde
Emmanuel Ayinde

Emmanuel Ayinde

Follow

Oct 8 '24

Understanding Stack Data Structure: A Step-by-Step Guide to Implementing Stack in JavaScript

#beginners #javascript #dsa #datastructures

5 reactions
Comments Add Comment

6 min read

Queue: Imagine a line at a ticket counter. The first person in line is the first to be served. First In, First Out (FIFO).

For more information on queue, check out my previous article.

Understanding Queues Data Structure: Mastering FIFO Principle in JavaScript

Emmanuel Ayinde
Emmanuel Ayinde

Emmanuel Ayinde

Follow

Oct 9 '24

Understanding Queues Data Structure: Mastering FIFO Principle in JavaScript

#beginners #javascript #dsa #programming

6 reactions
Comments Add Comment

5 min read

Now that we've refreshed our memories, let's go over some problems. Shall we?

Problem 1: Implement Stack using Queues

Problem Link: LeetCode - Implement Stack using Queues

Explanation:

We need to implement a stack using only queue operations. The main challenge is that queues follow FIFO, while stacks follow LIFO.

Approach:

We'll use two queues. When pushing an element, we'll add it to the first queue and then move all other elements behind it.

Solution:

class MyStack {
  constructor() {
    this.queue1 = [];
    this.queue2 = [];
  }

  push(x) {
    // Add the new element to queue2
    this.queue2.push(x);

    // Move all elements from queue1 to queue2
    while (this.queue1.length > 0) {
      this.queue2.push(this.queue1.shift());
    }

    // Swap queue1 and queue2
    [this.queue1, this.queue2] = [this.queue2, this.queue1];
  }

  pop() {
    return this.queue1.shift();
  }

  top() {
    return this.queue1[0];
  }

  empty() {
    return this.queue1.length === 0;
  }
}

Problem 2: Implement Queue using Stacks

Problem Link: LeetCode - Implement Queue using Stacks

Explanation:

We need to implement a queue using only stack operations. The challenge is to convert LIFO (stack) behavior to FIFO (queue) behavior.

Approach:

We'll use two stacks. One for enqueue operations and another for dequeue operations.

Solution:

class MyQueue {
  constructor() {
    this.stack1 = []; // For enqueue
    this.stack2 = []; // For dequeue
  }

  push(x) {
    this.stack1.push(x);
  }

  pop() {
    if (this.stack2.length === 0) {
      this.transferStack1ToStack2();
    }
    return this.stack2.pop();
  }

  peek() {
    if (this.stack2.length === 0) {
      this.transferStack1ToStack2();
    }
    return this.stack2[this.stack2.length - 1];
  }

  empty() {
    return this.stack1.length === 0 && this.stack2.length === 0;
  }

  transferStack1ToStack2() {
    while (this.stack1.length > 0) {
      this.stack2.push(this.stack1.pop());
    }
  }
}

Problem 3: Valid Parentheses

Problem Link: LeetCode - Valid Parentheses

Explanation:

We need to determine if the input string has valid parentheses, meaning every opening bracket must have a corresponding closing bracket in the correct order.

Approach:

We'll use a stack to keep track of opening brackets and check if they match with closing brackets.

Solution:

const isValid = (s) => {
  const stack = [];
  const bracketPairs = {
    ")": "(",
    "}": "{",
    "]": "[",
  };

  for (let char of s) {
    if (!bracketPairs[char]) {
      // It's an opening bracket, push to stack
      stack.push(char);
    } else {
      // It's a closing bracket
      if (stack.pop() !== bracketPairs[char]) {
        return false;
      }
    }
  }

  // If stack is empty, all brackets were matched
  return stack.length === 0;
};

Problem 4: Decode String

Problem Link: LeetCode - Decode String

Explanation:

We need to decode a string that contains repeated substrings enclosed in square brackets, preceded by a number indicating the repetition count.

Approach:

We'll use two stacks: one for numbers and another for characters. We'll build the decoded string piece by piece.

Solution:

const decodeString = (s) => {
  const numStack = [];
  const strStack = [];
  let currentNum = 0;
  let currentStr = "";

  for (let char of s) {
    if (char >= "0" && char <= "9") {
      currentNum = currentNum * 10 + parseInt(char);
    } else if (char === "[") {
      numStack.push(currentNum);
      strStack.push(currentStr);
      currentNum = 0;
      currentStr = "";
    } else if (char === "]") {
      let repeatTimes = numStack.pop();
      let prevStr = strStack.pop();
      currentStr = prevStr + currentStr.repeat(repeatTimes);
    } else {
      currentStr += char;
    }
  }

  return currentStr;
};

Conclusion

In this blog post, we've explored the fundamental concepts of Queues and Stacks and solved several LeetCode problems that showcase their implementation and use cases. By working through these problems, you've gained valuable insight into how these data structures can be applied to solve complex coding challenges.

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

Stay tuned and happy coding 👨‍💻🚀

Understanding Queues Data Structure: Mastering FIFO Principle in JavaScript

Emmanuel Ayinde — Wed, 09 Oct 2024 22:57:20 +0000

Picture this... 🎬 Imagine you're at a busy coffee shop during the morning rush ☕️. As you enter, you see a long line of caffeine-craving customers waiting to place their orders. The baristas, working efficiently behind the counter, take and prepare orders in the exact sequence that people joined the line. This everyday scenario perfectly illustrates the concept of a Queue as a data structure.

In the world of programming, a Queue is a fundamental data structure that adheres to the First In, First Out (FIFO) principle. Just like the coffee shop line, the first person to join the queue is the first one to be served and leave it 🥇. This simple yet powerful concept has wide-ranging applications in various areas of computer science and software development, from managing print jobs 🖨️ and handling network requests 🌐 to implementing breadth-first search algorithms and coordinating task scheduling in operating systems 💻.

In this particular article, we'll explore the fascinating world of Queues, delving into their inner workings, implementations, and practical applications in JavaScript 🚀. Whether you're new to coding or an intermediate programmer looking to deepen your understanding, this tutorial will provide you with the knowledge and skills to effectively utilize the Queue data structure in your projects 🛠️.

What is a Queue?
Key Terminology
Types of Queues
Queue Operations
Real-World Applications of Queues
Queue Implementation in JavaScript
Conclusion

What is a Queue?

A Queue is a linear data structure that follows the First In, First Out (FIFO) principle. It can be visualized as a line of people waiting for a service, where the person who arrives first is served first. In programming terms, this means that the first element added to the queue will be the first one to be removed.

Key Terminology

Before we delve deeper into Queues, let's familiarize ourselves with some key terms:

Term	Description
Enqueue	The process of adding an element to the rear (end) of the queue.
Dequeue	The process of removing an element from the front of the queue.
Front	The first element in the queue, which will be the next to be removed.
Rear	The last element in the queue, where new elements are added.
IsEmpty	A condition that checks if the queue has no elements.
Size	The number of elements currently in the queue.

Types of Queues

While we'll primarily focus on the basic Queue implementation, it's worth noting that there are several types of Queues:

Simple Queue: The standard FIFO queue we'll be implementing.
Circular Queue: A queue where the rear is connected to the front, forming a circle. This is more memory efficient for fixed-size queues.
Priority Queue: A queue where elements have associated priorities, and higher priority elements are dequeued before lower priority ones.

Queue Operations

The main operations performed on a Queue are:

Enqueue: Add an element to the rear of the queue.
Dequeue: Remove and return the element at the front of the queue.
Peek: Return the element at the front of the queue without removing it.
IsEmpty: Check if the queue is empty.
Size: Get the number of elements in the queue.

Real-World Applications of Queues

Queues have numerous practical applications in computer science and software development:

Task Scheduling: Operating systems use queues to manage processes and tasks.
Breadth-First Search (BFS): In graph algorithms, queues are used to explore nodes level by level.
Print Job Spooling: Printer queues manage the order of print jobs.
Keyboard Buffer: Queues store keystrokes in the order they were pressed.
Web Servers: Request queues help manage incoming HTTP requests.
Asynchronous Data Transfer: Queues in messaging systems ensure data is processed in the correct order.

Queue Implementation in JavaScript

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  // Add an element to the rear of the queue
  enqueue(value) {
    const newNode = new Node(value);
    if (this.isEmpty()) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
    this.size++;
  }

  // Remove and return the element at the front of the queue
  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const removedValue = this.front.value;
    this.front = this.front.next;
    this.size--;
    if (this.isEmpty()) {
      this.rear = null;
    }
    return removedValue;
  }

  // Return the element at the front of the queue without removing it
  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.front.value;
  }

  // Check if the queue is empty
  isEmpty() {
    return this.size === 0;
  }

  // Return the number of elements in the queue
  getSize() {
    return this.size;
  }

  // Print the elements of the queue
  print() {
    if (this.isEmpty()) {
      console.log("Queue is empty");
      return;
    }
    let current = this.front;
    let queueString = "";
    while (current) {
      queueString += current.value + " -> ";
      current = current.next;
    }
    console.log(queueString.slice(0, -4)); // Remove the last " -> "
  }
}

// Usage example
const queue = new Queue();

queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);

console.log("Queue after enqueuing 10, 20, and 30:");
queue.print(); // Output: 10 -> 20 -> 30

console.log("Front element:", queue.peek()); // Output: 10

console.log("Dequeued element:", queue.dequeue()); // Output: 10

console.log("Queue after dequeuing:");
queue.print(); // Output: 20 -> 30

console.log("Queue size:", queue.getSize()); // Output: 2

console.log("Is queue empty?", queue.isEmpty()); // Output: false

queue.enqueue(40);
console.log("Queue after enqueuing 40:");
queue.print(); // Output: 20 -> 30 -> 40

while (!queue.isEmpty()) {
  console.log("Dequeued:", queue.dequeue());
}

console.log("Is queue empty?", queue.isEmpty()); // Output: true

Conclusion

Congratulations! You've now mastered the Queue data structure in JavaScript. From understanding its basic principles to implementing various types of queues and solving LeetCode problems, you've gained a solid foundation in this essential computer science concept.

Queues are not just theoretical constructs; they have numerous real-world applications in software development, from managing asynchronous tasks to optimizing data flow in complex systems. As you continue your programming journey, you'll find that a deep understanding of queues will help you design more efficient algorithms and build more robust applications.

To further solidify your knowledge, I encourage you to practice more Queue-related problems on LeetCode and other coding platforms

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

Stay tuned and happy coding 👨‍💻🚀

Understanding Stack Data Structure: A Step-by-Step Guide to Implementing Stack in JavaScript

Emmanuel Ayinde — Tue, 08 Oct 2024 22:52:27 +0000

A Stack is a simple linear data structure that works like a stack of plates 🍽️. It follows the Last In, First Out (LIFO) principle. Think of it as a pile of plates: you can only add or remove plates from the top of the pile.

For a better understanding of stack, let's embark on a short journey of imagination 🌟.
Imagine you're at a fancy restaurant 🍽️, and the kitchen staff is preparing for a busy night 👨‍🍳. In the dish area, there's a tall stack of plates waiting to be used. As diners arrive and orders pour in, the staff takes plates from the top of the stack. When clean plates are added, they go right on top. This simple system ensures that the plates at the bottom of the stack which have been there the longest are used last, while the freshly cleaned plates on top are used first ✨.

This, in essence, is how a Stack data structure works. A Stack is a linear data structure that follows the Last In First Out (LIFO) principle. Just like with our stack of plates, the last item added to a Stack is the first one to be removed.

In this comprehensive tutorial on the stack data structure, we'll explore the following topics with a simple, beginner-friendly approach:

What is a Stack?
Pros and Cons of Using Stack
Real-World Applications of Stacks
Key Operations on a Stack
Stack Implementation in JavaScript
Conclusion

Are you ready? Let's dive in

What is a Stack?

A Stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Think of it like a stack of books: you can only add or remove books from the top of the stack.

Pros and Cons of Using Stack

Before we continue with the flow and write some codes, it is great to understanding where and where not to use Stack. The table below give an explicit Pros and Cons of Stack in details.

Pros	Cons
Simple and easy to implement	Limited access (only top element is directly accessible)
Efficient for Last-In-First-Out (LIFO) operations	Not suitable for random access of elements
Constant time O(1) for push and pop operations	Can lead to stack overflow if not managed properly
Useful for tracking state in algorithms (e.g., depth-first search)	Not ideal for searching or accessing arbitrary elements
Helps in memory management (e.g., call stack in programming languages)	Fixed size in some implementations (array-based stacks)
Useful for reversing data	May require resizing in dynamic implementations, which can be costly
Supports recursive algorithms naturally	Not efficient for large datasets that require frequent traversal
Helps in expression evaluation and syntax parsing	Potential for underflow if pop operation is called on an empty stack
Useful in undo mechanisms in software	Limited functionality compared to more complex data structures
Efficient for certain types of data organization (e.g., browser history)	Not suitable for problems requiring queue-like (FIFO) behavior

Key Operations on a Stack

The fundamental operations that can be performed on a stack are:

push(): Adds an element to the top of the stack.
pop(): Removes the topmost element from the stack.
peek(): Returns the top element of the stack without removing it.
isEmpty(): Checks if the stack is empty.
size(): Returns the number of elements in the stack.

Real-World Applications of Stacks

Stacks are every where in computer science and software development. Here are some common applications:

Undo Functionality: In text editors or graphic design software, each action is pushed onto a stack. When you hit "undo," the most recent action is popped off the stack and reversed.
Browser History: When you visit a new page, it's pushed onto a stack. The "back" button pops the current page off the stack, revealing the previous one.
Function Call Stack: In programming languages, function calls are managed using a stack. When a function is called, it's pushed onto the call stack. When it returns, it's popped off.
Expression Evaluation: Stacks are used to evaluate arithmetic expressions, especially those in postfix notation.
Backtracking Algorithms: In problems like maze-solving or puzzle-solving, stacks can keep track of the path taken, allowing easy backtracking when needed.

Stack Implementation in JavaScript

Now, let's implement a Stack in JavaScript. It is important to know that there are different ways to implement a stack in JavaScript. One of the common ways to implement a stack is using array, another way is to use linked list. In this article, we'll implement a stack using linked list (singly linked list).

Implement Stack using Linked List

I hope you still remember how linked list works? You might need to check out the linked list implementation in one of our previous articles in this same series.

Emmanuel Ayinde

Oct 4 '24

How to Implement Singly Linked List in JavaScript

#javascript #beginners #programming #dsa

Comments

5 min read

Now, let's start implementing our stack using singly linked list. Shall we?

First, we'll create a Node class to represent our stack individual item.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Then, we'll create a Stack class to represent our stack.

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // Stack Operations will be implemented here 👇
}

Push Operation

The push operation adds a new element to the top of the stack. It creates a new StackNode, sets its next pointer to the current top, and then updates top to point to this new node. Finally, it increments the size.

  // Push element to the top of the stack
  push(element) {
    const newNode = new Node(element);
    newNode.next = this.top;
    this.top = newNode;
    this.size++;
  }

Pop Operation

The pop operation removes the topmost element from the stack. It first checks if the stack is empty. If it is, it returns an error message. Otherwise, it removes the top element, updates the top pointer to the next node, and decrements the size. Finally, it returns the removed element.

  // Remove and return the top element
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const poppedElement = this.top.data;
    this.top = this.top.next;
    this.size--;
    return poppedElement;
  }

Peek Operation

The peek operation returns the top element without removing it. It first checks if the stack is empty. If it is, it returns an error message. Otherwise, it returns the data of the top element.

  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.data;
  }

isEmpty Operation

The isEmpty operation checks if the stack is empty. It returns true if the stack is empty, and false otherwise.

  // Check if the stack is empty
  isEmpty() {
    return this.size === 0;
  }

getSize Operation

The getSize operation returns the size of the stack. It returns the number of elements in the stack.

  // Return the size of the stack
  getSize() {
    return this.size;
  }

Print Operation

The print operation prints the stack. It returns the data of the top element.

  // Print the stack
  print() {
    let current = this.top;
    let result = "";
    while (current) {
      result += current.data + " ";
      current = current.next;
    }
    console.log(result.trim());
  }

Usage Example

// Usage example
const customStack = new CustomStack();
customStack.push(10);
customStack.push(20);
customStack.push(30);
console.log(customStack.pop()); // 30
console.log(customStack.peek()); // 20
console.log(customStack.getSize()); // 2
console.log(customStack.isEmpty()); // false
customStack.print(); // 20 10

In this implementation, we used a linked list (singly linked list) structure to represent our stack. Each element is a Node with a data value and a reference to the next Node. The top of the stack is always the most recently added Node.

Conclusion

Stacks are a fundamental data structure in computer science that follow the Last In, First Out (LIFO) principle. They are used in various applications, including managing function calls, implementing undo functionality, and evaluating arithmetic expressions.

In this tutorial, we've covered the basics of stacks, pros and cons of using them, and their implementation in JavaScript (using linked list). Understanding stacks is not just about knowing how to implement them, but also recognizing when they're the right tool for solving a problem.

As you continue your journey in software development, you'll find that stacks are an indispensable tool in your problem-solving toolkit. They're simple yet powerful, and mastering them will significantly enhance your ability to design efficient algorithms and data structures.

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:

Stay tuned and happy coding 👨‍💻🚀

DEV Community: Emmanuel Ayinde

Understanding Pointers in Go; The Two Runes (& and *) of Go

Table of Contents

Let's Start with a Story

How RAM Actually Works

RAM is a flat, indexed array of bytes

How the CPU reads and writes memory

What a "variable" actually is at runtime

Memory alignment

The Stack and The Heap

The Stack

The Heap

Escape analysis: Go decides for you

From RAM to Pointers - The Bridge

The & Operator - "Give me the address"

What can & be applied to?

The composite literal shortcut

The * Operator - "Go to that address"

The full picture together

Pointer Types Are Strongly Typed

nil - The Zero Value of Pointers

Pointers in Functions

The problem: pass by value

The solution: pass the address

Performance: avoiding large copies

Pointers & Structs

Linked list - the canonical pointer use case

Pointer Receivers vs Value Receivers

The new() Function

Advantages of Pointers in Go

1. Mutation across function boundaries

2. Avoiding expensive copies

3. Expressing optional values

4. Shared mutable state

5. Recursive data structures

6. Interface satisfaction and polymorphism

Disadvantages & Risks of Pointers in Go

1. Nil pointer dereferences - runtime panics

2. Heap allocations increase GC pressure

3. Pointer indirection degrades cache performance

4. Pointer aliasing makes code harder to reason about

5. Ambiguous data ownership

6. Increased cognitive overhead

Summary table

When to Use Pointers

✅ Use a pointer when…

❌ Avoid a pointer when…

ommon Gotchas

1. Loop variable capture

2. Returning a pointer to a local variable - safe in Go

3. Pointer comparison

4. Don't over-pointer

Quick Reference Cheat Sheet

Stay Updated and Connected

Emmanuel Ayinde Follow

[Boost]

Six Principles Your Resume Should Follow - So Recruiters Will Read It

Cracking Quick Sort algorithm: From Theory to Practice in Minutes

Table of Contents

What is Quick Sort Algorithm

How does quick sort work?

Quick sort can be broken down into four simple steps:

Step 1: Choose a Pivot

Step 2: Rearrange Array Around Pivot

Step 3: Swap Pivot to its Correct Position

Step 4: Recursive Quick Sort on Sub-arrays

Sorting the Right Sub-array [3, 2, 7, 6] recursively

Step 1: Choose a Pivot

Step 2: Rearrange Array Around Pivot

Step 3: Swap Pivot to Its Correct Position

Step 4: Recursive Quick Sort on Sub-arrays

Sorting the Left Sub-array [3, 2]

Step 1: Choose a Pivot

Step 2: Rearrange Array Around Pivot

Step 3: Swap Pivot to Its Correct Position

Step 4: Recursive Quick Sort on Sub-arrays

Final Sorted Array

Time Complexity

Space Complexity

JavaScript Implementation

The `&` Operator - "Give me the address"

What can `&` be applied to?

The `*` Operator - "Go to that address"

`nil` - The Zero Value of Pointers

The `new()` Function

Sorting the Right Sub-array `[3, 2, 7, 6]` recursively

Sorting the Left Sub-array `[3, 2]`

Problem: Sort An Array `[Medium]`

Problem 1: Sort an Array `[Easy]`

Problem 2: Insertion Sort List `[Medium]`

Problem 1: Maximum Product of Two Elements in an Array `[Easy]`

Problem 2: Sort Colors `[Medium]`