JAVA DSA Cheat Sheet

// Init
int[] arr = new int[20];
int[] arr = new int[]{ 1,2,3,4,5 };
int[][] grid = new int[10][10];
 
// Fill
Arrays.fill(arr, 10);
 
// Sort
Arrays.sort(arr);                              // ASC
Arrays.sort(arr, Collections.reverseOrder());  // DESC — requires Integer[], not int[]
 
// Reverse
Collections.reverse(Arrays.asList(arr));
 
// Copy
int[] copy  = Arrays.copyOf(arr, arr.length);
int[] slice = Arrays.copyOfRange(arr, 1, 4);  // indices [1, 4)
 
// Binary search (array must be sorted first)
int idx = Arrays.binarySearch(arr, target);   // returns index, or negative if not found

// Init
List<Integer> list = new ArrayList<>();
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
 
// 2D list
List<List<String>> grid = new ArrayList<>();
for (int i = 0; i < n; i++) grid.add(new ArrayList<>());

// Sorting
list.sort(Comparator.naturalOrder());
list.sort(Comparator.reverseOrder());
Collections.sort(list);
Collections.sort(list, Collections.reverseOrder());
list.sort((a, b) -> a[0] - b[0]);   // custom comparator

LinkedList<String> ll = new LinkedList<>();

// Prefer Deque over Stack (Stack extends Vector — synchronized, slow)
Deque<Integer> stack = new ArrayDeque<>();

Queue<Integer> q = new ArrayDeque<>();  // faster than LinkedList in practice

Deque<Integer> dq = new ArrayDeque<>();

// Min-heap (default — smallest at top)
PriorityQueue<Integer> minH = new PriorityQueue<>();
 
// Max-heap
PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());
 
// Custom comparator — sort int[] by index 1
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // min-heap on [1]
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]); // max-heap on [1]

// Top K largest elements — maintain a min-heap of size K
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
    pq.offer(num);
    if (pq.size() > k) pq.poll();  // evict smallest
}
// pq.peek() == kth largest
 
// Top K frequent elements
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
 
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
    pq.offer(new int[]{e.getKey(), e.getValue()});
    if (pq.size() > k) pq.poll();
}

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

// Iterate
for (Map.Entry<String, Integer> e : map.entrySet()) {
    String k = e.getKey();
    int v = e.getValue();
}
 
// computeIfAbsent — creates value if key absent (use for nested structures)
map.computeIfAbsent(key, k -> new ArrayList<>()).add(item);
 
// Frequency count — two equivalent ways
map.merge(num, 1, Integer::sum);
map.put(num, map.getOrDefault(num, 0) + 1);

Map<String, Integer> tm = new TreeMap<>();                           // ASC
Map<String, Integer> tm = new TreeMap<>(Collections.reverseOrder()); // DESC

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

// Set operations (all modify set1 in-place)
set1.retainAll(set2);  // intersection
set1.addAll(set2);     // union
set1.removeAll(set2);  // difference

TreeSet<Integer> ts = new TreeSet<>();                             // ASC
TreeSet<Integer> ts = new TreeSet<>(Comparator.reverseOrder());   // DESC

StringBuilder sb = new StringBuilder();
StringBuilder sb = new StringBuilder("hello");

// Conversions
String s = String.valueOf(42);       // int → String
int n    = Integer.parseInt("42");   // String → int
 
// Char frequency (a-z only)
int[] freq = new int[26];
for (char c : s.toCharArray())
    freq[c - 'a']++;
 
// Useful String methods
s.substring(i, j)                   // [i, j)
s.toLowerCase() / s.toUpperCase()
s.trim()                             // strip leading/trailing whitespace
s.replace('a', 'b')
s.contains("abc")
s.startsWith("ab") / s.endsWith("cd")
s.equals(other)                      // content equality — never use ==
s.compareTo(other)                   // lexicographic comparison
String.join("-", "a", "b", "c")     // "a-b-c"
String.valueOf(charArray)            // char[] → String

// Core operations
a & b      // AND
a | b      // OR
a ^ b      // XOR
~a         // bitwise NOT
a << n     // left shift  (× 2^n)
a >> n     // signed right shift (÷ 2^n)
a >>> n    // unsigned right shift

// Essential tricks
x & 1                    // 1 = odd, 0 = even
x & (x - 1)             // clear lowest set bit
x == 0                   // true only if x is 0 after above → x was power of 2
(x >> n) & 1             // get nth bit (0-indexed from right)
x | (1 << n)             // set nth bit
x & ~(1 << n)            // clear nth bit
x ^ (1 << n)             // toggle nth bit
Integer.bitCount(x)      // number of set bits (popcount)
Integer.highestOneBit(x) // value of highest set bit
 
// XOR identity: a ^ a = 0, a ^ 0 = a
// → find single non-duplicate where all others appear twice
int result = 0;
for (int n : nums) result ^= n;
 
// Power of 2 check
boolean isPow2 = n > 0 && (n & (n - 1)) == 0;
 
// Enumerate all subsets of n elements (bitmask)
for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) { /* element i is in subset */ }
    }
}

// Opposite ends — sorted array, pair sum
int l = 0, r = arr.length - 1;
while (l < r) {
    int sum = arr[l] + arr[r];
    if (sum == target) { /* found */ break; }
    else if (sum < target) l++;
    else r--;
}
 
// Fast / slow — cycle detection (Floyd's)
int slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) { /* cycle detected */ break; }
}

// Fixed size window of length k
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
for (int i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    maxSum = Math.max(maxSum, windowSum);
}
 
