Data Structures & Algorithms: Complete Guide

// O(1) - Constant Time
// The operation takes the same time regardless of input size
// Think of it like looking up a word in a dictionary by page number

function getFirstElement<T>(arr: T[]): T | undefined {
  return arr[0]; // Always one operation, no matter if array has 10 or 10 million elements
}

function getLastElement<T>(arr: T[]): T | undefined {
  return arr[arr.length - 1]; // Still O(1) - direct index access
}

// Hash table lookup is O(1) on average
const hashMap = new Map<string, number>();
hashMap.set("apple", 5);
hashMap.set("banana", 3);
console.log(hashMap.get("apple")); // O(1) lookup

// Array access by index
const numbers = [10, 20, 30, 40, 50];
console.log("First:", getFirstElement(numbers)); // 10
console.log("Last:", getLastElement(numbers));   // 50
console.log("Direct access numbers[2]:", numbers[2]); // 30 - O(1)

// O(n) - Linear Time
// Time grows proportionally with input size
// If input doubles, time roughly doubles

function findMax(arr: number[]): number {
  if (arr.length === 0) throw new Error("Empty array");

  let max = arr[0];
  let comparisons = 0;

  for (let i = 1; i < arr.length; i++) {
    comparisons++;
    if (arr[i] > max) {
      max = arr[i];
    }
  }

  console.log(`Array size: ${arr.length}, Comparisons: ${comparisons}`);
  return max;
}

// Linear search - must check each element
function linearSearch<T>(arr: T[], target: T): number {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1; // Not found
}

// Sum all elements - must visit each one
function sumArray(arr: number[]): number {
  return arr.reduce((sum, num) => sum + num, 0);
}

const data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log("Max:", findMax(data));
console.log("Index of 9:", linearSearch(data, 9));
console.log("Sum:", sumArray(data));

// O(log n) - Logarithmic Time
// Halves the problem size with each step
// EXTREMELY efficient for large datasets!
// 1 billion elements? Only ~30 steps needed!

function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
  let steps = 0;

  while (left <= right) {
    steps++;
    const mid = Math.floor((left + right) / 2);
    console.log(`Step ${steps}: Checking index ${mid}, value ${arr[mid]}`);

    if (arr[mid] === target) {
      console.log(`Found in ${steps} steps!`);
      return mid;
    }

    if (arr[mid] < target) {
      left = mid + 1;  // Discard left half
    } else {
      right = mid - 1; // Discard right half
    }
  }

  console.log(`Not found after ${steps} steps`);
  return -1;
}

// IMPORTANT: Array must be sorted for binary search!
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29];
console.log("Searching for 19 in array of", sortedArray.length, "elements:");
console.log("Result index:", binarySearch(sortedArray, 19));

console.log("\nSearching for 10 (not in array):");
binarySearch(sortedArray, 10);

// O(n²) - Quadratic Time
// Nested loops over the data = n * n operations
// AVOID for large inputs! 10,000 elements = 100,000,000 operations!

function bubbleSort(arr: number[]): number[] {
  const result = [...arr];
  const n = result.length;
  let swaps = 0;
  let comparisons = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      comparisons++;
      if (result[j] > result[j + 1]) {
        [result[j], result[j + 1]] = [result[j + 1], result[j]];
        swaps++;
      }
    }
  }

  console.log(`Array size: ${n}`);
  console.log(`Total comparisons: ${comparisons}`);
  console.log(`Total swaps: ${swaps}`);
  return result;
}

// Finding all pairs is also O(n²)
function findAllPairs(arr: number[]): [number, number][] {
  const pairs: [number, number][] = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      pairs.push([arr[i], arr[j]]);
    }
  }
  return pairs;
}

const unsorted = [64, 34, 25, 12, 22, 11, 90];
console.log("Original:", unsorted);
console.log("Sorted:", bubbleSort(unsorted));

console.log("\nAll pairs from [1,2,3]:", findAllPairs([1, 2, 3]));

// O(n log n) - Linearithmic Time
// The "sweet spot" for comparison-based sorting
// Merge Sort, Quick Sort, Heap Sort all achieve this

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // log n levels of recursion
  const right = mergeSort(arr.slice(mid));     // log n levels of recursion

  return merge(left, right);  // n operations at each level
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  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, ...left.slice(i), ...right.slice(j)];
}

