Java Data Structures and Algorithms

Arrays
Strings
Linked Lists
Stacks
Queues
Trees
Graphs
Hash Tables
Heaps
Sorting Algorithms
Searching Algorithms
Dynamic Programming

Arrays

When to Use Arrays

Fixed size data collection where you know the maximum number of elements
Random access to elements by index (O(1) access time)
Memory efficiency - elements stored in contiguous memory locations
Mathematical computations involving matrices or vectors

Key Characteristics

Time Complexity:
- Access: O(1)
- Search: O(n)
- Insertion: O(n) - worst case when inserting at beginning
- Deletion: O(n) - worst case when deleting from beginning

Common Use Cases

// 1. Two Pointer Technique
int[] arr = {1, 2, 3, 4, 5};
int left = 0, right = arr.length - 1;

// 2. Sliding Window
int[] nums = {1, 2, 3, 4, 5, 6};
int windowSize = 3;

// 3. Prefix Sum Arrays
int[] prefixSum = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
    prefixSum[i + 1] = prefixSum[i] + arr[i];
}

Best Practices

Use ArrayList when size is dynamic
Use primitive arrays for better performance with large datasets
Consider Arrays.sort() for O(n log n) sorting
Use System.arraycopy() for efficient array copying

Strings

When to Use Strings

Text processing and manipulation
Pattern matching algorithms
Parsing and tokenization
Input validation and formatting

Key Characteristics

Immutable in Java - each modification creates a new object
Time Complexity:
- Access: O(1)
- Concatenation: O(n) for String, O(1) amortized for StringBuilder

String vs StringBuilder vs StringBuffer

// Use String for: Immutable text, few modifications
String str = "Hello";

// Use StringBuilder for: Multiple modifications, single-threaded
StringBuilder sb = new StringBuilder();
sb.append("Hello").append(" World");

// Use StringBuffer for: Multiple modifications, multi-threaded
StringBuffer sbf = new StringBuffer();
sbf.append("Thread-safe");

Common String Algorithms

// KMP Algorithm for pattern matching
public int[] computeLPS(String pattern) {
    int[] lps = new int[pattern.length()];
    int len = 0, i = 1;

    while (i < pattern.length()) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            lps[i++] = ++len;
        } else if (len != 0) {
            len = lps[len - 1];
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

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

Linked Lists

When to Use Linked Lists

Dynamic size requirements
Frequent insertions/deletions at arbitrary positions
Unknown data size at compile time
Implementing other data structures (stacks, queues)

Types and Use Cases

Singly Linked List

class ListNode {
    int val;
    ListNode next;

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

// Use for: Simple sequential access, memory efficiency

Doubly Linked List

class DoublyListNode {
    int val;
    DoublyListNode prev, next;

    DoublyListNode(int val) {
        this.val = val;
    }
}

// Use for: Bidirectional traversal, LRU Cache implementation

Time Complexity

Access/Search: O(n)
Insertion: O(1) if position known, O(n) if searching first
Deletion: O(1) if node reference known, O(n) if searching first

Common Patterns

// Fast and Slow Pointers (Floyd's Cycle Detection)
public 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;
    }
    return false;
}

// Reverse Linked List
public ListNode reverseList(ListNode head) {
    ListNode prev = null, current = head;
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

Stacks

When to Use Stacks

LIFO (Last In, First Out) operations
Recursion simulation and backtracking
Expression evaluation and syntax parsing
Undo operations in applications
Function call management

Implementation Options

// Using ArrayDeque (Recommended)
Deque<Integer> stack = new ArrayDeque<>();

// Using Stack class (Legacy, not recommended)
Stack<Integer> legacyStack = new Stack<>();

// Using ArrayList
List<Integer> listStack = new ArrayList<>();

Common Use Cases

// 1. Balanced Parentheses
public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> map = Map.of(')', '(', '}', '{', ']', '[');

    for (char c : s.toCharArray()) {
        if (map.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

// 2. Next Greater Element
public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 2 * n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() <= nums[i % n]) {
            stack.pop();
        }
        if (i < n) {
            result[i] = stack.isEmpty() ? -1 : stack.peek();
        }
        stack.push(nums[i % n]);
    }
    return result;
}

