Java DSA Complete Cheat Sheet

A comprehensive, beginner-friendly guide to Data Structures and Algorithms in Java.

Features

• 24+ topics covered from basic to advanced
• Mental models for easy understanding
• Interview-focused patterns
• Ready-to-use code templates
• Time & Space complexity reference

How to Use

1. Read the concepts
2. Understand the mental models
3. Practice with examples
4. Refer during interviews

---

🚀 JAVA DSA COMPLETE CHEAT SHEET

🧩 1️⃣ ARRAYS

🏭 Think of a Train

Mental Model: Fixed seats in a row, numbered from 0

📦 Declaration & Initialization

// Method 1: Declare then assign
int[] arr = new int[5];  // [0,0,0,0,0]
arr[0] = 10;

// Method 2: Direct initialization
int[] arr = {1, 2, 3, 4, 5};

// Method 3: 2D Array
int[][] matrix = new int[3][3];
int[][] grid = {{1,2},{3,4}};

🔑 Core Operations

Operation	Syntax	Time
Access	arr[i]	O(1)
Update	arr[i] = val	O(1)
Length	arr.length	O(1)
Iterate	for(int x : arr)	O(n)

💡 Common Patterns

// Reverse array
int left = 0, right = arr.length - 1;
while (left < right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
    left++; right--;
}

// Find max
int max = arr[0];
for (int num : arr) {
    max = Math.max(max, num);
}

// Two pointer technique
int i = 0, j = arr.length - 1;
while (i < j) {
    // process
    i++; j--;
}

🧠 Remember

"Arrays are fast but fixed size"

---

🧩 2️⃣ STRINGS

🏭 Think of a Necklace

Mental Model: Immutable beads on a string

📦 Declaration & Core Methods

String s = "Hello";
String s2 = new String("World");

// MOST USED METHODS
s.length()              // 5
s.charAt(0)             // 'H'
s.substring(0, 2)       // "He"
s.indexOf('l')          // 2
s.contains("ell")       // true
s.equals("Hello")       // true (use this, not ==)
s.toLowerCase()         // "hello"
s.toUpperCase()         // "HELLO"
s.trim()               // remove spaces
s.split(" ")           // ["Hello"]
s.replace('H', 'J')    // "Jello"

🔥 StringBuilder (CRITICAL for DSA)

// Why? Strings are immutable, StringBuilder is mutable
StringBuilder sb = new StringBuilder();
sb.append("Hello");     // add
sb.append(" World");
sb.insert(5, ",");      // "Hello, World"
sb.delete(5, 6);        // remove comma
sb.reverse();           // reverse
sb.toString();          // convert to String

// Character operations
sb.charAt(0);           // access
sb.setCharAt(0, 'J');   // modify

💡 Common Patterns

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

// Reverse string
String reverse = new StringBuilder(s).reverse().toString();

// Convert char array to string
char[] arr = {'a', 'b', 'c'};
String s = new String(arr);

// Convert string to char array
char[] arr = s.toCharArray();

🧠 Remember

"Use StringBuilder for string manipulation in loops"

---

🧩 3️⃣ ARRAYLIST

🏭 Think of an Expandable Shelf

Mental Model: Dynamic array that grows automatically

📦 Declaration & Core Methods

import java.util.ArrayList;

ArrayList<Integer> list = new ArrayList<>();
// Or
List<Integer> list = new ArrayList<>(); // preferred

// CORE OPERATIONS
list.add(10);              // add at end
list.add(0, 5);            // add at index
list.get(0);               // access
list.set(0, 15);           // update
list.remove(0);            // remove by index
list.remove(Integer.valueOf(10)); // remove by value
list.size();               // length
list.contains(10);         // search
list.isEmpty();            // check empty
list.clear();              // remove all

💡 Common Patterns

// Iterate
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// Enhanced for
for (int num : list) {
    System.out.println(num);
}

// Convert to array
Integer[] arr = list.toArray(new Integer[0]);

// Convert array to list
List<Integer> list = Arrays.asList(1, 2, 3);
// Or (mutable)
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));

// Sort
Collections.sort(list);              // ascending
Collections.sort(list, Collections.reverseOrder()); // descending

// Reverse
Collections.reverse(list);

🧠 Remember

"ArrayList = dynamic array, use when size is unknown"

---

🧩 4️⃣ LINKEDLIST

🏭 Think of a Chain

Mental Model: Nodes connected by links