const data = [38, 27, 43, 3, 9, 82, 10];
console.log("Original:", data);
console.log("Merge Sorted:", mergeSort(data));

// Comparison with O(n²):
// n = 1,000,000
// O(n²) = 1,000,000,000,000 operations (1 trillion!)
// O(n log n) = 20,000,000 operations (20 million)
// That's 50,000x faster!

// Arrays: The Foundation of All Data Structures
// Contiguous memory, O(1) random access, cache-friendly

// Creating arrays
const numbers: number[] = [1, 2, 3, 4, 5];
const strings: string[] = ["apple", "banana", "cherry"];
const mixed: (number | string)[] = [1, "two", 3];

// ========== BASIC OPERATIONS ==========

// ACCESS - O(1): Direct index access
console.log("First element:", numbers[0]);        // 1
console.log("Last element:", numbers[numbers.length - 1]); // 5
console.log("Middle element:", numbers[Math.floor(numbers.length / 2)]); // 3

// SEARCH - O(n): Must check each element
const index = numbers.indexOf(3);
console.log("Index of 3:", index); // 2
console.log("Includes 4?", numbers.includes(4)); // true

// INSERT at end - O(1) amortized
numbers.push(6);
console.log("After push(6):", numbers); // [1,2,3,4,5,6]

// INSERT at beginning - O(n): shifts all elements!
numbers.unshift(0);
console.log("After unshift(0):", numbers); // [0,1,2,3,4,5,6]

// INSERT at index - O(n)
numbers.splice(3, 0, 99);  // Insert 99 at index 3
console.log("After splice:", numbers); // [0,1,2,99,3,4,5,6]

// DELETE from end - O(1)
const popped = numbers.pop();
console.log("Popped:", popped, "Array:", numbers);

// DELETE from beginning - O(n)
const shifted = numbers.shift();
console.log("Shifted:", shifted, "Array:", numbers);

// DELETE at index - O(n)
numbers.splice(2, 1);  // Remove 1 element at index 2
console.log("After delete at index 2:", numbers);

// Array Methods Every Developer Must Know
// These are your daily tools for array manipulation

const nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

// ========== TRANSFORMATION METHODS ==========

// MAP: Transform each element - O(n)
const doubled = nums.map(n => n * 2);
console.log("Doubled:", doubled); // [2,4,6,8,10,12,14,16,18,20]

// FILTER: Keep elements matching condition - O(n)
const evens = nums.filter(n => n % 2 === 0);
console.log("Evens:", evens); // [2,4,6,8,10]

// REDUCE: Accumulate to single value - O(n)
const sum = nums.reduce((acc, n) => acc + n, 0);
console.log("Sum:", sum); // 55

const product = nums.reduce((acc, n) => acc * n, 1);
console.log("Product:", product); // 3628800

// FIND: Get first matching element - O(n)
const firstEven = nums.find(n => n % 2 === 0);
console.log("First even:", firstEven); // 2

// FINDINDEX: Get index of first match - O(n)
const firstEvenIndex = nums.findIndex(n => n % 2 === 0);
console.log("First even index:", firstEvenIndex); // 1

// SOME: Check if any element matches - O(n)
const hasEven = nums.some(n => n % 2 === 0);
console.log("Has even?", hasEven); // true

// EVERY: Check if all elements match - O(n)
const allPositive = nums.every(n => n > 0);
console.log("All positive?", allPositive); // true

// ========== CHAINING METHODS ==========
// Powerful pattern: chain multiple operations
const result = nums
  .filter(n => n % 2 === 0)      // Keep evens: [2,4,6,8,10]
  .map(n => n * n)               // Square: [4,16,36,64,100]
  .reduce((a, b) => a + b, 0);   // Sum: 220
console.log("Evens squared summed:", result);

// ===== INTERVIEW CLASSIC: Two Sum =====
// Given an array and target, find two numbers that add up to target
// Return their indices

// BRUTE FORCE: O(n²) - Check all pairs
function twoSumBrute(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
}

// OPTIMAL: O(n) - Use hash map to find complement
function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>(); // value -> index

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (seen.has(complement)) {
      return [seen.get(complement)!, i];
    }

    seen.set(nums[i], i);
  }

  return [];
}