Time Complexity

Push: O(1)
Pop: O(1)
Peek: O(1)
Search: O(n)

Queues

When to Use Queues

FIFO (First In, First Out) operations
BFS (Breadth-First Search) traversals
Level-order processing in trees
Task scheduling and buffering
Handling requests in web servers

Types and Implementations

Regular Queue

// Using LinkedList
Queue<Integer> queue = new LinkedList<>();

// Using ArrayDeque (Better performance)
Queue<Integer> queue = new ArrayDeque<>();

Priority Queue

// Min Heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Custom Comparator
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

Deque (Double-ended Queue)

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);  // Add to front
deque.addLast(2);   // Add to rear
deque.removeFirst(); // Remove from front
deque.removeLast();  // Remove from rear

Common Patterns

// BFS Template
public void bfs(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            // Process current node

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
}

// Sliding Window Maximum using Deque
public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>();
    int[] result = new int[nums.length - k + 1];

    for (int i = 0; i < nums.length; i++) {
        // Remove indices outside window
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }

        // Remove smaller elements
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }

        deque.offerLast(i);

        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

Trees

When to Use Trees

Hierarchical data representation
Efficient searching with BST (O(log n))
Expression parsing with expression trees
File system representation
Decision making with decision trees

Types of Trees

Binary Tree

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }
}

Binary Search Tree (BST)

Left subtree values < root value
Right subtree values > root value
Inorder traversal gives sorted sequence

// BST Operations
public 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;
}

public TreeNode search(TreeNode root, int val) {
    if (root == null || root.val == val) return root;
    return val < root.val ? search(root.left, val) : search(root.right, val);
}

AVL Tree (Self-balancing BST)

Height difference between left and right subtrees ≤ 1
Automatic rebalancing through rotations
Guaranteed O(log n) operations

Trie (Prefix Tree)

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

class Trie {
    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
}

// Use for: Auto-complete, spell checkers, IP routing

Tree Traversals

// Inorder (Left, Root, Right) - gives sorted order for BST
public void inorder(TreeNode root) {
    if (root != null) {
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
}

// Preorder (Root, Left, Right) - good for copying tree
public void preorder(TreeNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }
}

// Postorder (Left, Right, Root) - good for deletion
public void postorder(TreeNode root) {
    if (root != null) {
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.val + " ");
    }
}

// Level Order (BFS)
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

Graphs

When to Use Graphs

Network modeling (social networks, computer networks)
Path finding algorithms
Dependency resolution
State space exploration
Relationship mapping

Graph Representations

Adjacency List

// Using ArrayList
List<List<Integer>> adjList = new ArrayList<>();

// Using HashMap for weighted graphs
Map<Integer, List<int[]>> graph = new HashMap<>();

// For undirected graph
public void addEdge(int u, int v) {
    adjList.get(u).add(v);
    adjList.get(v).add(u);  // Add both directions
}

Adjacency Matrix

int[][] adjMatrix = new int[n][n];

// For weighted graph
adjMatrix[u][v] = weight;

// Space: O(V²), Good for dense graphs

Graph Traversal Algorithms

DFS (Depth-First Search)

public void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
    visited[node] = true;
    System.out.print(node + " ");

    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

