Data Structures & Algorithms
35 Real Interview Questions

A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently. Different problems need different structures because there is no single "best" structure — each has trade-offs:

• Array — O(1) indexed access, but expensive to insert in the middle
• Hash Table — O(1) key lookup, but no ordering
• Queue — FIFO order guaranteed, but no random access
• Tree — hierarchical relationships, O(log n) ordered operations

The right data structure can turn an O(n²) solution into an O(n log n) or even O(n) solution. Choosing poorly is often why code is slow in production.

Use arrays when: you need frequent random access by index, size is known and fixed, cache performance matters (numerical processing, image data).

Use linked lists when: you need frequent insertion/deletion at the head or middle (given a pointer), size is unpredictable, or you're building other structures (queue, deque, adjacency list).

Singly Linked List: each node has data + one next pointer. Forward traversal only. Memory efficient.

Doubly Linked List: each node has data + prev + next. Bidirectional traversal. O(1) deletion given a node (no need to traverse to find predecessor). Extra memory per node. Used in: browser history, LRU cache implementation.

Circular Linked List: the last node's next points back to the head (for singly) or the head's prev points to the last node (for doubly). Used in: round-robin scheduling, circular buffers, multiplayer game turn management.

The idea: change each node's next pointer to point to its predecessor. Maintain three pointers to avoid losing reference to the rest of the list.

// Java — Iterative reversal
Node reverse(Node head) {
    Node prev = null;
    Node curr = head;
    Node next = null;

    while (curr != null) {
        next = curr.next;    // 1. Save the next node
        curr.next = prev;    // 2. Reverse the pointer
        prev = curr;         // 3. Advance prev
        curr = next;         // 4. Advance curr
    }
    return prev; // prev is now the new head
}

// Time: O(n)  |  Space: O(1)

Trace through [1 → 2 → 3 → null]:

Step 1: prev=null, curr=1. next=2, 1.next=null, prev=1, curr=2.
Step 2: prev=1, curr=2. next=3, 2.next=1, prev=2, curr=3.
Step 3: prev=2, curr=3. next=null, 3.next=2, prev=3, curr=null.
Return prev=3 → new list: [3 → 2 → 1 → null] ✓

Floyd's "Tortoise and Hare" algorithm: use two pointers — slow moves 1 step per iteration, fast moves 2 steps. If there's a cycle, they will eventually meet. If fast reaches null, no cycle.

// Java — Detect cycle
boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;        // move 1 step
        fast = fast.next.next;   // move 2 steps
        if (slow == fast) return true;  // they met → cycle
    }
    return false;
}
// Time: O(n)  |  Space: O(1)

Why do they always meet if a cycle exists? Because fast gains on slow at exactly 1 step per iteration. If they're k steps apart in the cycle, they'll meet in k more iterations.

Finding the cycle start (bonus): after they meet, reset one pointer to head. Move both one step at a time. Where they meet again = the cycle start node.

The same two-pointer technique: slow moves 1 step, fast moves 2. When fast reaches the end, slow is at the middle.

// Java — Find middle node
Node findMiddle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow; // middle node
}
// Time: O(n)  |  Space: O(1)

For even-length lists [1,2,3,4]: this returns node 3 (the second middle). If you need the first middle (node 2), change the condition to fast.next != null && fast.next.next != null.

This is used in Merge Sort on linked lists — find the middle, split the list, sort each half, merge.

Sorted Array: Finding the insertion position = O(log n) via binary search. But shifting elements to make room = O(n). Total: O(n). The shift dominates.

Sorted Linked List: Finding the correct position by traversing = O(n) (can't binary search a linked list — no random access). The actual insertion after finding the position = O(1). Total: O(n). Both are O(n), but for different reasons.

Approach 1 — HashSet (Most Common):

// O(n) time, O(n) space
List<Integer> findDuplicates(int[] arr) {
    Set<Integer> seen = new HashSet<>();
    List<Integer> dupes = new ArrayList<>();
    for (int x : arr) {
        if (!seen.add(x)) dupes.add(x); // add() returns false if already present
    }
    return dupes;
}

Approach 2 — Sort first (no extra space):

// O(n log n) time, O(1) extra space
Arrays.sort(arr);
for (int i = 0; i < arr.length - 1; i++) {
    if (arr[i] == arr[i+1]) System.out.println(arr[i] + " is a duplicate");
}

Approach 3 — Index marking (if values are 1..n):

// O(n) time, O(1) extra space — only works when values are in [1, n]
for (int i = 0; i < arr.length; i++) {
    int idx = Math.abs(arr[i]) - 1;
    if (arr[idx] < 0) System.out.println(idx + 1 + " is a duplicate");
    else arr[idx] = -arr[idx]; // mark as visited by negating
}

Using two pointers that traverse data at different speeds or from different ends — often converts O(n²) naive solutions into O(n).

Example 1 — Check if a string is a palindrome:

// O(n) time, O(1) space
boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}

