Complete DSA Master Guide

Complete DSA Mastery Guide

Everything you need to master Data Structures & Algorithms 🎯

Progress: 0% Complete

🎯 DSA Fundamentals

1. What are Data Structures & Algorithms?

Data Structure: A way to organize and store data efficiently for easy access and modification.

Algorithm: A step-by-step procedure to solve a problem or perform a task.

Why study them together? To write efficient, scalable programs that can handle large amounts of data.

Real-world Example: Library System

🏛️ Data Structure: How books are organized (by category, author, etc.)

🔍 Algorithm: How you find a specific book (search strategy)

2. Big O Notation Mastery

Big O describes how an algorithm's performance scales with input size. Think of it as the "growth rate" of your algorithm.

📊 Common Complexities (Best to Worst)

O(1) - Constant

O(log n) - Logarithmic

O(n) - Linear

O(n log n) - Linearithmic

O(n²) - Quadratic

O(2ⁿ) - Exponential

🌟 Real Examples

O(1): Accessing array element by index
O(log n): Binary search in sorted array
O(n): Finding max element in unsorted array
O(n log n): Merge sort, heap sort
O(n²): Bubble sort, selection sort
O(2ⁿ): Recursive Fibonacci (naive)

🔍 Complexity Analysis Example

// O(n²) - Nested loops
for (let i = 0; i < n; i++) {        // Runs n times
    for (let j = 0; j < n; j++) {    // Runs n times for each i
        console.log(i, j);           // O(1) operation
    }
}
// Total: n × n × 1 = O(n²)

3. Recursion vs Iteration

🔄 Recursive Approach

✅ Elegant and clean code
✅ Great for tree/graph problems
❌ More memory usage (call stack)
❌ Can cause stack overflow

function factorial(n) {
    if (n <= 1) return 1;    // Base case
    return n * factorial(n-1); // Recursive call
}
// Time: O(n), Space: O(n)

🔁 Iterative Approach

✅ Memory efficient
✅ No stack overflow risk
❌ Sometimes more complex logic
❌ Less intuitive for some problems

function factorial(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}
// Time: O(n), Space: O(1)

🧠 Fundamentals Quiz

Q1: What's the time complexity of this code?

for (i = 1; i < n; i *= 2) {
    console.log(i);
}

Show Answer

A: O(log n) - The loop runs log₂(n) times because i doubles each iteration (1, 2, 4, 8, 16...)

Q2: Which is better for calculating Fibonacci(50): recursive or iterative?

Show Answer

A: Iterative! Recursive Fibonacci is O(2ⁿ) while iterative is O(n). For n=50, recursive would take billions of operations!

Q3: Why is binary search O(log n) instead of O(n)?

Show Answer

A: Because it eliminates half the remaining elements in each step. For 1000 elements, it only needs ~10 comparisons instead of up to 1000.

🏗️ Essential Data Structures

1. Arrays - The Foundation

Arrays store elements in contiguous memory locations, enabling O(1) random access.

Array Visualization

Index: 0, 1, 2, 3, 4

⚡ Strengths

• O(1) random access by index
• Memory efficient (contiguous)
• Cache-friendly
• Simple to understand and use

⚠️ Weaknesses

• Fixed size (in many languages)
• O(n) insertion/deletion
• Wasted memory if not full
• O(n) search in unsorted array

📝 Common Array Operations

// Access: O(1)
let element = arr[2];

// Search: O(n)
let index = arr.indexOf(target);

// Insert at end: O(1) amortized
arr.push(newElement);

// Insert at beginning: O(n)
arr.unshift(newElement);

// Delete from end: O(1)
arr.pop();

// Delete from beginning: O(n)
arr.shift();

2. Linked Lists - Dynamic Flexibility

Linked lists store elements in nodes connected by pointers, allowing dynamic size.

Singly Linked List

→

∅

Singly Linked

• One direction traversal
• Less memory per node
• Good for stacks

Doubly Linked

• Bidirectional traversal
• More memory per node
• Good for deques

Circular

• Last points to first
• No null pointers
• Good for round-robin

🔗 Linked List Implementation

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    
    // Insert at beginning: O(1)
    prepend(val) {
        this.head = new ListNode(val, this.head);
        this.size++;
    }
    
    // Search: O(n)
    find(val) {
        let current = this.head;
        while (current) {
            if (current.val === val) return current;
            current = current.next;
        }
        return null;
    }
}

3. Stacks & Queues - LIFO vs FIFO

📚 Stack (LIFO)

Last In, First Out - like a stack of plates

↑ Top

// Stack operations
stack.push(8);     // O(1)
stack.push(3);     // O(1)
let top = stack.pop(); // O(1), returns 3
let peek = stack.top(); // O(1), returns 8

