Avi's Notes

Java Coding Interview Cheat-sheet

30 min read

Table of Contents

  1. Basic Syntax & Patterns
  2. Arrays & Strings
  3. Linked Lists
  4. Stacks & Queues
  5. Trees & Graphs
  6. Dynamic Programming
  7. Sorting & Searching
  8. Hash Tables & Sets
  9. Mathematical Algorithms
  10. Common Patterns & Tricks
  11. Performance Tips & Best Practices
  12. Advanced Topics & Patterns

Basic Syntax & Patterns

Essential Imports

import java.util.*;
import java.util.stream.*;

Common Data Types & Operations

// Primitive types - know their ranges
int x = Integer.MAX_VALUE;    // 2^31 - 1
long y = Long.MAX_VALUE;      // 2^63 - 1
double d = Double.MAX_VALUE;
 
// String operations - strings are immutable
String s = "hello";
s.charAt(0);           // 'h' - O(1)
s.substring(1, 3);     // "el" - O(n)
s.indexOf('e');        // 1 - O(n)
s.length();           // 5 - O(1)
 
// StringBuilder for mutable strings - crucial for performance
StringBuilder sb = new StringBuilder();
sb.append("hello");    // O(1) amortized
sb.toString();         // O(n)

Input/Output Patterns

// Fast input reading
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String line = sc.nextLine();
 
// Multiple test cases pattern
while (sc.hasNext()) {
    // process input
}

Arrays & Strings

Array Basics & Common Operations

// Declaration and initialization
int[] arr = new int[n];              // O(n) space
int[] arr2 = {1, 2, 3, 4, 5};       
Arrays.fill(arr, -1);               // Fill with value - O(n)
 
// Essential array methods
Arrays.sort(arr);                    // O(n log n)
int pos = Arrays.binarySearch(arr, target);  // O(log n) - array must be sorted
Arrays.copyOf(arr, newLength);       // O(n)

Two Pointer Technique

Use for: Array/string problems, palindromes, pairs with target sum

// Classic two-pointer for sorted array pair sum
public int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1}; // Not found
}
 
// Sliding window for subarray problems
public int maxSubarray(int[] nums, int k) {
    int maxSum = 0, windowSum = 0;
    
    // Initial window
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
    }
    maxSum = windowSum;
    
    // Slide the window
    for (int i = k; i < nums.length; i++) {
        windowSum += nums[i] - nums[i - k];  // Add new, remove old
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

String Processing Patterns

// Character frequency counting - O(n) time, O(1) space for ASCII
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    
    int[] count = new int[26];  // For lowercase letters only
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    
    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}
 
// String reversal and palindrome check
public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
        
        if (Character.toLowerCase(s.charAt(left)) != 
            Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Linked Lists

Node Definition & Basic Operations

// Singly linked list node
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}
 
// Doubly linked list node
class DoublyListNode {
    int val;
    DoublyListNode prev, next;
    DoublyListNode(int val) { this.val = val; }
}

Essential Linked List Patterns

// Reverse a linked list - O(n) time, O(1) space
public ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
 
// Fast & slow pointer for cycle detection (Floyd's algorithm)
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;
}
 
// Find middle of linked list
public ListNode findMiddle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;  // For even length, returns second middle
}
 
// Merge two sorted lists - O(m + n) time, O(1) space
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

Stacks & Queues

Stack Implementation & Use Cases

// Stack declaration
Stack<Integer> stack = new Stack<>();
Deque<Integer> stack2 = new ArrayDeque<>();  // Preferred over Stack class
 
// Basic operations - all O(1)
stack.push(element);
int top = stack.pop();
int peek = stack.peek();
boolean isEmpty = stack.isEmpty();
 
// Valid parentheses pattern - O(n) time, O(n) space
public boolean isValidParentheses(String s) {
    Stack<Character> stack = new Stack<>();
    Map<Character, Character> mapping = new HashMap<>();
    mapping.put(')', '(');
    mapping.put('}', '{');
    mapping.put(']', '[');
    
    for (char c : s.toCharArray()) {
        if (mapping.containsKey(c)) {  // Closing bracket
            if (stack.isEmpty() || stack.pop() != mapping.get(c)) {
                return false;
            }
        } else {  // Opening bracket
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

Queue Implementation & BFS Pattern

// Queue declaration
Queue<Integer> queue = new LinkedList<>();
Deque<Integer> deque = new ArrayDeque<>();  // More efficient
 
// Basic operations
queue.offer(element);     // Add to rear - O(1)
int front = queue.poll(); // Remove from front - O(1)
int peek = queue.peek();  // Look at front - O(1)
 
// Level-order traversal template (BFS)
public 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 levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(currentLevel);
    }
    return result;
}

Monotonic Stack/Queue Patterns

// Next greater element using monotonic stack - O(n) time
public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Stack<Integer> stack = new Stack<>();  // Store indices
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}
 
