What are Data Structures?

Foundations · 5 min read

A data structure is a way of organising and storing data in memory so it can be accessed and modified efficiently. Choosing the right data structure is often the most important decision in solving a problem.

Think of it like this

Imagine you're organising books:

Stacked in a pile → Stack (last in, first out)
In a queue at checkout → Queue (first in, first out)
In alphabetical order on a shelf → Sorted Array / BST
In a filing cabinet with folders → Hash Map
In a family tree → Tree
Road network between cities → Graph

Linear vs Non-Linear

Type	Structure	Examples
Linear	Elements in a sequence	Array, Linked List, Stack, Queue
Non-Linear	Elements in a hierarchy or network	Tree, Graph

Abstract Data Types (ADTs)

An ADT defines what operations are supported, not how they are implemented. For example, a Stack ADT says "push, pop, peek" — it can be implemented using an array OR a linked list underneath.

Why Data Structures Matter in Interviews

Every coding interview tests which structure you choose and why
Wrong structure = slower code (can fail time limit)
Interviewers look for: correct choice, knowledge of trade-offs, time/space complexity justification

💡 Interview tip: Before writing code, always think: "What operations do I need? Insert, delete, search, sort? What's my time constraint?" — then pick the structure.

Arrays

Data Structures · 8 min read

An array stores elements in contiguous memory. Every element is at index i and directly addressable in O(1). It's the most fundamental data structure.

Memory Layout

If an int array starts at memory address 100 and each int is 4 bytes:

// arr = [10, 20, 30, 40, 50]
Index:   0    1    2    3    4
Address: 100  104  108  112  116

arr[2] → go to 100 + (2 × 4) = 108 → value: 30  // O(1) — that's why index access is instant

Time Complexity

Operation	Complexity	Why
Access by index	O(1)	Direct address calculation
Search (unsorted)	O(n)	Must check each element
Search (sorted)	O(log n)	Binary search
Insert at end	O(1) amortized	Dynamic array doubles capacity
Insert at middle	O(n)	Must shift elements right
Delete at middle	O(n)	Must shift elements left

Pattern 1 — Prefix Sum (Range Queries in O(1))

Pre-compute cumulative sums so any range sum [l, r] is answered in O(1).

int[] arr = {3, 1, 4, 1, 5};
int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++)
    prefix[i+1] = prefix[i] + arr[i];
// prefix = [0, 3, 4, 8, 9, 14]

// Sum from index 1 to 3 (inclusive): prefix[4] - prefix[1] = 9 - 3 = 6
int rangeSum(int l, int r) { return prefix[r+1] - prefix[l]; }

Pattern 2 — Kadane's Algorithm (Max Subarray Sum)

int maxSubarray(int[] arr) {
    int maxSoFar = arr[0], maxEndingHere = arr[0];
    for (int i = 1; i < arr.length; i++) {
        // Either extend the current subarray OR start fresh from current element
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
        maxSoFar      = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}
// Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]  → Output: 6  (subarray [4,-1,2,1])

Pattern 3 — Two Pointers (Pair Sum in Sorted Array)

boolean hasPairWithSum(int[] sorted, int target) {
    int lo = 0, hi = sorted.length - 1;
    while (lo < hi) {
        int sum = sorted[lo] + sorted[hi];
        if      (sum == target) return true;
        else if (sum <  target) lo++;   // need bigger sum → move left ptr right
        else                    hi--;   // need smaller sum → move right ptr left
    }
    return false;
}  // O(n) time, O(1) space

Pattern 4 — Sliding Window (Max Sum of K-size Window)

int maxSumWindow(int[] arr, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += arr[i];  // first window
    int max = sum;
    for (int i = k; i < arr.length; i++) {
        sum += arr[i] - arr[i - k];     // slide: add new, remove old
        max = Math.max(max, sum);
    }
    return max;
}  // O(n) instead of O(n*k) brute force

💡 Interview tip: Arrays + Prefix Sum + Two Pointers + Sliding Window solve about 40% of all array interview questions.

Hash Tables

Data Structures · 8 min read

A hash table (also called hash map or dictionary) gives O(1) average lookup, insert, and delete. It maps keys to values using a hash function.

How It Works Internally

// Step 1: Compute hash of key
hash("name") → 4   // some integer

// Step 2: Map to bucket index
index = hash % bucketCount    // e.g. 4 % 7 = 4 → slot 4

// Step 3: Store key-value pair at that slot
bucket[4] → ("name", "Aftab")

Handling Collisions (Two Keys → Same Slot)

Chaining — each bucket holds a linked list. If two keys hash to slot 4, both go in that slot's list. Java's HashMap uses chaining.
Open Addressing — if slot is taken, probe the next slot (linear probing, quadratic probing). Used in Python dicts.

// Chaining example (conceptual)
bucket[4] → [("name", "Aftab")] → [("mane", "lion")]  // both hashed to 4

Java HashMap — Core Operations

Map<String, Integer> map = new HashMap<>();

map.put("apple", 3);          // insert/update  O(1)
map.get("apple");              // returns 3      O(1)
map.containsKey("apple");    // true           O(1)
map.remove("apple");          // delete         O(1)
map.getOrDefault("x", 0);   // safe get, no NPE

// Iterate
for (Map.Entry<String, Integer> e : map.entrySet())
    System.out.println(e.getKey() + " = " + e.getValue());

// Frequency count pattern (most common hash map use)
int[] nums = {1, 2, 2, 3, 3, 3};
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums)
    freq.put(n, freq.getOrDefault(n, 0) + 1);
// freq = {1:1, 2:2, 3:3}

Pattern — Two Sum (O(n) with HashMap)

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();  // value → index
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement))
            return new int[]{ seen.get(complement), i };
        seen.put(nums[i], i);
    }
    return new int[]{-1, -1};
}
// [2,7,11,15], target=9 → [0,1]  (2+7=9)

Pattern — Group Anagrams

List<List<String>> groupAnagrams(String[] words) {
    Map<String, List<String>> map = new HashMap<>();
    for (String w : words) {
        char[] ch = w.toCharArray();
        Arrays.sort(ch);
        String key = new String(ch);            // "eat","tea","ate" all → "aet"
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
    }
    return new ArrayList<>(map.values());
}

HashSet — For Uniqueness & O(1) Lookup

Set<Integer> set = new HashSet<>();
set.add(1); set.add(2); set.add(2);  // {1, 2} — duplicates ignored
set.contains(2);   // true  O(1)
set.remove(1);    // O(1)

// Check duplicate in array — O(n)
boolean hasDuplicate(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int n : nums)
        if (!seen.add(n)) return true;  // add() returns false if already exists
    return false;
}

💡 When you see "find a pair", "check if exists", "count occurrences", or "group by" in an interview — reach for HashMap/HashSet first.

Linked Lists

Data Structures · 10 min read