Example 2 — Two-Sum in a sorted array:

// Find two numbers that sum to target in a sorted array
// O(n) time, O(1) space
int[] twoSum(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;   // need larger sum
        else right--;                    // need smaller sum
    }
    return new int[]{};
}

Stack (LIFO — Last In, First Out): think of a stack of plates. The last plate placed on top is the first one removed. Operations: push (add to top), pop (remove from top), peek/top (see top without removing). All O(1).

Real-world uses of Stack:

• Function call stack (recursion management)
• Undo/redo operations in editors
• Browser back button navigation
• Balanced parentheses checker
• Expression evaluation (infix → postfix conversion)
• DFS graph traversal (iterative version)

Queue (FIFO — First In, First Out): think of a line at a ticket counter. The first person in line is served first. Operations: enqueue (add to rear), dequeue (remove from front), peek/front (see front without removing). All O(1).

Real-world uses of Queue:

• CPU process scheduling (Ready Queue)
• BFS graph traversal
• Print spoolers (printer queue)
• Producer-consumer systems
• Request handling in web servers
• Breadth-first search in AI pathfinding

Problem with a simple array-based queue: After several enqueue/dequeue operations, the front pointer moves forward, leaving empty slots at the beginning. Even if the queue has space at the front, you can't use it — the array appears "full" when it isn't. This is called false overflow.

Circular Queue solution: Treat the array as circular using modular arithmetic. When rear reaches the end, it wraps around to position 0 if there's free space there.

// Key operations
enqueue(x):
    if (size == capacity) → OVERFLOW
    rear = (rear + 1) % capacity
    arr[rear] = x
    size++

dequeue():
    if (size == 0) → UNDERFLOW
    int val = arr[front]
    front = (front + 1) % capacity
    size--
    return val

Used in: real-time OS scheduling, audio/video streaming buffers (ring buffers), hardware interrupt handling queues.

A priority queue dequeues elements based on priority rather than insertion order — the highest (or lowest) priority element is always served first, regardless of when it was inserted.

Naïve implementations:

• Sorted array: insert O(n), remove max O(1) → too slow for inserts
• Unsorted array: insert O(1), remove max O(n) → too slow for removes

Heap implementation (standard): insert O(log n), remove max/min O(log n), peek O(1). The best trade-off.

In Java: PriorityQueue<Integer> pq = new PriorityQueue<>(); — min-heap by default. For max-heap: new PriorityQueue<>(Collections.reverseOrder())

Real-world uses: Dijkstra's shortest path algorithm, OS process scheduling, A* pathfinding in games, Huffman encoding for data compression, hospital emergency triage systems.

Binary Tree: each node has at most 2 children (left and right). No ordering constraint. A general-purpose hierarchical structure.

Binary Search Tree (BST): a binary tree with the additional ordering property: for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering enables efficient search.

When does a BST degrade to O(n)? When elements are inserted in sorted order (1, 2, 3, 4, 5...) — the tree becomes a right-skewed linked list. Solution: self-balancing BSTs (AVL tree, Red-Black tree) maintain O(log n) in all cases.

Key BST property: an inorder traversal (Left → Root → Right) of a BST produces elements in sorted ascending order. This is how you verify if a tree is a valid BST.

For the tree:     1
                     /  \
                 2    3
               /  \
            4    5

// Inorder — Recursive
void inorder(Node root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

// Level-order — Iterative (uses Queue)
void levelOrder(Node root) {
    if (root == null) return;
    Queue<Node> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        Node node = q.poll();
        System.out.print(node.val + " ");
        if (node.left != null)  q.offer(node.left);
        if (node.right != null) q.offer(node.right);
    }
}