// Sliding window maximum using deque - O(n) time
public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new ArrayDeque<>();  // Store indices
    int[] result = new int[nums.length - k + 1];
    int ri = 0;
    
    for (int i = 0; i < nums.length; i++) {
        // Remove indices outside current window
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }
        
        // Maintain decreasing order in deque
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }
        
        deque.offerLast(i);
        
        if (i >= k - 1) {
            result[ri++] = nums[deque.peekFirst()];
        }
    }
    return result;
}

Trees & Graphs

Binary Tree Node & Traversals

// Binary tree node definition
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
 
// Recursive traversals - O(n) time, O(h) space where h is height
public void inorderTraversal(TreeNode root, List<Integer> result) {
    if (root != null) {
        inorderTraversal(root.left, result);   // Left
        result.add(root.val);                  // Root
        inorderTraversal(root.right, result);  // Right
    }
}
 
public void preorderTraversal(TreeNode root, List<Integer> result) {
    if (root != null) {
        result.add(root.val);                  // Root
        preorderTraversal(root.left, result);  // Left
        preorderTraversal(root.right, result); // Right
    }
}
 
public void postorderTraversal(TreeNode root, List<Integer> result) {
    if (root != null) {
        postorderTraversal(root.left, result);  // Left
        postorderTraversal(root.right, result); // Right
        result.add(root.val);                   // Root
    }
}
 
// Iterative inorder using stack
public List<Integer> inorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

Binary Search Tree Operations

// BST search - O(h) time where h is height
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);
}
 
// BST insertion - O(h) time
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;
}
 
// Validate BST - O(n) time, O(h) space
public boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}
 
private boolean validate(TreeNode node, Integer min, Integer max) {
    if (node == null) return true;
    if ((min != null && node.val <= min) || (max != null && node.val >= max)) {
        return false;
    }
    return validate(node.left, min, node.val) && validate(node.right, node.val, max);
}

Graph Representations & Traversals

// Adjacency list representation
Map<Integer, List<Integer>> adjList = new HashMap<>();
 
// DFS recursive - O(V + E) time, O(V) space
public void dfs(int node, Set<Integer> visited, Map<Integer, List<Integer>> graph) {
    visited.add(node);
    System.out.print(node + " ");
    
    for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited.contains(neighbor)) {
            dfs(neighbor, visited, graph);
        }
    }
}
 
// BFS using queue - O(V + E) time, O(V) space
public void bfs(int start, Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    
    visited.add(start);
    queue.offer(start);
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                queue.offer(neighbor);
            }
        }
    }
}
 
// Shortest path in unweighted graph using BFS
public int shortestPath(int[][] grid, int[] start, int[] target) {
    int m = grid.length, n = grid[0].length;
    boolean[][] visited = new boolean[m][n];
    Queue<int[]> queue = new LinkedList<>();
    
    queue.offer(new int[]{start[0], start[1], 0});  // {row, col, distance}
    visited[start[0]][start[1]] = true;
    
    int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};  // Up, Down, Left, Right
    
    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int row = curr[0], col = curr[1], dist = curr[2];
        
        if (row == target[0] && col == target[1]) {
            return dist;
        }
        
        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && 
                grid[newRow][newCol] != 1 && !visited[newRow][newCol]) {
                visited[newRow][newCol] = true;
                queue.offer(new int[]{newRow, newCol, dist + 1});
            }
        }
    }
    return -1;  // Path not found
}

Dynamic Programming

Classic DP Patterns & Examples

1. Fibonacci Sequence - Bottom-up Approach

// O(n) time, O(1) space
public int fibonacci(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

2. Longest Increasing Subsequence - O(n²) DP

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);  // Each element forms LIS of length 1
    
    int maxLength = 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);
            }
        }
        maxLength = Math.max(maxLength, dp[i]);
    }
    return maxLength;
}

3. Coin Change - Unbounded Knapsack

// Minimum coins to make amount - O(amount * coins) time
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // Initialize with impossible value
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

