Algorithms & Data Structures I

Module 1: From Coder to Computer Scientist

Why DSA is Non-Negotiable

The Architect's Trade-offs

So far, we have focused on making our code work. Now, we learn to make it work well.

Writing code is a series of trade-offs, primarily between:

• Time Complexity (How fast it runs)
• Space Complexity (How much memory it uses)

Choosing the right Data Structure and the right Algorithm is how a senior engineer makes these trade-offs intelligently.

The Language of Performance: Big O Notation

How do we talk about the "speed" of an algorithm? We can't use seconds, because that depends on the computer.

Big O Notation is a way to describe how the runtime or space requirement of an algorithm grows as the input size (n) grows.

It describes the worst-case scenario.

Module 2: Big O Notation

Analyzing Algorithmic Efficiency

O(1) — Constant Time

The algorithm takes the same amount of time regardless of the input size.

Analogy: Picking the first apple from a barrel. It doesn't matter if there are 10 apples or 10,000.

                        function getFirstElement(arr: any[]): any {
                            return arr[0]; // Always one operation
                        }
                    

O(n) — Linear Time

The runtime grows linearly with the size of the input (n).

Analogy: Reading every page in a book. A 200-page book takes twice as long as a 100-page book.

                        function findValue(arr: any[], value: any): boolean {
                            for (let i = 0; i < arr.length; i++) { // Loop runs n times
                                if (arr[i] === value) {
                                    return true;
                                }
                            }
                            return false;
                        }
                    

O(n²) — Quadratic Time

The runtime grows quadratically with the input size. This is common with nested loops.

Analogy: Shaking hands with everyone in a room. If you have `n` people, each person shakes `n-1` hands.

This type of algorithm gets very slow, very quickly and should be avoided if possible for large inputs.

                        function hasDuplicates(arr: any[]): boolean {
                            for (let i = 0; i < arr.length; i++) {       // Outer loop runs n times
                                for (let j = 0; j < arr.length; j++) {   // Inner loop runs n times
                                    if (i !== j && arr[i] === arr[j]) {
                                        return true;
                                    }
                                }
                            }
                            return false;
                        }
                    

O(log n) — Logarithmic Time

The runtime grows logarithmically. The algorithm's time increases, but by a diminishing amount as the input size grows. This is incredibly efficient.

These algorithms work by repeatedly dividing the problem in half.

Analogy: Finding a word in a physical dictionary. You open to the middle, decide which half the word is in, and discard the other half. You repeat this until you find the word.

The classic example is **Binary Search**.

Module 3: Linear Data Structures

Arrays and Linked Lists

Arrays Revisited: The Performance Perspective

Arrays store elements in a contiguous block of memory. This has profound performance implications.

• Access by Index (`arr[i]`): O(1) - Constant. The computer can instantly calculate the memory address of any element.
• Insertion/Deletion at Beginning (`unshift`, `shift`): O(n) - Linear. Every other element must be shifted, which is very slow for large arrays.
• Insertion/Deletion at End (`push`, `pop`): O(1) - Constant (amortized). No re-indexing is needed.
• Search: O(n) - Linear. You have to check every element in the worst case.

Linked Lists: The Chain

A Linked List stores elements as separate objects called nodes. Each node contains its data and a pointer (or reference) to the next node in the sequence.

Analogy: A scavenger hunt. Each clue tells you the data and where to find the next clue.

Implementing a Linked List Node

                        class ListNode {
                            public value: T;
                            public next: ListNode | null;

                            constructor(value: T) {
                                this.value = value;
                                this.next = null; // Initially, it doesn't point to anything
                            }
                        }

                        // Creating a simple list: A -> B
                        const nodeA = new ListNode('A');
                        const nodeB = new ListNode('B');
                        nodeA.next = nodeB;
                    

Linked Lists: The Performance Perspective

Linked Lists have the opposite trade-offs of arrays.

• Access by Index (`list.get(i)`): O(n) - Linear. You must traverse the list from the `head` to find the i-th element.
• Insertion/Deletion at Beginning: O(1) - Constant. You just change the `head` pointer. Incredibly fast.
• Insertion/Deletion at End: O(1) if you keep a pointer to the `tail` node, otherwise O(n).
• Search: O(n) - Linear.

Module 4: Abstract Data Types

Stacks and Queues

Stacks: LIFO

Last-In, First-Out. The last element added is the first one to be removed.

Analogy: A stack of plates. You add a plate to the top, and you remove a plate from the top.

Core Operations:

• `push(item)`: Add an item to the top.
• `pop()`: Remove an item from the top.
• `peek()`: Look at the top item without removing it.

The JavaScript call stack is a perfect real-world example!

Implementing a Stack with an Array

An array is a perfect underlying data structure for a stack, because its `push` and `pop` methods are both fast O(1) operations.

                        class Stack {
                            private storage: T[] = [];

                            push(item: T): void {
                                this.storage.push(item);
                            }

                            pop(): T | undefined {
                                return this.storage.pop();
                            }

                            peek(): T | undefined {
                                return this.storage[this.storage.length - 1];
                            }
                        }
                     

Queues: FIFO

First-In, First-Out. The first element added is the first one to be removed.

Analogy: A line at a checkout counter. The first person in line is the first person to be served.

Core Operations:

• `enqueue(item)`: Add an item to the back of the line.
• `dequeue()`: Remove an item from the front of the line.
• `peek()`: Look at the front item without removing it.

The Node.js Event Loop's Callback Queue is a perfect real-world example!

Implementing a Queue with an Array

You can use an array, but there's a performance catch.

                        class Queue {
                            private storage: T[] = [];

                            enqueue(item: T): void {
                                this.storage.push(item); // Fast O(1)
                            }

                            dequeue(): T | undefined {
                                return this.storage.shift(); // 🚨 SLOW! O(n)
                            }
                        }
                     

Using `shift()` is inefficient for a queue with many items. A Linked List is actually a much better underlying data structure for implementing a high-performance queue.