A balanced tree is one where the height difference between the left and right subtrees of any node is bounded — specifically ≤1 for AVL trees. The height of a balanced tree with n nodes is O(log n).

Why it matters: tree operations (search, insert, delete) are O(height). In a balanced tree: height = O(log n) → operations are O(log n). In an unbalanced (skewed) tree: height = O(n) → operations degrade to O(n) — same as a linked list.

Self-balancing BSTs:

• AVL Tree: strictly balanced (height diff ≤1). More rotations on insert/delete. Faster searches. Good for read-heavy workloads.
• Red-Black Tree: loosely balanced (approximately balanced). Fewer rotations. Used in: Java TreeMap/TreeSet, C++ std::map, Linux process scheduler.

B-Tree (used in databases): n-ary balanced tree optimized for disk storage. Each node holds multiple keys, minimizing disk I/O. MySQL's InnoDB uses B+ trees for indexes.

A heap is a complete binary tree (all levels filled except possibly the last, filled left to right) that satisfies the heap property:

• Max-heap: every parent ≥ its children. Root = maximum element.
• Min-heap: every parent ≤ its children. Root = minimum element.

Array representation (no wasted space):

Key operations:

• Peek (get max/min): O(1) — always at index 0
• Insert (heapify up): O(log n) — add at end, bubble up
• Remove max/min (heapify down): O(log n) — swap root with last, remove last, sink root down
• Build heap from array: O(n) — not O(n log n) as you might expect

Uses: Priority Queue implementation, Heap Sort, Dijkstra's algorithm, finding the k-th largest/smallest element in O(n log k), median maintenance with two heaps.

A trie is a tree-like data structure where each path from root to a node represents a prefix of a string. Each node has up to 26 children (for lowercase English letters). The end of a word is marked with a boolean flag isEnd.

// Trie Node
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

// Insert "cat" into trie:
// root → c → a → t (isEnd=true)

Operations (all O(m) where m = word length):

• Insert: traverse/create nodes for each character, mark end
• Search: traverse nodes; return true only if last node has isEnd=true
• StartsWith: traverse nodes; return true if path exists (don't need isEnd)

Use when: autocomplete, spell-checking, prefix matching, IP routing tables, word games (Boggle, Scrabble), dictionary search. A trie is faster than a hash table for prefix queries.

Trade-off: fast O(m) lookups but high memory usage — each node can have up to 26 child pointers. For memory efficiency: use HashMap for children instead of fixed array, or use a Ternary Search Tree.

A graph G = (V, E) consists of a set of vertices (nodes) V and a set of edges E connecting pairs of vertices.

Types:

• Directed (Digraph): edges have direction (A→B ≠ B→A). Example: web pages + hyperlinks, Twitter follow graph.
• Undirected: edges are bidirectional (A-B = B-A). Example: Facebook friendship graph, road map.
• Weighted: edges have numerical weights. Example: road distances, network bandwidth.
• Unweighted: edges have no weight (or weight = 1).

Representation 1 — Adjacency Matrix: V×V 2D array. matrix[i][j] = 1 if edge exists. Space: O(V²). Edge lookup: O(1). Iteration over neighbors: O(V). Best for dense graphs.

Representation 2 — Adjacency List: array of lists where list[i] contains all neighbors of vertex i. Space: O(V+E). Neighbor iteration: O(degree). Best for sparse graphs (most real-world graphs).

// Adjacency List — Java
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
// Add edge 0-1 (undirected)
graph.get(0).add(1);
graph.get(1).add(0);

// BFS — Iterative (uses Queue)
void bfs(List<List<Integer>> graph, int start) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> q = new LinkedList<>();
    visited[start] = true;
    q.offer(start);
    while (!q.isEmpty()) {
        int node = q.poll();
        System.out.print(node + " ");
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.offer(neighbor);
            }
        }
    }
}

// DFS — Recursive
void dfs(List<List<Integer>> graph, boolean[] visited, int node) {
    visited[node] = true;
    System.out.print(node + " ");
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) dfs(graph, visited, neighbor);
    }
}

Use BFS when: shortest path in unweighted graph, finding all nodes within a distance, level-order tree traversal, connected components.

Use DFS when: topological sorting, cycle detection in directed graphs, finding strongly connected components, backtracking problems, maze/path solving.

HashMap (Java) / dict (Python):

