Java DSA Cheat Sheet
Basic Syntax & Input/Output
Main Method & Imports
import java.util.*;
import java.io.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Your code here
sc.close();
}
}
Input/Output
// Scanner input
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String s = sc.nextLine();
String word = sc.next();
// Fast I/O for competitive programming
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String line = br.readLine();
int num = Integer.parseInt(br.readLine());
bw.write("Result: " + result + "\n");
bw.flush();
// Output
System.out.println("Hello");
System.out.print("No newline");
System.out.printf("%d %.2f %s\n", num, decimal, string);
Data Types & Operations
Primitive Types
int i = 42; // 32-bit: -2^31 to 2^31-1
long l = 42L; // 64-bit: -2^63 to 2^63-1
double d = 3.14; // 64-bit floating point
char c = 'A'; // 16-bit Unicode
boolean b = true; // true/false
// Constants
final int MAX_SIZE = 1000;
String Operations
String s = "hello";
int len = s.length();
char ch = s.charAt(0);
String sub = s.substring(1, 4); // "ell"
String[] parts = s.split(" ");
String joined = String.join(",", parts);
// String comparison
s1.equals(s2); // Content equality
s1.compareTo(s2); // Lexicographic comparison
// StringBuilder (mutable)
StringBuilder sb = new StringBuilder();
sb.append("text");
sb.insert(0, "prefix");
sb.deleteCharAt(0);
String result = sb.toString();
Math Operations
Math.max(a, b);
Math.min(a, b);
Math.abs(x);
Math.pow(base, exp);
Math.sqrt(x);
Math.ceil(x);
Math.floor(x);
Math.log(x); // Natural log
Math.log10(x); // Base 10 log
// Integer operations
Integer.MAX_VALUE; // 2147483647
Integer.MIN_VALUE; // -2147483648
Integer.parseInt("123");
String.valueOf(123);
Arrays
1D Arrays
// Declaration and initialization
int[] arr = new int[5];
int[] arr = {1, 2, 3, 4, 5};
int[] arr = new int[]{1, 2, 3, 4, 5};
// Operations
int len = arr.length;
Arrays.fill(arr, -1); // Fill with value
Arrays.sort(arr); // Sort ascending
Arrays.sort(arr, Collections.reverseOrder()); // Sort descending (Integer[] needed)
// Binary search (array must be sorted)
int index = Arrays.binarySearch(arr, target);
// Copy array
int[] copy = Arrays.copyOf(arr, arr.length);
int[] copy = arr.clone();
2D Arrays
// Declaration
int[][] matrix = new int[rows][cols];
int[][] matrix = {{1,2,3}, {4,5,6}};
// Jagged arrays
int[][] jagged = new int[3][];
jagged[0] = new int[2];
jagged[1] = new int[4];
// Iteration
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[i].length; j++) {
// matrix[i][j]
}
}
// Enhanced for loop
for(int[] row : matrix) {
for(int val : row) {
// val
}
}
Collections Framework
ArrayList
ArrayList<Integer> list = new ArrayList<>();
list.add(1); // Add element
list.add(0, 5); // Add at index
list.get(0); // Get element
list.set(0, 10); // Set element
list.remove(0); // Remove by index
list.remove(Integer.valueOf(5)); // Remove by value
list.size(); // Size
list.isEmpty(); // Check if empty
list.contains(5); // Check if contains
// Convert to array
Integer[] array = list.toArray(new Integer[0]);
// Sorting
Collections.sort(list);
Collections.sort(list, Collections.reverseOrder());
LinkedList
LinkedList<Integer> ll = new LinkedList<>();
ll.addFirst(1);
ll.addLast(2);
ll.removeFirst();
ll.removeLast();
ll.peekFirst(); // Get first without removing
ll.peekLast(); // Get last without removing
Stack
Stack<Integer> stack = new Stack<>();
stack.push(1); // Add to top
int top = stack.pop(); // Remove and return top
int peek = stack.peek(); // Get top without removing
boolean empty = stack.isEmpty();
// Alternative: Use ArrayDeque
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.pop();
stack.peek();
Queue
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // Add to rear
int front = queue.poll(); // Remove and return front
int peek = queue.peek(); // Get front without removing
boolean empty = queue.isEmpty();
// Priority Queue (Min Heap by default)
PriorityQueue<Integer> pq = new PriorityQueue<>();
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
pq.offer(5);
pq.offer(1);
pq.offer(3);
int min = pq.poll(); // Returns 1
// Custom comparator
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
Deque (Double-ended Queue)
ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
deque.removeFirst();
deque.removeLast();
deque.peekFirst();
deque.peekLast();
HashSet
HashSet<Integer> set = new HashSet<>();
set.add(1);
set.remove(1);
boolean contains = set.contains(1);
int size = set.size();
// LinkedHashSet maintains insertion order
LinkedHashSet<Integer> linkedSet = new LinkedHashSet<>();
// TreeSet (sorted)
TreeSet<Integer> treeSet = new TreeSet<>();
int first = treeSet.first();
int last = treeSet.last();
HashMap
HashMap<String, Integer> map = new HashMap<>();
map.put("key", 1); // Add/update
int value = map.get("key"); // Get value
int value = map.getOrDefault("key", 0); // Get with default
boolean hasKey = map.containsKey("key");
boolean hasValue = map.containsValue(1);
map.remove("key");
// Iteration
for(String key : map.keySet()) {
int val = map.get(key);
}
for(Map.Entry<String, Integer> entry : map.entrySet()) {
String key = entry.getKey();
int value = entry.getValue();
}
// TreeMap (sorted by keys)
TreeMap<String, Integer> treeMap = new TreeMap<>();
String firstKey = treeMap.firstKey();
String lastKey = treeMap.lastKey();
Common DSA Patterns
Two Pointers
// Array two pointers
int left = 0, right = arr.length - 1;
while(left < right) {
if(condition) {
left++;
} else {
right--;
}
}
// Fast and slow pointers (Floyd's algorithm)
int slow = 0, fast = 0;
while(fast < n && fast + 1 < n) {
slow++;
fast += 2;
}
Sliding Window
int left = 0;
for(int right = 0; right < arr.length; right++) {
// Add arr[right] to window
while(windowNotValid) {
// Remove arr[left] from window
left++;
}
// Process current window [left, right]
}
Binary Search
// Template for binary search
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;
}
}
// Find leftmost/rightmost position
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;
}
DFS (Depth-First Search)
// Recursive DFS
void dfs(int[][] grid, int row, int col, boolean[][] visited) {
if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length ||
visited[row][col]) {
return;
}
visited[row][col] = true;
// Process current cell
// Visit neighbors
dfs(grid, row + 1, col, visited);
dfs(grid, row - 1, col, visited);
dfs(grid, row, col + 1, visited);
dfs(grid, row, col - 1, visited);
}
// Iterative DFS using stack
Stack<int[]> stack = new Stack<>();
stack.push(new int[]{startRow, startCol});
while(!stack.isEmpty()) {
int[] current = stack.pop();
int row = current[0], col = current[1];
if(visited[row][col]) continue;
visited[row][col] = true;
// Add neighbors to stack
// stack.push(new int[]{newRow, newCol});
}
BFS (Breadth-First Search)
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{startRow, startCol});
visited[startRow][startCol] = true;
int level = 0;
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
int[] current = queue.poll();
int row = current[0], col = current[1];
// Process current cell
// Add unvisited neighbors
int[][] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
for(int[] dir : directions) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if(isValid(newRow, newCol) && !visited[newRow][newCol]) {
visited[newRow][newCol] = true;
queue.offer(new int[]{newRow, newCol});
}
}
}
level++;
}
Union-Find (Disjoint Set)
class UnionFind {
int[] parent, rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for(int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
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]++;
}
return true;
}
}
Trie (Prefix Tree)
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd = false;
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
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.isEnd = true;
}
public boolean search(String word) {
TrieNode curr = root;
for(char c : word.toCharArray()) {
int index = c - 'a';
if(curr.children[index] == null) return false;
curr = curr.children[index];
}
return curr.isEnd;
}
}
Dynamic Programming
Common DP Patterns
// 1D DP
int[] dp = new int[n + 1];
dp[0] = base_case;
for(int i = 1; i <= n; i++) {
dp[i] = // transition from previous states
}
// 2D DP
int[][] dp = new int[m + 1][n + 1];
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
if(i == 0 || j == 0) {
dp[i][j] = base_case;
} else {
dp[i][j] = // transition
}
}
}
// Memoization (Top-down)
Map<String, Integer> memo = new HashMap<>();
int solve(int i, int j) {
String key = i + "," + j;
if(memo.containsKey(key)) return memo.get(key);
// Base cases
if(i == 0 || j == 0) return base_case;
int result = // recursive calls
memo.put(key, result);
return result;
}
Useful Utilities
Comparators
// Sort array of arrays by first element
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
// Sort in descending order
Arrays.sort(arr, (a, b) -> b - a);
// Multiple criteria sorting
Arrays.sort(people, (a, b) -> {
if(a[0] == b[0]) return a[1] - b[1]; // Secondary sort
return a[0] - b[0]; // Primary sort
});
// Custom object sorting
Collections.sort(list, new Comparator<Person>() {
public int compare(Person a, Person b) {
return a.age - b.age;
}
});
Bit Manipulation
// Common 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
// Useful tricks
int rightmostSetBit = n & (-n); // Get rightmost set bit
int clearRightmostSetBit = n & (n-1); // Clear rightmost set bit
boolean isPowerOfTwo = n > 0 && (n & (n-1)) == 0;
int countSetBits = Integer.bitCount(n);
import java.util.*;
import java.util.stream.*;
/**
* Java Tips and Tricks for Data Structures and Algorithms
* Essential patterns and shortcuts for coding interviews
*/
public class JavaDSATips {
// ================== 1. STRING MANIPULATION TRICKS ==================
public static void stringTricks() {
System.out.println("=== STRING TRICKS ===");
// Convert string to char array (most common)
String s = "hello";
char[] chars = s.toCharArray();
// Convert char array back to string
String result = new String(chars);
// String to integer conversion
String num = "123";
int number = Integer.parseInt(num);
// Character to digit conversion
char ch = '5';
int digit = ch - '0'; // Result: 5
// Digit to character conversion
int d = 7;
char character = (char) (d + '0'); // Result: '7'
// Check if character is alphanumeric
char c = 'A';
boolean isAlphaNumeric = Character.isLetterOrDigit(c);
boolean isDigit = Character.isDigit(c);
boolean isLetter = Character.isLetter(c);
// String comparison (lexicographical)
String str1 = "abc", str2 = "def";
int comparison = str1.compareTo(str2); // negative if str1 < str2
// Reverse a string using StringBuilder
String original = "hello";
String reversed = new StringBuilder(original).reverse().toString();
// Check if string is palindrome
String palindrome = "racecar";
boolean isPalindrome = palindrome.equals(new StringBuilder(palindrome).reverse().toString());
System.out.println("Original: " + original + ", Reversed: " + reversed);
System.out.println("Is palindrome: " + isPalindrome);
}
// ================== 2. ARRAY MANIPULATION TRICKS ==================
public static void arrayTricks() {
System.out.println("\n=== ARRAY TRICKS ===");
// Initialize array with specific value
int[] arr = new int[5];
Arrays.fill(arr, -1); // Fill with -1
// 2D array initialization
int[][] matrix = new int[3][4];
for (int[] row : matrix) {
Arrays.fill(row, Integer.MAX_VALUE);
}
// Copy array
int[] original = {1, 2, 3, 4, 5};
int[] copy = Arrays.copyOf(original, original.length);
int[] subArray = Arrays.copyOfRange(original, 1, 4); // [2, 3, 4]
// Sort array
Arrays.sort(original);
// Sort in descending order
Integer[] boxed = {5, 2, 8, 1, 9};
Arrays.sort(boxed, Collections.reverseOrder());
// Binary search (array must be sorted)
int[] sorted = {1, 3, 5, 7, 9};
int index = Arrays.binarySearch(sorted, 5); // Returns index or negative if not found
// Convert array to list
List<Integer> list = Arrays.asList(boxed);
// Find min and max in array
int min = Arrays.stream(sorted).min().orElse(Integer.MAX_VALUE);
int max = Arrays.stream(sorted).max().orElse(Integer.MIN_VALUE);
// Two pointers technique setup
int left = 0, right = sorted.length - 1;
while (left < right) {
// Process logic here
left++;
right--;
}
System.out.println("Subarray: " + Arrays.toString(subArray));
System.out.println("Min: " + min + ", Max: " + max);
}
// ================== 3. COLLECTIONS SHORTCUTS ==================
public static void collectionTricks() {
System.out.println("\n=== COLLECTION TRICKS ===");
// List initialization shortcuts
List<Integer> list1 = Arrays.asList(1, 2, 3, 4, 5);
List<Integer> list2 = new ArrayList<>(Arrays.asList(1, 2, 3));
List<String> list3 = List.of("a", "b", "c"); // Java 9+ (immutable)
// Set initialization
Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3));
Set<String> set2 = Set.of("x", "y", "z"); // Java 9+ (immutable)
// Map initialization
Map<String, Integer> map = Map.of("a", 1, "b", 2, "c", 3); // Java 9+
// Traditional map initialization
Map<Character, Integer> charCount = new HashMap<>();
String text = "hello";
for (char c : text.toCharArray()) {
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
// Using computeIfAbsent for nested structures
Map<String, List<String>> groupMap = new HashMap<>();
groupMap.computeIfAbsent("key1", k -> new ArrayList<>()).add("value1");
// Priority Queue (Min Heap by default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Priority Queue (Max Heap)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// Custom comparator
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // Sort by second element
// Deque as stack and queue
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // Add to top
stack.pop(); // Remove from top
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // Add to rear
queue.poll(); // Remove from front
System.out.println("Character count: " + charCount);
}
// ================== 4. MATHEMATICAL TRICKS ==================
public static void mathTricks() {
System.out.println("\n=== MATH TRICKS ===");
// GCD and LCM
int a = 12, b = 18;
int gcd = gcd(a, b);
int lcm = (a * b) / gcd;
// Check if number is prime
boolean isPrime = isPrime(17);
// Generate all divisors
List<Integer> divisors = getDivisors(12);
// Check if power of 2
boolean isPowerOf2 = isPowerOfTwo(16);
// Bit manipulation tricks
int n = 5; // Binary: 101
// Check if i-th bit is set
boolean isBitSet = (n & (1 << 2)) != 0; // Check 2nd bit
// Set i-th bit
int setBit = n | (1 << 1); // Set 1st bit
// Clear i-th bit
int clearBit = n & ~(1 << 0); // Clear 0th bit
// Toggle i-th bit
int toggleBit = n ^ (1 << 1); // Toggle 1st bit
// Count set bits
int setBits = Integer.bitCount(n);
// Find rightmost set bit
int rightmostSetBit = n & -n;
System.out.println("GCD: " + gcd + ", LCM: " + lcm);
System.out.println("Is prime: " + isPrime);
System.out.println("Divisors: " + divisors);
System.out.println("Set bits: " + setBits);
}
// ================== 5. GRAPH ALGORITHMS SETUP ==================
public static void graphTricks() {
System.out.println("\n=== GRAPH TRICKS ===");
// Adjacency List representation
int n = 5; // number of nodes
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
// Add edge
int u = 0, v = 1;
adj.get(u).add(v);
adj.get(v).add(u); // For undirected graph
// BFS setup
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
queue.offer(0);
visited[0] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
// DFS setup
boolean[] vis = new boolean[n];
dfs(0, adj, vis);
// Directions array for 2D grid
int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}}; // up, down, left, right
int[][] directions8 = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}}; // 8 directions
System.out.println("Graph setup complete");
}
// ================== 6. TREE ALGORITHMS ==================
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
public static void treeTricks() {
System.out.println("\n=== TREE TRICKS ===");
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
// Inorder traversal (iterative)
List<Integer> inorder = inorderTraversal(root);
// Level order traversal
List<List<Integer>> levelOrder = levelOrderTraversal(root);
// Tree height
int height = getHeight(root);
System.out.println("Inorder: " + inorder);
System.out.println("Height: " + height);
}
// ================== 7. SORTING AND SEARCHING TRICKS ==================
public static void sortingTricks() {
System.out.println("\n=== SORTING TRICKS ===");
// Custom sorting
int[][] intervals = {{1,3}, {2,6}, {8,10}, {15,18}};
// Sort by start time
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// Sort by end time
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
// Sort strings by length
String[] words = {"apple", "pie", "washington", "book"};
Arrays.sort(words, (a, b) -> a.length() - b.length());
// Sort with multiple criteria
Arrays.sort(intervals, (a, b) -> {
if (a[0] != b[0]) return a[0] - b[0]; // First by start time
return a[1] - b[1]; // Then by end time
});
// Binary search variations
int[] arr = {1, 2, 2, 2, 3, 4, 5};
int target = 2;
// Find leftmost occurrence
int leftmost = findLeftmost(arr, target);
// Find rightmost occurrence
int rightmost = findRightmost(arr, target);
System.out.println("Leftmost index of " + target + ": " + leftmost);
System.out.println("Rightmost index of " + target + ": " + rightmost);
}
// ================== 8. DYNAMIC PROGRAMMING PATTERNS ==================
public static void dpTricks() {
System.out.println("\n=== DP TRICKS ===");
// 1D DP initialization
int n = 10;
int[] dp = new int[n + 1];
Arrays.fill(dp, -1); // For memoization
// 2D DP initialization
int m = 5;
int[][] dp2d = new int[n][m];
for (int[] row : dp2d) {
Arrays.fill(row, -1);
}
// Fibonacci example (bottom-up)
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
// Space optimization technique
int prev2 = 0, prev1 = 1, curr = 0;
for (int i = 2; i <= n; i++) {
curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
System.out.println("10th Fibonacci: " + dp[n]);
}
// ================== 9. UTILITY HELPER METHODS ==================
// GCD using Euclidean algorithm
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// Check if number is prime
public static 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;
}
// Get all divisors
public static List<Integer> getDivisors(int n) {
List<Integer> divisors = new ArrayList<>();
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
divisors.add(i);
if (i != n / i) {
divisors.add(n / i);
}
}
}
Collections.sort(divisors);
return divisors;
}
// Check if power of 2
public static boolean isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
// DFS helper
public static void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, adj, visited);
}
}
}
// Tree traversal helpers
public static List<Integer> inorderTraversal(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;
}
public static List<List<Integer>> levelOrderTraversal(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;
}
public static int getHeight(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
// Binary search variants
public static int findLeftmost(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;
}
public static int findRightmost(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;
}
// ================== 10. COMMON PATTERNS & TEMPLATES ==================
public static void commonPatterns() {
System.out.println("\n=== COMMON PATTERNS ===");
// Sliding window pattern
String s = "abcabcbb";
int maxLength = longestSubstringWithoutRepeating(s);
// Two sum pattern
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] twoSumResult = twoSum(nums, target);
// Fast and slow pointers (Floyd's cycle detection)
// Useful for linked lists and arrays
System.out.println("Longest substring length: " + maxLength);
System.out.println("Two sum result: " + Arrays.toString(twoSumResult));
}
// Sliding window example
public static int longestSubstringWithoutRepeating(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;
}
// Two sum with HashMap
public static 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];
}
// ================== MAIN METHOD ==================
public static void main(String[] args) {
stringTricks();
arrayTricks();
collectionTricks();
mathTricks();
graphTricks();
treeTricks();
sortingTricks();
dpTricks();
commonPatterns();
System.out.println("\n=== QUICK REFERENCE COMPLETED ===");
System.out.println("Remember: Practice these patterns until they become muscle memory!");
}
}
Common Edge Cases to Consider
- Empty arrays/strings
- Single element arrays
- Integer overflow (use
longwhen needed) - Null inputs
- Negative numbers
- Duplicate elements
- Array bounds checking