Data Structures and Algorithms Guide: Complete Reference

Why DSA Matters

Data Structures and Algorithms form the foundation of computer science. Mastering DSA is essential for coding interviews and building efficient software. In every Amazon technical interview, you will be evaluated on your ability to identify the right data structure and algorithm for a problem. Understanding trade-offs between time and space complexity is what separates strong candidates from average ones.

When you encounter a problem like "find the kth largest element in a stream," your ability to immediately recognize that a min-heap of size k solves this in O(n log k) time is what interviewers are testing. DSA knowledge is not about memorizing solutions — it is about building intuition for problem decomposition and recognizing patterns across hundreds of problems.

Data Structures

Arrays

What: Contiguous memory storage where each element is accessible by its index. Arrays are the most fundamental data structure and the building block for more complex structures like heaps, hash tables, and matrices.

How they work: When you create an array of size n, the system allocates a single contiguous block of memory. Element arr[i] is stored at base_address + (i * element_size). This is why array access is O(1) — no traversal needed, just arithmetic.

Operations:

Real-world applications: Image processing (pixel arrays), database row storage, lookup tables, implementing stacks and queues, and matrix operations in machine learning.

Code walkthrough — Two Sum using a hash map for O(n):

```java
public 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[] {};
}
```

Walkthrough: For each element, we compute the complement (target - current). We check the hash map for the complement in O(1). If found, we return both indices. If not, we store the current element and its index. The array is traversed once, giving us O(n) time and O(n) space.

Linked Lists

What: Nodes with pointers where each node stores data and a reference to the next node. Unlike arrays, linked lists do not require contiguous memory — nodes can be scattered across the heap.

How they work: Each Node contains data and a "next" pointer. To access the 5th element, you must traverse from the head through 4 nodes. This makes linked lists poor for random access but excellent for frequent insertions and deletions.

```java
class Node {
int data;
Node next;
Node(int data) { this.data = data; }
}
```

Operations:

Real-world applications: Implementation of stacks and queues, undo functionality in text editors, adjacency lists for graphs, polynomial arithmetic, and music playlists where songs are played sequentially.

Code walkthrough — Reverse a linked list iteratively:

```java
public Node reverseList(Node head) {
Node prev = null;
Node curr = head;
while (curr != null) {
Node next = curr.next; // Save next
curr.next = prev; // Reverse pointer
prev = curr; // Move prev forward
curr = next; // Move curr forward
}
return prev;
}
```

Walkthrough: We maintain two pointers — prev (starts null) and curr (starts at head). At each step, we save the next node, reverse the current node's pointer to point backward, then advance both pointers. When curr becomes null, prev points to the new head. Time: O(n), Space: O(1).

Stacks

What: LIFO (Last In, First Out) structure. Think of a stack of plates — you can only add or remove from the top.

```java
Stack stack = new Stack<>();
stack.push(1); // Add to top
stack.pop(); // Remove from top
stack.peek(); // View top without removing
```

Operations:

Real-world applications: Undo/redo in text editors, browser back button, function call stack during recursion, expression evaluation, syntax parsing, and depth-first search on graphs.

Code walkthrough — Valid Parentheses:

```java
public boolean isValid(String s) {
Stack stack = new Stack<>();
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();
}
```

Walkthrough: Push opening brackets onto the stack. When you encounter a closing bracket, check if the top of the stack is the matching opening bracket. If not, or if the stack is empty, the string is invalid. At the end, the stack must be empty (all opening brackets were matched). Time: O(n), Space: O(n).

Queues

What: FIFO (First In, First Out) structure. Think of a line at a store — first person in line is the first to be served.

```java
Queue queue = new LinkedList<>();
queue.offer(1); // Add to back
queue.poll(); // Remove from front
queue.peek(); // View front without removing
```

Operations:

Real-world applications: BFS traversal, task scheduling in operating systems, print queue management, message queues in distributed systems, and buffering for streaming data.

Priority Queue variant: A priority queue serves elements based on priority rather than insertion order. Implemented with a heap, it gives O(log n) insertion and O(log n) extraction of the minimum or maximum.

```java
// Min-heap priority queue
PriorityQueue minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
int smallest = minHeap.poll(); // Returns 1
```

Hash Maps

What: Key-value pairs with O(1) average-case lookup, insertion, and deletion. Hash maps use a hash function to compute an index into an array of buckets or slots.

How they work: When you call map.put(key, value), the hash function computes hash(key) % capacity to find the bucket index. Collisions (two keys mapping to the same bucket) are handled via chaining (linked list at each bucket) or open addressing. Load factor (elements / capacity) determines when to resize.