4. Longest Common Subsequence - 2D DP

// O(m * n) time and space
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] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

5. Maximum Subarray Sum - Kadane’s Algorithm

// O(n) time, O(1) space
public int maxSubArray(int[] nums) {
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}

Memoization Template

// Top-down DP with memoization
private Map<String, Integer> memo = new HashMap<>();
 
public int solveWithMemo(int[] params) {
    String key = Arrays.toString(params);  // Create unique key
    if (memo.containsKey(key)) return memo.get(key);
    
    // Base cases
    if (/* base condition */) return /* base value */;
    
    // Recursive calls
    int result = /* compute result using recursive calls */;
    memo.put(key, result);
    return result;
}

Sorting & Searching

Built-in Sorting

// Array sorting - O(n log n)
Arrays.sort(arr);                           // Primitive arrays
Arrays.sort(objArray);                      // Object arrays (must implement Comparable)
Arrays.sort(arr, Collections.reverseOrder()); // Reverse order for Integer[]
 
// Custom comparator
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  // Sort by first element
 
// List sorting
Collections.sort(list);
list.sort((a, b) -> a - b);                // Using lambda
list.sort(Comparator.comparingInt(x -> x)); // Method reference

Quick Sort Implementation

// O(n log n) average, O(n²) worst case
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;
}

Merge Sort Implementation

// O(n log n) time, O(n) space - stable 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);
}

Binary Search Variations

// Standard binary search - O(log n)
public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // Avoid overflow
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
 
// Find first occurrence (leftmost)
public int findFirst(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;  // Continue searching left
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}
 
// Find last occurrence (rightmost)
public int findLast(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;
            left = mid + 1;   // Continue searching right
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

Hash Tables & Sets

HashMap & HashSet Usage

// HashMap - O(1) average time for all operations
Map<String, Integer> map = new HashMap<>();
map.put("key", value);           // Insert/update
Integer val = map.get("key");    // Retrieve
boolean exists = map.containsKey("key");  // Check existence
map.remove("key");               // Delete
map.getOrDefault("key", 0);      // Get with default value
 
// Iterate over map
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}
 
// HashSet - O(1) average time for add, remove, contains
Set<Integer> set = new HashSet<>();
set.add(element);                // Add element
boolean exists = set.contains(element);  // Check membership
set.remove(element);             // Remove element

Common Hash Table Patterns

// Two Sum using HashMap - O(n) time, O(n) space
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();  // value -> index
    
    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[]{-1, -1};
}
 
// Group Anagrams - O(n * m log m) where n is number of strings, m is max length
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 = new String(chars);
        
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
    }
    
    return new ArrayList<>(map.values());
}
 
// Longest Substring Without Repeating Characters - Sliding Window + HashSet
public int lengthOfLongestSubstring(String s) {
    Set<Character> seen = new HashSet<>();
    int left = 0, maxLength = 0;
    
    for (int right = 0; right < s.length(); right++) {
        while (seen.contains(s.charAt(right))) {
            seen.remove(s.charAt(left));
            left++;
        }
        seen.add(s.charAt(right));
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

Mathematical Algorithms

Number Theory & Arithmetic

// GCD using Euclidean algorithm - O(log min(a, b))
public int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
 
// LCM using GCD
public int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
 
// Fast exponentiation - O(log n)
public long power(long base, long exp, long mod) {
    long result = 1;
    base %= mod;
    
    while (exp > 0) {
        if ((exp & 1) == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}
 
// Check if number is prime - O(√n)
public boolean isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}
 
// Sieve of Eratosthenes - find all primes up to n - O(n log log n)
public List<Integer> sieveOfEratosthenes(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;
            }
        }
    }
    
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) primes.add(i);
    }
    return primes;
}

Bit Manipulation

// Basic bit operations
int setBit = n | (1 << i);        // Set i-th bit
int clearBit = n & ~(1 << i);     // Clear i-th bit
int toggleBit = n ^ (1 << i);     // Toggle i-th bit
boolean isSet = (n & (1 << i)) != 0;  // Check if i-th bit is set
 
// Count set bits (Brian Kernighan's algorithm) - O(number of set bits)
public int countSetBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);  // Remove rightmost set bit
        count++;
    }
    return count;
}
 
// Find single number (all others appear twice) - O(n) time, O(1) space
public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;  // XOR cancels out pairs
    }
    return result;
}
 