A linked list is a chain of nodes where each node stores data and a reference (pointer) to the next node. Unlike arrays, nodes are not stored contiguously in memory — they can be anywhere in RAM.

Array vs Linked List

Operation	Array	Linked List
Access by index	O(1)	O(n)
Search	O(n)	O(n)
Insert at head	O(n) — must shift	O(1)
Insert at tail	O(1) amortized	O(1) with tail pointer
Insert at middle	O(n) — must shift	O(1) once you have the node
Delete at head	O(n) — must shift	O(1)
Memory	Compact (no extra pointers)	Extra pointer per node

Singly Linked List — Node & Core Operations

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

// Build: 1 → 2 → 3
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

// Traverse
ListNode cur = head;
while (cur != null) {
    System.out.print(cur.val + " ");
    cur = cur.next;
}

// Insert at head — O(1)
ListNode insertAtHead(ListNode head, int val) {
    ListNode node = new ListNode(val);
    node.next = head;
    return node;  // new head
}

// Delete a node with given value
ListNode delete(ListNode head, int val) {
    ListNode dummy = new ListNode(0);   // dummy head simplifies edge cases
    dummy.next = head;
    ListNode prev = dummy;
    while (prev.next != null) {
        if (prev.next.val == val) { prev.next = prev.next.next; break; }
        prev = prev.next;
    }
    return dummy.next;
}

Reverse a Linked List (Most Common Interview Problem)

ListNode reverse(ListNode head) {
    ListNode prev = null;
    ListNode cur  = head;
    while (cur != null) {
        ListNode nextTemp = cur.next;  // save next
        cur.next = prev;               // reverse pointer
        prev = cur;                    // advance prev
        cur  = nextTemp;               // advance cur
    }
    return prev;  // prev is the new head
}
// 1→2→3→null  becomes  null←1←2←3  →  new head = 3

Fast & Slow Pointer — Find Middle + Detect Cycle

// Find middle node
ListNode findMiddle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;        // moves 1 step
        fast = fast.next.next;   // moves 2 steps
    }
    return slow;  // when fast hits end, slow is at middle
}

// Floyd's Cycle Detection
boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;  // they meet inside cycle
    }
    return false;
}

Linked List Types

Data Structures · 8 min read

1. Singly Linked List

Each node has one pointer: next. Can only traverse forward.

// Structure: head → [1|next] → [2|next] → [3|null]
class SinglyNode {
    int val;
    SinglyNode next;
    SinglyNode(int val) { this.val = val; }
}
// Use when: you only traverse forward, memory is tight, or you need a simple stack/queue.

2. Doubly Linked List

Each node has two pointers: prev and next. Can traverse both directions. Java's LinkedList is a doubly linked list.

class DNode {
    int val;
    DNode prev, next;
    DNode(int val) { this.val = val; }
}
// Structure: null ← [1|prev|next] ↔ [2|prev|next] ↔ [3|prev|next] → null

class DoublyLinkedList {
    DNode head, tail;

    void addToFront(int val) {
        DNode node = new DNode(val);
        if (head == null) { head = tail = node; return; }
        node.next = head;
        head.prev = node;
        head = node;
    }

    void addToBack(int val) {
        DNode node = new DNode(val);
        if (tail == null) { head = tail = node; return; }
        tail.next = node;
        node.prev = tail;
        tail = node;
    }

    void deleteNode(DNode node) {       // O(1) — this is the big advantage over singly!
        if (node.prev != null) node.prev.next = node.next;
        else head = node.next;            // deleting head
        if (node.next != null) node.next.prev = node.prev;
        else tail = node.prev;            // deleting tail
    }
}
// Use when: you need to traverse backwards, or need O(1) delete given a node pointer (e.g., LRU Cache).

3. Circular Linked List

The tail's next points back to the head instead of null. Can be singly or doubly circular.

// Singly circular: head → [1] → [2] → [3] → (back to head)
class CircularList {
    SinglyNode head = null;

    void add(int val) {
        SinglyNode node = new SinglyNode(val);
        if (head == null) { head = node; node.next = head; return; }
        SinglyNode tail = head;
        while (tail.next != head) tail = tail.next;
        tail.next = node;
        node.next = head;
    }

    void traverse() {
        if (head == null) return;
        SinglyNode cur = head;
        do {
            System.out.print(cur.val + " ");
            cur = cur.next;
        } while (cur != head);   // stop when we loop back to head
    }
}
// Use when: you need continuous looping (round-robin scheduling, circular buffers).

Interview — LRU Cache (Classic Doubly LL + HashMap)

class LRUCache {
    int capacity;
    Map<Integer, DNode> map = new HashMap<>();
    DNode head = new DNode(0);  // dummy head
    DNode tail = new DNode(0);  // dummy tail

    LRUCache(int cap) {
        capacity = cap;
        head.next = tail; tail.prev = head;
    }
    int get(int key) {
        if (!map.containsKey(key)) return -1;
        DNode node = map.get(key);
        moveToFront(node);  // recently used
        return node.val;
    }
    void put(int key, int value) {
        if (map.containsKey(key)) {
            DNode node = map.get(key);
            node.val = value;
            moveToFront(node);
        } else {
            if (map.size() == capacity) {
                map.remove(tail.prev.val);
                removeNode(tail.prev);   // evict LRU (tail side)
            }
            DNode node = new DNode(value);
            map.put(key, node);
            addToFront(node);
        }
    }
    // Helper methods: addToFront, removeNode, moveToFront (standard doubly-LL ops)
}
// get() and put() both O(1)!

Stacks & Queues

Data Structures · 8 min read

Stack — Last In, First Out (LIFO)

Think of a stack of plates — you add to the top, remove from the top.

// Use Deque<Integer> (not java.util.Stack which is slow)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);   // push to top     O(1)
stack.push(20);
stack.peek();    // view top = 20   O(1)
stack.pop();     // remove top = 20 O(1)
stack.isEmpty();  // false

Classic — Balanced Parentheses

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return stack.isEmpty();
}
// "{[]}" → true    "([)]" → false

Monotonic Stack — Next Greater Element

int[] nextGreater(int[] arr) {
    int[] result = new int[arr.length];
    Arrays.fill(result, -1);   // default: no greater element
    Deque<Integer> stack = new ArrayDeque<>();  // stores indices
    for (int i = 0; i < arr.length; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
            result[stack.pop()] = arr[i];
        }
        stack.push(i);
    }
    return result;
}
// [2, 1, 5, 3, 6] → [5, 5, 6, 6, -1]

Queue — First In, First Out (FIFO)

Think of a bank queue — first person in gets served first.

Queue<Integer> queue = new LinkedList<>();
queue.offer(10);   // enqueue  O(1)
queue.offer(20);
queue.peek();     // front = 10  O(1)
queue.poll();     // dequeue = 10  O(1)