// Test cases
console.log("Example 1:", twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log("Example 2:", twoSum([3, 2, 4], 6));      // [1, 2]
console.log("Example 3:", twoSum([3, 3], 6));         // [0, 1]

// Why hash map works:
// For each number, we ask: "Have I seen its complement before?"
// If yes, we found our pair!
// If no, store current number for future lookups

// ===== INTERVIEW CLASSIC: Maximum Subarray (Kadane's Algorithm) =====
// Find the contiguous subarray with the largest sum
// This is THE algorithm to know for array problems!

function maxSubArray(nums: number[]): number {
  if (nums.length === 0) return 0;

  let maxSum = nums[0];      // Best sum found so far
  let currentSum = nums[0];  // Sum of current subarray

  // Track the actual subarray (bonus)
  let start = 0, end = 0, tempStart = 0;

  for (let i = 1; i < nums.length; i++) {
    // Key insight: Should we extend current subarray or start fresh?
    // If currentSum + nums[i] < nums[i], start fresh!
    if (currentSum + nums[i] < nums[i]) {
      currentSum = nums[i];
      tempStart = i;
    } else {
      currentSum = currentSum + nums[i];
    }

    // Update max if current is better
    if (currentSum > maxSum) {
      maxSum = currentSum;
      start = tempStart;
      end = i;
    }
  }

  console.log(`Max subarray: [${nums.slice(start, end + 1)}]`);
  console.log(`From index ${start} to ${end}`);
  return maxSum;
}

// Test cases
console.log("Max sum:", maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
console.log("\nMax sum:", maxSubArray([1])); // 1
console.log("\nMax sum:", maxSubArray([5, 4, -1, 7, 8])); // 23

// Visual walkthrough for [-2, 1, -3, 4, -1, 2, 1, -5, 4]:
// i=0: current=-2, max=-2
// i=1: current=1 (start fresh), max=1
// i=2: current=-2, max=1
// i=3: current=4 (start fresh), max=4
// i=4: current=3, max=4
// i=5: current=5, max=5
// i=6: current=6, max=6 ← Winner: [4,-1,2,1]
// i=7: current=1, max=6
// i=8: current=5, max=6

// ===== SINGLY LINKED LIST =====
// Each node points to the next node
// Advantages: O(1) insert/delete at known position
// Disadvantages: No random access, extra memory for pointers

class ListNode<T> {
  value: T;
  next: ListNode<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

class SinglyLinkedList<T> {
  head: ListNode<T> | null = null;
  tail: ListNode<T> | null = null;
  length: number = 0;

  // Add to end - O(1) with tail pointer
  append(value: T): this {
    const node = new ListNode(value);

    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail!.next = node;
      this.tail = node;
    }

    this.length++;
    return this;
  }

  // Add to beginning - O(1)
  prepend(value: T): this {
    const node = new ListNode(value);
    node.next = this.head;
    this.head = node;

    if (!this.tail) {
      this.tail = node;
    }

    this.length++;
    return this;
  }

  // Get at index - O(n)
  getAt(index: number): T | null {
    if (index < 0 || index >= this.length) return null;

    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current!.next;
    }

    return current!.value;
  }

  // Insert at index - O(n)
  insertAt(index: number, value: T): boolean {
    if (index < 0 || index > this.length) return false;
    if (index === 0) { this.prepend(value); return true; }
    if (index === this.length) { this.append(value); return true; }

    const node = new ListNode(value);
    let current = this.head;

    for (let i = 0; i < index - 1; i++) {
      current = current!.next;
    }

    node.next = current!.next;
    current!.next = node;
    this.length++;

    return true;
  }

  // Remove at index - O(n)
  removeAt(index: number): T | null {
    if (index < 0 || index >= this.length) return null;

    let removed: ListNode<T>;

    if (index === 0) {
      removed = this.head!;
      this.head = this.head!.next;
      if (this.length === 1) this.tail = null;
    } else {
      let current = this.head;
      for (let i = 0; i < index - 1; i++) {
        current = current!.next;
      }
      removed = current!.next!;
      current!.next = removed.next;
      if (index === this.length - 1) this.tail = current;
    }

    this.length--;
    return removed.value;
  }

  // Print list
  print(): string {
    const values: T[] = [];
    let current = this.head;

    while (current) {
      values.push(current.value);
      current = current.next;
    }

    return values.join(" -> ") + " -> null";
  }
}

// Demo
const list = new SinglyLinkedList<number>();
list.append(1).append(2).append(3).append(4);
console.log("Initial:", list.print());

list.prepend(0);
console.log("After prepend(0):", list.print());

list.insertAt(2, 99);
console.log("After insertAt(2, 99):", list.print());

console.log("Get at index 3:", list.getAt(3));

list.removeAt(2);
console.log("After removeAt(2):", list.print());

console.log("Length:", list.length);

// ===== INTERVIEW CLASSIC: Reverse a Linked List =====
// THE most common linked list interview question!
// Learn this pattern cold - it appears everywhere

class ListNode {
  constructor(
    public val: number,
    public next: ListNode | null = null
  ) {}
}

// ITERATIVE APPROACH - O(n) time, O(1) space
// This is the preferred solution
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let current = head;

  while (current !== null) {
    // 1. Save the next node (we'll lose reference otherwise)
    const nextTemp = current.next;

    // 2. Reverse the pointer
    current.next = prev;

    // 3. Move prev and current forward
    prev = current;
    current = nextTemp;
  }

  // prev is now the new head
  return prev;
}