📦 Node Structure

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

🔑 Core Operations

// Create linked list
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

// Traverse
ListNode current = head;
while (current != null) {
    System.out.println(current.val);
    current = current.next;
}

💡 Common Patterns

// Reverse linked list
ListNode reverse(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// Find middle (slow-fast pointer)
ListNode middle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

// Detect cycle
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;
}

🧠 Remember

"Slow-fast pointer is the secret weapon for LinkedList"

---

🧩 5️⃣ STACK

🏭 Think of a Stack of Plates

Mental Model: LIFO - Last In First Out

📦 Implementation

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

// CORE OPERATIONS
stack.push(10);        // add on top
stack.pop();           // remove from top
stack.peek();          // see top element
stack.isEmpty();       // check empty
stack.size();          // size
stack.search(10);      // position from top (1-indexed)

💡 Common Patterns

// Valid parentheses
boolean isValid(String s) {
    Stack<Character> 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();
}

// Next greater element
int[] nextGreater(int[] arr) {
    int n = arr.length;
    int[] result = new int[n];
    Stack<Integer> stack = new Stack<>();
    
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() <= arr[i]) {
            stack.pop();
        }
        result[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(arr[i]);
    }
    return result;
}

🧠 Remember

"Stack = plates, always work on top"

---

🧩 6️⃣ QUEUE

🏭 Think of a Line at a Ticket Counter

Mental Model: FIFO - First In First Out

📦 Implementation

import java.util.Queue;
import java.util.LinkedList;

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

// CORE OPERATIONS
queue.offer(10);       // add (use this)
queue.add(10);         // add (throws exception)
queue.poll();          // remove from front
queue.peek();          // see front
queue.isEmpty();       // check empty
queue.size();          // size

💡 Common Patterns

// BFS in tree/graph
void bfs(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val);
        
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

// Level order traversal
List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    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;
}

🧠 Remember

"Queue = waiting line, first come first serve"

---

🧩 7️⃣ HASHMAP

🏭 Think of a Dictionary

Mental Model: Word → Meaning (Key → Value)

📦 Core Operations

import java.util.HashMap;
import java.util.Map;

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

// MOST USED OPERATIONS
map.put("Krish", 21);           // insert/update
map.get("Krish");               // 21
map.getOrDefault("Ram", 0);     // safe get
map.containsKey("Krish");       // true
map.containsValue(21);          // true
map.remove("Krish");            // delete
map.size();                     // count
map.isEmpty();                  // check empty
map.keySet();                   // all keys
map.values();                   // all values
map.entrySet();                 // all entries

// Update pattern
map.put("Krish", map.getOrDefault("Krish", 0) + 1);

💡 Common Patterns

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

// Two sum
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[]{};
}

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

// Or
for (String key : map.keySet()) {
    System.out.println(key + " -> " + map.get(key));
}

🧠 Remember

"If you need fast lookup, use HashMap"

---

🧩 8️⃣ HASHSET

🏭 Think of a VIP List

Mental Model: Unique entries only, no duplicates

📦 Core Operations

import java.util.HashSet;
import java.util.Set;

Set<Integer> set = new HashSet<>();

// CORE OPERATIONS
set.add(10);           // add
set.remove(10);        // delete
set.contains(10);      // search
set.size();            // count
set.isEmpty();         // check empty
set.clear();           // remove all

💡 Common Patterns

// Remove duplicates
int[] removeDuplicates(int[] arr) {
    Set<Integer> set = new HashSet<>();
    for (int num : arr) {
        set.add(num);
    }
    return set.stream().mapToInt(i -> i).toArray();
}

// Check if array has duplicates
boolean hasDuplicate(int[] arr) {
    Set<Integer> set = new HashSet<>();
    for (int num : arr) {
        if (!set.add(num)) return true; // add returns false if exists
    }
    return false;
}

// Iterate
for (int num : set) {
    System.out.println(num);
}

🧠 Remember

"HashSet = uniqueness enforcer"

---

🧩 9️⃣ PRIORITY QUEUE (HEAP)

🏭 Think of Hospital Emergency

Mental Model: Priority matters, not arrival time

📦 Implementation

import java.util.PriorityQueue;

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

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

// CORE OPERATIONS
minHeap.offer(10);     // add
minHeap.poll();        // remove top
minHeap.peek();        // see top
minHeap.size();        // count
minHeap.isEmpty();     // check empty