// Iterative DFS
public void dfsIterative(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Deque<Integer> stack = new ArrayDeque<>();

    stack.push(start);

    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (!visited[node]) {
            visited[node] = true;
            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

BFS (Breadth-First Search)

public void bfs(int start, List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new ArrayDeque<>();

    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

Shortest Path Algorithms

Dijkstra's Algorithm

public int[] dijkstra(int start, List<List<int[]>> graph) {
    int n = graph.size();
    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[] current = pq.poll();
        int node = current[0];
        int distance = current[1];

        if (distance > dist[node]) continue;

        for (int[] edge : graph.get(node)) {
            int neighbor = edge[0];
            int weight = edge[1];
            int newDist = dist[node] + weight;

            if (newDist < dist[neighbor]) {
                dist[neighbor] = newDist;
                pq.offer(new int[]{neighbor, newDist});
            }
        }
    }
    return dist;
}

Floyd-Warshall Algorithm

public int[][] floydWarshall(int[][] graph) {
    int n = graph.length;
    int[][] dist = new int[n][n];

    // Initialize distance matrix
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    // Floyd-Warshall
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != Integer.MAX_VALUE &&
                    dist[k][j] != Integer.MAX_VALUE &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    return dist;
}

Topological Sorting

// Kahn's Algorithm (BFS-based)
public List<Integer> topologicalSort(int n, List<List<Integer>> graph) {
    int[] indegree = new int[n];
    for (int i = 0; i < n; i++) {
        for (int neighbor : graph.get(i)) {
            indegree[neighbor]++;
        }
    }

    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
        }
    }

    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);

        for (int neighbor : graph.get(node)) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }

    return result.size() == n ? result : new ArrayList<>(); // Cycle detection
}

Hash Tables

When to Use Hash Tables

Fast lookups - O(1) average case
Frequency counting
Caching and memoization
Set operations (union, intersection)
Grouping related data

Java Hash Table Implementations

// HashMap - Not synchronized, allows null
HashMap<String, Integer> hashMap = new HashMap<>();

// LinkedHashMap - Maintains insertion order
LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();

// TreeMap - Sorted order, O(log n) operations
TreeMap<String, Integer> treeMap = new TreeMap<>();

// ConcurrentHashMap - Thread-safe
ConcurrentHashMap<String, Integer> concurrentHashMap = new ConcurrentHashMap<>();

// HashSet for unique elements
Set<Integer> hashSet = new HashSet<>();

Common Patterns

// Frequency Map
public Map<Character, Integer> getFrequency(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) {
        freq.put(c, freq.getOrDefault(c, 0) + 1);
    }
    return freq;
}

// Two Sum using HashMap
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[0];
}

// Group Anagrams
public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();

    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = String.valueOf(chars);

        map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
    }

    return new ArrayList<>(map.values());
}

Hash Function Design Principles

Uniform distribution of hash codes
Deterministic - same input produces same hash
Fast computation
Avalanche effect - small input changes cause large hash changes

Heaps

When to Use Heaps

Priority-based operations
Finding k-th largest/smallest elements
Median maintenance
Merging k sorted arrays
Task scheduling with priorities

Types of Heaps

Min Heap

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Custom objects
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

Max Heap

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Or using lambda
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

Common Heap Patterns

// K Largest Elements
public int[] findKLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }

    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        result[i] = minHeap.poll();
    }
    return result;
}

// Median Finder
class MedianFinder {
    PriorityQueue<Integer> maxHeap; // Left half
    PriorityQueue<Integer> minHeap; // Right half

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.offer(num);
        } else {
            minHeap.offer(num);
        }

        // Balance heaps
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        } else if (minHeap.size() > maxHeap.size() + 1) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
        return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
    }
}

// Merge K Sorted Lists
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

    for (ListNode list : lists) {
        if (list != null) {
            pq.offer(list);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        current.next = node;
        current = current.next;

        if (node.next != null) {
            pq.offer(node.next);
        }
    }

    return dummy.next;
}

Time Complexity

Insert: O(log n)
Delete Max/Min: O(log n)
Peek Max/Min: O(1)
Build Heap: O(n)

Sorting Algorithms

When to Use Different Sorting Algorithms

Quick Sort

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

private int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

// Use for: General purpose, average O(n log n), in-place
// Avoid for: Already sorted data (worst case O(n²))

Merge Sort

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    System.arraycopy(temp, 0, arr, left, temp.length);
}

// Use for: Stable sorting, guaranteed O(n log n), linked lists
// Space: O(n)

Heap Sort

public void heapSort(int[] arr) {
    int n = arr.length;

    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Extract elements
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

private void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, n, largest);
    }
}

// Use for: Guaranteed O(n log n), in-place, not stable

Counting Sort

public void countingSort(int[] arr, int max) {
    int[] count = new int[max + 1];
    int[] output = new int[arr.length];

    // Count frequencies
    for (int num : arr) {
        count[num]++;
    }

    // Calculate positions
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    // Build output array
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    System.arraycopy(output, 0, arr, 0, arr.length);
}