// Check if power of 2 - O(1)
public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Common Patterns & Tricks

Prefix Sum Technique

// Range sum queries in O(1) after O(n) preprocessing
class PrefixSum {
    private int[] prefixSum;
    
    public PrefixSum(int[] nums) {
        prefixSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }
    
    public int rangeSum(int left, int right) {  // Both inclusive
        return prefixSum[right + 1] - prefixSum[left];
    }
}
 
// Subarray sum equals K - O(n) time using prefix sum + HashMap
public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixSumCount = new HashMap<>();
    prefixSumCount.put(0, 1);  // Empty subarray has sum 0
    
    int count = 0, prefixSum = 0;
    for (int num : nums) {
        prefixSum += num;
        count += prefixSumCount.getOrDefault(prefixSum - k, 0);
        prefixSumCount.put(prefixSum, prefixSumCount.getOrDefault(prefixSum, 0) + 1);
    }
    return count;
}

Union-Find (Disjoint Set)

// Efficient for connectivity problems - O(α(n)) per operation with path compression
class UnionFind {
    private int[] parent, rank;
    private int components;
    
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        components = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // Path compression
        }
        return parent[x];
    }
    
    public boolean union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        
        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        components--;
        return true;
    }
    
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
    
    public int getComponents() {
        return components;
    }
}

Backtracking Template

// General backtracking pattern for permutations/combinations
public List<List<Integer>> backtrack(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    
    backtrackHelper(nums, path, used, result);
    return result;
}
 
private void backtrackHelper(int[] nums, List<Integer> path, 
                           boolean[] used, List<List<Integer>> result) {
    // Base case - valid solution found
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));  // Make copy!
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;  // Skip used elements
        
        // Make choice
        path.add(nums[i]);
        used[i] = true;
        
        // Recurse
        backtrackHelper(nums, path, used, result);
        
        // Backtrack (undo choice)
        path.remove(path.size() - 1);
        used[i] = false;
    }
}
 
// N-Queens problem example
public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(board[i], '.');
    }
    
    backtrackQueens(board, 0, result);
    return result;
}
 
private void backtrackQueens(char[][] board, int row, List<List<String>> result) {
    if (row == board.length) {
        result.add(constructBoard(board));
        return;
    }
    
    for (int col = 0; col < board.length; col++) {
        if (isValidQueenPlacement(board, row, col)) {
            board[row][col] = 'Q';
            backtrackQueens(board, row + 1, result);
            board[row][col] = '.';  // Backtrack
        }
    }
}
 
private boolean isValidQueenPlacement(char[][] board, int row, int col) {
    int n = board.length;
    
    // Check column
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    
    // Check diagonal (top-left to bottom-right)
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    
    // Check diagonal (top-right to bottom-left)
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    
    return true;
}

Important Constants & Limits

// Integer limits
int maxInt = Integer.MAX_VALUE;      // 2,147,483,647 (2^31 - 1)
int minInt = Integer.MIN_VALUE;      // -2,147,483,648 (-2^31)
long maxLong = Long.MAX_VALUE;       // 9,223,372,036,854,775,807 (2^63 - 1)
 
// Common modulo for large number problems
final int MOD = 1_000_000_007;
 
// Direction vectors for grid traversal
int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};  // Up, Down, Left, Right
int[][] diagonals = {{-1,-1}, {-1,1}, {1,-1}, {1,1}}; // Four diagonals
 
// For 8-directional movement (including diagonals)
int[][] eightDirections = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, 
                          {0,1}, {1,-1}, {1,0}, {1,1}};

Performance Tips & Best Practices

Time Complexity Quick Reference

  • Constant: O(1) - Hash table operations, array access
  • Logarithmic: O(log n) - Binary search, balanced tree operations
  • Linear: O(n) - Single loop, linear search
  • Linearithmic: O(n log n) - Efficient sorting, divide & conquer
  • Quadratic: O(n²) - Nested loops, bubble sort
  • Exponential: O(2ⁿ) - Naive recursive solutions, subset generation

Memory Optimization

// Use primitive collections when possible (avoid autoboxing)
// TIntArrayList instead of ArrayList<Integer> (if using external libraries)
 
// Reuse objects to avoid GC pressure
StringBuilder sb = new StringBuilder();  // Reuse instead of creating new ones
 
// Use arrays instead of ArrayList when size is known
int[] arr = new int[n];  // More memory efficient than ArrayList<Integer>
 