// Deque — works as both stack and queue
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);    // add to front
deque.addLast(2);     // add to back
deque.removeFirst();  // remove from front
deque.removeLast();   // remove from back

💡 Stack use cases: undo/redo, DFS, function call stack, expression evaluation
Queue use cases: BFS, task scheduling, print queue, message buffering

Binary Trees

Data Structures · 10 min read

A binary tree is a hierarchical structure where each node has at most two children: left and right. It's the foundation for BSTs, heaps, tries, and many more structures.

Terminology You Must Know

Root — top node, no parent
Leaf — node with no children
Height — longest path from root to a leaf
Depth — distance from root to a specific node
Level — depth + 1 (root is level 1)
Subtree — any node and all its descendants

Types of Binary Trees

Type	Property
Full Binary Tree	Every node has 0 or 2 children (no node has exactly 1)
Complete Binary Tree	All levels filled except possibly last; last level filled left to right
Perfect Binary Tree	All internal nodes have 2 children; all leaves at same depth
Balanced Binary Tree	Height difference between left and right subtree ≤ 1 (for every node)
Degenerate/Skewed	Every node has only one child — behaves like a linked list

Node Structure

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

The 4 Traversals (Must Know All)

// Tree:    1
//         / \
//        2   3
//       / \
//      4   5

// 1. Inorder: Left → Root → Right   (gives SORTED output for BST)
void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    System.out.print(node.val + " ");  // 4 2 5 1 3
    inorder(node.right);
}

// 2. Preorder: Root → Left → Right   (used to copy/serialize tree)
void preorder(TreeNode node) {
    if (node == null) return;
    System.out.print(node.val + " ");  // 1 2 4 5 3
    preorder(node.left);
    preorder(node.right);
}

// 3. Postorder: Left → Right → Root  (used to delete tree, evaluate expressions)
void postorder(TreeNode node) {
    if (node == null) return;
    postorder(node.left);
    postorder(node.right);
    System.out.print(node.val + " ");  // 4 5 2 3 1
}

// 4. Level Order (BFS): Level by level   (used for shortest path, level problems)
List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();                    // number of nodes at this level
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left  != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Height of a Binary Tree

int height(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

// Diameter = longest path between any two nodes
int diameter = 0;
int diameterOfTree(TreeNode node) {
    if (node == null) return 0;
    int left  = diameterOfTree(node.left);
    int right = diameterOfTree(node.right);
    diameter = Math.max(diameter, left + right);   // path through this node
    return 1 + Math.max(left, right);
}

💡 Interview tip: Most binary tree problems are solved with recursion. Ask: "What should I return from each node? What do I do with left and right results?"

Binary Search Tree (BST)

Data Structures · 8 min read

A BST is a binary tree with one rule: left subtree values < node < right subtree values for every node. This makes search O(log n) on a balanced tree.

Search, Insert, Delete

// Search — O(log n) balanced, O(n) worst case (skewed)
boolean search(TreeNode root, int val) {
    if (root == null) return false;
    if (val == root.val) return true;
    return val < root.val ? search(root.left, val) : search(root.right, val);
}

// Insert
TreeNode insert(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.val) root.left  = insert(root.left,  val);
    else               root.right = insert(root.right, val);
    return root;
}

// Delete — 3 cases
TreeNode delete(TreeNode root, int val) {
    if (root == null) return null;
    if      (val < root.val) root.left  = delete(root.left,  val);
    else if (val > root.val) root.right = delete(root.right, val);
    else {
        if (root.left  == null) return root.right; // case 1: no left child
        if (root.right == null) return root.left;  // case 2: no right child
        // case 3: two children — replace with inorder successor (smallest in right subtree)
        TreeNode successor = root.right;
        while (successor.left != null) successor = successor.left;
        root.val   = successor.val;
        root.right = delete(root.right, successor.val);
    }
    return root;
}

Validate a BST

boolean isValidBST(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;
    return isValidBST(node.left,  min, node.val)
        && isValidBST(node.right, node.val, max);
}
// call: isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE)

💡 Inorder traversal of a valid BST always produces a sorted sequence. Use this fact to validate or convert BSTs.

Graphs

Data Structures · 10 min read

A graph is a set of vertices (nodes) connected by edges. Unlike trees, graphs can have cycles and multiple paths between nodes.

Types of Graphs