• Hash-based — computes a hash for each key
• O(1) average for get, put, remove
• Keys are unordered — iteration order not guaranteed (Java) or insertion order preserved (Python 3.7+)
• Use when: you need fast lookup by key and don't care about ordering

TreeMap (Java) / SortedDict:

• Red-Black tree based
• O(log n) for all operations
• Keys are sorted — always in ascending order
• Supports range queries: subMap(from, to), floorKey(k), ceilingKey(k)
• Use when: you need keys in sorted order, or need range-based queries

// Java example
// HashMap — O(1) lookup, unordered
Map<String, Integer> freq = new HashMap<>();
freq.put("apple", 3);
freq.get("apple"); // O(1)

// TreeMap — O(log n), sorted by key
Map<String, Integer> sorted = new TreeMap<>();
sorted.put("banana", 1);
sorted.put("apple", 3);
// Iteration: apple, banana (alphabetical)
sorted.firstKey();  // "apple"
sorted.lastKey();   // "banana"

A hash table (hash map) maps keys to values using a hash function that converts a key into an array index. This enables O(1) average-case lookup, insert, and delete.

Hash function: index = hashCode(key) % arrayCapacity. A good hash function distributes keys uniformly to minimize collisions.

Collision: two different keys hash to the same index. Two standard solutions:

1. Chaining (Java HashMap uses this): each array slot holds a linked list (or balanced tree in Java 8+ when list gets long). Multiple keys at the same index are chained together. Worst case: all keys collide → O(n) operations. Average: O(1) with a good hash function.

2. Open Addressing (linear probing, quadratic probing, double hashing): when a collision occurs, probe for the next empty slot in the array itself. Memory-compact but performance degrades badly with high load factor.

Load Factor: n/capacity (number of entries / array size). Java's HashMap rehashes when load factor > 0.75 — doubles the array and re-inserts all entries (amortized O(1) for inserts).

// How Java's HashMap works internally (simplified)
// Stores: array of "buckets" (initially 16 slots)
// Each bucket = linked list (or tree if >8 entries)
// put("key", value):
//   1. Compute hashCode("key")
//   2. index = hashCode & (capacity-1)  // bitwise for power-of-2 sizes
//   3. If bucket empty → store directly
//   4. If collision → append to linked list, check for equals()
//   5. If load factor exceeded → rehash (double capacity)

// Binary Search — Iterative (preferred)
int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // avoids integer overflow
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // not found
}
// Each iteration halves the search space
// 10 steps can search 2^10 = 1,024 elements
// 20 steps can search 2^20 = 1,048,576 elements

Problem: Given an array and a target, find two numbers that add up to the target. Return their indices.

Approach 1 — Brute Force: O(n²) time, O(1) space

// Check every pair
for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        if (arr[i] + arr[j] == target) return new int[]{i, j};

Approach 2 — HashMap: O(n) time, O(n) space ← Best for unsorted

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement))
            return new int[]{map.get(complement), i};
        map.put(nums[i], i);
    }
    return new int[]{};
}
// For each element x, check if (target - x) is already in the map

Approach 3 — Two Pointers: O(n log n) time, O(1) space ← Best if sorted

// Sort the array first, then two pointers
Arrays.sort(nums); // O(n log n)
int left = 0, right = nums.length - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return; // found
    else if (sum < target) left++;
    else right--;
}

A sliding window maintains a contiguous "window" over an array/string, expanding and shrinking it to satisfy a condition. It converts many O(n²) problems into O(n) by avoiding recomputation.

Fixed-size window — Maximum sum of subarray of size k:

int maxSumSubarray(int[] arr, int k) {
    int windowSum = 0;
    // Compute sum of first window
    for (int i = 0; i < k; i++) windowSum += arr[i];
    int maxSum = windowSum;

    // Slide window: add next element, remove first element
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k]; // add new, drop old
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}
// O(n) time, O(1) space — vs O(n*k) for brute force

Variable-size window — Longest substring without repeating characters:

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int maxLen = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (lastSeen.containsKey(c) && lastSeen.get(c) >= left)
            left = lastSeen.get(c) + 1; // shrink window
        lastSeen.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen; // O(n) time, O(k) space where k = alphabet size
}

// Merge Sort — Divide and Conquer
void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

void merge(int[] arr, int l, int m, int r) {
    int[] temp = new int[r - l + 1];
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r)
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    while (i <= m) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    for (int x = 0; x < temp.length; x++) arr[l + x] = temp[x];
}