// Clear collections after use in long-running algorithms
map.clear();
list.clear();

Common Pitfalls to Avoid

  1. Integer Overflow: Use long for large calculations
  2. Array Index Bounds: Always check i < arr.length
  3. Null Pointer: Check for null before dereferencing
  4. Infinite Loops: Ensure loop variables are updated correctly
  5. Stack Overflow: Limit recursion depth, use iterative solutions when possible
  6. Off-by-One Errors: Be careful with array indices and loop bounds

Quick Debug Tips

// Print array contents
System.out.println(Arrays.toString(arr));
 
// Print 2D array
for (int[] row : matrix) {
    System.out.println(Arrays.toString(row));
}
 
// Assert for testing assumptions
assert condition : "Error message";
 
// Use meaningful variable names and add comments for complex logic

Advanced Topics & Patterns

Heap (Priority Queue) Operations

// Min-heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
 
// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
 
// Custom comparator for objects
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
 
// Top K elements pattern - O(n log k)
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
        count.put(num, count.getOrDefault(num, 0) + 1);
    }
    
    PriorityQueue<Integer> heap = new PriorityQueue<>(
        (a, b) -> count.get(a) - count.get(b)  // Min heap by frequency
    );
    
    for (int num : count.keySet()) {
        heap.offer(num);
        if (heap.size() > k) {
            heap.poll();
        }
    }
    
    return heap.stream().mapToInt(i -> i).toArray();
}
 
// Merge K sorted lists using heap - O(n log k)
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
    
    for (ListNode list : lists) {
        if (list != null) heap.offer(list);
    }
    
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        curr.next = node;
        curr = curr.next;
        
        if (node.next != null) {
            heap.offer(node.next);
        }
    }
    
    return dummy.next;
}

Trie (Prefix Tree) Implementation

// Trie for word storage and prefix search
class TrieNode {
    TrieNode[] children = new TrieNode[26];  // For lowercase letters
    boolean isWord = false;
}
 
class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    // Insert word - O(m) where m is word length
    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (curr.children[index] == null) {
                curr.children[index] = new TrieNode();
            }
            curr = curr.children[index];
        }
        curr.isWord = true;
    }
    
    // Search word - O(m)
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isWord;
    }
    
    // Check if prefix exists - O(m)
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
    
    private TrieNode searchPrefix(String prefix) {
        TrieNode curr = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (curr.children[index] == null) {
                return null;
            }
            curr = curr.children[index];
        }
        return curr;
    }
}

Segment Tree for Range Queries

// Segment tree for range sum queries with updates - O(log n) per operation
class SegmentTree {
    private int[] tree;
    private int n;
    
    public SegmentTree(int[] nums) {
        n = nums.length;
        tree = new int[4 * n];
        build(nums, 0, 0, n - 1);
    }
    
    private void build(int[] nums, int node, int start, int end) {
        if (start == end) {
            tree[node] = nums[start];
        } else {
            int mid = start + (end - start) / 2;
            build(nums, 2 * node + 1, start, mid);
            build(nums, 2 * node + 2, mid + 1, end);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }
    
    public void update(int idx, int val) {
        update(0, 0, n - 1, idx, val);
    }
    
    private void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = start + (end - start) / 2;
            if (idx <= mid) {
                update(2 * node + 1, start, mid, idx, val);
            } else {
                update(2 * node + 2, mid + 1, end, idx, val);
            }
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }
    
    public int query(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }
    
    private int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;  // No overlap
        if (l <= start && end <= r) return tree[node];  // Complete overlap
        
        // Partial overlap
        int mid = start + (end - start) / 2;
        return query(2 * node + 1, start, mid, l, r) + 
               query(2 * node + 2, mid + 1, end, l, r);
    }
}

Topological Sort (Kahn’s Algorithm)

// Topological sort for DAG - O(V + E)
public int[] topologicalSort(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] indegree = new int[numCourses];
    
    // Initialize graph
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    
    // Build graph and calculate indegrees
    for (int[] pre : prerequisites) {
        graph.get(pre[1]).add(pre[0]);  // pre[1] -> pre[0]
        indegree[pre[0]]++;
    }
    
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    int[] result = new int[numCourses];
    int index = 0;
    
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result[index++] = node;
        
        for (int neighbor : graph.get(node)) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }
    
    return index == numCourses ? result : new int[0];  // Check for cycle
}

Advanced String Algorithms