Directed — edges have direction (A→B doesn't mean B→A). Example: Twitter follows.
Undirected — edges go both ways. Example: Facebook friends.
Weighted — edges have costs. Example: road distances.
Unweighted — all edges equal. Example: maze cells.
Cyclic — contains at least one cycle.
Acyclic — no cycles. A DAG (Directed Acyclic Graph) is used in build systems, scheduling.

Representations

// 1. Adjacency List — preferred for sparse graphs, O(V+E) space
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.computeIfAbsent(1, k -> new ArrayList<>()).add(2);
graph.computeIfAbsent(1, k -> new ArrayList<>()).add(3);
graph.computeIfAbsent(2, k -> new ArrayList<>()).add(4);
// graph: 1→[2,3], 2→[4]

// 2. Adjacency Matrix — O(V²) space, good for dense graphs
int V = 5;
int[][] matrix = new int[V][V];
matrix[1][2] = 1;   // edge from 1 to 2
matrix[2][1] = 1;   // undirected: also 2 to 1

Key Graph Terms

Term	Meaning
Degree	Number of edges connected to a vertex
Path	Sequence of vertices connected by edges
Cycle	Path that starts and ends at the same vertex
Connected	Every vertex reachable from every other (undirected)
Strongly Connected	Every vertex reachable from every other (directed)
Topological Sort	Linear ordering of vertices where u comes before v for every edge u→v (only for DAGs)

💡 Graph problems are solved with BFS (shortest path, levels) or DFS (cycles, connected components, topological sort). Covered in detail in the Searching section.

What is an Algorithm?

Algorithms · 5 min read

An algorithm is a finite, well-defined sequence of steps to solve a specific problem. It takes input, processes it, and produces output.

5 Properties Every Algorithm Must Have

Input — takes zero or more inputs
Output — produces at least one output
Definiteness — every step is clear and unambiguous
Finiteness — must terminate after a finite number of steps
Effectiveness — every step must be basic enough to be carried out

Algorithm vs Program

An algorithm is language-independent — it's the idea/logic
A program is the implementation of an algorithm in a specific language
The same algorithm (e.g., binary search) can be written in Java, Python, C++

How to Analyse an Algorithm

We measure two things:

Time Complexity — how many steps/operations as input grows
Space Complexity — how much extra memory as input grows

// Example: find max in an array
int findMax(int[] arr) {       // Input: array of n elements
    int max = arr[0];             // 1 operation
    for (int x : arr) {           // n iterations
        if (x > max) max = x;    // 1 operation each
    }
    return max;
}
// Time: O(n)   Space: O(1) — only one extra variable regardless of input size

💡 A good algorithm is correct (gives right answer), efficient (fast and low memory), and simple (easy to understand and maintain).

Time & Space Complexity

Algorithms · 8 min read

Big-O notation describes how an algorithm's runtime or memory grows with input size n. We always analyse the worst case unless told otherwise.

Big-O Cheat Sheet (Fastest to Slowest)

Big-O	Name	Example	n=1000
O(1)	Constant	Array index access, HashMap lookup	1 op
O(log n)	Logarithmic	Binary search, BST ops	~10 ops
O(n)	Linear	Single loop, linear search	1,000 ops
O(n log n)	Linearithmic	Merge sort, heap sort	~10,000 ops
O(n²)	Quadratic	Bubble/selection/insertion sort, nested loops	1,000,000 ops
O(2ⁿ)	Exponential	Brute-force subsets, naive recursion	Astronomical
O(n!)	Factorial	Permutations, travelling salesman brute-force	Impossible

Rules for Calculating Big-O

// Rule 1: Drop constants
// O(2n) → O(n),  O(500) → O(1)

// Rule 2: Drop lower-order terms
// O(n² + n) → O(n²)

// Rule 3: Loops multiply when nested, add when sequential
for (int i = 0; i < n; i++)          // O(n)
    for (int j = 0; j < n; j++)      // O(n)
        doSomething();                 // Total: O(n²)

for (int i = 0; i < n; i++) {}      // O(n)
for (int j = 0; j < n; j++) {}      // O(n) — sequential, not nested
// Total: O(n) + O(n) = O(n)

// Rule 4: Halving each step → O(log n)
while (n > 1) n = n / 2;           // O(log n)

Space Complexity

// O(1) space — fixed variables, no data structures growing with n
int sum = 0;
for (int x : arr) sum += x;

// O(n) space — array/list that grows with n
int[] copy = Arrays.copyOf(arr, arr.length);

// O(log n) space — recursion depth of binary search / merge sort
// Recursive call stack counts as space!

💡 In interviews, always state both time AND space complexity. Say: "This solution is O(n) time and O(1) space." Interviewers deduct marks if you don't mention both.

Recursion

Algorithms · 10 min read

Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive solution needs two things: a base case (stopping condition) and a recursive case (calling itself with smaller input).

How the Call Stack Works

int factorial(int n) {
    if (n == 0) return 1;         // BASE CASE — must exist or infinite recursion
    return n * factorial(n - 1);   // RECURSIVE CASE — smaller input each time
}

// factorial(4) call stack (grows downward):
// factorial(4)  → 4 * factorial(3)
//   factorial(3)  → 3 * factorial(2)
//     factorial(2)  → 2 * factorial(1)
//       factorial(1)  → 1 * factorial(0)
//         factorial(0)  → 1  ← base case, unwind starts
// Returns: 4 * 3 * 2 * 1 * 1 = 24

Fibonacci — Naive vs Optimised

// Naive — O(2ⁿ): each call branches into 2 more calls
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);    // fib(5) calls fib(3) TWICE — wasteful
}

// With memoization — O(n): each value computed once
Map<Integer, Integer> memo = new HashMap<>();
int fibMemo(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);
    int result = fibMemo(n - 1) + fibMemo(n - 2);
    memo.put(n, result);
    return result;
}

Backtracking Template

// Generate all subsets of [1,2,3]
void backtrack(List<List<Integer>> res, List<Integer> curr, int[] nums, int start) {
    res.add(new ArrayList<>(curr));          // add snapshot of current path
    for (int i = start; i < nums.length; i++) {
        curr.add(nums[i]);                    // choose
        backtrack(res, curr, nums, i + 1);   // explore
        curr.remove(curr.size() - 1);        // un-choose (backtrack)
    }
}

💡 3-step recursion recipe: 1) Define what the function returns. 2) Write the base case. 3) Assume recursive call works for n-1, use its result to solve n.

Stack Overflow

Algorithms · 6 min read

A Stack Overflow happens when the call stack runs out of memory because too many function calls are stacked up without returning. The most common cause is recursion with no base case or a base case that's never reached.

How the Call Stack Works

Every time you call a function, a new stack frame is pushed onto the call stack. It holds local variables, parameters, and the return address. When the function returns, the frame is popped off.

// Stack Overflow: missing base case — runs forever
int badFactorial(int n) {
    return n * badFactorial(n - 1);   // never stops! → StackOverflowError
}

// Stack Overflow: base case never reached
int badSearch(int[] arr, int i) {
    if (i == 1000000) return -1;    // arr.length might be 10 — never reaches 1000000
    return badSearch(arr, i + 1);
}

How to Fix

Add/fix the base case — always verify the recursion terminates
Convert to iterative — use an explicit stack (Deque) instead of call stack
Increase stack size — -Xss4m JVM flag (rarely the real fix)
Use tail recursion — some languages optimise tail calls (Java doesn't, but the pattern is cleaner)

// Tail recursion — recursive call is the LAST operation (no work after it)
int factTail(int n, int acc) {
    if (n == 0) return acc;
    return factTail(n - 1, n * acc);  // result is passed forward, not multiplied after return
}
// call: factTail(5, 1)

// Convert to iterative to avoid stack overflow entirely
int factIterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

⚠️ Java's default thread stack is ~512KB. Deep recursion on large inputs (n > ~10,000) will throw java.lang.StackOverflowError. Always prefer iteration for large inputs.

Sorting Algorithms

Algorithms · 5 min read

Sorting arranges elements in order (ascending or descending). It's fundamental because many other algorithms (binary search, merging) require sorted input.

Comparison at a Glance

Algorithm	Best	Average	Worst	Space	Stable?	Strategy
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Compare adjacent
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No	Find minimum
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Build sorted prefix
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	Divide & conquer
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Partition
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Heap property

A sort is stable if equal elements maintain their original relative order. This matters when sorting objects by one field when they're already sorted by another.

💡 Java's Arrays.sort(int[]) uses Dual-Pivot Quicksort. Arrays.sort(Object[]) and Collections.sort() use TimSort (merge + insertion), which is stable.

Bubble Sort

Algorithms · 6 min read

Bubble sort repeatedly compares adjacent pairs and swaps them if out of order. The largest element "bubbles up" to its correct position after each pass.

Visualisation

// Array: [5, 3, 1, 4, 2]
// Pass 1: compare neighbours, swap if needed
// [5,3,1,4,2] → [3,5,1,4,2] → [3,1,5,4,2] → [3,1,4,5,2] → [3,1,4,2,5]  ← 5 in place
// Pass 2: [1,3,4,2,5] → ... → [1,3,2,4,5]  ← 4 in place
// Pass 3: [1,2,3,4,5]  ← done

Implementation

void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {          // n-1 passes
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {   // last i elements are already sorted
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;   // optimisation: already sorted → O(n) best case
    }
}
// Time: O(n²) average/worst, O(n) best (already sorted)   Space: O(1)

💡 Bubble sort is almost never used in production. Its value is in simplicity and teaching. Interviewers may ask you to code it, explain it, or discuss when NOT to use it.

Selection Sort

Algorithms · 5 min read

Selection sort divides the array into a sorted part (left) and unsorted part (right). It repeatedly finds the minimum element in the unsorted part and moves it to the end of the sorted part.

Visualisation

// Array: [5, 3, 1, 4, 2]
// Pass 1: min of [5,3,1,4,2] = 1 → swap with index 0 → [1, 3, 5, 4, 2]
// Pass 2: min of [3,5,4,2]   = 2 → swap with index 1 → [1, 2, 5, 4, 3]
// Pass 3: min of [5,4,3]     = 3 → swap with index 2 → [1, 2, 3, 4, 5]
// Pass 4: min of [4,5]       = 4 → already in place  → [1, 2, 3, 4, 5]

Implementation

void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;   // track index of minimum
        }
        int temp = arr[minIdx]; arr[minIdx] = arr[i]; arr[i] = temp;  // swap min to front
    }
}
// Time: O(n²) always — no early exit.   Space: O(1)
// Makes at most n-1 swaps — useful when write operations are expensive