// Use for: Small range integers, O(n + k) time, stable

Comparison of Sorting Algorithms

Algorithm	Best Case	Average Case	Worst Case	Space	Stable
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Counting Sort	O(n + k)	O(n + k)	O(n + k)	O(k)	Yes
Radix Sort	O(d(n + k))	O(d(n + k))	O(d(n + k))	O(n + k)	Yes

Searching Algorithms

Binary Search

// Iterative Binary Search
public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

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

// Recursive Binary Search
public int binarySearchRecursive(int[] arr, int target, int left, int right) {
    if (left > right) return -1;

    int mid = left + (right - left) / 2;

    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
    return binarySearchRecursive(arr, target, left, mid - 1);
}

// Binary Search Variants
// Find first occurrence
public int findFirst(int[] arr, int target) {
    int left = 0, right = arr.length - 1, result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            result = mid;
            right = mid - 1; // Continue searching left
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

// Find last occurrence
public int findLast(int[] arr, int target) {
    int left = 0, right = arr.length - 1, result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            result = mid;
            left = mid + 1; // Continue searching right
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

// Search in Rotated Sorted Array
public int searchRotated(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) return mid;

        // Left half is sorted
        if (nums[left] <= nums[mid]) {
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // Right half is sorted
        else {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

Linear Search

public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

// Use for: Unsorted arrays, small datasets, simple implementation
// Time: O(n), Space: O(1)

Ternary Search

public int ternarySearch(int[] arr, int target, int left, int right) {
    if (right >= left) {
        int mid1 = left + (right - left) / 3;
        int mid2 = right - (right - left) / 3;

        if (arr[mid1] == target) return mid1;
        if (arr[mid2] == target) return mid2;

        if (target < arr[mid1]) {
            return ternarySearch(arr, target, left, mid1 - 1);
        } else if (target > arr[mid2]) {
            return ternarySearch(arr, target, mid2 + 1, right);
        } else {
            return ternarySearch(arr, target, mid1 + 1, mid2 - 1);
        }
    }
    return -1;
}

// Use for: Finding maximum/minimum in unimodal functions
// Time: O(log₃ n)

Dynamic Programming

When to Use Dynamic Programming

Overlapping subproblems - same subproblems solved multiple times
Optimal substructure - optimal solution contains optimal solutions to subproblems
Optimization problems (min/max)
Counting problems

DP Approaches

Top-Down (Memoization)

// Fibonacci with Memoization
Map<Integer, Integer> memo = new HashMap<>();

public int fibonacciMemo(int n) {
    if (n <= 1) return n;

    if (memo.containsKey(n)) {
        return memo.get(n);
    }

    int result = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
    memo.put(n, result);
    return result;
}

Bottom-Up (Tabulation)

// Fibonacci with Tabulation
public int fibonacciTab(int n) {
    if (n <= 1) return n;

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

// Space Optimized
public int fibonacciOptimized(int n) {
    if (n <= 1) return n;

    int prev2 = 0, prev1 = 1;

    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

Classic DP Problems

0/1 Knapsack

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    values[i - 1] + dp[i - 1][w - weights[i - 1]], // Take item
                    dp[i - 1][w] // Don't take item
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}

// Space Optimized O(capacity)
public int knapsackOptimized(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];

    for (int i = 0; i < weights.length; i++) {
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }

    return dp[capacity];
}

Longest Common Subsequence (LCS)

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

// Space Optimized O(min(m, n))
public int lcsOptimized(String text1, String text2) {
    if (text1.length() < text2.length()) {
        return lcsOptimized(text2, text1);
    }

    int n = text2.length();
    int[] prev = new int[n + 1];
    int[] curr = new int[n + 1];

    for (int i = 1; i <= text1.length(); i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                curr[j] = 1 + prev[j - 1];
            } else {
                curr[j] = Math.max(prev[j], curr[j - 1]);
            }
        }
        int[] temp = prev;
        prev = curr;
        curr = temp;
    }

    return prev[n];
}

Longest Increasing Subsequence (LIS)

// O(n²) DP Solution
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Arrays.stream(dp).max().orElse(0);
}

// O(n log n) Binary Search Solution
public int lengthOfLISOptimal(int[] nums) {
    List<Integer> tails = new ArrayList<>();

    for (int num : nums) {
        int pos = Collections.binarySearch(tails, num);
        if (pos < 0) {
            pos = -(pos + 1);
        }

        if (pos == tails.size()) {
            tails.add(num);
        } else {
            tails.set(pos, num);
        }
    }

    return tails.size();
}

Edit Distance (Levenshtein Distance)

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];

    // Initialize base cases
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1]; // No operation needed
            } else {
                dp[i][j] = 1 + Math.min(
                    Math.min(dp[i - 1][j], dp[i][j - 1]), // Delete or Insert
                    dp[i - 1][j - 1] // Replace
                );
            }
        }
    }

    return dp[m][n];
}