💡 Common Patterns

// Kth largest element
int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    return minHeap.peek();
}

// Top K frequent elements
List<Integer> topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }
    
    PriorityQueue<Integer> heap = new PriorityQueue<>(
        (a, b) -> freq.get(a) - freq.get(b)
    );
    
    for (int num : freq.keySet()) {
        heap.offer(num);
        if (heap.size() > k) heap.poll();
    }
    
    return new ArrayList<>(heap);
}

🧠 Remember

"Min heap for smallest, Max heap for largest"

---

🧩 🔟 SORTING

📦 Built-in Sorting

import java.util.Arrays;
import java.util.Collections;

// Arrays
int[] arr = {3, 1, 4, 1, 5};
Arrays.sort(arr);                    // ascending

// ArrayList
List<Integer> list = new ArrayList<>();
Collections.sort(list);              // ascending
Collections.sort(list, Collections.reverseOrder()); // descending

// Custom comparator
Arrays.sort(arr, (a, b) -> b - a);   // descending

// 2D array sort
int[][] intervals = {{1,3}, {2,6}, {8,10}};
Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // sort by first element

💡 Custom Comparator Patterns

// Sort strings by length
String[] words = {"apple", "pie", "banana"};
Arrays.sort(words, (a, b) -> a.length() - b.length());

// Sort objects
class Student {
    String name;
    int marks;
}

Arrays.sort(students, (a, b) -> b.marks - a.marks); // descending marks

🧠 Remember

"Arrays.sort for arrays, Collections.sort for lists"

---

🧩 1️⃣1️⃣ BINARY SEARCH

🏭 Think of Finding a Page in Dictionary

Mental Model: Keep dividing in half

📦 Template

// Standard binary search
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;
}

// Built-in
Arrays.binarySearch(arr, target); // returns index or negative

💡 Common Patterns

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

// Search in rotated sorted array
int search(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;
        
        if (nums[left] <= nums[mid]) {
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

🧠 Remember

"Binary search needs sorted array, O(log n) time"

---

🧩 1️⃣2️⃣ RECURSION

🏭 Think of Russian Dolls

Mental Model: Function calls itself

📦 Template

returnType recursiveFunction(parameters) {
    // Base case
    if (baseCondition) {
        return baseValue;
    }
    
    // Recursive case
    return recursiveFunction(modifiedParameters);
}

💡 Common Patterns

// Factorial
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Fibonacci
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// Power
int power(int x, int n) {
    if (n == 0) return 1;
    int half = power(x, n / 2);
    if (n % 2 == 0) return half * half;
    return x * half * half;
}

// Print 1 to n
void print(int n) {
    if (n == 0) return;
    print(n - 1);
    System.out.println(n);
}

// Print n to 1
void printReverse(int n) {
    if (n == 0) return;
    System.out.println(n);
    printReverse(n - 1);
}

🧠 Remember

"Base case + recursive case = recursion"

---

🧩 1️⃣3️⃣ BACKTRACKING

🏭 Think of Maze Solving

Mental Model: Try → Fail → Undo → Try another path

📦 Template

void backtrack(params) {
    // Base case
    if (foundSolution) {
        addToResult();
        return;
    }
    
    // Try all choices
    for (choice : choices) {
        // Make choice
        choose(choice);
        
        // Recurse
        backtrack(newParams);
        
        // Undo choice (backtrack)
        unchoose(choice);
    }
}

💡 Common Patterns

// Permutations
List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums);
    return result;
}

void backtrack(List<List<Integer>> result, List<Integer> temp, int[] nums) {
    if (temp.size() == nums.length) {
        result.add(new ArrayList<>(temp));
        return;
    }
    
    for (int num : nums) {
        if (temp.contains(num)) continue;
        temp.add(num);
        backtrack(result, temp, nums);
        temp.remove(temp.size() - 1);
    }
}

// Subsets
List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums, 0);
    return result;
}

void backtrack(List<List<Integer>> result, List<Integer> temp, 
               int[] nums, int start) {
    result.add(new ArrayList<>(temp));
    
    for (int i = start; i < nums.length; i++) {
        temp.add(nums[i]);
        backtrack(result, temp, nums, i + 1);
        temp.remove(temp.size() - 1);
    }
}

🧠 Remember

"Choose → Explore → Unchoose"

---

🧩 1️⃣4️⃣ DYNAMIC PROGRAMMING

🏭 Think of a Notebook