⚠️ Selection sort is NOT stable — swapping can change the relative order of equal elements. Use when minimising the number of writes (e.g., writing to flash memory).

Insertion Sort

Algorithms · 6 min read

Insertion sort builds a sorted array one element at a time. Think of sorting playing cards in your hand — you pick each new card and insert it in its correct position among the already-sorted cards.

Visualisation

// Array: [5, 3, 1, 4, 2]
// i=1: key=3, shift 5 right → [3, 5, 1, 4, 2]
// i=2: key=1, shift 5,3 right → [1, 3, 5, 4, 2]
// i=3: key=4, shift 5 right → [1, 3, 4, 5, 2]
// i=4: key=2, shift 5,4,3 right → [1, 2, 3, 4, 5]

Implementation

void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];    // element to place
        int j   = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];   // shift larger elements right
            j--;
        }
        arr[j + 1] = key;          // insert key in its correct position
    }
}
// Time: O(n²) worst, O(n) best (already sorted)   Space: O(1)   Stable: Yes

💡 Insertion sort is adaptive (fast on nearly sorted data) and online (can sort a stream as elements arrive). Java's TimSort uses insertion sort for small sub-arrays (< 32 elements).

Divide & Conquer

Algorithms · 7 min read

Divide and Conquer is a problem-solving strategy with three steps:

Divide — split the problem into smaller subproblems
Conquer — recursively solve each subproblem
Combine — merge the solutions of subproblems into the final answer

Classic Examples

Merge Sort — divide array in half, sort each half, merge
Quick Sort — partition around a pivot, sort each side
Binary Search — eliminate half the search space each step
Strassen Matrix Multiplication — O(n^2.81) instead of O(n³)

Recurrence Relations

// Merge Sort splits into 2 halves, each of size n/2, then O(n) merge
// T(n) = 2·T(n/2) + O(n) → O(n log n)  [Master Theorem Case 2]

// Binary Search splits into 1 half of size n/2, constant work
// T(n) = T(n/2) + O(1) → O(log n)

// Master Theorem (quick reference):
// T(n) = a·T(n/b) + f(n)
// If f(n) = O(n^c) and c < log_b(a) → T(n) = O(n^log_b(a))
// If f(n) = O(n^c) and c = log_b(a) → T(n) = O(n^c · log n)
// If f(n) = O(n^c) and c > log_b(a) → T(n) = O(f(n))

Template

int divideAndConquer(int[] arr, int lo, int hi) {
    if (lo == hi) return arr[lo];          // base case: single element
    int mid = lo + (hi - lo) / 2;
    int left  = divideAndConquer(arr, lo, mid);       // conquer left
    int right = divideAndConquer(arr, mid + 1, hi);   // conquer right
    return combine(left, right);                       // combine
}

Merge Sort

Algorithms · 8 min read

Merge sort divides the array in half recursively until single elements remain (always sorted), then merges them back in sorted order.

Visualisation

// [5, 3, 1, 4, 2]
//       Divide
//  [5,3,1]       [4,2]
//  [5,3] [1]   [4] [2]
//  [5][3]
//       Merge (conquer)
//  [3,5] [1]   [2,4]
//  [1,3,5]     [2,4]
//       [1,2,3,4,5]

Full Implementation

void mergeSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;              // base: 0 or 1 element
    int mid = lo + (hi - lo) / 2;
    mergeSort(arr, lo, mid);           // sort left half
    mergeSort(arr, mid + 1, hi);      // sort right half
    merge(arr, lo, mid, hi);           // merge both halves
}

void merge(int[] arr, int lo, int mid, int hi) {
    int[] temp = Arrays.copyOfRange(arr, lo, hi + 1);
    int i = 0,  j = mid - lo + 1,  k = lo;
    int leftEnd  = mid - lo;
    int rightEnd = hi - lo;

    while (i <= leftEnd && j <= rightEnd) {
        if (temp[i] <= temp[j]) arr[k++] = temp[i++];
        else                     arr[k++] = temp[j++];
    }
    while (i <= leftEnd)  arr[k++] = temp[i++];  // copy remaining left
    while (j <= rightEnd) arr[k++] = temp[j++];  // copy remaining right
}

// Usage: mergeSort(arr, 0, arr.length - 1)
// Time: O(n log n) always   Space: O(n) — needs auxiliary array   Stable: Yes

💡 Merge sort is guaranteed O(n log n). It's the go-to for sorting linked lists (no random access needed) and for external sorting (data too big for RAM).

Quick Sort

Algorithms · 9 min read

Quick sort picks a pivot, partitions the array so elements smaller than pivot go left and larger go right, then recursively sorts each side. The partition step is done in place.

Visualisation

// [5, 3, 1, 4, 2]  pivot = 2 (last element, Lomuto scheme)
// Partition: elements < 2 go left, > 2 go right
// → [1, 2, 5, 4, 3]  pivot 2 is now at index 1
// Recurse left [1] and right [5,4,3]
// Right: pivot=3 → [3, 4, 5] → pivot=4 → done
// Final: [1, 2, 3, 4, 5]

Implementation (Lomuto Partition)

void quickSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = partition(arr, lo, hi);
    quickSort(arr, lo, pivot - 1);
    quickSort(arr, pivot + 1, hi);
}

int partition(int[] arr, int lo, int hi) {
    int pivot = arr[hi];   // choose last element as pivot
    int i     = lo - 1;   // index of last element smaller than pivot
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    int tmp = arr[i+1]; arr[i+1] = arr[hi]; arr[hi] = tmp;  // place pivot
    return i + 1;   // pivot's final position
}
// Usage: quickSort(arr, 0, arr.length - 1)

Pivot Choice Matters