```java
Map<String, Integer> map = new HashMap<>();
map.put("key", 1); // O(1) average
map.get("key"); // O(1) average
map.containsKey("key"); // O(1) average
map.remove("key"); // O(1) average
```

Operations:

Worst case O(n) happens when all keys hash to the same bucket, degrading to a linked list traversal. With a good hash function and low load factor, this is extremely rare.

Real-world applications: Caching (LRU cache), counting character frequencies, detecting duplicates, implementing adjacency lists for graphs, database indexing, and DNS resolution.

Code walkthrough — Group Anagrams:

```java
public List<List> groupAnagrams(String[] strs) {
Map<String, List> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
```

Walkthrough: For each string, sort its characters to create a canonical key. Anagrams produce the same sorted string. Group all strings sharing the same key. Time: O(n * k log k) where k is the max string length. Space: O(n * k).

Trees

What: Hierarchical data structure with a root node and child nodes forming a parent-child relationship. Trees are recursive — each subtree is itself a tree.

```java
class TreeNode {
int val;
TreeNode left, right;
}
```

Types and when to use them:

• Binary Tree: At most 2 children. Used in expression parsing, Huffman coding, and decision trees.
• BST (Binary Search Tree): Left child < Parent < Right child. Enables O(log n) search, insert, and delete. Used in database indexing and ordered maps.
• AVL Tree: Self-balancing BST where the height difference between left and right subtrees is at most 1. Guarantees O(log n) operations. Used in databases requiring strict balance.
• Red-Black Tree: Self-balancing BST with less strict balancing than AVL. Slightly faster insertions and deletions. Used in Java's TreeMap, C++ std::map, and Linux kernel.
• Trie (Prefix Tree): Each node represents a character. Used for autocomplete, spell checking, and IP routing.

Code walkthrough — Maximum Depth of Binary Tree:

```java
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
```

Walkthrough: This is a textbook recursive problem. The depth of a null tree is 0. For any non-null tree, the depth is 1 plus the maximum depth of its two subtrees. Time: O(n) — we visit each node once. Space: O(h) where h is the height (due to recursion stack).

In-order traversal of BST gives sorted order — this is a critical property used to validate BSTs and extract sorted data.

```java
public void inOrder(TreeNode root, List result) {
if (root == null) return;
inOrder(root.left, result);
result.add(root.val);
inOrder(root.right, result);
}
```

Graphs

What: Nodes (vertices) connected by edges. Graphs model relationships — social networks, road maps, dependency graphs, and more.

Representations:
```java
// Adjacency Matrix: O(1) edge lookup, O(V^2) space
int[][] matrix = new int[n][n];
matrix[u][v] = 1; // Edge from u to v

// Adjacency List: O(degree) edge lookup, O(V + E) space
Map<Integer, List> graph = new HashMap<>();
graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
```

When to use which: Adjacency matrix is better for dense graphs (E close to V^2) and when you need O(1) edge existence checks. Adjacency list is better for sparse graphs (E close to V) and saves memory.

Traversal — DFS vs BFS:

```java
// DFS using stack
void dfs(Map<Integer, List> graph, int start) {
Set visited = new HashSet<>();
Stack stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (visited.contains(node)) continue;
visited.add(node);
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) stack.push(neighbor);
}
}
}

// BFS using queue
void bfs(Map<Integer, List> graph, int start) {
Set visited = new HashSet<>();
Queue queue = new LinkedList<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : graph.get(node)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}
```

Key insight: DFS uses a stack (or recursion) and explores as deep as possible before backtracking. BFS uses a queue and explores all neighbors at the current depth before moving deeper. For shortest path in unweighted graphs, BFS is the correct choice.

Real-world applications: Social network friend recommendations, GPS navigation (shortest route), web page crawling, detecting cycles in dependencies, and solving puzzles like mazes.

Algorithms

Sorting

When to choose which:

• Nearly sorted data: Insertion sort (O(n) best case)
• Guaranteed O(n log n): Merge sort or heap sort
• Average case performance: Quick sort (fastest in practice)
• Memory constrained: Heap sort (O(1) extra space)
• Stability required: Merge sort or insertion sort

Searching

Binary Search (Sorted Array) — eliminates half the search space each step:

```java
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Avoids overflow
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
```

Complexity: O(log n) time, O(1) space. For an array of 1 billion elements, binary search finds the target in at most 30 comparisons.

Binary search variations (critical for interviews):

• Find first/last occurrence of a target
• Find smallest element greater than target
• Search in a rotated sorted array
• Find peak element in a mountain array