Mental Model: Save answers to avoid recalculating

📦 Approaches

1. Top-Down (Memoization): Recursion + Cache
2. Bottom-Up (Tabulation): Iterative + DP array

💡 Common Patterns

// Fibonacci (Memoization)
int fib(int n, int[] memo) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

// Fibonacci (Tabulation)
int fib(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];
}

// Climbing stairs
int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 0/1 Knapsack
int knapsack(int[] wt, int[] val, int W, int n) {
    int[][] dp = new int[n + 1][W + 1];
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = Math.max(
                    val[i - 1] + dp[i - 1][w - wt[i - 1]],
                    dp[i - 1][w]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

🧠 Remember

"DP = storing results to avoid recomputation"

---

🧩 1️⃣5️⃣ GRAPHS

🏭 Think of Social Network

Mental Model: People (nodes) connected by friendships (edges)

📦 Graph Representation

// 1. Adjacency List (MOST COMMON)
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
    graph.add(new ArrayList<>());
}
// Add edge
graph.get(u).add(v);

// 2. Adjacency Matrix
int[][] graph = new int[n][n];
graph[u][v] = 1; // edge from u to v

💡 DFS (Depth First Search)

void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
    visited[node] = true;
    System.out.println(node);
    
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

💡 BFS (Breadth First Search)

void bfs(List<List<Integer>> graph, int start) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();
    
    queue.offer(start);
    visited[start] = true;
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println(node);
        
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

💡 Detect Cycle

// Undirected graph
boolean hasCycle(List<List<Integer>> graph, int node, 
                 boolean[] visited, int parent) {
    visited[node] = true;
    
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            if (hasCycle(graph, neighbor, visited, node)) {
                return true;
            }
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

🧠 Remember

"DFS uses stack (recursion), BFS uses queue"

---

🧩 1️⃣6️⃣ TREES

🏭 Think of Family Tree

Mental Model: Parent-child relationship

📦 Tree Node

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

💡 Tree Traversals

// Inorder (Left → Root → Right)
void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.println(root.val);
    inorder(root.right);
}

// Preorder (Root → Left → Right)
void preorder(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);
    preorder(root.left);
    preorder(root.right);
}

// Postorder (Left → Right → Root)
void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.println(root.val);
}

// Level order (BFS)
void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val);
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

💡 Common Problems

// Height of tree
int height(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(height(root.left), height(root.right));
}

// Diameter of tree
int diameter(TreeNode root) {
    if (root == null) return 0;
    
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    int leftDiameter = diameter(root.left);
    int rightDiameter = diameter(root.right);
    
    return Math.max(leftHeight + rightHeight, 
                    Math.max(leftDiameter, rightDiameter));
}

// Check if balanced
boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    
    return Math.abs(leftHeight - rightHeight) <= 1 
           && isBalanced(root.left) 
           && isBalanced(root.right);
}

// Lowest common ancestor
TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    
    TreeNode left = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

🧠 Remember

"Inorder gives sorted order in BST"

---

🧩 1️⃣7️⃣ BINARY SEARCH TREE (BST)

🏭 Think of Sorted Phone Book

Mental Model: Left < Root < Right

💡 Common Operations

// Search in BST
TreeNode search(TreeNode root, int val) {
    if (root == null || root.val == val) return root;
    if (val < root.val) return search(root.left, val);
    return search(root.right, val);
}

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

// Delete in BST
TreeNode delete(TreeNode root, int val) {
    if (root == null) return null;
    
    if (val < root.val) {
        root.left = delete(root.left, val);
    } else if (val > root.val) {
        root.right = delete(root.right, val);
    } else {
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        TreeNode minNode = findMin(root.right);
        root.val = minNode.val;
        root.right = delete(root.right, minNode.val);
    }
    return root;
}

TreeNode findMin(TreeNode root) {
    while (root.left != null) root = root.left;
    return root;
}

// Validate BST
boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}

boolean validate(TreeNode root, Integer min, Integer max) {
    if (root == null) return true;
    if ((min != null && root.val <= min) || 
        (max != null && root.val >= max)) {
        return false;
    }
    return validate(root.left, min, root.val) && 
           validate(root.right, root.val, max);
}

🧠 Remember

"BST inorder traversal = sorted array"

---

🧩 1️⃣8️⃣ SLIDING WINDOW

🏭 Think of a Moving Window on Train

Mental Model: Fixed/variable size window that slides