// RECURSIVE APPROACH - O(n) time, O(n) space (call stack)
function reverseListRecursive(head: ListNode | null): ListNode | null {
  // Base case: empty or single node
  if (head === null || head.next === null) {
    return head;
  }

  // Recursively reverse the rest
  const newHead = reverseListRecursive(head.next);

  // The magic: make the next node point back to us
  head.next.next = head;
  head.next = null;

  return newHead;
}

// Helper to print list
function printList(head: ListNode | null): string {
  const values: number[] = [];
  while (head) {
    values.push(head.val);
    head = head.next;
  }
  return values.join(" -> ");
}

// Create: 1 -> 2 -> 3 -> 4 -> 5
let head: ListNode | null = new ListNode(1,
  new ListNode(2,
    new ListNode(3,
      new ListNode(4,
        new ListNode(5)))));

console.log("Original:", printList(head));

head = reverseList(head);
console.log("Reversed:", printList(head));

// Visual walkthrough:
// Initial:  1 -> 2 -> 3 -> 4 -> 5 -> null
//           ^
//           current, prev=null
//
// Step 1:   null <- 1    2 -> 3 -> 4 -> 5 -> null
//                   ^    ^
//                   prev current
//
// Step 2:   null <- 1 <- 2    3 -> 4 -> 5 -> null
//                        ^    ^
//                        prev current
// ... continue until current is null

// ===== INTERVIEW CLASSIC: Detect Cycle in Linked List =====
// Floyd's Cycle Detection (Tortoise and Hare)
// Brilliant algorithm using two pointers at different speeds

class ListNode {
  constructor(
    public val: number,
    public next: ListNode | null = null
  ) {}
}

// Detect if cycle exists - O(n) time, O(1) space
function hasCycle(head: ListNode | null): boolean {
  if (!head || !head.next) return false;

  let slow = head;        // Moves 1 step at a time
  let fast = head.next;   // Moves 2 steps at a time

  while (slow !== fast) {
    // If fast reaches end, no cycle
    if (!fast || !fast.next) {
      return false;
    }

    slow = slow.next!;
    fast = fast.next.next;
  }

  // They met - there's a cycle!
  return true;
}

// Find where cycle begins - O(n) time, O(1) space
function detectCycle(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return null;

  let slow = head;
  let fast = head;

  // Phase 1: Detect if cycle exists
  while (fast && fast.next) {
    slow = slow.next!;
    fast = fast.next.next;

    if (slow === fast) {
      // Phase 2: Find cycle start
      // Mathematical proof: distance from head to cycle start
      // equals distance from meeting point to cycle start
      let pointer = head;
      while (pointer !== slow) {
        pointer = pointer.next!;
        slow = slow.next!;
      }
      return pointer;
    }
  }

  return null; // No cycle
}

// Create a list with cycle: 1 -> 2 -> 3 -> 4 -> 5
//                                    ^         |
//                                    |_________|
const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);
const node4 = new ListNode(4);
const node5 = new ListNode(5);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node3;  // Creates cycle back to node3