// Use cases:
// - Function call stack
// - Undo operations
// - Expression evaluation
// - Browser history

🚶 Queue (FIFO)

First In, First Out - like a line of people

Front →

← Rear

// Queue operations
queue.enqueue(5);  // O(1)
queue.enqueue(3);  // O(1)
let front = queue.dequeue(); // O(1), returns 5
let peek = queue.front(); // O(1), returns 3

// Use cases:
// - BFS traversal
// - Process scheduling
// - Print queue
// - Breadth-first search

4. Trees - Hierarchical Power

Trees organize data hierarchically, enabling efficient search, insertion, and deletion operations.

Binary Search Tree

Left < Parent < Right property maintained

🌟 BST Properties

• Left subtree < Root < Right subtree
• In-order traversal gives sorted sequence
• Average O(log n) search/insert/delete
• Worst case O(n) if unbalanced

🚀 Tree Traversals

• In-order: Left → Root → Right
• Pre-order: Root → Left → Right
• Post-order: Left → Right → Root
• Level-order: BFS (layer by layer)

🌳 BST Implementation

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST {
    constructor() {
        this.root = null;
    }
    
    insert(val) {
        this.root = this.insertNode(this.root, val);
    }
    
    insertNode(node, val) {
        if (!node) return new TreeNode(val);
        
        if (val < node.val) {
            node.left = this.insertNode(node.left, val);
        } else {
            node.right = this.insertNode(node.right, val);
        }
        return node;
    }
    
    search(val) {
        return this.searchNode(this.root, val);
    }
    
    searchNode(node, val) {
        if (!node || node.val === val) return node;
        
        if (val < node.val) {
            return this.searchNode(node.left, val);
        }
        return this.searchNode(node.right, val);
    }
}

5. Hash Tables - Lightning Fast Lookups

Hash tables provide average O(1) access time using hash functions to map keys to array indices.

Hash Table Structure

null

"key1"

null

"key2"

null

hash("key1") = 1, hash("key2") = 3

⚡ Advantages

• Average O(1) insert/delete/search
• Perfect for key-value storage
• Great for counting, caching
• Constant time complexity (average)

⚠️ Challenges

• Collision handling needed
• No ordering of elements
• Worst case O(n) if many collisions
• Memory overhead for sparse data

🔑 Hash Table Applications

// Two Sum using Hash Map
function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    return [];
}

// Frequency Counter
function charFrequency(str) {
    const freq = new Map();
    for (let char of str) {
        freq.set(char, (freq.get(char) || 0) + 1);
    }
    return freq;
}

📊 Data Structures Quiz

Q1: When should you choose a linked list over an array?

Show Answer

A: When you need frequent insertions/deletions and the size varies significantly. Arrays are better for random access and when size is relatively stable.

Q2: What data structure would you use to implement browser "back" functionality?

Show Answer

A: Stack! Each page visit is pushed onto the stack, and hitting "back" pops the most recent page (LIFO).

Q3: Why is inserting at the beginning of an array O(n)?

Show Answer

A: Because all existing elements must be shifted one position to the right to make space for the new element.

⚡ Essential Algorithms

1. Searching Algorithms

🔍 Linear Search

O(n) Time

O(1) Space

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

// Works on: Any array (sorted or unsorted)
// Best case: O(1) - target is first element
// Worst case: O(n) - target is last or missing

🎯 Binary Search

O(log n) Time

O(1) Space

function binarySearch(arr, target) {
    let left = 0, 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;
}

// Requirement: Array must be SORTED
// Eliminates half of search space each step

2. Sorting Algorithms Masterclass

Algorithm	Best	Average	Worst	Space	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✅
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	❌
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✅
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌

🚀 Quick Sort Implementation

function quickSort(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
        let pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
    return arr;
}

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

🔀 Merge Sort Implementation

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    let i = 0, j = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    
    return result.concat(left.slice(i), right.slice(j));
}

🧮 Algorithms Quiz

Q1: Why does Quick Sort have O(n²) worst-case complexity?

Show Answer

A: When the pivot is always the smallest or largest element (e.g., in already sorted arrays), it creates unbalanced partitions, leading to n levels of recursion with O(n) work each.

Q2: Which sorting algorithm would you choose for sorting a massive dataset that doesn't fit in memory?

Show Answer

A: Merge Sort! Its divide-and-conquer approach works well with external storage, and it has guaranteed O(n log n) performance.

Q3: What makes binary search so much faster than linear search?

Show Answer

A: Binary search eliminates half of the remaining possibilities with each comparison. For 1 million elements, it needs at most 20 comparisons vs up to 1 million for linear search!

