Essential Java Utilities

Displaying array contents efficiently:

int[] dataset = {1, 2, 3, 4, 5};
System.out.println(java.util.Arrays.toString(dataset));

Sorting primitives:

int[] values = {5, 4, 2, 4, 9, 1};
java.util.Arrays.sort(values);

Reading text files using modern try-with-resources:

public static void readFileContent(String filename) {
    try (java.io.BufferedReader br = new java.io.BufferedReader(new java.io.FileReader(filename))) {
        String line;
        while ((line = br.readLine()) != null) {
            System.out.println(line);
        }
    } catch (java.io.IOException ex) {
        ex.printStackTrace();
    }
}

Integer-to-string conversion performance comparison:

public static void benchmarkConversion() {
    int iterations = 50000;
    Integer value = 123;
    
    long start = System.currentTimeMillis();
    for (int i = 0; i < iterations; i++) {
        String s = String.valueOf(value);
    }
    System.out.println("String.valueOf(): " + (System.currentTimeMillis() - start) + "ms");
    
    start = System.currentTimeMillis();
    for (int i = 0; i < iterations; i++) {
        String s = value.toString();
    }
    System.out.println("toString(): " + (System.currentTimeMillis() - start) + "ms");
    
    start = System.currentTimeMillis();
    for (int i = 0; i < iterations; i++) {
        String s = value + "";
    }
    System.out.println("Concatenation: " + (System.currentTimeMillis() - start) + "ms");
}

IDE productivity shortcuts: psvm (main method), sout (print), fori (forward loop), forr (reverse loop), iter (enhanced for-each).

Iterating collections:

java.util.List<String> items = new java.util.ArrayList<>();
items.add("alpha");
items.add("beta");
for (String item : items) {
    System.out.println(item);
}

StringBuilder manipulation:

StringBuilder sb = new StringBuilder();
sb.append(100).append(3.14).append(true);
sb.insert(2, "XYZ");
sb.delete(2, 5);
sb.reverse();
String result = sb.toString();

Mathematiacl Utilities

Euclidean algorithm for GCD:

public static int computeGCD(int x, int y) {
    while (y != 0) {
        int remainder = x % y;
        x = y;
        y = remainder;
    }
    return x;
}

LCM calculation using GCD:

public static int computeLCM(int x, int y) {
    return Math.abs(x * y) / computeGCD(x, y);
}

Array Manipulation Patterns

Two Sum using hash map:

public int[] findTwoSum(int[] arr, int goal) {
    java.util.Map<Integer, Integer> seen = new java.util.HashMap<>();
    for (int idx = 0; idx < arr.length; idx++) {
        int complement = goal - arr[idx];
        if (seen.containsKey(complement)) {
            return new int[]{seen.get(complement), idx};
        }
        seen.put(arr[idx], idx);
    }
    throw new IllegalArgumentException("No solution found");
}

Remove duplicates from sorted array (two-pointer technique):

public int deduplicate(int[] data) {
    if (data.length == 0) return 0;
    int writeIndex = 0;
    for (int scan = 1; scan < data.length; scan++) {
        if (data[scan] != data[writeIndex]) {
            data[++writeIndex] = data[scan];
        }
    }
    return writeIndex + 1;
}

Remove specific value in-place:

public int filterValue(int[] arr, int target) {
    int insertPos = 0;
    for (int element : arr) {
        if (element != target) {
            arr[insertPos++] = element;
        }
    }
    return insertPos;
}

Happy Number detection (Floyd's cycle detection):

public boolean isHappy(int n) {
    int tortoise = n;
    int hare = getNext(n);
    while (hare != 1 && tortoise != hare) {
        tortoise = getNext(tortoise);
        hare = getNext(getNext(hare));
    }
    return hare == 1;
}

private int getNext(int num) {
    int total = 0;
    while (num > 0) {
        int digit = num % 10;
        total += digit * digit;
        num /= 10;
    }
    return total;
}

Move zeros to end while preserving order:

public void shiftZeros(int[] nums) {
    int anchor = 0;
    for (int cursor = 0; cursor < nums.length; cursor++) {
        if (nums[cursor] != 0) {
            int temp = nums[anchor];
            nums[anchor] = nums[cursor];
            nums[cursor] = temp;
            anchor++;
        }
    }
}

Check subsequence:

public boolean checkSubsequence(String s, String t) {
    int sPtr = 0, tPtr = 0;
    while (sPtr < s.length() && tPtr < t.length()) {
        if (s.charAt(sPtr) == t.charAt(tPtr)) {
            sPtr++;
        }
        tPtr++;
    }
    return sPtr == s.length();
}

Monotonic array check:

public boolean isMonotonic(int[] arr) {
    boolean increasing = true, decreasing = true;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > arr[i - 1]) decreasing = false;
        if (arr[i] < arr[i - 1]) increasing = false;
    }
    return increasing || decreasing;
}

Remove palindromic subsequences (special case with only 'a' and 'b'):

public int minDeletions(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return 2;
        left++;
        right--;
    }
    return 1;
}

Container with most water (two-pointer):