Coin Change

// Minimum coins needed
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

// Number of ways to make amount
public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;

    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

House Robber

public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];

    int prev2 = 0, prev1 = 0;

    for (int num : nums) {
        int current = Math.max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

// House Robber II (Circular)
public int robCircular(int[] nums) {
    if (nums.length == 1) return nums[0];

    // Case 1: Rob houses 0 to n-2
    int max1 = robLinear(nums, 0, nums.length - 2);

    // Case 2: Rob houses 1 to n-1
    int max2 = robLinear(nums, 1, nums.length - 1);

    return Math.max(max1, max2);
}

private int robLinear(int[] nums, int start, int end) {
    int prev2 = 0, prev1 = 0;

    for (int i = start; i <= end; i++) {
        int current = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

DP on Trees

// House Robber III (Binary Tree)
public int robTree(TreeNode root) {
    int[] result = robHelper(root);
    return Math.max(result[0], result[1]);
}

// Returns [rob_root, not_rob_root]
private int[] robHelper(TreeNode node) {
    if (node == null) return new int[]{0, 0};

    int[] left = robHelper(node.left);
    int[] right = robHelper(node.right);

    int robRoot = node.val + left[1] + right[1];
    int notRobRoot = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

    return new int[]{robRoot, notRobRoot};
}

DP Optimization Techniques

Space Optimization

Rolling Array: Use only necessary rows/columns
State Compression: Represent state more efficiently

Time Optimization

Memoization: Cache expensive computations
Bottom-up: Avoid recursion overhead

Algorithm Design Patterns

Two Pointers

// Valid Palindrome
public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;

    while (left < right) {
        while (left < right && !Character.isAlphanumeric(s.charAt(left))) {
            left++;
        }
        while (left < right && !Character.isAlphanumeric(s.charAt(right))) {
            right--;
        }

        if (Character.toLowerCase(s.charAt(left)) !=
            Character.toLowerCase(s.charAt(right))) {
            return false;
        }

        left++;
        right--;
    }

    return true;
}

Sliding Window

// Longest Substring Without Repeating Characters
public int lengthOfLongestSubstring(String s) {
    Set<Character> window = new HashSet<>();
    int left = 0, maxLength = 0;

    for (int right = 0; right < s.length(); right++) {
        while (window.contains(s.charAt(right))) {
            window.remove(s.charAt(left));
            left++;
        }

        window.add(s.charAt(right));
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

// Minimum Window Substring
public String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();

    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    int left = 0, right = 0, valid = 0;
    int start = 0, len = Integer.MAX_VALUE;

    while (right < s.length()) {
        char c = s.charAt(right);
        right++;

        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }

        while (valid == need.size()) {
            if (right - left < len) {
                start = left;
                len = right - left;
            }

            char d = s.charAt(left);
            left++;

            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }

    return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}

Backtracking

// Generate Parentheses
public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(result, "", 0, 0, n);
    return result;
}

private void backtrack(List<String> result, String current,
                      int open, int close, int max) {
    if (current.length() == max * 2) {
        result.add(current);
        return;
    }

    if (open < max) {
        backtrack(result, current + "(", open + 1, close, max);
    }
    if (close < open) {
        backtrack(result, current + ")", open, close + 1, max);
    }
}

// N-Queens
public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];

    for (char[] row : board) {
        Arrays.fill(row, '.');
    }

    backtrackQueens(result, board, 0);
    return result;
}