// Worst case O(n²): always pick smallest/largest element as pivot
// e.g., already sorted [1,2,3,4,5] with last-element pivot → n-1 partitions each of size n-1

// Fix: Randomised pivot — swap a random element with arr[hi] before partitioning
int randIdx = lo + (int)(Math.random() * (hi - lo + 1));
int tmp = arr[randIdx]; arr[randIdx] = arr[hi]; arr[hi] = tmp;
// Now worst case is extremely unlikely → average O(n log n)

// Fix: Median-of-3 — pick median of first, middle, last as pivot (Java's Dual-Pivot uses this idea)

💡 Quick sort is the fastest in practice for in-memory sorting due to cache locality. It sorts the array in-place unlike merge sort. Use randomised pivot to avoid O(n²) worst case.

Selecting a Sorting Algorithm

Algorithms · 5 min read

Decision Guide

Situation	Best Choice	Why
General purpose, primitives	Quick Sort / Arrays.sort()	Fast in practice, in-place, cache-friendly
Need stable sort	Merge Sort / Collections.sort()	Equal elements maintain order
Nearly sorted data	Insertion Sort	O(n) on nearly sorted input
Small array (< 20 elements)	Insertion Sort	Low overhead, fast in practice
Linked List	Merge Sort	No random access needed; O(n log n) guaranteed
Limited writes to disk/flash	Selection Sort	At most n-1 swaps regardless
Teaching / simplest code	Bubble Sort	Easiest to understand
Guaranteed O(n log n), any case	Merge Sort / Heap Sort	Quick sort has O(n²) worst case

Java Built-in Sorting

int[] arr = {5, 3, 1};
Arrays.sort(arr);                         // ascending, primitives — Dual-Pivot Quicksort

String[] words = {"banana", "apple"};
Arrays.sort(words);                        // natural order — TimSort
Arrays.sort(words, Comparator.reverseOrder()); // descending

List<Integer> list = Arrays.asList(3, 1, 2);
Collections.sort(list);                   // stable sort — TimSort
list.sort((a, b) -> b - a);              // descending with lambda comparator

Linear Search

Algorithms · 4 min read

Linear search scans every element from left to right until it finds the target or exhausts the array. It works on any array — sorted or unsorted.

Implementation

int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;   // found: return index
    }
    return -1;                             // not found
}
// Time: O(n) worst case   Space: O(1)

// Search for object (equals-based)
<T> int linearSearch(T[] arr, T target) {
    for (int i = 0; i < arr.length; i++)
        if (arr[i].equals(target)) return i;
    return -1;
}

When to Use Linear Search

Array is unsorted and sorting it first isn't worth it
Array is small (n < 20) — overhead of binary search isn't justified
Searching a linked list (no random access, can't binary search)
You need to find all occurrences, not just the first

Binary Search

Algorithms · 9 min read

Binary search finds a target in a sorted array in O(log n) by eliminating half the search space each step.

Classic Implementation

int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // avoids integer overflow vs (lo+hi)/2
        if      (arr[mid] == target) return mid;
        else if (arr[mid] <  target) lo = mid + 1;
        else                         hi = mid - 1;
    }
    return -1;
}
// [1,3,5,7,9], target=5 → lo=0,hi=4 → mid=2 (arr[2]=5) → return 2

Find First / Last Occurrence

// First occurrence (lower bound)
int firstOccurrence(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1, result = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) { result = mid; hi = mid - 1; }  // keep searching left
        else if (arr[mid] < target) lo = mid + 1;
        else                        hi = mid - 1;
    }
    return result;
}

// Binary search on the ANSWER (search on range, not array)
// "Find the minimum speed to finish reading books in h hours"
int lo = 1, hi = maxElement;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (canFinish(mid)) hi = mid;    // mid works → try smaller
    else               lo = mid + 1; // mid too slow → need more speed
}

💡 Binary search appears in many hidden forms: rotated sorted array, peak element, square root, kth smallest — any time you can binary search on a condition, not just a value.

Breadth-First Search (BFS)

Algorithms · 9 min read

BFS explores a graph (or tree) level by level, visiting all neighbours of the current node before going deeper. It uses a Queue.

Why BFS?

Finds the shortest path in an unweighted graph
Level-order tree traversal
Find all nodes at distance k from source
Check if a graph is bipartite
Web crawlers, social network friend suggestions

BFS on a Graph

void bfs(Map<Integer, List<Integer>> graph, int start) {
    Queue<Integer> queue   = new LinkedList<>();
    Set<Integer>   visited = new HashSet<>();
    queue.offer(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        for (int neighbour : graph.getOrDefault(node, List.of())) {
            if (!visited.contains(neighbour)) {
                visited.add(neighbour);
                queue.offer(neighbour);
            }
        }
    }
}

BFS Shortest Path (with distance tracking)

Map<Integer, Integer> shortestPath(Map<Integer, List<Integer>> graph, int start) {
    Map<Integer, Integer> dist    = new HashMap<>();
    Queue<Integer>        queue   = new LinkedList<>();
    dist.put(start, 0);
    queue.offer(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int nb : graph.getOrDefault(node, List.of())) {
            if (!dist.containsKey(nb)) {
                dist.put(nb, dist.get(node) + 1);
                queue.offer(nb);
            }
        }
    }
    return dist;   // dist.get(target) = shortest hops from start to target
}
// Time: O(V + E)   Space: O(V)

BFS on a Grid (Common in Interviews)

// Shortest path in a maze — 0=open, 1=wall
int bfsGrid(int[][] grid, int[] start, int[] end) {
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{start[0], start[1], 0});   // {row, col, distance}
    grid[start[0]][start[1]] = 1;               // mark visited
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        if (cur[0] == end[0] && cur[1] == end[1]) return cur[2];
        for (int[] d : dirs) {
            int r = cur[0]+d[0], c = cur[1]+d[1];
            if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] == 0) {
                grid[r][c] = 1;
                q.offer(new int[]{r, c, cur[2]+1});
            }
        }
    }
    return -1;   // no path
}

Depth-First Search (DFS)

Algorithms · 9 min read

DFS explores as deep as possible along each branch before backtracking. It uses a Stack (or recursion, which uses the call stack).

Why DFS?

Detect cycles in a graph
Find connected components
Topological sort (scheduling tasks with dependencies)
Solve mazes, puzzles, backtracking problems
All tree traversals (preorder, inorder, postorder)

DFS — Recursive (Graph)

void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
    visited.add(node);
    System.out.print(node + " ");
    for (int nb : graph.getOrDefault(node, List.of())) {
        if (!visited.contains(nb))
            dfs(graph, nb, visited);
    }
}
// call: dfs(graph, startNode, new HashSet<>())

DFS — Iterative (using Stack)