Pattern: Binary search on answer space — when the answer is a number in a range, binary search over the range and check feasibility at each mid point.

Graph Algorithms

Dijkstra's Algorithm (Single-Source Shortest Path, non-negative weights):

```java
int[] dijkstra(Map<Integer, List<int[]>> graph, int start, int n) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int node = curr[0], d = curr[1];
if (d > dist[node]) continue; // Stale entry
for (int[] edge : graph.get(node)) {
int next = edge[0], weight = edge[1];
if (dist[node] + weight < dist[next]) {
dist[next] = dist[node] + weight;
pq.offer(new int[]{next, dist[next]});
}
}
}
return dist;
}
```

Complexity: O((V + E) log V) with a binary heap. The "if d > dist[node] continue" check is crucial — it avoids processing stale entries in the priority queue.

When to use which graph algorithm:

• BFS: Shortest path in unweighted graphs, level-order traversal
• Dijkstra: Shortest path with non-negative weights
• Bellman-Ford: Shortest path with negative weights, detects negative cycles
• Floyd-Warshall: All-pairs shortest path, O(V^3)
• Topological Sort: Ordering tasks with dependencies (DFS or Kahn's algorithm)
• Union-Find: Dynamic connectivity, cycle detection in undirected graphs

Algorithm Paradigms

Divide and Conquer

Strategy: Break the problem into independent subproblems, solve each recursively, then combine the solutions.

Template:

1. Base case: solve directly if problem is small enough
2. Divide: split into subproblems
3. Conquer: solve subproblems recursively
4. Combine: merge subproblem solutions

Examples: Merge Sort (divide array, sort halves, merge), Quick Sort (partition around pivot, sort partitions), Binary Search (eliminate half the search space), Maximum Subarray (Kadane's is actually DP, but the divide-and-conquer variant exists).

Complexity: Often yields O(n log n) recurrences solved by the Master Theorem.

Dynamic Programming

Strategy: Solve problems by combining solutions to overlapping subproblems. DP works when a problem has:

1. Optimal substructure: Optimal solution contains optimal solutions to subproblems
2. Overlapping subproblems: Same subproblems are solved repeatedly

Two approaches:

• Top-down (Memoization): Start from the main problem, recursively solve subproblems, cache results
• Bottom-up (Tabulation): Start from the smallest subproblems, build up to the solution

Example — Climbing Stairs (n stairs, take 1 or 2 steps):

```java
// Top-down with memoization
Map<Integer, Integer> memo = new HashMap<>();
public int climbStairs(int n) {
if (n <= 1) return 1;
if (memo.containsKey(n)) return memo.get(n);
int result = climbStairs(n - 1) + climbStairs(n - 2);
memo.put(n, result);
return result;
}

// Bottom-up tabulation
public int climbStairs(int n) {
if (n <= 1) return 1;
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];
}
```

Walkthrough: dp[i] represents the number of ways to reach step i. To reach step i, you could have come from step i-1 (one step) or step i-2 (two steps). So dp[i] = dp[i-1] + dp[i-2]. Time: O(n), Space: O(n) — can be optimized to O(1) since we only need the last two values.

Classic DP problems to know:

• 0/1 Knapsack
• Longest Common Subsequence
• Longest Increasing Subsequence
• Coin Change
• Edit Distance
• Matrix Chain Multiplication

Greedy

Strategy: Make the locally optimal choice at each step, hoping to reach a global optimum. Greedy works when the problem has:

1. Greedy choice property: A local optimal choice leads to a global optimum
2. Optimal substructure: Like DP

Example — Activity Selection (maximum number of non-overlapping activities):

```java
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 0;
int prevEnd = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < prevEnd) {
count++; // Overlap — remove this interval
} else {
prevEnd = intervals[i][1]; // No overlap — keep it
}
}
return count;
}
```

Walkthrough: Sort intervals by end time. Greedily keep the interval with the earliest end time (leaves maximum room for future intervals). If an interval overlaps with the previous one, remove it. Time: O(n log n) for sorting.

When greedy fails: When the problem requires considering future consequences of current choices, greedy is incorrect. Use DP instead. Example: the 0/1 Knapsack cannot be solved greedily by value-to-weight ratio because selecting a high-ratio item might prevent including two smaller items with higher total value.

Backtracking

Strategy: Explore all possible solutions by building candidates incrementally, abandon a candidate as soon as it is determined to be invalid (pruning).

Template:
```java
void backtrack(State state, List choice) {
if (isSolution(state)) {
result.add(new ArrayList<>(choice));
return;
}
for (Candidate c : candidates) {
if (!isValid(state, c)) continue; // Pruning
state.add(c); // Make choice
backtrack(state, choice); // Recurse
state.remove(c); // Undo choice (backtrack)
}
}
```

Example — Generate all permutations of n distinct numbers:

```java
public List<List> permute(int[] nums) {
List<List> result = new ArrayList<>();
backtrack(nums, new ArrayList<>(), new boolean[nums.length], result);
return result;
}

private void backtrack(int[] nums, List path, boolean[] used,
List<List> result) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.add(nums[i]);
backtrack(nums, path, used, result);
path.remove(path.size() - 1);
used[i] = false;
}
}
```

Complexity: O(n * n!) — n! permutations, each takes O(n) to copy. The pruning in other backtracking problems (like N-Queens) dramatically reduces the effective search space.

Common backtracking problems: N-Queens, Sudoku Solver, Word Search, Palindrome Partitioning, Combination Sum.

Common Interview Patterns

Recognizing patterns is the key to solving new problems quickly. Here are the essential patterns every candidate should master:

1. Two Pointers: Use when traversing a sorted array or linked list from both ends. Examples: Two Sum II, Container With Most Water, Trapping Rain Water.
2. Sliding Window: Use for contiguous subarray/substring problems. Examples: Maximum Sum Subarray of Size K, Longest Substring Without Repeating Characters, Minimum Window Substring.
3. Fast & Slow Pointers: Use for cycle detection and finding middle elements. Examples: Linked List Cycle, Happy Number, Middle of Linked List.
4. Merge Intervals: Use when dealing with overlapping ranges. Examples: Merge Intervals, Insert Interval, Meeting Rooms II.
5. Cyclic Sort: Use when dealing with arrays containing numbers in a given range. Examples: Find Missing Number, Find All Duplicates, First Missing Positive.
6. Tree BFS/DFS: Level-order traversal (BFS) or recursive traversal (DFS). Examples: Binary Tree Level Order, Validate BST, Lowest Common Ancestor.
7. Heap / Top-K: Use when finding the kth largest/smallest element. Examples: Kth Largest Element, Top K Frequent Elements, Merge K Sorted Lists.
8. Subsets / Combinations: Use backtracking to enumerate all subsets. Examples: Subsets, Combination Sum, Phone Letter Combinations.
9. Graph Topological Sort: Use for ordering with dependencies. Examples: Course Schedule, Alien Dictionary, Task Scheduler.
10. Union-Find: Use for connected components and cycle detection. Examples: Number of Provinces, Redundant Connection, Accounts Merge.

Practice Roadmap

Phase 1: Foundations (Weeks 1-4)

Week 1-2: Arrays and Strings

• Two Sum, Contains Duplicate, Max Subarray
• Longest Common Prefix, Reverse String
• Rotate Array, Merge Sorted Array
• Product of Array Except Self

Week 3-4: Linked Lists and Hash Maps

• Reverse Linked List, Merge Two Sorted Lists
• Detect Cycle, Remove Nth Node From End
• Group Anagrams, Top K Frequent Elements
• LRU Cache, Valid Anagram

Phase 2: Trees and Graphs (Weeks 5-8)

Week 5-6: Binary Trees

• Maximum Depth, Invert Binary Tree
• Symmetric Tree, Subtree of Another Tree
• Binary Tree Level Order Traversal
• Validate BST, Kth Smallest in BST

Week 7-8: Graphs

• Number of Islands, Clone Graph
• Course Schedule, Pacific Atlantic Water Flow
• Word Ladder, Rotting Oranges
• Network Delay Time (Dijkstra)

Phase 3: Advanced Topics (Weeks 9-12)

Week 9-10: Dynamic Programming

• Climbing Stairs, House Robber
• Coin Change, Longest Increasing Subsequence
• Word Break, Unique Paths
• Edit Distance, Burst Balloons

Week 11-12: Greedy and Backtracking

• Jump Game, Task Scheduler
• N-Queens, Sudoku Solver
• Combination Sum, Permutations
• Word Search, Palindrome Partitioning

Phase 4: Interview Simulation (Weeks 13-16)

• Timed practice sessions (45 minutes per problem)
• Mock interviews with peers
• Review and optimize previously solved problems
• Focus on pattern recognition and explaining your approach
• Practice writing clean, bug-free code on the first attempt

Resources

• DSA Roadmap - Structured learning path
• Practice Problems - Practice problems
• DSA Cheat Sheet - Quick reference
• Coding Patterns - 15 essential patterns
• Java DSA Templates - Java implementations
• System Design - Architecture interviews