private void backtrackQueens(List<List<String>> result, char[][] board, int row) {
    if (row == board.length) {
        result.add(construct(board));
        return;
    }

    for (int col = 0; col < board.length; col++) {
        if (isValidQueenPlacement(board, row, col)) {
            board[row][col] = 'Q';
            backtrackQueens(result, board, row + 1);
            board[row][col] = '.';
        }
    }
}

private boolean isValidQueenPlacement(char[][] board, int row, int col) {
    // Check column
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }

    // Check diagonal
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }

    // Check anti-diagonal
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }

    return true;
}

Time and Space Complexity Analysis

Big O Notation

O(1) - Constant time
O(log n) - Logarithmic time
O(n) - Linear time
O(n log n) - Linearithmic time
O(n²) - Quadratic time
O(2ⁿ) - Exponential time
O(n!) - Factorial time

Common Complexity Examples

// O(1) - Constant
public int getFirst(int[] arr) {
    return arr[0]; // Single operation
}

// O(n) - Linear
public int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) { // n iterations
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// O(n²) - Quadratic
public void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) { // n iterations
        for (int j = 0; j < arr.length - i - 1; j++) { // n iterations
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

// O(log n) - Logarithmic
public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) { // log n iterations
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// O(n log n) - Merge Sort
public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid); // T(n/2)
        mergeSort(arr, mid + 1, right); // T(n/2)
        merge(arr, left, mid, right); // O(n)
    }
}

Best Practices and Tips

Code Organization

// Good: Clear method names and single responsibility
public class BinarySearchTree {
    private TreeNode root;

    public void insert(int val) { /* implementation */ }
    public boolean search(int val) { /* implementation */ }
    public void delete(int val) { /* implementation */ }
    private TreeNode findMin(TreeNode node) { /* helper */ }
}

// Good: Use meaningful variable names
public int findSecondLargest(int[] nums) {
    int largest = Integer.MIN_VALUE;
    int secondLargest = Integer.MIN_VALUE;

    for (int num : nums) {
        if (num > largest) {
            secondLargest = largest;
            largest = num;
        } else if (num > secondLargest && num != largest) {
            secondLargest = num;
        }
    }

    return secondLargest;
}

Error Handling

// Always validate inputs
public int binarySearch(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        throw new IllegalArgumentException("Array cannot be null or empty");
    }

    // Binary search implementation
    return -1;
}

// Handle edge cases
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head; // Handle empty list or single node
    }

    // Reversal logic
    return null;
}

Performance Considerations

// Prefer primitive arrays for large datasets
int[] primitiveArray = new int[1000000]; // Better performance
Integer[] wrapperArray = new Integer[1000000]; // More memory overhead

// Use StringBuilder for string concatenation
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 1000; i++) {
    sb.append("value").append(i); // O(1) amortized
}
String result = sb.toString();

// Avoid creating unnecessary objects in loops
// Bad
for (int i = 0; i < n; i++) {
    String temp = "prefix" + i; // Creates new String object each iteration
}

// Good
StringBuilder sb = new StringBuilder("prefix");
int originalLength = sb.length();
for (int i = 0; i < n; i++) {
    sb.setLength(originalLength);
    sb.append(i);
    String temp = sb.toString();
}

Interview Preparation Checklist

Must-Know Algorithms

✅ Binary Search and its variants
✅ DFS and BFS traversals
✅ Quick Sort and Merge Sort
✅ Dynamic Programming patterns
✅ Two Pointers and Sliding Window
✅ Backtracking template

Must-Know Data Structures

✅ Arrays and Strings manipulation
✅ Linked List operations
✅ Stack and Queue applications
✅ Binary Trees and BST
✅ Hash Tables for lookups
✅ Heaps for priority operations

Problem-Solving Strategy

Understand the problem completely
Ask clarifying questions about constraints
Think of brute force solution first
Optimize using appropriate data structures/algorithms
Code with clean, readable implementation
Test with edge cases and examples
Analyze time and space complexity