void dfsIterative(Map<Integer, List<Integer>> graph, int start) {
    Deque<Integer> stack   = new ArrayDeque<>();
    Set<Integer>   visited = new HashSet<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (visited.contains(node)) continue;
        visited.add(node);
        System.out.print(node + " ");
        for (int nb : graph.getOrDefault(node, List.of()))
            if (!visited.contains(nb)) stack.push(nb);
    }
}
// Time: O(V + E)   Space: O(V)

Cycle Detection in Directed Graph

boolean hasCycle(Map<Integer, List<Integer>> graph, int node,
                     Set<Integer> visited, Set<Integer> inStack) {
    visited.add(node);
    inStack.add(node);
    for (int nb : graph.getOrDefault(node, List.of())) {
        if (!visited.contains(nb) && hasCycle(graph, nb, visited, inStack))
            return true;
        if (inStack.contains(nb)) return true;   // back edge = cycle
    }
    inStack.remove(node);
    return false;
}

Topological Sort (DFS-based)

List<Integer> topoSort(Map<Integer, List<Integer>> graph, List<Integer> nodes) {
    Set<Integer>   visited = new HashSet<>();
    Deque<Integer> stack   = new ArrayDeque<>();
    for (int node : nodes)
        if (!visited.contains(node))
            topoHelper(graph, node, visited, stack);
    List<Integer> result = new ArrayList<>(stack);
    return result;   // stack order = topological order
}
void topoHelper(Map<Integer, List<Integer>> g, int node,
                 Set<Integer> visited, Deque<Integer> stack) {
    visited.add(node);
    for (int nb : g.getOrDefault(node, List.of()))
        if (!visited.contains(nb)) topoHelper(g, nb, visited, stack);
    stack.push(node);   // push AFTER processing all neighbours
}

Selecting a Searching Algorithm

Algorithms · 4 min read

Situation	Algorithm	Time
Unsorted array / linked list	Linear Search	O(n)
Sorted array, find exact value	Binary Search	O(log n)
Shortest path in unweighted graph/grid	BFS	O(V+E)
Explore all paths, detect cycles, topo sort	DFS	O(V+E)
Shortest path in weighted graph (no negative)	Dijkstra	O((V+E) log V)
Shortest path with negative weights	Bellman-Ford	O(V·E)
Search with constraints (sudoku, N-queens)	DFS + Backtracking	Exponential

💡 Interview rule of thumb: "Shortest path unweighted → BFS. Explore everything → DFS. Shortest path weighted → Dijkstra."

Dijkstra's Algorithm

Graph Algorithms · 10 min read

Dijkstra finds the shortest path from a source to all other vertices in a graph with non-negative edge weights. It is a greedy algorithm that always expands the lowest-cost unvisited node.

How It Works

Set distance to source = 0, all others = ∞
Add source to a min-heap (priority queue)
While heap not empty: pop node with smallest distance
For each neighbour: if dist[node] + edge_weight < dist[neighbour], update dist[neighbour] and push to heap
Repeat until all nodes visited

// Graph: adjacency list of [neighbour, weight] pairs
int[] dijkstra(Map<Integer, List<int[]>> graph, int src, int V) {
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // Min-heap: [distance, node]
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, src});

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], node = curr[1];
        if (d > dist[node]) continue;   // stale entry — skip

        for (int[] edge : graph.getOrDefault(node, List.of())) {
            int nb = edge[0], w = edge[1];
            if (dist[node] + w < dist[nb]) {
                dist[nb] = dist[node] + w;
                pq.offer(new int[]{dist[nb], nb});
            }
        }
    }
    return dist;   // dist[i] = shortest distance from src to i
}
// Time: O((V + E) log V)   Space: O(V + E)

💡 Dijkstra does NOT work with negative edge weights. Use Bellman-Ford instead.

Bellman-Ford Algorithm

Graph Algorithms · 8 min read

Bellman-Ford finds the shortest path from a source to all vertices and handles negative edge weights. It can also detect negative weight cycles.

How It Works

Repeatedly relax all edges V-1 times. A shortest path in a graph with V vertices has at most V-1 edges, so V-1 relaxation passes are always enough.

// Edge list: each edge = [u, v, weight]
int[] bellmanFord(int[][] edges, int V, int src) {
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // Relax all edges V-1 times
    for (int i = 0; i < V - 1; i++) {
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }

    // V-th relaxation: if any distance still improves → negative cycle exists
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
            throw new RuntimeException("Negative cycle detected!");
    }
    return dist;
}
// Time: O(V × E)   Space: O(V)

Dijkstra vs Bellman-Ford

Property	Dijkstra	Bellman-Ford
Negative weights	❌ Doesn't work	✅ Handles them
Negative cycles	❌ Doesn't detect	✅ Detects them
Time complexity	O((V+E) log V)	O(V·E)
Strategy	Greedy (priority queue)	Dynamic programming (relaxation)
Best for	Dense graphs, non-negative weights	Negative weights, small graphs

Negative Edge Weights & Relaxation

Graph Algorithms · 7 min read

Why Negative Weights Break Dijkstra

Dijkstra assumes: once a node is popped from the priority queue with distance d, that's the shortest distance. Negative edges can create a shorter path to a node after it's already been finalised.

// Example: A→B weight=1, A→C weight=4, C→B weight=-5
// Dijkstra processes B first (dist=1 via A→B)
// Then processes C (dist=4), finds C→B = 4 + (-5) = -1 < 1
// But B is already "finalised" at dist=1 → WRONG answer
// Bellman-Ford would keep relaxing and correct this to dist[B] = -1

What is Relaxation?

Relaxation is the core operation of shortest-path algorithms. For every edge (u → v, weight w):

// Relax edge u → v with weight w
if (dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;   // found a shorter path to v via u
}
// "Relax" means: try to improve the current known distance to v
// Both Dijkstra and Bellman-Ford use this exact formula
// Dijkstra relaxes greedily (closest node first)
// Bellman-Ford relaxes ALL edges V-1 times systematically

Negative Weight Cycles

A negative weight cycle is a cycle whose total weight is negative. Going around the cycle repeatedly reduces the path cost infinitely — so no finite shortest path exists.

// A → B → C → A with weights 1, -3, 1
// Total cycle weight = 1 + (-3) + 1 = -1  (negative!)
// Each loop around the cycle: dist -= 1 → -∞
// Detection: if a distance improves on the V-th relaxation pass → negative cycle exists

Sparse Graphs

Graph Algorithms · 5 min read

A sparse graph has far fewer edges than the maximum possible. A dense graph has edges close to the maximum (V² for directed, V(V-1)/2 for undirected).

Sparse vs Dense

Property	Sparse	Dense
Edge count E	E ≈ O(V)	E ≈ O(V²)
Examples	Road networks, social graphs, trees	Complete graphs, fully connected networks
Best representation	Adjacency List — O(V + E) space	Adjacency Matrix — O(1) edge lookup
Dijkstra complexity	O((V+E) log V) ≈ O(V log V)	O((V+E) log V) ≈ O(V² log V)
Bellman-Ford	O(V·E) ≈ O(V²) — acceptable	O(V·E) ≈ O(V³) — very slow