Why Quick Sort is faster in practice despite same Big-O: better cache performance (in-place), smaller constant factor, avoidable worst case with randomized pivot. Most modern standard library sorts use introsort (Quick Sort + Heap Sort + Insertion Sort hybrid).

A sort is stable if it preserves the relative order of equal elements — if two elements have the same key, the one that appears first in the input still appears first in the output.

Why it matters: when sorting by multiple criteria. Example: sort employee records first by department, then by name. If you sort by name first (stable sort), then by department (stable sort), the name order within each department is preserved. With an unstable sort, this breaks.

// Example: Sort [(Alice, Engineering), (Bob, Marketing), (Charlie, Engineering)]
// By name: [(Alice, E), (Bob, M), (Charlie, E)]
// Then stable sort by dept: [(Alice, E), (Charlie, E), (Bob, M)]
// Alice comes before Charlie because stable sort preserved their original order
// Unstable sort: Charlie might come before Alice — unpredictable

Stable sorts: Merge Sort ✅, Insertion Sort ✅, Bubble Sort ✅, Tim Sort (Python/Java default) ✅, Counting Sort ✅

Unstable sorts: Quick Sort ❌, Heap Sort ❌, Selection Sort ❌

Recursion is a technique where a function calls itself with a smaller version of the same problem, progressively breaking it down until reaching a trivially solvable case.

Every recursive function has two parts:

• Base case: the terminating condition — the simplest version of the problem where the answer is known directly, requiring no further recursion.
• Recursive case: the function calls itself with a simpler/smaller input, moving toward the base case.

// Factorial — classic recursion
int factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n <= 1) return 1;
    // Recursive case: n! = n × (n-1)!
    return n * factorial(n - 1);
}

// Call stack for factorial(4):
// factorial(4) → 4 * factorial(3)
// factorial(3) → 3 * factorial(2)
// factorial(2) → 2 * factorial(1)
// factorial(1) → 1  ← BASE CASE — unwinds from here

Without the base case: the function calls itself indefinitely — infinite recursion → the call stack fills completely → StackOverflowError (Java) / RecursionError (Python).

Each recursive call uses a stack frame (stores return address, local variables, parameters). Java's default stack size allows ~500–10,000 frames depending on frame size. Deep recursion on large inputs can overflow even with a correct base case.

// Fibonacci — Recursion vs Iteration
// Recursive: O(2^n) time — exponential! (without memoization)
int fibR(int n) { return n <= 1 ? n : fibR(n-1) + fibR(n-2); }

// Iterative: O(n) time, O(1) space — much better
int fibI(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) { int c = a+b; a = b; b = c; }
    return b;
}

Rule of thumb: Use recursion when it makes the solution significantly cleaner and the depth is bounded (e.g., tree traversal — depth is O(log n) for balanced trees). Use iteration for performance-critical code and large inputs where stack depth matters.

Divide and Conquer solves a problem by:

1. Divide: split the problem into smaller subproblems of the same type
2. Conquer: solve each subproblem recursively (base case: subproblem small enough to solve directly)
3. Combine: merge the solutions of subproblems into the solution of the original

Classic example — Merge Sort:

• Divide: split array in half
• Conquer: sort each half recursively
• Combine: merge two sorted halves into one sorted array

Other D&C algorithms: Quick Sort, Binary Search, Strassen's Matrix Multiplication, Closest Pair of Points, Karatsuba Integer Multiplication.

Time complexity (Master Theorem): For T(n) = aT(n/b) + f(n): T(n) = O(n log n) for Merge Sort (a=2, b=2, f(n)=O(n)).

Dynamic Programming (DP) solves optimization problems by breaking them into overlapping subproblems, solving each exactly once, storing the result, and using it when the same subproblem appears again.

Two necessary conditions:

• Optimal Substructure: the optimal solution to the problem can be constructed from optimal solutions of its subproblems. "The best way to solve the big problem comes from the best ways to solve the pieces."
• Overlapping Subproblems: the same subproblems are solved multiple times during the recursive computation. If subproblems never repeat, D&C suffices — no need for DP.

Fibonacci — why DP helps:

// Naive recursion: O(2^n) — subproblems repeat massively
fib(5) calls fib(4) AND fib(3)
fib(4) calls fib(3) AND fib(2)  ← fib(3) computed TWICE
fib(3) calls fib(2) AND fib(1)  ← fib(2) computed MULTIPLE TIMES