📦 Fixed Window Template

// Maximum sum of k elements
int maxSum(int[] arr, int k) {
    int windowSum = 0, maxSum = 0;
    
    // First window
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;
    
    // Slide window
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

📦 Variable Window Template

// Longest substring without repeating characters
int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, maxLen = 0;
    
    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(s.charAt(right));
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

// Minimum window substring
String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";
    
    Map<Character, Integer> map = new HashMap<>();
    for (char c : t.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    
    int left = 0, minLen = Integer.MAX_VALUE, minStart = 0;
    int count = map.size();
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (map.containsKey(c)) {
            map.put(c, map.get(c) - 1);
            if (map.get(c) == 0) count--;
        }
        
        while (count == 0) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minStart = left;
            }
            
            char leftChar = s.charAt(left);
            if (map.containsKey(leftChar)) {
                map.put(leftChar, map.get(leftChar) + 1);
                if (map.get(leftChar) > 0) count++;
            }
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
}

🧠 Remember

"Sliding window = two pointers moving in same direction"

---

🧩 1️⃣9️⃣ TWO POINTERS

🏭 Think of Two Hands

Mental Model: Use two indices to solve in one pass

💡 Common Patterns

// Two sum in sorted array
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++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};
}

// Remove duplicates from sorted array
int removeDuplicates(int[] nums) {
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

// Container with most water
int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;
    
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

// Three sum
List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

🧠 Remember

"Two pointers reduce O(n²) to O(n)"

---

🧩 2️⃣0️⃣ GREEDY ALGORITHMS

🏭 Think of Eating Buffet

Mental Model: Make locally optimal choice at each step

💡 Common Patterns

// Activity selection
int maxActivities(int[] start, int[] end) {
    int[][] activities = new int[start.length][2];
    for (int i = 0; i < start.length; i++) {
        activities[i] = new int[]{start[i], end[i]};
    }
    Arrays.sort(activities, (a, b) -> a[1] - b[1]);
    
    int count = 1, lastEnd = activities[0][1];
    for (int i = 1; i < activities.length; i++) {
        if (activities[i][0] >= lastEnd) {
            count++;
            lastEnd = activities[i][1];
        }
    }
    return count;
}

// Jump game
boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

// Fractional knapsack
double fractionalKnapsack(int W, int[] wt, int[] val) {
    int n = wt.length;
    double[][] items = new double[n][3];
    
    for (int i = 0; i < n; i++) {
        items[i][0] = wt[i];
        items[i][1] = val[i];
        items[i][2] = (double) val[i] / wt[i];
    }
    
    Arrays.sort(items, (a, b) -> Double.compare(b[2], a[2]));
    
    double totalValue = 0;
    for (int i = 0; i < n; i++) {
        if (W >= items[i][0]) {
            totalValue += items[i][1];
            W -= items[i][0];
        } else {
            totalValue += items[i][2] * W;
            break;
        }
    }
    return totalValue;
}

🧠 Remember

"Greedy = best choice now, hope it leads to global optimum"

---

🧩 2️⃣1️⃣ BIT MANIPULATION

🏭 Think of Light Switches

Mental Model: Each bit is a switch (0 or 1)

📦 Core Operations

// Check if kth bit is set
boolean isSet(int n, int k) {
    return (n & (1 << k)) != 0;
}

// Set kth bit
int setBit(int n, int k) {
    return n | (1 << k);
}

// Clear kth bit
int clearBit(int n, int k) {
    return n & ~(1 << k);
}

// Toggle kth bit
int toggleBit(int n, int k) {
    return n ^ (1 << k);
}

// Count set bits
int countSetBits(int n) {
    int count = 0;
    while (n > 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

// Or use built-in
int count = Integer.bitCount(n);

💡 Common Patterns

// Check if power of 2
boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

// Single number (XOR trick)
int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

// Swap two numbers without temp
void swap(int a, int b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

// Find missing number
int missingNumber(int[] nums) {
    int n = nums.length;
    int xor = 0;
    for (int i = 0; i <= n; i++) xor ^= i;
    for (int num : nums) xor ^= num;
    return xor;
}

🧠 Remember

"XOR of same numbers = 0, XOR of 0 and x = x"

---

🧩 2️⃣2️⃣ MATH & NUMBER THEORY

💡 Common Operations

// GCD (Greatest Common Divisor)
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// LCM (Least Common Multiple)
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

// Check prime
boolean isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

// Prime factors
List<Integer> primeFactors(int n) {
    List<Integer> factors = new ArrayList<>();
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.add(i);
            n /= i;
        }
    }
    if (n > 1) factors.add(n);
    return factors;
}

// Sieve of Eratosthenes
boolean[] sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

// Fast power (a^b % mod)
long power(long a, long b, long mod) {
    long result = 1;
    a %= mod;
    while (b > 0) {
        if ((b & 1) == 1) result = (result * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return result;
}

🧠 Remember

"For prime checking, only iterate till √n"

---

🧩 2️⃣3️⃣ TRIE (PREFIX TREE)

🏭 Think of Autocomplete

Mental Model: Tree where each path forms a word

📦 Implementation

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

class Trie {
    TrieNode root;
    
    Trie() {
        root = new TrieNode();
    }
    
    // Insert word
    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEndOfWord = true;
    }
    
    // Search word
    boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return node.isEndOfWord;
    }
    
    // Check prefix
    boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;
    }
}

🧠 Remember

"Trie = efficient word search & autocomplete"

---

🧩 2️⃣4️⃣ IMPORTANT UTILITIES

📦 Math Class

Math.max(a, b)              // maximum
Math.min(a, b)              // minimum
Math.abs(x)                 // absolute value
Math.pow(x, y)              // x^y
Math.sqrt(x)                // square root
Math.ceil(x)                // ceiling
Math.floor(x)               // floor
Math.round(x)               // round

📦 Arrays Class

Arrays.sort(arr)            // sort
Arrays.fill(arr, val)       // fill with value
Arrays.equals(arr1, arr2)   // compare arrays
Arrays.toString(arr)        // print array
Arrays.copyOf(arr, len)     // copy array

📦 Collections Class

Collections.sort(list)              // sort
Collections.reverse(list)           // reverse
Collections.max(list)               // max element
Collections.min(list)               // min element
Collections.frequency(list, val)    // count occurrences

📦 String Conversion

// String to int
int num = Integer.parseInt("123");

// int to String
String s = String.valueOf(123);
String s = Integer.toString(123);

// char to int
int num = c - '0';

// int to char
char c = (char)(num + '0');

// String to char array
char[] arr = s.toCharArray();

// char array to String
String s = new String(arr);

---

🎯 GOLDEN RULES TO REMEMBER

🔑 Time Complexity Quick Reference

Operation	Time
Array access	O(1)
Binary search	O(log n)
Linear search	O(n)
Sorting	O(n log n)
Nested loops	O(n²)
DFS/BFS	O(V + E)

🔑 Space Complexity

Structure	Space
Array/List	O(n)
HashMap/Set	O(n)
Recursion depth	O(n)

🔑 When to Use What

Problem Type	Data Structure
Fast lookup	HashMap/HashSet
Maintain order	ArrayList
LIFO	Stack
FIFO	Queue
Priority	PriorityQueue (Heap)
Range queries	Segment Tree
Uniqueness	HashSet
Sorted data	TreeSet/TreeMap

🔑 Pattern Recognition

• Two pointers: Sorted array, palindrome
• Sliding window: Substring, subarray
• Binary search: Sorted array, search space
• DFS: Tree, graph, backtracking
• BFS: Shortest path, level order
• DP: Overlapping subproblems
• Greedy: Local optimum → global optimum
• Backtracking: Generate all combinations

---

✅ FINAL CHECKLIST

✅ Always check edge cases: empty input, single element, duplicates ✅ Initialize variables properly: avoid NullPointerException ✅ Use correct comparison: equals() for Objects, == for primitives ✅ Watch out for integer overflow: use long when needed ✅ Test with small examples first ✅ Trace your code step-by-step ✅ Consider time and space complexity

---

🧠 MEMORIZE THESE GOLDEN SENTENCES

🔑 "If you need fast lookup, use HashMap" 🔑 "Stack = LIFO, Queue = FIFO" 🔑 "Binary search needs sorted array" 🔑 "DFS uses recursion, BFS uses queue" 🔑 "Sliding window = two pointers in same direction" 🔑 "Use StringBuilder for string manipulation in loops" 🔑 "XOR of same numbers = 0" 🔑 "DP = save results to avoid recomputation" 🔑 "Greedy = best choice now" 🔑 "Always validate inputs before processing"

---

---

Support

If this helped you, give it a star!

License

MIT License