console.log("Has cycle:", hasCycle(node1)); // true

const cycleStart = detectCycle(node1);
console.log("Cycle starts at node with value:", cycleStart?.val); // 3

// Why does Floyd's algorithm work?
// If there's a cycle, fast will eventually "lap" slow
// They MUST meet because fast gains 1 node per iteration
// Meeting point math proves the cycle start location

// ===== STACK: Last In, First Out (LIFO) =====
// Think of a stack of plates - you can only add/remove from the top
// Operations: push, pop, peek - all O(1)!

class Stack<T> {
  private items: T[] = [];

  // Add to top - O(1)
  push(item: T): void {
    this.items.push(item);
  }

  // Remove from top - O(1)
  pop(): T | undefined {
    return this.items.pop();
  }

  // View top without removing - O(1)
  peek(): T | undefined {
    return this.items[this.items.length - 1];
  }

  // Check if empty - O(1)
  isEmpty(): boolean {
    return this.items.length === 0;
  }

  // Get size - O(1)
  size(): number {
    return this.items.length;
  }

  // Clear all elements
  clear(): void {
    this.items = [];
  }

  // Print stack (for debugging)
  print(): string {
    return `Stack (top->bottom): [${this.items.slice().reverse().join(", ")}]`;
  }
}

// Demo
const stack = new Stack<number>();

console.log("=== Stack Operations ===");
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.print()); // [30, 20, 10]

console.log("Peek:", stack.peek());        // 30
console.log("Pop:", stack.pop());          // 30
console.log("After pop:", stack.print());  // [20, 10]
console.log("Size:", stack.size());        // 2
console.log("Is empty?", stack.isEmpty()); // false

// Real-world uses of stacks:
// 1. Undo/Redo functionality
// 2. Browser back button
// 3. Function call stack
// 4. Expression evaluation
// 5. Syntax parsing

// ===== INTERVIEW CLASSIC: Valid Parentheses =====
// Check if brackets are properly balanced and nested
// This is a MUST-KNOW stack problem!

function isValid(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = {
    ')': '(',
    ']': '[',
    '}': '{'
  };

  for (const char of s) {
    if (char === '(' || char === '[' || char === '{') {
      // Opening bracket: push to stack
      stack.push(char);
    } else {
      // Closing bracket: must match top of stack
      if (stack.length === 0 || stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }

  // Stack must be empty (all brackets matched)
  return stack.length === 0;
}

// Test cases
console.log("'()' =>", isValid("()"));           // true
console.log("'()[]{}' =>", isValid("()[]{}"));   // true
console.log("'(]' =>", isValid("(]"));           // false
console.log("'([)]' =>", isValid("([)]"));       // false
console.log("'{[]}' =>", isValid("{[]}"));       // true
console.log("'(((' =>", isValid("((("));         // false (unclosed)
console.log("')))' =>", isValid(")))"));         // false (no opening)

// Why this works:
// - Opening brackets go on stack
// - Closing brackets must match most recent opening (LIFO!)
// - If we can't match or stack isn't empty, it's invalid

// ===== INTERVIEW CLASSIC: Min Stack =====
// Design a stack that supports push, pop, top, and getMin in O(1)
// The trick: maintain a second stack to track minimums!

class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];  // Tracks minimum at each level

  push(val: number): void {
    this.stack.push(val);

    // Push to minStack if empty or val <= current min
    if (this.minStack.length === 0 || val <= this.getMin()) {
      this.minStack.push(val);
    }
  }

  pop(): void {
    const popped = this.stack.pop();

    // If popped value was the min, remove from minStack too
    if (popped === this.getMin()) {
      this.minStack.pop();
    }
  }

  top(): number {
    return this.stack[this.stack.length - 1];
  }

  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}

// Demo
const minStack = new MinStack();

minStack.push(-2);
minStack.push(0);
minStack.push(-3);
console.log("Min:", minStack.getMin()); // -3

minStack.pop();
console.log("Top:", minStack.top());    // 0
console.log("Min:", minStack.getMin()); // -2

minStack.push(-1);
console.log("Min:", minStack.getMin()); // -2 (still!)

// Why two stacks?
// When we pop, we need to know what the min was BEFORE that element
// The minStack keeps a history of minimums