Common Mistake Patterns to Avoid

Off-by-one errors in loops and array access
Not handling null/empty inputs
Integer overflow in calculations
Modifying collection while iterating
Incorrect loop termination conditions
Not considering edge cases (empty, single element)

Table of Contents​

Arrays​

When to Use Arrays​

Key Characteristics​

Common Use Cases​

Best Practices​

Strings​

When to Use Strings​

Key Characteristics​

String vs StringBuilder vs StringBuffer​

Common String Algorithms​

Linked Lists​

When to Use Linked Lists​

Types and Use Cases​

Singly Linked List​

Doubly Linked List​

Time Complexity​

Common Patterns​

Stacks​

When to Use Stacks​

Implementation Options​

Common Use Cases​

Time Complexity​

Queues​

When to Use Queues​

Types and Implementations​

Regular Queue​

Priority Queue​

Deque (Double-ended Queue)​

Common Patterns​

Trees​

When to Use Trees​

Types of Trees​

Binary Tree​

Binary Search Tree (BST)​

AVL Tree (Self-balancing BST)​

Trie (Prefix Tree)​

Tree Traversals​

Graphs​

When to Use Graphs​

Graph Representations​

Adjacency List​

Adjacency Matrix​

Graph Traversal Algorithms​

DFS (Depth-First Search)​

BFS (Breadth-First Search)​

Shortest Path Algorithms​

Dijkstra's Algorithm​

Floyd-Warshall Algorithm​

Topological Sorting​

Hash Tables​

When to Use Hash Tables​

Java Hash Table Implementations​

Common Patterns​

Hash Function Design Principles​

Heaps​

When to Use Heaps​

Types of Heaps​

Min Heap​

Max Heap​

Common Heap Patterns​

Time Complexity​

Sorting Algorithms​

When to Use Different Sorting Algorithms​

Quick Sort​

Merge Sort​

Heap Sort​

Counting Sort​

Comparison of Sorting Algorithms​

Searching Algorithms​

Binary Search​

Linear Search​

Ternary Search​

Dynamic Programming​

When to Use Dynamic Programming​

DP Approaches​

Top-Down (Memoization)​

Bottom-Up (Tabulation)​

Classic DP Problems​

0/1 Knapsack​

Table of Contents

Arrays

When to Use Arrays

Key Characteristics

Common Use Cases

Best Practices

Strings

When to Use Strings

Key Characteristics

String vs StringBuilder vs StringBuffer

Common String Algorithms

Linked Lists

When to Use Linked Lists

Types and Use Cases

Singly Linked List

Doubly Linked List

Time Complexity

Common Patterns

Stacks

When to Use Stacks

Implementation Options

Common Use Cases

Time Complexity

Queues

When to Use Queues

Types and Implementations

Regular Queue

Priority Queue

Deque (Double-ended Queue)

Common Patterns

Trees

When to Use Trees

Types of Trees

Binary Tree

Binary Search Tree (BST)

AVL Tree (Self-balancing BST)

Trie (Prefix Tree)

Tree Traversals

Graphs

When to Use Graphs

Graph Representations

Adjacency List

Adjacency Matrix

Graph Traversal Algorithms

DFS (Depth-First Search)

BFS (Breadth-First Search)

Shortest Path Algorithms

Dijkstra's Algorithm

Floyd-Warshall Algorithm

Topological Sorting

Hash Tables

When to Use Hash Tables

Java Hash Table Implementations

Common Patterns

Hash Function Design Principles

Heaps

When to Use Heaps

Types of Heaps

Min Heap

Max Heap

Common Heap Patterns

Time Complexity

Sorting Algorithms

When to Use Different Sorting Algorithms

Quick Sort

Merge Sort

Heap Sort

Counting Sort

Comparison of Sorting Algorithms

Searching Algorithms

Binary Search

Linear Search

Ternary Search

Dynamic Programming

When to Use Dynamic Programming

DP Approaches

Top-Down (Memoization)

Bottom-Up (Tabulation)

Classic DP Problems

0/1 Knapsack