public int maxWater(int[] height) {
    int maxArea = 0;
    int left = 0, right = height.length - 1;
    while (left < right) {
        int width = right - left;
        int h = Math.min(height[left], height[right]);
        maxArea = Math.max(maxArea, width * h);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

Next permutation:

public void nextPermutation(int[] nums) {
    int pivot = nums.length - 2;
    while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) {
        pivot--;
    }
    if (pivot >= 0) {
        int successor = nums.length - 1;
        while (successor >= 0 && nums[successor] <= nums[pivot]) {
            successor--;
        }
        swap(nums, pivot, successor);
    }
    reverse(nums, pivot + 1);
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

private void reverse(int[] arr, int start) {
    int end = arr.length - 1;
    while (start < end) {
        swap(arr, start++, end--);
    }
}

Rotate array by k positions:

public void rotate(int[] nums, int k) {
    k %= nums.length;
    reverseRange(nums, 0, nums.length - 1);
    reverseRange(nums, 0, k - 1);
    reverseRange(nums, k, nums.length - 1);
}

private void reverseRange(int[] arr, int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

Find duplicate (Floyd's cycle):

public int findDuplicate(int[] arr) {
    int tortoise = arr[0];
    int hare = arr[0];
    do {
        tortoise = arr[tortoise];
        hare = arr[arr[hare]];
    } while (tortoise != hare);
    
    tortoise = arr[0];
    while (tortoise != hare) {
        tortoise = arr[tortoise];
        hare = arr[hare];
    }
    return hare;
}

Alternative binary search approach:

public int findDuplicateBinary(int[] nums) {
    int low = 1, high = nums.length - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        int count = 0;
        for (int num : nums) {
            if (num <= mid) count++;
        }
        if (count > mid) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

Tree Algorithms

Inorder traversal (recursive):

public java.util.List<Integer> inorderTraversal(TreeNode root) {
    java.util.List<Integer> values = new java.util.ArrayList<>();
    traverse(root, values);
    return values;
}

private void traverse(TreeNode node, java.util.List<Integer> values) {
    if (node == null) return;
    traverse(node.left, values);
    values.add(node.val);
    traverse(node.right, values);
}

Check tree equality:

public boolean areIdentical(TreeNode tree1, TreeNode tree2) {
    if (tree1 == null && tree2 == null) return true;
    if (tree1 == null || tree2 == null) return false;
    if (tree1.val != tree2.val) return false;
    return areIdentical(tree1.left, tree2.left) && areIdentical(tree1.right, tree2.right);
}

Symmetric tree check:

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;
    return left.val == right.val && isMirror(left.left, right.right) && isMirror(left.right, right.left);
}

Maximum depth (recursive):

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Maximum depth (iterative BFS):

public int maxDepthBFS(TreeNode root) {
    if (root == null) return 0;
    java.util.Queue<TreeNode> queue = new java.util.LinkedList<>();
    queue.offer(root);
    int levels = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode current = queue.poll();
            if (current.left != null) queue.offer(current.left);
            if (current.right != null) queue.offer(current.right);
        }
        levels++;
    }
    return levels;
}

Minimum depth:

public int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;
    
    int depth = Integer.MAX_VALUE;
    if (root.left != null) {
        depth = Math.min(minDepth(root.left), depth);
    }
    if (root.right != null) {
        depth = Math.min(minDepth(root.right), depth);
    }
    return depth + 1;
}

Path sum existence:

public boolean hasPathSum(TreeNode root, int target) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return target == root.val;
    return hasPathSum(root.left, target - root.val) || hasPathSum(root.right, target - root.val);
}

Invert binary tree:

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode leftInverted = invertTree(root.right);
    TreeNode rightInverted = invertTree(root.left);
    root.left = leftInverted;
    root.right = rightInverted;
    return root;
}

Find mode in BST (constant space, Morris traversal not required, just inorder):

class Solution {
    private Integer prevVal = null;
    private int currCount = 0;
    private int maxFreq = 0;
    private java.util.List<Integer> modes = new java.util.ArrayList<>();
    
    public int[] findMode(TreeNode root) {
        inorder(root);
        int[] result = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) {
            result[i] = modes.get(i);
        }
        return result;
    }
    
    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        
        if (prevVal != null && node.val == prevVal) {
            currCount++;
        } else {
            currCount = 1;
            prevVal = node.val;
        }
        
        if (currCount > maxFreq) {
            maxFreq = currCount;
            modes.clear();
            modes.add(node.val);
        } else if (currCount == maxFreq) {
            modes.add(node.val);
        }
        
        inorder(node.right);
    }
}

Dynamic Programming Patterns

Maximum subarray (Kadane's algorithm):

public int maxSubArray(int[] arr) {
    int currentSum = arr[0];
    int bestSum = arr[0];
    for (int i = 1; i < arr.length; i++) {
        currentSum = Math.max(arr[i], currentSum + arr[i]);
        bestSum = Math.max(bestSum, currentSum);
    }
    return bestSum;
}

Climbing stairs (Fibonacci):

public int climbStairs(int n) {
    if (n <= 1) return 1;
    int prev2 = 1, prev1 = 1;
    for (int step = 2; step <= n; step++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

Counting bits (DP):

public int[] countBits(int n) {
    int[] bitCounts = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        bitCounts[i] = bitCounts[i >> 1] + (i & 1);
    }
    return bitCounts;
}

Alternative using least significant bit:

public int[] countBitsLSB(int n) {
    int[] bitCounts = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        bitCounts[i] = bitCounts[i & (i - 1)] + 1;
    }
    return bitCounts;
}

Longest continuous increasing subsequence:

public int findLengthOfLCIS(int[] arr) {
    if (arr.length == 0) return 0;
    int maxLen = 1, currLen = 1;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > arr[i - 1]) {
            currLen++;
            maxLen = Math.max(maxLen, currLen);
        } else {
            currLen = 1;
        }
    }
    return maxLen;
}