// Variable size window — shrink left when window becomes invalid
int l = 0, result = 0;
Map<Character, Integer> freq = new HashMap<>();
for (int r = 0; r < s.length(); r++) {
    freq.merge(s.charAt(r), 1, Integer::sum);
    while (freq.size() > k) {                         // condition violated
        freq.merge(s.charAt(l), -1, Integer::sum);
        if (freq.get(s.charAt(l)) == 0) freq.remove(s.charAt(l));
        l++;
    }
    result = Math.max(result, r - l + 1);
}

// 1D
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++)
    prefix[i + 1] = prefix[i] + arr[i];
// sum of arr[l..r] inclusive
int rangeSum = prefix[r + 1] - prefix[l];
 
// 2D
int[][] p = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        p[i][j] = grid[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
// sum of submatrix (r1,c1) to (r2,c2) inclusive
int sum = p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1];

// Standard — find exact target in sorted array
int l = 0, r = arr.length - 1;
while (l <= r) {
    int mid = l + (r - l) / 2;   // never (l + r) / 2 — overflows
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) l = mid + 1;
    else r = mid - 1;
}
return -1;
 
// Lower bound — leftmost index where arr[i] >= target
int l = 0, r = arr.length;
while (l < r) {
    int mid = l + (r - l) / 2;
    if (arr[mid] >= target) r = mid;
    else l = mid + 1;
}
// l is the answer
 
// Upper bound — leftmost index where arr[i] > target  (i.e. r-1 is last occurrence of target)
int l = 0, r = arr.length;
while (l < r) {
    int mid = l + (r - l) / 2;
    if (arr[mid] > target) r = mid;
    else l = mid + 1;
}
// l - 1 is last occurrence of target
 
// Binary search on answer — "search on the result space, not the array"
// Pattern: find minimum X such that condition(X) is true
int l = minPossible, r = maxPossible;
while (l < r) {
    int mid = l + (r - l) / 2;
    if (condition(mid)) r = mid;
    else l = mid + 1;
}
// l is the minimum valid answer

// Build adjacency list
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
    graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
    graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]); // undirected
}
 
// BFS — shortest path in unweighted graph, level-by-level
Queue<Integer> queue = new ArrayDeque<>();
boolean[] visited = new boolean[n];
queue.offer(start);
visited[start] = true;
int level = 0;
while (!queue.isEmpty()) {
    int size = queue.size();          // freeze current level count
    for (int i = 0; i < size; i++) {
        int node = queue.poll();
        for (int nb : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited[nb]) {
                visited[nb] = true;
                queue.offer(nb);
            }
        }
    }
    level++;
}
 
// DFS — iterative
Deque<Integer> stack = new ArrayDeque<>();
boolean[] visited = new boolean[n];
stack.push(start);
while (!stack.isEmpty()) {
    int node = stack.pop();
    if (visited[node]) continue;
    visited[node] = true;
    for (int nb : graph.getOrDefault(node, new ArrayList<>()))
        if (!visited[nb]) stack.push(nb);
}
 
// DFS — recursive
boolean[] visited = new boolean[n];
void dfs(int node) {
    visited[node] = true;
    for (int nb : graph.getOrDefault(node, new ArrayList<>()))
        if (!visited[nb]) dfs(nb);
}

int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};       // 4-directional
// 8-directional: also add {1,1},{1,-1},{-1,1},{-1,-1}
 
boolean[][] visited = new boolean[m][n];
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{startR, startC});
visited[startR][startC] = true;
 
while (!q.isEmpty()) {
    int[] curr = q.poll();
    for (int[] d : dirs) {
        int nr = curr[0] + d[0];
        int nc = curr[1] + d[1];
        if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
            visited[nr][nc] = true;
            q.offer(new int[]{nr, nc});
        }
    }
}

// Sort 2D array by first col, break ties by second col
Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
 
// Sort strings by length, then lexicographically
list.sort((a, b) -> a.length() != b.length() ? a.length() - b.length() : a.compareTo(b));
 
// Sort by absolute value
Arrays.sort(arr, (a, b) -> Math.abs(a) - Math.abs(b));

Integer.MAX_VALUE   // 2^31 - 1  ≈ 2.1 billion
Integer.MIN_VALUE   // -2^31     ≈ -2.1 billion
Long.MAX_VALUE      // use when intermediate products exceed int range
 
Math.max(a, b) / Math.min(a, b)
Math.abs(x)
Math.pow(base, exp)                          // returns double
Math.sqrt(x)                                 // returns double
(int)(Math.log(x) / Math.log(2))            // log base 2
 
// GCD / LCM
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
 
// Overflow guard for multiplication
long result = (long) a * b;

// Convert List<Integer> → int[]
int[] arr = list.stream().mapToInt(Integer::intValue).toArray();
 
// Convert int[] → List<Integer>
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
 
// Max / min / sum of array via stream
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int sum = Arrays.stream(arr).sum();
 
// Fill 2D dp array
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
 
// Char ↔ digit
int d = c - '0';
char c = (char)('0' + d);
 
// Character checks
Character.isDigit(c)
Character.isLetter(c)
Character.isAlphabetic(c)
Character.isUpperCase(c) / Character.isLowerCase(c)
Character.toLowerCase(c) / Character.toUpperCase(c)
 
// Ternary for inline min/max
int clamp = Math.max(lo, Math.min(val, hi));
 
// Integer overflow safe addition check
boolean overflows = (long) a + b > Integer.MAX_VALUE;