Why It Matters for Algorithm Choice

Sparse graphs: Adjacency list + Dijkstra with priority queue is fastest
Dense graphs: Adjacency matrix + simple Dijkstra O(V²) may beat heap-based Dijkstra
Very sparse with negatives: Bellman-Ford O(V·E) ≈ O(V²) — still usable

// Adjacency list (sparse): wastes no space on non-existent edges
Map<Integer, List<int[]>> adjList = new HashMap<>();   // O(V + E) space

// Adjacency matrix (dense): O(1) edge lookup at cost of O(V²) space
int[][] adjMatrix = new int[V][V];   // adjMatrix[u][v] = weight, 0 if no edge

Dynamic Programming

Advanced · 12 min read

Dynamic Programming (DP) solves problems by breaking them into overlapping subproblems and storing results to avoid recomputation. It's applicable when the problem has optimal substructure (optimal solution built from optimal sub-solutions).

Two Approaches

Top-Down (Memoization) — recursive, store results in a map/array
Bottom-Up (Tabulation) — iterative, fill a DP table from smallest subproblem up

Classic 1 — Coin Change

// Minimum coins to make amount.  coins=[1,5,10], amount=11 → 2 (10+1)
int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);   // fill with "impossible" sentinel
    dp[0] = 0;                       // base: 0 coins needed for amount 0
    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (coin <= a)
                dp[a] = Math.min(dp[a], dp[a - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Classic 2 — 0/1 Knapsack

// Max value fitting in knapsack of capacity W
int knapsack(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[][] dp = new int[n + 1][W + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w];    // don't take item i
            if (wt[i-1] <= w)
                dp[i][w] = Math.max(dp[i][w], val[i-1] + dp[i-1][w-wt[i-1]]);
        }
    }
    return dp[n][W];
}

Classic 3 — Longest Common Subsequence (LCS)

int lcs(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m+1][n+1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i-1) == b.charAt(j-1))
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}
// lcs("abcde","ace") = 3  (a,c,e)

💡 DP interview checklist: Can I define subproblem? Is there a recurrence relation? What's the base case? Should I go top-down or bottom-up?

Caching & Memoization

Advanced · 7 min read

Caching stores results of expensive computations so they can be reused instantly. Memoization is caching applied specifically to recursive functions — store the result of each unique input on first computation, return it immediately on subsequent calls.

Without Memoization — Exponential Work

// fib(5) call tree WITHOUT memoization:
//           fib(5)
//          /       \
//       fib(4)    fib(3)
//       /    \    /   \
//    fib(3) fib(2) fib(2) fib(1)
// fib(3) called TWICE, fib(2) called THREE times → O(2ⁿ)

With Memoization — Linear Work

Map<Integer, Long> cache = new HashMap<>();

long fib(int n) {
    if (n <= 1) return n;
    if (cache.containsKey(n)) return cache.get(n);  // HIT: return cached
    long result = fib(n-1) + fib(n-2);
    cache.put(n, result);                              // MISS: compute and store
    return result;
}
// Each fib(n) computed exactly once → O(n) time, O(n) space

Memoization vs Tabulation

Property	Memoization (Top-Down)	Tabulation (Bottom-Up)
Direction	Recursion — start at n, go to base case	Iteration — start at base case, go to n
Stack usage	Uses call stack (risk of overflow)	No recursion, no overflow risk
Only computes?	Only needed subproblems	All subproblems (even unused ones)
Code style	Easier to write (natural recursion)	More efficient (no function call overhead)

Array-based Memo (Faster than HashMap)

long[] memo = new long[n + 1];
Arrays.fill(memo, -1);   // -1 means "not computed yet"

long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

// Convert to tabulation (bottom-up) for max efficiency:
long[] dp = new long[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
// Space optimised: only keep last 2 values → O(1) space
long a = 0, b = 1;
for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }

💡 Rule: If you see the same recursive call being made multiple times with the same arguments — memoize it. This pattern converts O(2ⁿ) to O(n) instantly.

Heap / Priority Queue

Advanced · 7 min read

A heap is a complete binary tree satisfying the heap property. In a min-heap, every parent is smaller than its children — so the minimum is always at the root (O(1) access). Java's PriorityQueue is a min-heap.

// Min-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5); minHeap.offer(2); minHeap.offer(8); minHeap.offer(1);
minHeap.poll();  // 1 — always removes smallest   O(log n)
minHeap.peek();  // 2 — view min without removing  O(1)

// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(5); maxHeap.offer(2); maxHeap.offer(8);
maxHeap.poll();  // 8 — largest first

Top-K Elements (Most Common Heap Interview Pattern)

// Find top K largest elements — O(n log k)
int[] topK(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();   // size-k min-heap
    for (int n : nums) {
        minHeap.offer(n);
        if (minHeap.size() > k) minHeap.poll();   // evict smallest if over size k
    }
    return minHeap.stream().mapToInt(Integer::intValue).toArray();
}
// [3,1,4,1,5,9,2,6], k=3 → [4,5,6] or [4,6,9] depending on input

Merge K Sorted Lists

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode head : lists) if (head != null) pq.offer(head);
    ListNode dummy = new ListNode(0), cur = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        cur.next = node; cur = cur.next;
        if (node.next != null) pq.offer(node.next);
    }
    return dummy.next;
}
// Time: O(n log k) where n = total nodes, k = number of lists

Greedy Algorithms

Advanced · 6 min read

Greedy algorithms make the locally optimal choice at each step and never reconsider. They work when the problem has the greedy-choice property (local optimal leads to global optimal) and optimal substructure.

Activity Selection Problem

// Pick maximum non-overlapping activities — sort by end time, always pick earliest finish
int maxActivities(int[] start, int[] end) {
    Integer[] idx = IntStream.range(0, start.length).boxed().toArray(Integer[]::new);
    Arrays.sort(idx, (a, b) -> end[a] - end[b]);  // sort by end time
    int count = 1, lastEnd = end[idx[0]];
    for (int i = 1; i < idx.length; i++) {
        if (start[idx[i]] >= lastEnd) {
            count++;
            lastEnd = end[idx[i]];
        }
    }
    return count;
}

Classic Greedy Problems

Problem	Greedy Choice
Activity Selection	Always pick activity with earliest end time
Fractional Knapsack	Always take highest value/weight ratio first
Huffman Coding	Merge two least-frequent nodes first
Jump Game	Track maximum reachable index, update greedily
Dijkstra's Algorithm	Always expand lowest-cost unvisited node
Prim's / Kruskal's MST	Always pick minimum weight edge

⚠️ Greedy doesn't always work. For 0/1 Knapsack (can't take fractions), greedy fails — use Dynamic Programming. If in doubt: prove greedy with an exchange argument, or use DP.