// Memoized (top-down DP): O(n) — compute each subproblem once
int[] memo = new int[n+1];
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n]; // already computed
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

// Tabulation (bottom-up DP): O(n) time, O(1) space
int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) { int c = a+b; a = b; b = c; }
    return b;
}

// Climbing Stairs — dp[i] = ways to climb i stairs (1 or 2 at a time)

// Tabulation (bottom-up) — O(n) time, O(n) space
int climbStairs(int n) {
    int[] dp = new int[n+1];
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

// Space-optimized — O(n) time, O(1) space
int climbStairs(int n) {
    int a = 1, b = 1;
    for (int i = 2; i <= n; i++) { int c = a+b; a = b; b = c; }
    return b;
}

Greedy: at each step, make the locally optimal choice (the best choice right now, without reconsidering past decisions). Fast — O(n) or O(n log n) typically. But only correct when the greedy choice always leads to a globally optimal solution.

Dynamic Programming: considers all possible choices at each step via subproblems. Always correct for problems with optimal substructure. Slower — typically O(n²) or O(n·W) space and time.

How to decide: Ask "If I make the greedy choice, will it always be part of an optimal solution?" If yes and you can prove it, use greedy. If not sure or choices depend on future decisions, use DP.

Backtracking explores a decision tree of choices. At each step, make a choice and recurse. If the choice leads to a dead end (constraint violated), undo the choice (backtrack) and try the next option.

Template:

void backtrack(State current, List<State> result) {
    // Base case: found a valid complete solution
    if (isSolution(current)) {
        result.add(copy(current));
        return;
    }
    // Try all choices at this step
    for (Choice c : getChoices(current)) {
        if (isValid(current, c)) {
            makeChoice(current, c);     // 1. Make the choice
            backtrack(current, result); // 2. Recurse
            undoChoice(current, c);     // 3. Undo (backtrack)
        }
    }
}

Example — Generate all subsets of [1, 2, 3]:

void subsets(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
    result.add(new ArrayList<>(current)); // every state is a valid subset
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);            // choose nums[i]
        subsets(nums, i+1, current, result); // recurse
        current.remove(current.size()-1); // unchoose (backtrack)
    }
}
// For [1,2,3]: generates [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]

Classic backtracking problems: N-Queens, Sudoku solver, all permutations, all subsets, word search in a grid, combination sum, letter combinations of phone number digits.

The fundamental trade-off in algorithm design: you can often trade more memory for faster computation, or vice versa.

Classic example — Fibonacci:

Two-Sum example:

• Brute force (nested loops): O(n²) time, O(1) space
• HashMap approach: O(n) time, O(n) space
• Sorted + two pointers: O(n log n) time, O(1) space

Caching/memoization: almost every DP optimization trades O(n) or O(n²) space to reduce exponential time to polynomial.

When space is the constraint: use the iterative, space-optimized approach (keep only what's needed). When time is the constraint: trade memory for speed via memoization, precomputation, or lookup tables.

A palindrome reads the same forward and backward. "racecar", "madam", "level" are palindromes.

Approach 1 — Two Pointers (Optimal):

// O(n) time, O(1) space — most efficient
boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return false;
        left++;
        right--;
    }
    return true; // all characters matched
}

Approach 2 — Reverse and Compare:

// O(n) time, O(n) space — simple but uses extra memory
boolean isPalindrome(String s) {
    String reversed = new StringBuilder(s).reverse().toString();
    return s.equals(reversed);
}

Approach 3 — Recursive:

// O(n) time, O(n) stack space
boolean isPalindrome(String s, int left, int right) {
    if (left >= right) return true; // base case
    if (s.charAt(left) != s.charAt(right)) return false;
    return isPalindrome(s, left + 1, right - 1);
}

Extension — Case-insensitive, alphanumeric only (LeetCode 125):

// "A man, a plan, a canal: Panama" → true
boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
            return false;
        left++; right--;
    }
    return true;
}

Check palindrome number (no string conversion):

// 121 → true, -121 → false, 10 → false
boolean isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int reversed = 0;
    while (x > reversed) {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }
    // x == reversed (odd length) or x == reversed/10 (even length)
    return x == reversed || x == reversed / 10;
}