KMP (Knuth-Morris-Pratt) Pattern Matching

// KMP string matching - O(n + m) where n is text length, m is pattern length
public int strStr(String haystack, String needle) {
    if (needle.isEmpty()) return 0;
    
    int[] lps = computeLPS(needle);
    int i = 0, j = 0;
    
    while (i < haystack.length()) {
        if (haystack.charAt(i) == needle.charAt(j)) {
            i++;
            j++;
        }
        
        if (j == needle.length()) {
            return i - j;  // Found pattern
        } else if (i < haystack.length() && haystack.charAt(i) != needle.charAt(j)) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}
 
// Compute Longest Prefix Suffix array
private 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)) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

Dijkstra’s Shortest Path Algorithm

// Single-source shortest path - O((V + E) log V)
public int[] dijkstra(int[][] graph, int src) {
    int n = graph.length;
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);  // {node, distance}
    pq.offer(new int[]{src, 0});
    boolean[] visited = new boolean[n];
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int u = curr[0];
        
        if (visited[u]) continue;
        visited[u] = true;
        
        for (int v = 0; v < n; v++) {
            if (graph[u][v] != 0 && !visited[v]) {  // Edge exists
                int newDist = dist[u] + graph[u][v];
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    pq.offer(new int[]{v, newDist});
                }
            }
        }
    }
    return dist;
}

Matrix Manipulation Patterns

// Rotate matrix 90 degrees clockwise - O(n²) time, O(1) space
public void rotate(int[][] matrix) {
    int n = matrix.length;
    
    // Transpose
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    
    // Reverse each row
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n / 2; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][n - 1 - j];
            matrix[i][n - 1 - j] = temp;
        }
    }
}
 
// Spiral matrix traversal - O(m * n)
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix.length == 0) return result;
    
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    
    while (top <= bottom && left <= right) {
        // Traverse right
        for (int col = left; col <= right; col++) {
            result.add(matrix[top][col]);
        }
        top++;
        
        // Traverse down
        for (int row = top; row <= bottom; row++) {
            result.add(matrix[row][right]);
        }
        right--;
        
        // Traverse left
        if (top <= bottom) {
            for (int col = right; col >= left; col--) {
                result.add(matrix[bottom][col]);
            }
            bottom--;
        }
        
        // Traverse up
        if (left <= right) {
            for (int row = bottom; row >= top; row--) {
                result.add(matrix[row][left]);
            }
            left++;
        }
    }
    return result;
}

Interval Problems

// Merge overlapping intervals - O(n log n)
public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;
    
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    
    for (int[] interval : intervals) {
        if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
            merged.add(interval);  // No overlap
        } else {
            // Overlap - merge intervals
            merged.get(merged.size() - 1)[1] = 
                Math.max(merged.get(merged.size() - 1)[1], interval[1]);
        }
    }
    
    return merged.toArray(new int[merged.size()][]);
}
 
// Insert new interval - O(n)
public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0;
    
    // Add all intervals before newInterval
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i]);
        i++;
    }
    
    // Merge overlapping intervals with newInterval
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval);
    
    // Add remaining intervals
    while (i < intervals.length) {
        result.add(intervals[i]);
        i++;
    }
    
    return result.toArray(new int[result.size()][]);
}

LRU Cache Implementation

// LRU Cache using HashMap + Doubly Linked List - O(1) for all operations
class LRUCache {
    class DLLNode {
        int key, value;
        DLLNode prev, next;
        
        DLLNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private Map<Integer, DLLNode> cache = new HashMap<>();
    private int capacity;
    private DLLNode head, tail;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new DLLNode(0, 0);
        tail = new DLLNode(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        DLLNode node = cache.get(key);
        if (node == null) return -1;
        
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DLLNode node = cache.get(key);
        
        if (node == null) {
            DLLNode newNode = new DLLNode(key, value);
            
            if (cache.size() >= capacity) {
                DLLNode tail = removeTail();
                cache.remove(tail.key);
            }
            
            cache.put(key, newNode);
            addToHead(newNode);
        } else {
            node.value = value;
            moveToHead(node);
        }
    }
    
    private void addToHead(DLLNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    private void removeNode(DLLNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void moveToHead(DLLNode node) {
        removeNode(node);
        addToHead(node);
    }
    
    private DLLNode removeTail() {
        DLLNode lastNode = tail.prev;
        removeNode(lastNode);
        return lastNode;
    }
}

Graph View