💪 Practice Problems

🟢 Easy Problems

1. Two Sum

Problem: Given an array of integers and a target sum, return indices of two numbers that add up to the target.

Example: nums = [2,7,11,15], target = 9 → Output: [0,1]

Show Solution

function twoSum(nums, target) {
    const map = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    return [];
}

// Time: O(n), Space: O(n)
// Key insight: Use HashMap to store complements

2. Valid Parentheses

Problem: Given a string containing just '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Example: "()" → true, "()[]{}" → true, "(]" → false

Show Solution

function isValid(s) {
    const stack = [];
    const pairs = { ')': '(', '}': '{', ']': '[' };
    
    for (let char of s) {
        if (char in pairs) {
            if (stack.pop() !== pairs[char]) return false;
        } else {
            stack.push(char);
        }
    }
    
    return stack.length === 0;
}

// Time: O(n), Space: O(n)
// Perfect use case for Stack data structure!

🟡 Medium Problems

3. Maximum Subarray (Kadane's Algorithm)

Problem: Find the contiguous subarray with the largest sum.

Example: [-2,1,-3,4,-1,2,1,-5,4] → 6 (subarray [4,-1,2,1])

Show Solution

function maxSubArray(nums) {
    let maxSoFar = nums[0];
    let maxEndingHere = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        // Either extend existing subarray or start new one
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}

// Time: O(n), Space: O(1)
// Kadane's Algorithm - Dynamic Programming classic!

4. Reverse Linked List

Problem: Reverse a singly linked list.

Example: 1→2→3→4→5 becomes 5→4→3→2→1

Show Solution

function reverseList(head) {
    let prev = null;
    let current = head;
    
    while (current !== null) {
        let nextTemp = current.next;  // Store next
        current.next = prev;          // Reverse link
        prev = current;               // Move prev forward
        current = nextTemp;           // Move current forward
    }
    
    return prev; // prev is the new head
}

// Time: O(n), Space: O(1)
// Classic three-pointer technique!

🔴 Hard Problems

5. Merge k Sorted Lists

Problem: Merge k sorted linked lists and return it as one sorted list.

Show Solution

function mergeKLists(lists) {
    if (!lists.length) return null;
    
    while (lists.length > 1) {
        let mergedLists = [];
        
        for (let i = 0; i < lists.length; i += 2) {
            let l1 = lists[i];
            let l2 = lists[i + 1] || null;
            mergedLists.push(mergeTwoLists(l1, l2));
        }
        
        lists = mergedLists;
    }
    
    return lists[0];
}

// Time: O(n log k), Space: O(1)
// Divide and conquer approach!

📋 Ultimate DSA Cheat Sheet

🚀 Complexity Quick Reference

Array Access: O(1)

Array Search: O(n)

Binary Search: O(log n)

Hash Table Access: O(1)

Linked List Access: O(n)

Stack/Queue Ops: O(1)

Merge Sort: O(n log n)

Quick Sort (avg): O(n log n)

🎯 When to Use What

Use Arrays when:

• You need random access to elements
• Memory usage is critical
• Size is relatively fixed

Use Linked Lists when:

• Frequent insertions/deletions
• Size varies significantly
• You don't need random access

Use Hash Tables when:

• Fast lookups are critical
• Key-value relationships
• Counting occurrences

Use Trees when:

• Hierarchical data
• Range queries
• Ordered data with fast ops

🧠 Problem-Solving Patterns

Two Pointers

Use when: Array/string problems with pairs or palindromes

let left = 0, right = arr.length - 1;
while (left < right) {
    // Process pair
    if (condition) left++;
    else right--;
}

Sliding Window

Use when: Subarray/substring problems with constraints

let left = 0;
for (let right = 0; right < arr.length; right++) {
    // Expand window
    while (windowInvalid) {
        // Shrink window
        left++;
    }
}

Fast & Slow Pointers

Use when: Cycle detection, finding middle

let slow = head, fast = head;
while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true; // Cycle
}

Divide & Conquer

Use when: Problems can be broken into smaller subproblems

function solve(problem) {
    if (baseCase) return solution;
    
    subproblems = divide(problem);
    solutions = subproblems.map(solve);
    return combine(solutions);
}

💡 Interview Tips

✅ Do This

• Always clarify the problem first
• Start with a brute force solution
• Think out loud about optimizations
• Consider edge cases (empty, single element)
• Trace through your code with examples
• Discuss time/space complexity

❌ Avoid This

• Don't jump into coding immediately
• Don't ignore the interviewer's hints
• Don't get stuck on one approach
• Don't forget to test your solution
• Don't panic if you can't solve it perfectly
• Don't ignore simpler solutions