Description: Given a string as a char array, reverse it in-place without using extra space beyond O(1).

Example: Input: s = ['h','e','l','l','o']
Output: ['o','l','l','e','h']

• Technique: Two pointers swap characters from both ends inward.
• Complexity: O(n) time, O(1) space.

public class ReverseString {
    public static void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left++] = s[right];
            s[right--] = temp;
        }
    }

    public static void main(String[] args) {
        char[] s = {'h', 'e', 'l', 'l', 'o'};
        reverseString(s);
        System.out.println(Arrays.toString(s)); // [o, l, l, e, h]
    }
}
                                

Description: Given an array of integers and a target sum, find two numbers that add up to the target and return their indices. Assume exactly one solution exists.

Example: Input: nums = [2,7,11,15], target = 9
Output: [0,1] (2 + 7 = 9)

• Technique: HashMap stores complements, checking for matches in one pass.
• Complexity: O(n) time, O(n) space.

import java.util.HashMap;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        HashMap<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[]{};
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int[] result = twoSum(nums, 9);
        System.out.println(Arrays.toString(result)); // [0, 1]
    }
}
                                

Description: Given an integer array, determine if it contains any duplicate values.

Example: Input: nums = [1,2,3,1]
Output: true (1 appears twice)

• Technique: HashSet adds elements, returning false on duplicates.
• Complexity: O(n) time, O(n) space.

import java.util.HashSet;

public class ContainsDuplicate {
    public static boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println(containsDuplicate(nums)); // true
    }
}
                                

Description: Given an array of stock prices, find the maximum profit from one buy and one sell, buying before selling.

Example: Input: prices = [7,1,5,3,6,4]
Output: 5 (buy at 1, sell at 6)

• Technique: Greedy tracks min price and max profit in one pass.
• Complexity: O(n) time, O(1) space.

public class MaxProfit {
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE, maxProfit = 0;
        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices)); // 5
    }
}
                                

Description: Given two strings, check if one is an anagram of the other (same characters, same frequencies).

Example: Input: s = "anagram", t = "nagaram"
Output: true

• Technique: Array counts character frequencies, comparing both strings.
• Complexity: O(n) time, O(1) space (fixed 26 chars).

public class ValidAnagram {
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        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;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("anagram", "nagaram")); // true
    }
}
                                

Description: Given a string, find the index of the first character that appears only once, or -1 if none exists.

Example: Input: s = "leetcode"
Output: 0 ('l' is first unique)

• Technique: Array tracks frequencies, then scans string for first with count 1.
• Complexity: O(n) time, O(1) space.

public class FirstUniqueChar {
    public static int firstUniqChar(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) count[c - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            if (count[s.charAt(i) - 'a'] == 1) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(firstUniqChar("leetcode")); // 0
    }
}
                                

Description: Given an array of integers, move all zeros to the end while maintaining the relative order of non-zero elements, in-place.

Example: Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

• Technique: Two passes: first moves non-zeros to front, second fills rest with zeros.
• Complexity: O(n) time, O(1) space.

public class MoveZeroes {
    public static void moveZeroes(int[] nums) {
        int nonZeroPos = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) nums[nonZeroPos++] = nums[i];
        }
        while (nonZeroPos < nums.length) nums[nonZeroPos++] = 0;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};
        moveZeroes(nums);
        System.out.println(Arrays.toString(nums)); // [1, 3, 12, 0, 0]
    }
}
                                

Description: Given two integer arrays, return an array of their intersection (elements present in both), with no duplicates.

Example: Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

• Technique: HashSet stores one array, checks intersection with the other.
• Complexity: O(n + m) time, O(n) space.

import java.util.*;

public class IntersectionArrays {
    public static int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums1) set.add(num);
        HashSet<Integer> result = new HashSet<>();
        for (int num : nums2) {
            if (set.contains(num)) result.add(num);
        }
        int[] output = new int[result.size()];
        int i = 0;
        for (int num : result) output[i++] = num;
        return output;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 2, 1}, nums2 = {2, 2};
        System.out.println(Arrays.toString(intersection(nums1, nums2))); // [2]
    }
}
                                

Description: Given an array, return an array where each element is the product of all other elements, without using division.

Example: Input: nums = [1,2,3,4]
Output: [24,12,8,6] (e.g., 24 = 2*3*4)

• Technique: Two passes compute left and right products in-place.
• Complexity: O(n) time, O(1) space (excluding output).

public class ProductExceptSelf {
    public static int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        result[0] = 1;
        for (int i = 1; i < nums.length; i++) result[i] = result[i - 1] * nums[i - 1];
        int right = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] *= right;
            right *= nums[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        System.out.println(Arrays.toString(productExceptSelf(nums))); // [24, 12, 8, 6]
    }
}
                                

Description: Given an array where adjacent elements are different, find an index of a peak element (greater than its neighbors). Multiple peaks may exist.

Example: Input: nums = [1,2,3,1]
Output: 2 (3 is peak)

• Technique: Binary search finds peak by comparing mid with neighbors.
• Complexity: O(log n) time, O(1) space.

public class FindPeakElement {
    public static int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) right = mid;
            else left = mid + 1;
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println(findPeakElement(nums)); // 2
    }
}
                                

Description: Given two sorted integer arrays nums1 and nums2, merge them into nums1 in sorted order, where nums1 has enough space.

Example: Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

• Technique: Two pointers merge from end to avoid overwriting.
• Complexity: O(m + n) time, O(1) space.

public class MergeSortedArrays {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1, p = m + n - 1;
        while (p2 >= 0 && p1 >= 0) {
            nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
        }
        while (p2 >= 0) nums1[p--] = nums2[p2--];
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int[] nums2 = {2, 5, 6};
        merge(nums1, 3, nums2, 3);
        System.out.println(Arrays.toString(nums1)); // [1, 2, 2, 3, 5, 6]
    }
}
                                

Description: Given a sorted array and a target, return the index where the target is or should be inserted to maintain sorted order.

Example: Input: nums = [1,3,5,6], target = 5
Output: 2 (5 is at index 2)

• Technique: Binary search finds the position in logarithmic time.
• Complexity: O(log n) time, O(1) space.

public class SearchInsert {
    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        System.out.println(searchInsert(nums, 5)); // 2
    }
}
                                

Description: Given a string of parentheses ('(', ')', '{', '}', '[', ']'), determine if it’s valid (properly nested and closed).

Example: Input: s = "({[]})"
Output: true

• Technique: Stack pushes opening brackets, pops to match closing ones.
• Complexity: O(n) time, O(n) space.

import java.util.Stack;

public class ValidParentheses {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') stack.push(c);
            else if (stack.isEmpty()) return false;
            else if (c == ')' && stack.pop() != '(') return false;
            else if (c == '}' && stack.pop() != '{') return false;
            else if (c == ']' && stack.pop() != '[') return false;
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValid("({[]})")); // true
    }
}
                                

Description: Given a sorted array, remove duplicates in-place and return the new length, keeping only unique elements.

Example: Input: nums = [1,1,2,3,3]
Output: 3 (nums becomes [1,2,3,_,_])

• Technique: Two pointers: one tracks unique position, other scans array.
• Complexity: O(n) time, O(1) space.

public class RemoveDuplicates {
    public static int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int k = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) nums[k++] = nums[i];
        }
        return k;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 3, 3};
        int len = removeDuplicates(nums);
        System.out.println(len + ": " + Arrays.toString(Arrays.copyOf(nums, len))); // 3: [1, 2, 3]
    }
}
                                

Description: Given an array, rotate it to the right by k steps, where k may be larger than the array length.

Example: Input: nums = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

• Technique: Reverse entire array, then reverse first k and remaining elements.
• Complexity: O(n) time, O(1) space.

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

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        rotate(nums, 2);
        System.out.println(Arrays.toString(nums)); // [4, 5, 1, 2, 3]
    }
}
                                

Description: Given a singly linked list, reverse it and return the new head.

Example: Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

• Technique: Iterative pointer manipulation reverses links.
• Complexity: O(n) time, O(1) space.

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

public class ReverseList {
    public static 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;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode result = reverseList(head);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        } // 5 4 3 2 1
    }
}
                                

Description: Merge two sorted linked lists into a new sorted linked list.

Example: Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

• Technique: Iterative merging with a dummy node compares and links nodes.
• Complexity: O(n + m) time, O(1) space.

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

public class MergeTwoLists {
    public static 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;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);
        ListNode result = mergeTwoLists(l1, l2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        } // 1 1 2 3 4 4
    }
}
                                

Description: Given a linked list, determine if it has a cycle (a node pointing back to a previous node).

Example: Input: head = [3,2,0,-4], pos = 1 (tail connects to node 2)
Output: true

• Technique: Floyd’s cycle detection uses fast and slow pointers.
• Complexity: O(n) time, O(1) space.

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

public class HasCycle {
    public static 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;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = head.next;
        System.out.println(hasCycle(head)); // true
    }
}
                                

Description: Given a linked list and an integer n, remove the nth node from the end and return the head.

Example: Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

• Technique: Two pointers with a gap of n find the node to remove.
• Complexity: O(n) time, O(1) space.

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

public class RemoveNthFromEnd {
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i < n + 1; i++) fast = fast.next;
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode result = removeNthFromEnd(head, 2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        } // 1 2 3 5
    }
}
                                

Description: Given two linked lists representing non-negative integers (digits in reverse order), add them and return the sum as a linked list.

Example: Input: l1 = [2,4,3], l2 = [5,6,4] (342 + 465)
Output: [7,0,8] (807)

• Technique: Iterative addition with carry handling builds the result list.
• Complexity: O(max(n,m)) time, O(max(n,m)) space.

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

public class AddTwoNumbers {
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int x = l1 != null ? l1.val : 0;
            int y = l2 != null ? l2.val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);
        ListNode result = addTwoNumbers(l1, l2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        } // 7 0 8
    }
}
                                

Description: Given a binary tree, return the inorder traversal of its nodes’ values (left, root, right).

Example: Input: root = [1,null,2,3] (1 as root, 2 as right, 3 as 2’s left)
Output: [1,3,2]

• Technique: Iterative approach uses a stack to traverse left, then root, then right.
• Complexity: O(n) time, O(h) space (h = tree height).

import java.util.*;

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

public class InorderTraversal {
    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 void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        System.out.println(inorderTraversal(root)); // [1, 3, 2]
    }
}
                                

Description: Given a binary tree, find its maximum depth (number of nodes along the longest path from root to leaf).

Example: Input: root = [3,9,20,null,null,15,7]
Output: 3 (path: 3->20->15 or 7)

• Technique: Recursion computes max depth of left and right subtrees.
• Complexity: O(n) time, O(h) space.

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

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

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(maxDepth(root)); // 3
    }
}
                                

Description: Given a binary tree, check if it’s symmetric (a mirror of itself around its center).

Example: Input: root = [1,2,2,3,4,4,3]
Output: true

• Technique: Recursion compares left and right subtrees symmetrically.
• Complexity: O(n) time, O(h) space.

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

public class SymmetricTree {
    public static boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

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

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        System.out.println(isSymmetric(root)); // true
    }
}
                                

Description: Given a binary tree and a target sum, determine if there’s a root-to-leaf path where the sum of node values equals the target.

Example: Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true (path: 5->4->11->2)

• Technique: Recursion subtracts node values, checking leaf sums.
• Complexity: O(n) time, O(h) space.

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

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

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.right = new TreeNode(1);
        System.out.println(hasPathSum(root, 22)); // true
    }
}
                                

Description: Given n stairs, you can climb 1 or 2 steps at a time. Find the number of distinct ways to reach the top.

Example: Input: n = 3
Output: 3 (ways: 1+1+1, 1+2, 2+1)

• Technique: DP uses Fibonacci-like sequence for ways to climb.
• Complexity: O(n) time, O(1) space.

public class ClimbStairs {
    public static int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }

    public static void main(String[] args) {
        System.out.println(climbStairs(3)); // 3
    }
}
                                

Description: Given a 2D grid of '1's (land) and '0's (water), count the number of islands, where an island is surrounded by water and formed by connecting adjacent lands horizontally or vertically.

Example: Input: grid = [["1","1","0","0"],["1","1","0","0"],["0","0","1","0"]]
Output: 2 (two islands: top-left and bottom-right)

• Technique: DFS marks connected land as visited, counting each new island.
• Complexity: O(mn) time, O(mn) space (recursion stack).

public class NumberOfIslands {
    public static int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private static void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return;
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }

    public static void main(String[] args) {
        char[][] grid = {{'1','1','0','0'},{'1','1','0','0'},{'0','0','1','0'}};
        System.out.println(numIslands(grid)); // 2
    }
}
                                

Description: Given a binary tree and two nodes p and q, find their lowest common ancestor (the deepest node that is an ancestor of both).

Example: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3 (3 is LCA of 5 and 1)

• Technique: Recursion finds paths to p and q, returning the split point.
• Complexity: O(n) time, O(h) space.

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

public class LowestCommonAncestor {
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        TreeNode p = root.left, q = root.right;
        System.out.println(lowestCommonAncestor(root, p, q).val); // 3
    }
}
                                

Description: Given a binary tree, return the level order traversal of its nodes’ values (left to right, level by level).

Example: Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

• Technique: BFS uses a queue to process nodes level by level.
• Complexity: O(n) time, O(w) space (w = max width).

import java.util.*;

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

public class LevelOrderTraversal {
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(levelOrder(root)); // [[3], [9, 20], [15, 7]]
    }
}
                                

Description: Given a binary tree, determine if it’s height-balanced (the height difference between left and right subtrees of every node is at most 1).

Example: Input: root = [3,9,20,null,null,15,7]
Output: true

• Technique: Bottom-up recursion computes heights, checking balance.
• Complexity: O(n) time, O(h) space.

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

public class BalancedBinaryTree {
    public static boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private static int height(TreeNode node) {
        if (node == null) return 0;
        int left = height(node.left);
        if (left == -1) return -1;
        int right = height(node.right);
        if (right == -1 || Math.abs(left - right) > 1) return -1;
        return Math.max(left, right) + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(isBalanced(root)); // true
    }
}
                                

Description: Given two binary trees, check if they are structurally identical and have the same node values.

Example: Input: p = [1,2,3], q = [1,2,3]
Output: true

• Technique: Recursion compares nodes and their subtrees.
• Complexity: O(n) time, O(h) space.

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

public class SameTree {
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public static void main(String[] args) {
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);
        TreeNode q = new TreeNode(1);
        q.left = new TreeNode(2);
        q.right = new TreeNode(3);
        System.out.println(isSameTree(p, q)); // true
    }
}
                                

Description: Given a number of courses and prerequisites as pairs, determine if you can finish all courses (no cyclic dependencies).

Example: Input: numCourses = 2, prerequisites = [[1,0]]
Output: true (0 -> 1)

• Technique: DFS detects cycles in a directed graph.
• Complexity: O(V + E) time, O(V) space.

import java.util.*;

public class CourseSchedule {
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] pre : prerequisites) graph.get(pre[1]).add(pre[0]);
        boolean[] visited = new boolean[numCourses];
        boolean[] recStack = new boolean[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(i, graph, visited, recStack)) return false;
        }
        return true;
    }

    private static boolean dfs(int course, List<List<Integer>> graph, boolean[] visited, boolean[] recStack) {
        if (recStack[course]) return false;
        if (visited[course]) return true;
        visited[course] = true;
        recStack[course] = true;
        for (int next : graph.get(course)) {
            if (!dfs(next, graph, visited, recStack)) return false;
        }
        recStack[course] = false;
        return true;
    }

    public static void main(String[] args) {
        int[][] prerequisites = {{1, 0}};
        System.out.println(canFinish(2, prerequisites)); // true
    }
}
                                

Description: Given a reference to a node in an undirected graph, return a deep copy (clone) of the graph.

Example: Input: node = [[2,4],[1,3],[2,4],[1,3]] (adjacency list)
Output: A cloned graph

• Technique: DFS with a HashMap tracks cloned nodes to avoid cycles.
• Complexity: O(V + E) time, O(V) space.

import java.util.*;

class Node {
    int val;
    List<Node> neighbors;
    Node(int val) { this.val = val; this.neighbors = new ArrayList<>(); }
}

public class CloneGraph {
    public static Node cloneGraph(Node node) {
        if (node == null) return null;
        HashMap<Node, Node> map = new HashMap<>();
        return dfs(node, map);
    }

    private static Node dfs(Node node, HashMap<Node, Node> map) {
        if (map.containsKey(node)) return map.get(node);
        Node copy = new Node(node.val);
        map.put(node, copy);
        for (Node neighbor : node.neighbors) {
            copy.neighbors.add(dfs(neighbor, map));
        }
        return copy;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.neighbors.add(node2); node1.neighbors.add(node4);
        node2.neighbors.add(node1); node2.neighbors.add(node3);
        node3.neighbors.add(node2); node3.neighbors.add(node4);
        node4.neighbors.add(node1); node4.neighbors.add(node3);
        Node cloned = cloneGraph(node1);
        System.out.println(cloned.val); // 1 (cloned graph root)
    }
}
                                

Description: Given a directed acyclic graph (DAG) as a number of nodes and edges, return a topological ordering of the nodes.

Example: Input: numNodes = 4, edges = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]

• Technique: DFS with a stack builds the order by finishing nodes last-to-first.
• Complexity: O(V + E) time, O(V) space.

import java.util.*;

public class TopologicalSort {
    public static int[] topologicalSort(int numNodes, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) graph.get(edge[1]).add(edge[0]);
        boolean[] visited = new boolean[numNodes];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < numNodes; i++) {
            if (!visited[i]) dfs(i, graph, visited, stack);
        }
        int[] result = new int[numNodes];
        for (int i = 0; i < numNodes; i++) result[i] = stack.pop();
        return result;
    }

    private static void dfs(int node, List<List<Integer>> graph, boolean[] visited, Stack<Integer> stack) {
        visited[node] = true;
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) dfs(neighbor, graph, visited, stack);
        }
        stack.push(node);
    }

    public static void main(String[] args) {
        int[][] edges = {{1,0},{2,0},{3,1},{3,2}};
        System.out.println(Arrays.toString(topologicalSort(4, edges))); // [0, 1, 2, 3]
    }
}
                                

Description: Given an undirected graph as a number of nodes and edges, count the number of connected components.

Example: Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2 (components: 0-1-2, 3-4)

• Technique: Union-Find merges connected nodes, counting distinct roots.
• Complexity: O(E * α(N)) time, O(N) space (α = inverse Ackermann).

public class ConnectedComponents {
    static int[] parent;

    public static int countComponents(int n, int[][] edges) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int components = n;
        for (int[] edge : edges) {
            int x = find(edge[0]), y = find(edge[1]);
            if (x != y) {
                parent[x] = y;
                components--;
            }
        }
        return components;
    }

    private static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    public static void main(String[] args) {
        int[][] edges = {{0,1},{1,2},{3,4}};
        System.out.println(countComponents(5, edges)); // 2
    }
}
                                

Description: Given two words and a word list, find the shortest transformation sequence length from beginWord to endWord, changing one letter at a time, using only words in the list.

Example: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5 (hit -> hot -> dot -> dog -> cog)

• Technique: BFS finds shortest path in an implicit graph of word transformations.
• Complexity: O(N * 26 * L) time, O(N) space (N = word list size, L = word length).

import java.util.*;

public class WordLadder {
    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if (!set.contains(endWord)) return 0;
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int level = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                if (word.equals(endWord)) return level;
                char[] chars = word.toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char original = chars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String newWord = new String(chars);
                        if (set.contains(newWord)) {
                            queue.offer(newWord);
                            set.remove(newWord);
                        }
                    }
                    chars[j] = original;
                }
            }
            level++;
        }
        return 0;
    }

    public static void main(String[] args) {
        List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
        System.out.println(ladderLength("hit", "cog", wordList)); // 5
    }
}
                                

Description: Given an integer array, find the length of the longest strictly increasing subsequence (not necessarily contiguous).

Example: Input: nums = [10,9,2,5,3,7,101,18]
Output: 4 (e.g., [2,3,7,101])

• Technique: DP with binary search maintains an array of smallest tails.
• Complexity: O(n log n) time, O(n) space.

public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int num : nums) {
            int i = 0, j = size;
            while (i < j) {
                int mid = i + (j - i) / 2;
                if (tails[mid] < num) i = mid + 1;
                else j = mid;
            }
            tails[i] = num;
            if (i == size) size++;
        }
        return size;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS(nums)); // 4
    }
}
                                

Description: Given an array of coin denominations and a target amount, find the minimum number of coins needed to make the amount, or -1 if impossible.

Example: Input: coins = [1,2,5], amount = 11
Output: 3 (5 + 5 + 1)

• Technique: DP builds minimum coins needed for each amount up to target.
• Complexity: O(amount * n) time, O(amount) space.

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        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];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        System.out.println(coinChange(coins, 11)); // 3
    }
}
                                

Description: Given an array of house values, find the maximum amount you can rob without robbing adjacent houses.

Example: Input: nums = [2,7,9,3,1]
Output: 12 (2 + 9 + 1)

• Technique: DP chooses max between robbing current house plus previous non-adjacent, or skipping it.
• Complexity: O(n) time, O(1) space.

public class HouseRobber {
    public static int rob(int[] nums) {
        int prev = 0, curr = 0;
        for (int num : nums) {
            int temp = curr;
            curr = Math.max(prev + num, curr);
            prev = temp;
        }
        return curr;
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 9, 3, 1};
        System.out.println(rob(nums)); // 12
    }
}
                                

Description: Given a string of digits, count the number of ways to decode it into letters (1 = A, 2 = B, ..., 26 = Z), where some digits can form two-digit codes.

Example: Input: s = "226"
Output: 3 ("BBF", "VF", "BF")

• Technique: DP tracks ways to decode up to each position.
• Complexity: O(n) time, O(n) space.

public class DecodeWays {
    public static int numDecodings(String s) {
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i <= s.length(); i++) {
            int oneDigit = s.charAt(i - 1) - '0';
            int twoDigits = Integer.parseInt(s.substring(i - 2, i));
            if (oneDigit >= 1) dp[i] += dp[i - 1];
            if (twoDigits >= 10 && twoDigits <= 26) dp[i] += dp[i - 2];
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
        System.out.println(numDecodings("226")); // 3
    }
}
                                

Description: Given a string and a dictionary of words, determine if the string can be segmented into a space-separated sequence of dictionary words.

Example: Input: s = "leetcode", wordDict = ["leet","code"]
Output: true ("leet code")

• Technique: DP checks if prefixes can be formed from dictionary words.
• Complexity: O(n²) time, O(n) space.

import java.util.*;

public class WordBreak {
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
        List<String> wordDict = Arrays.asList("leet", "code");
        System.out.println(wordBreak("leetcode", wordDict)); // true
    }
}
                                

Description: Design a Least Recently Used (LRU) cache with get and put operations, evicting the least recently used item when capacity is reached.

Example: Input: capacity = 2, operations = ["put(1,1)","put(2,2)","get(1)","put(3,3)","get(2)"]
Output: [-, -, 1, -, -1] (2 evicted)

• Technique: HashMap and doubly linked list maintain order and fast access.
• Complexity: O(1) time for get/put, O(capacity) space.

import java.util.HashMap;

class LRUCache {
    class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private HashMap<Integer, Node> map;
    private Node head, tail;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
        } else {
            node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node lru = tail.prev;
                removeNode(lru);
                map.remove(lru.key);
            }
        }
    }

    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
        cache.put(3, 3);
        System.out.println(cache.get(2)); // -1
    }
}
                                

Description: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Example: Input: ["push(3)","push(5)","getMin","pop","getMin"]
Output: [-, -, 3, -, 3]

• Technique: Two stacks: one for values, one for tracking minimums.
• Complexity: O(1) time for all operations, O(n) space.

import java.util.Stack;

public class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) minStack.push(val);
    }

    public void pop() {
        int val = stack.pop();
        if (val == minStack.peek()) minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(3);
        minStack.push(5);
        System.out.println(minStack.getMin()); // 3
        minStack.pop();
        System.out.println(minStack.getMin()); // 3
    }
}
                                

Description: Given an array of meeting intervals (start, end times), determine if a person can attend all meetings without conflicts.

Example: Input: intervals = [[0,30],[5,10],[15,20]]
Output: false (5-10 overlaps with 0-30)

• Technique: Sort by start time, check for overlapping end times.
• Complexity: O(n log n) time, O(1) space.

import java.util.Arrays;

public class MeetingRooms {
    public static boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] intervals = {{0,30},{5,10},{15,20}};
        System.out.println(canAttendMeetings(intervals)); // false
    }
}
                                

Description: Given an array representing elevation heights, compute how much water can be trapped between bars after raining.

Example: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6 (water trapped at various indices)

• Technique: Two pointers track max left and right heights, calculating trapped water.
• Complexity: O(n) time, O(1) space.

public class TrappingRainWater {
    public static int trap(int[] height) {
        int left = 0, right = height.length - 1, water = 0;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (leftMax < rightMax) water += leftMax - height[left++];
            else water += rightMax - height[right--];
        }
        return water;
    }

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height)); // 6
    }
}
                                

Description: Given an array of heights representing vertical lines, find two lines that form a container with the most water.

Example: Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49 (lines at 1 and 8, width 7, min height 7)

• Technique: Two pointers maximize area by moving shorter line inward.
• Complexity: O(n) time, O(1) space.

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

    public static void main(String[] args) {
        int[] height = {1,8,6,2,5,4,8,3,7};
        System.out.println(maxArea(height)); // 49
    }
}
                                

Description: Given an array of strings, group all anagrams together (words with the same characters, different arrangements).

Example: Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]

• Technique: HashMap uses sorted string as key to group anagrams.
• Complexity: O(n * k log k) time, O(n) space (k = max string length).

import java.util.*;

public class GroupAnagrams {
    public static List<List<String>> groupAnagrams(String[] strs) {
        HashMap<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());
    }

    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(groupAnagrams(strs)); // [[eat, tea, ate], [tan, nat], [bat]]
    }
}
                                

Description: Given an array of integers and an integer k, find the total number of continuous subarrays whose sum equals k.

Example: Input: nums = [1,1,1], k = 2
Output: 2 ([1,1] twice)

• Technique: HashMap stores cumulative sums to count subarrays.
• Complexity: O(n) time, O(n) space.

import java.util.HashMap;

public class SubarraySum {
    public static int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0, count = 0;
        for (int num : nums) {
            sum += num;
            count += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1};
        System.out.println(subarraySum(nums, 2)); // 2
    }
}
                                

Description: Given an array of distinct integers, return all possible permutations.

Example: Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

• Technique: Backtracking swaps elements to generate permutations.
• Complexity: O(n!) time, O(n) space.

import java.util.*;

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

    private static void backtrack(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums) list.add(num);
            result.add(list);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            backtrack(nums, start + 1, result);
            swap(nums, start, i);
        }
    }

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

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(permute(nums)); // [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    }
}
                                

Description: Given an array of distinct integers and a target, return all unique combinations where the numbers sum to the target (can reuse numbers).

Example: Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

• Technique: Backtracking builds combinations by including/excluding numbers.
• Complexity: O(2^n) time, O(target) space.

import java.util.*;

public class CombinationSum {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] candidates, int target, int start, List<Integer> curr, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(curr));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] <= target) {
                curr.add(candidates[i]);
                backtrack(candidates, target - candidates[i], i, curr, result);
                curr.remove(curr.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        System.out.println(combinationSum(candidates, 7)); // [[2,2,3], [7]]
    }
}
                                

Description: Given two sorted arrays, find the median of the combined sorted array.

Example: Input: nums1 = [1,3], nums2 = [2]
Output: 2.0 (combined: [1,2,3], median = 2)

• Technique: Binary search finds partition where left and right halves balance.
• Complexity: O(log(min(m,n))) time, O(1) space.

public class MedianOfTwoSortedArrays {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
        int m = nums1.length, n = nums2.length;
        int left = 0, right = m;
        while (left <= right) {
            int partX = (left + right) / 2;
            int partY = (m + n + 1) / 2 - partX;
            int maxLeftX = partX == 0 ? Integer.MIN_VALUE : nums1[partX - 1];
            int minRightX = partX == m ? Integer.MAX_VALUE : nums1[partX];
            int maxLeftY = partY == 0 ? Integer.MIN_VALUE : nums2[partY - 1];
            int minRightY = partY == n ? Integer.MAX_VALUE : nums2[partY];
            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                if ((m + n) % 2 == 0) {
                    return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
                } else {
                    return Math.max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) right = partX - 1;
            else left = partX + 1;
        }
        return 0.0;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 3}, nums2 = {2};
        System.out.println(findMedianSortedArrays(nums1, nums2)); // 2.0
    }
}
                                

Description: Given a string and an integer k, find the length of the longest substring that contains at most k distinct characters. For example, in "eceba" with k=2, "ece" is a valid substring (2 distinct chars: 'e', 'c'), but "eceba" has 4 ('e', 'c', 'b', 'a').

Example: Input: s = "eceba", k = 2
Output: 3 ("ece")

• Technique: Sliding window uses a HashMap to count characters, expanding right and shrinking left when distinct chars exceed k.
• Complexity: O(n) time, O(k) space.

import java.util.HashMap;

public class LongestSubstringKDistinct {
    public static int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0, start = 0;
        for (int end = 0; end < s.length(); end++) {
            map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) + 1);
            while (map.size() > k) {
                map.put(s.charAt(start), map.get(s.charAt(start)) - 1);
                if (map.get(s.charAt(start)) == 0) map.remove(s.charAt(start));
                start++;
            }
            max = Math.max(max, end - start + 1);
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstringKDistinct("eceba", 2)); // 3
    }
}
                                

Description: Given an array of integers, determine if it can be split into two subarrays with equal sums. The split must be contiguous (e.g., [1,5,11,5] can split as [1,11] and [5,5], both summing to 12).

Example: Input: nums = [1,5,11,5]
Output: true (split at index 2: [1,5] + [11,5] = 6 + 16 is not equal, but [1,11] + [5,5] = 12 + 12 works)

• Technique: Compute total sum, check if it’s even, then find a prefix sum equal to half using a single pass.
• Complexity: O(n) time, O(1) space.

public class PartitionEqualSum {
    public static boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2, sum = 0;
        for (int num : nums) {
            sum += num;
            if (sum == target) return true;
            if (sum > target) return false;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(canPartition(nums)); // true
    }
}
                                

Description: Given a sorted array and a target sum, find two numbers that add up to the target. Return their 1-based indices. Assume each input has exactly one solution.

Example: Input: numbers = [2,7,11,15], target = 9
Output: [1,2] (2 + 7 = 9)

• Technique: Two pointers start from ends, moving based on sum comparison, leveraging the sorted order.
• Complexity: O(n) time, O(1) space.

public class TwoSumII {
    public static int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) return new int[]{left + 1, right + 1};
            else if (sum < target) left++;
            else right--;
        }
        return new int[]{};
    }

    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int[] result = twoSum(numbers, 9);
        System.out.println(Arrays.toString(result)); // [1, 2]
    }
}
                                

Description: Given an array of integers, find the contiguous subarray with the largest product. Handle negatives, which can flip max to min.

Example: Input: nums = [2,3,-2,4]
Output: 6 ([2,3] has product 6)

• Technique: DP tracks max and min products at each step, as negatives require both.
• Complexity: O(n) time, O(1) space.

public class MaxProductSubarray {
    public static int maxProduct(int[] nums) {
        int maxSoFar = nums[0], minSoFar = nums[0], result = maxSoFar;
        for (int i = 1; i < nums.length; i++) {
            int curr = nums[i];
            int tempMax = Math.max(curr, Math.max(maxSoFar * curr, minSoFar * curr));
            minSoFar = Math.min(curr, Math.min(maxSoFar * curr, minSoFar * curr));
            maxSoFar = tempMax;
            result = Math.max(result, maxSoFar);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, -2, 4};
        System.out.println(maxProduct(nums)); // 6
    }
}
                                

Description: Given a sorted array rotated at some pivot (e.g., [4,5,6,7,0,1,2]), find the minimum element. No duplicates.

Example: Input: nums = [4,5,6,7,0,1,2]
Output: 0

• Technique: Binary search finds the pivot where the array dips below its right neighbor.
• Complexity: O(log n) time, O(1) space.

public class FindMinRotated {
    public static int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        System.out.println(findMin(nums)); // 0
    }
}
                                

Description: Given a list of intervals, merge all overlapping ones into non-overlapping intervals. Each interval is [start, end].

Example: Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]] (1-3 and 2-6 overlap)

• Technique: Sort by start time, then merge by comparing endpoints with the last added interval.
• Complexity: O(n log n) time, O(n) space.

import java.util.*;

public class MergeIntervals {
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> result = new ArrayList<>();
        for (int[] interval : intervals) {
            if (result.isEmpty() || result.get(result.size() - 1)[1] < interval[0]) {
                result.add(interval);
            } else {
                result.get(result.size() - 1)[1] = Math.max(result.get(result.size() - 1)[1], interval[1]);
            }
        }
        return result.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        int[][] result = merge(intervals);
        for (int[] interval : result) System.out.println(Arrays.toString(interval));
    }
}
                                

Description: Given an array of integers, rearrange it into the next lexicographically greater permutation. If none exists, sort to lowest (e.g., [3,2,1] -> [1,2,3]).

Example: Input: nums = [1,2,3]
Output: [1,3,2]

• Technique: Find the first decreasing element from right, swap with the next larger, reverse the tail.
• Complexity: O(n) time, O(1) space.

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

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

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) swap(nums, start++, end--);
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        nextPermutation(nums);
        System.out.println(Arrays.toString(nums)); // [1, 3, 2]
    }
}
                                

Description: Given an array of stock prices, maximize profit by buying and selling multiple times (no overlapping transactions).

Example: Input: prices = [7,1,5,3,6,4]
Output: 7 (buy at 1, sell at 5: +4; buy at 3, sell at 6: +3)

• Technique: Greedy adds profit from every price increase.
• Complexity: O(n) time, O(1) space.

public class StockProfitII {
    public static int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        }
        return profit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices)); // 7
    }
}
                                

Description: Given an array where one element appears more than n/2 times, find that majority element.

Example: Input: nums = [3,2,3]
Output: 3 (appears 2/3 times)

• Technique: Boyer-Moore voting cancels out non-majority pairs, leaving the majority.
• Complexity: O(n) time, O(1) space.

public class MajorityElement {
    public static int majorityElement(int[] nums) {
        int candidate = nums[0], count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (count == 0) candidate = nums[i];
            count += (nums[i] == candidate) ? 1 : -1;
        }
        return candidate;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 3};
        System.out.println(majorityElement(nums)); // 3
    }
}
                                

Description: Given an m x n matrix, return all elements in spiral order (top row left-to-right, right column top-to-bottom, etc.).

Example: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

• Technique: Simulation uses four boundaries, shrinking inward after each traversal.
• Complexity: O(mn) time, O(1) space (excluding output).

import java.util.*;

public class SpiralMatrix {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) result.add(matrix[top][j]);
            top++;
            for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
            right--;
            if (top <= bottom) {
                for (int j = right; j >= left; j--) result.add(matrix[bottom][j]);
                bottom--;
            }
            if (left <= right) {
                for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
                left++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(spiralOrder(matrix)); // [1,2,3,6,9,8,7,4,5]
    }
}
                                

Description: Given a string, find the longest substring that is a palindrome (reads the same forward and backward).

Example: Input: s = "babad"
Output: "bab" ("aba" also valid)

• Technique: Expand around center checks each position for odd and even-length palindromes.
• Complexity: O(n²) time, O(1) space.

public class LongestPalindrome {
    public static String longestPalindrome(String s) {
        int start = 0, maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > maxLen) {
                start = i - (len - 1) / 2;
                maxLen = len;
            }
        }
        return s.substring(start, start + maxLen);
    }

    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad")); // "bab"
    }
}
                                

Description: Compress a string by replacing runs of repeated characters with the char and count (e.g., "aabccc" -> "a2b1c3"). Return the new length.

Example: Input: chars = ['a','a','b','c','c','c']
Output: 6 (chars becomes ['a','2','b','1','c','3'])

• Technique: Two pointers track runs, writing compressed result in-place.
• Complexity: O(n) time, O(1) space.

public class StringCompression {
    public static int compress(char[] chars) {
        int write = 0, anchor = 0;
        for (int read = 0; read < chars.length; read++) {
            if (read + 1 == chars.length || chars[read + 1] != chars[read]) {
                chars[write++] = chars[anchor];
                if (read > anchor) {
                    String count = String.valueOf(read - anchor + 1);
                    for (char c : count.toCharArray()) chars[write++] = c;
                }
                anchor = read + 1;
            }
        }
        return write;
    }

    public static void main(String[] args) {
        char[] chars = {'a','a','b','c','c','c'};
        int len = compress(chars);
        System.out.println(len); // 6
        System.out.println(Arrays.toString(Arrays.copyOf(chars, len))); // [a, 2, b, 1, c, 3]
    }
}
                                

Description: Given a string s and pattern t, find the smallest substring of s containing all characters of t (including duplicates).

Example: Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

• Technique: Sliding window uses two HashMaps to track required and current counts, shrinking when valid.
• Complexity: O(n) time, O(k) space (k = charset size).

import java.util.HashMap;

public class MinWindowSubstring {
    public static String minWindow(String s, String t) {
        HashMap<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        int required = tMap.size(), formed = 0;
        HashMap<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0, minLen = Integer.MAX_VALUE, minLeft = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (tMap.containsKey(c) && window.get(c).intValue() == tMap.get(c).intValue()) formed++;
            while (left <= right && formed == required) {
                c = s.charAt(left);
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                }
                window.put(c, window.get(c) - 1);
                if (tMap.containsKey(c) && window.get(c) < tMap.get(c)) formed--;
                left++;
            }
            right++;
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
    }

    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC")); // "BANC"
    }
}
                                

Description: Given a string, reverse only the vowels (a, e, i, o, u, case-insensitive), leaving consonants in place.

Example: Input: s = "hello"
Output: "holle" (e and o swapped)

• Technique: Two pointers move inward, swapping vowels while skipping consonants.
• Complexity: O(n) time, O(1) space.

public class ReverseVowels {
    public static String reverseVowels(String s) {
        char[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;
        String vowels = "aeiouAEIOU";
        while (left < right) {
            while (left < right && vowels.indexOf(chars[left]) == -1) left++;
            while (left < right && vowels.indexOf(chars[right]) == -1) right--;
            char temp = chars[left];
            chars[left++] = chars[right];
            chars[right--] = temp;
        }
        return new String(chars);
    }

    public static void main(String[] args) {
        System.out.println(reverseVowels("hello")); // "holle"
    }
}
                                

Description: Given a string and integer k, find the longest substring length where you can replace up to k characters to make all the same.

Example: Input: s = "ABAB", k = 2
Output: 4 (replace 2 B’s to A’s: "AAAA")

• Technique: Sliding window tracks max char count, shrinking if replacements exceed k.
• Complexity: O(n) time, O(1) space (26 chars).

public class CharacterReplacement {
    public static int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int maxCount = 0, maxLen = 0, start = 0;
        for (int end = 0; end < s.length(); end++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
            while (end - start + 1 - maxCount > k) {
                count[s.charAt(start) - 'A']--;
                start++;
            }
            maxLen = Math.max(maxLen, end - start + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(characterReplacement("ABAB", 2)); // 4
    }
}
                                

Description: Find the first occurrence of a substring (needle) in a string (haystack), returning its starting index or -1 if not found.

Example: Input: haystack = "hello", needle = "ll"
Output: 2

• Technique: Two pointers scan for matches, sliding window-like (simpler than KMP here).
• Complexity: O(n*m) time, O(1) space.

public class StrStr {
    public static int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0;
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            int j = 0;
            while (j < needle.length() && haystack.charAt(i + j) == needle.charAt(j)) j++;
            if (j == needle.length()) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(strStr("hello", "ll")); // 2
    }
}
                                

Description: Generate the nth term of the "count and say" sequence: 1, 11 (one 1), 21 (two 1s), 1211 (one 2, one 1), etc.

Example: Input: n = 4
Output: "1211"

• Technique: Recursion builds each term by counting consecutive digits of the previous term.
• Complexity: O(2^n) time, O(2^n) space.

public class CountAndSay {
    public static String countAndSay(int n) {
        if (n == 1) return "1";
        String prev = countAndSay(n - 1);
        StringBuilder result = new StringBuilder();
        int count = 1;
        for (int i = 0; i < prev.length(); i++) {
            if (i + 1 < prev.length() && prev.charAt(i) == prev.charAt(i + 1)) count++;
            else {
                result.append(count).append(prev.charAt(i));
                count = 1;
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(countAndSay(4)); // "1211"
    }
}
                                

Description: Multiply two non-negative numbers represented as strings, returning the product as a string (no conversion to int).

Example: Input: num1 = "123", num2 = "456"
Output: "56088"

• Technique: Simulation mimics digit-by-digit multiplication, storing results in an array with carry handling.
• Complexity: O(mn) time, O(m+n) space.

public class MultiplyStrings {
    public static String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int[] result = new int[num1.length() + num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            for (int j = num2.length() - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int sum = mul + result[i + j + 1];
                result[i + j + 1] = sum % 10;
                result[i + j] += sum / 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int digit : result) if (!(sb.length() == 0 && digit == 0)) sb.append(digit);
        return sb.length() == 0 ? "0" : sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(multiply("123", "456")); // "56088"
    }
}
                                

Description: Given a singly linked list, return the middle node. If even length, return the second middle node.

Example: Input: head = [1,2,3,4,5]
Output: [3,4,5] (node with value 3)

• Technique: Fast and slow pointers: fast moves twice as fast, stopping at the middle.
• Complexity: O(n) time, O(1) space.

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

public class MiddleOfList {
    public static ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        System.out.println(middleNode(head).val); // 3
    }
}
                                

Description: Given a linked list, swap every two adjacent nodes and return the new head. Values stay the same, only links change.

Example: Input: head = [1,2,3,4]
Output: [2,1,4,3]

• Technique: Pointer manipulation swaps pairs iteratively using a dummy node.
• Complexity: O(n) time, O(1) space.

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

public class SwapPairs {
    public static ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy;
        while (curr.next != null && curr.next.next != null) {
            ListNode first = curr.next;
            ListNode second = curr.next.next;
            curr.next = second;
            first.next = second.next;
            second.next = first;
            curr = first;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        ListNode result = swapPairs(head);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        } // 2 1 4 3
    }
}
                                

Description: Given a linked list, rotate it to the right by k places. If k exceeds length, use k % length.

Example: Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

• Technique: Close list into a ring, find new tail, break ring at k steps from end.
• Complexity: O(n) time, O(1) space.

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

public class RotateList {
    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        int length = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }
        k %= length;
        if (k == 0) return head;
        tail.next = head;
        ListNode newTail = head;
        for (int i = 0; i < length - k - 1; i++) newTail = newTail.next;
        ListNode newHead = newTail.next;
        newTail.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode result = rotateRight(head, 2);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        } // 4 5 1 2 3
    }
}
                                

Description: Given a linked list, group all odd-indexed nodes (1-based) followed by even-indexed nodes, preserving relative order.

Example: Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

• Technique: Pointer manipulation splits into odd/even lists, then merges.
• Complexity: O(n) time, O(1) space.

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

public class OddEvenList {
    public static ListNode oddEvenList(ListNode head) {
        if (head == null) return null;
        ListNode odd = head, even = head.next, evenHead = even;
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode result = oddEvenList(head);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        } // 1 3 5 2 4
    }
}
                                

Description: Given two linked lists, find their intersection node (where they merge), or null if none exists.

Example: Input: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], intersect at 8
Output: node with value 8

• Technique: Two pointers traverse both lists, switching heads to align lengths.
• Complexity: O(n + m) time, O(1) space.

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

public class IntersectionOfLists {
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }
        return p1;
    }

    public static void main(String[] args) {
        ListNode a = new ListNode(4);
        a.next = new ListNode(1);
        ListNode intersect = new ListNode(8);
        a.next.next = intersect;
        intersect.next = new ListNode(4);
        intersect.next.next = new ListNode(5);
        ListNode b = new ListNode(5);
        b.next = new ListNode(6);
        b.next.next = new ListNode(1);
        b.next.next.next = intersect;
        ListNode result = getIntersectionNode(a, b);
        System.out.println(result.val); // 8
    }
}
                                

Description: Given a linked list and value x, partition it so all nodes less than x come before nodes greater than or equal to x, preserving relative order.

Example: Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

• Technique: Two pointers build separate less-than and greater-than lists, then merge.
• Complexity: O(n) time, O(1) space.

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

public class PartitionList {
    public static ListNode partition(ListNode head, int x) {
        ListNode beforeDummy = new ListNode(0), afterDummy = new ListNode(0);
        ListNode before = beforeDummy, after = afterDummy;
        while (head != null) {
            if (head.val < x) {
                before.next = head;
                before = before.next;
            } else {
                after.next = head;
                after = after.next;
            }
            head = head.next;
        }
        after.next = null;
        before.next = afterDummy.next;
        return beforeDummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(2);
        ListNode result = partition(head, 3);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        } // 1 2 2 4 3 5
    }
}
                                

Description: Given an m x n matrix where each row is sorted left-to-right and each column top-to-bottom, search for a target value.

Example: Input: matrix = [[1,4,7],[2,5,8],[3,6,9]], target = 5
Output: true

• Technique: Start from top-right, move left if too big, down if too small, using sorted properties.
• Complexity: O(m + n) time, O(1) space.

public class SearchMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int row = 0, col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            if (matrix[row][col] == target) return true;
            else if (matrix[row][col] > target) col--;
            else row++;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 4, 7}, {2, 5, 8}, {3, 6, 9}};
        System.out.println(searchMatrix(matrix, 5)); // true
    }
}
                                

Description: Given a 2D grid of 1s (land) and 0s (water), find the maximum area of an island, where an island is a group of connected 1s (horizontally or vertically).

Example: Input: grid = [[1,1,0,0],[1,1,0,0],[0,0,1,0]]
Output: 4 (top-left island of four 1s)

• Technique: DFS explores connected land cells, marking them visited and summing their area.
• Complexity: O(mn) time, O(mn) space (recursion stack).

public class MaxAreaOfIsland {
    public static int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) maxArea = Math.max(maxArea, dfs(grid, i, j));
            }
        }
        return maxArea;
    }

    private static int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) return 0;
        grid[i][j] = 0;
        return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
    }

    public static void main(String[] args) {
        int[][] grid = {{1,1,0,0},{1,1,0,0},{0,0,1,0}};
        System.out.println(maxAreaOfIsland(grid)); // 4
    }
}
                                

Description: Given a binary tree, return the preorder traversal of its nodes' values (root, left, right).

Example: Input: root = [1,null,2,3] (1 as root, 2 as right child, 3 as 2's left child)
Output: [1,2,3]

• Technique: Iterative approach uses a stack to process root first, then right, then left.
• Complexity: O(n) time, O(h) space (h = tree height).

import java.util.*;

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

public class PreorderTraversal {
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        System.out.println(preorderTraversal(root)); // [1, 2, 3]
    }
}
                                

Description: Given a binary tree, determine if it’s a valid BST: each node’s value is greater than all in its left subtree and less than all in its right subtree.

Example: Input: root = [2,1,3]
Output: true (1 < 2 < 3)

• Technique: DFS with bounds checks each node against a valid range.
• Complexity: O(n) time, O(h) space.

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

public class ValidateBST {
    public static boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private static boolean isValidBST(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.val <= min || node.val >= max) return false;
        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        System.out.println(isValidBST(root)); // true
    }
}
                                

Description: Given preorder (root, left, right) and inorder (left, root, right) traversals, construct the binary tree.

Example: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

• Technique: Recursion uses preorder’s first element as root, splits inorder to build subtrees.
• Complexity: O(n) time with HashMap, O(n) space.

import java.util.HashMap;

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

public class BuildTree {
    HashMap<Integer, Integer> inorderMap = new HashMap<>();
    int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) inorderMap.put(inorder[i], i);
        return build(preorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;
        TreeNode root = new TreeNode(preorder[preIndex++]);
        int inIndex = inorderMap.get(root.val);
        root.left = build(preorder, inStart, inIndex - 1);
        root.right = build(preorder, inIndex + 1, inEnd);
        return root;
    }

    public static void main(String[] args) {
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        BuildTree bt = new BuildTree();
        TreeNode root = bt.buildTree(preorder, inorder);
        System.out.println(root.val + "," + root.left.val + "," + root.right.val); // 3,9,20
    }
}
                                

Description: Flatten a binary tree into a linked list in-place, using preorder traversal order (root, left, right).

Example: Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

• Technique: Recursion flattens right, then left, reassigning pointers.
• Complexity: O(n) time, O(h) space.

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

public class FlattenTree {
    public static void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.right = root.left;
        root.left = null;
        TreeNode curr = root;
        while (curr.right != null) curr = curr.right;
        curr.right = root.right;
        root.right = curr == root ? null : root.right;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);
        flatten(root);
        while (root != null) {
            System.out.print(root.val + " ");
            root = root.right;
        } // 1 2 3 4 5 6
    }
}
                                

Description: Given a binary tree, return the zigzag level order traversal (left-to-right on odd levels, right-to-left on even levels).

Example: Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

• Technique: BFS with a queue, reversing odd-level lists.
• Complexity: O(n) time, O(n) space.

import java.util.*;

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

public class ZigzagLevelOrder {
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true;
        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);
            }
            if (!leftToRight) Collections.reverse(level);
            result.add(level);
            leftToRight = !leftToRight;
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(zigzagLevelOrder(root)); // [[3], [20, 9], [15, 7]]
    }
}
                                

Description: Given a binary tree, find the length of its diameter (longest path between any two nodes, may not pass through root).

Example: Input: root = [1,2,3,4,5]
Output: 3 (path 4-2-1-3 or 5-2-1-3)

• Technique: DFS computes max depth of left and right subtrees, tracking global max diameter.
• Complexity: O(n) time, O(h) space.

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

public class DiameterOfTree {
    static int maxDiameter = 0;

    public static int diameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        height(root);
        return maxDiameter;
    }

    private static int height(TreeNode node) {
        if (node == null) return 0;
        int left = height(node.left);
        int right = height(node.right);
        maxDiameter = Math.max(maxDiameter, left + right);
        return Math.max(left, right) + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        System.out.println(diameterOfBinaryTree(root)); // 3
    }
}
                                

Description: Given an n x n binary matrix (0s passable, 1s blocked), find the shortest path length from top-left to bottom-right using 8-directional moves.

Example: Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4 (path: (0,0) -> (0,1) -> (1,2) -> (2,2))

• Technique: BFS finds shortest path in an unweighted graph, using a queue.
• Complexity: O(n²) time, O(n²) space.

import java.util.*;

public class ShortestPathBinaryMatrix {
    public static int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1) return -1;
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        grid[0][0] = 1;
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0], col = cell[1];
            if (row == n - 1 && col == n - 1) return grid[row][col];
            for (int[] dir : dirs) {
                int newRow = row + dir[0], newCol = col + dir[1];
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] == 0) {
                    queue.offer(new int[]{newRow, newCol});
                    grid[newRow][newCol] = grid[row][col] + 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[][] grid = {{0,0,0},{1,1,0},{1,1,0}};
        System.out.println(shortestPathBinaryMatrix(grid)); // 4
    }
}
                                

Description: Given an image (2D array), a starting pixel (sr, sc), and a new color, replace the old color with the new color for all connected pixels of the same old color (4-directional).

Example: Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

• Technique: DFS recursively floods connected pixels with the new color.
• Complexity: O(mn) time, O(mn) space.

public class FloodFill {
    public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image[sr][sc] == newColor) return image;
        dfs(image, sr, sc, image[sr][sc], newColor);
        return image;
    }

    private static void dfs(int[][] image, int r, int c, int oldColor, int newColor) {
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] != oldColor) return;
        image[r][c] = newColor;
        dfs(image, r + 1, c, oldColor, newColor);
        dfs(image, r - 1, c, oldColor, newColor);
        dfs(image, r, c + 1, oldColor, newColor);
        dfs(image, r, c - 1, oldColor, newColor);
    }

    public static void main(String[] args) {
        int[][] image = {{1,1,1},{1,1,0},{1,0,1}};
        int[][] result = floodFill(image, 1, 1, 2);
        for (int[] row : result) System.out.println(Arrays.toString(row));
        // [[2,2,2],[2,2,0],[2,0,1]]
    }
}
                                

Description: Given a grid with 0 (empty), 1 (fresh orange), and 2 (rotten orange), find the minimum minutes until all oranges rot (rotten spreads 4-directionally), or -1 if impossible.

Example: Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

• Technique: BFS starts from all rotten oranges, spreading to fresh ones level by level.
• Complexity: O(mn) time, O(mn) space.

import java.util.*;

public class RottingOranges {
    public static int orangesRotting(int[][] grid) {
        int fresh = 0, minutes = 0;
        Queue<int[]> queue = new LinkedList<>();
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) queue.offer(new int[]{i, j});
                else if (grid[i][j] == 1) fresh++;
            }
        }
        while (!queue.isEmpty() && fresh > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                for (int[] dir : dirs) {
                    int r = cell[0] + dir[0], c = cell[1] + dir[1];
                    if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length && grid[r][c] == 1) {
                        grid[r][c] = 2;
                        queue.offer(new int[]{r, c});
                        fresh--;
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }

    public static void main(String[] args) {
        int[][] grid = {{2,1,1},{1,1,0},{0,1,1}};
        System.out.println(orangesRotting(grid)); // 4
    }
}
                                

Description: Given an m x n grid of heights, find all cells where water can flow to both Pacific (top/left) and Atlantic (bottom/right) oceans.

Example: Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1]]
Output: [[0,4],[1,3],[1,4],[2,2]]

• Technique: DFS from ocean borders marks reachable cells, intersecting Pacific and Atlantic sets.
• Complexity: O(mn) time, O(mn) space.

import java.util.*;

public class PacificAtlantic {
    public static List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        for (int i = 0; i < m; i++) {
            dfs(heights, pacific, i, 0, Integer.MIN_VALUE, dirs);
            dfs(heights, atlantic, i, n - 1, Integer.MIN_VALUE, dirs);
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, pacific, 0, j, Integer.MIN_VALUE, dirs);
            dfs(heights, atlantic, m - 1, j, Integer.MIN_VALUE, dirs);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) result.add(Arrays.asList(i, j));
            }
        }
        return result;
    }

    private static void dfs(int[][] heights, boolean[][] visited, int r, int c, int prev, int[][] dirs) {
        if (r < 0 || r >= heights.length || c < 0 || c >= heights[0].length || visited[r][c] || heights[r][c] < prev) return;
        visited[r][c] = true;
        for (int[] dir : dirs) dfs(heights, visited, r + dir[0], c + dir[1], heights[r][c], dirs);
    }

    public static void main(String[] args) {
        int[][] heights = {{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1}};
        System.out.println(pacificAtlantic(heights)); // [[0,4], [1,3], [1,4], [2,2]]
    }
}
                                

Description: Given n nodes and an edge list, check if it forms a valid tree (connected, no cycles).

Example: Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

• Technique: Union-Find detects cycles and ensures connectivity (n-1 edges).
• Complexity: O(n + e * α(n)) time, O(n) space (α = inverse Ackermann).

public class GraphValidTree {
    static int[] parent;

    public static boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] edge : edges) {
            int x = find(edge[0]), y = find(edge[1]);
            if (x == y) return false;
            parent[x] = y;
        }
        return true;
    }

    private static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0,1},{0,2},{0,3},{1,4}};
        System.out.println(validTree(n, edges)); // true
    }
}
                                

Description: Given a list of accounts (name + email list), merge accounts with common emails, returning merged lists with sorted emails.

Example: Input: accounts = [["John","j1","j2"],["John","j3","j2"],["Mary","m1"]]
Output: [["John","j1","j2","j3"],["Mary","m1"]]

• Technique: Union-Find groups emails by account, then maps to names.
• Complexity: O(n * α(n)) time, O(n) space (n = total emails).

import java.util.*;

public class AccountsMerge {
    public static List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> parent = new HashMap<>();
        Map<String, String> emailToName = new HashMap<>();
        Map<String, TreeSet<String>> unions = new HashMap<>();

        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                parent.put(email, email);
                emailToName.put(email, name);
            }
        }

        for (List<String> account : accounts) {
            String p1 = find(parent, account.get(1));
            for (int i = 2; i < account.size(); i++) {
                String p2 = find(parent, account.get(i));
                parent.put(p2, p1);
            }
        }

        for (String email : parent.keySet()) {
            String root = find(parent, email);
            unions.computeIfAbsent(root, k -> new TreeSet<>()).add(email);
        }

        List<List<String>> result = new ArrayList<>();
        for (String root : unions.keySet()) {
            List<String> merged = new ArrayList<>();
            merged.add(emailToName.get(root));
            merged.addAll(unions.get(root));
            result.add(merged);
        }
        return result;
    }

    private static String find(Map<String, String> parent, String email) {
        if (!parent.get(email).equals(email)) parent.put(email, find(parent, parent.get(email)));
        return parent.get(email);
    }

    public static void main(String[] args) {
        List<List<String>> accounts = Arrays.asList(
            Arrays.asList("John", "j1", "j2"),
            Arrays.asList("John", "j3", "j2"),
            Arrays.asList("Mary", "m1")
        );
        System.out.println(accountsMerge(accounts)); // [["John","j1","j2","j3"],["Mary","m1"]]
    }
}
                                

Description: Given an undirected graph with weighted edges, find the minimum spanning tree’s total weight using Kruskal’s algorithm.

Example: Input: n = 4, edges = [[0,1,10],[0,2,6],[1,3,15],[2,3,4]]
Output: 20 (edges: 0-2, 2-3, 0-1)

• Technique: Union-Find sorts edges by weight, adding non-cyclic ones.
• Complexity: O(e log e) time, O(n) space.

import java.util.*;

public class KruskalMST {
    static int[] parent;

    public static int minCost(int n, int[][] edges) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
        int cost = 0, count = 0;
        for (int[] edge : edges) {
            int x = find(edge[0]), y = find(edge[1]);
            if (x != y) {
                parent[x] = y;
                cost += edge[2];
                count++;
            }
            if (count == n - 1) break;
        }
        return count == n - 1 ? cost : -1;
    }

    private static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{0,1,10},{0,2,6},{1,3,15},{2,3,4}};
        System.out.println(minCost(n, edges)); // 20
    }
}
                                

Description: Given an undirected graph with non-negative weights, find the shortest path length from a source to all nodes using Dijkstra’s algorithm.

Example: Input: n = 4, edges = [[0,1,4],[0,2,8],[1,2,11],[1,3,2],[2,3,1]], src = 0
Output: [0,4,7,6]

• Technique: Priority queue processes nodes by shortest distance first, relaxing edges.
• Complexity: O((n + e) log n) time, O(n + e) space.

import java.util.*;

public class Dijkstra {
    public static int[] shortestPath(int n, int[][] edges, int src) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
            graph.get(edge[1]).add(new int[]{edge[0], edge[2]});
        }
        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]);
        pq.offer(new int[]{src, 0});
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0], d = curr[1];
            if (d > dist[u]) continue;
            for (int[] neighbor : graph.get(u)) {
                int v = neighbor[0], w = neighbor[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{0,1,4},{0,2,8},{1,2,11},{1,3,2},{2,3,1}};
        System.out.println(Arrays.toString(shortestPath(n, edges, 0))); // [0, 4, 7, 6]
    }
}
                                

Description: Given an m x n grid of non-negative numbers, find the minimum path sum from top-left to bottom-right, moving only right or down.

Example: Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7 (path: 1->3->1->1->1)

• Technique: DP updates grid in-place with minimum sums from top-left.
• Complexity: O(mn) time, O(1) space.

public class MinPathSum {
    public static int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 1; i < m; i++) grid[i][0] += grid[i - 1][0];
        for (int j = 1; j < n; j++) grid[0][j] += grid[0][j - 1];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(minPathSum(grid)); // 7
    }
}
                                

Description: Given an m x n grid, find the number of unique paths from top-left to bottom-right, moving only right or down.

Example: Input: m = 3, n = 2
Output: 3 (paths: RRD, RDR, DRR)

• Technique: DP uses a 1D array to count paths, as each cell is sum of paths from above and left.
• Complexity: O(mn) time, O(n) space.

public class UniquePaths {
    public static int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 2)); // 3
    }
}
                                

Description: Given a 2D binary matrix of 0s and 1s, find the area of the largest square containing all 1s.

Example: Input: matrix = [["1","0","1","0"],["1","0","1","1"],["1","1","1","1"]]
Output: 4 (bottom-right 2x2 square)

• Technique: DP builds square sizes based on min of top, left, and top-left neighbors.
• Complexity: O(mn) time, O(mn) space.

public class MaximalSquare {
    public static int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length, maxSide = 0;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }

    public static void main(String[] args) {
        char[][] matrix = {{'1','0','1','0'},{'1','0','1','1'},{'1','1','1','1'}};
        System.out.println(maximalSquare(matrix)); // 4
    }
}
                                

Description: Given an array of positive integers, determine if it can be partitioned into two subsets with equal sums.

Example: Input: nums = [1,5,11,5]
Output: true (e.g., [1,5,5] and [11])

• Technique: DP uses a boolean array to track achievable sums up to target (half of total).
• Complexity: O(n * sum) time, O(sum) space.

public class PartitionEqualSubsetSum {
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] |= dp[j - num];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        System.out.println(canPartition(nums)); // true
    }
}
                                

Description: Given a string, find the length of the longest palindromic subsequence (not necessarily contiguous).

Example: Input: s = "bbbab"
Output: 4 ("bbbb")

• Technique: DP compares string with its reverse, finding longest common subsequence.
• Complexity: O(n²) time, O(n²) space.

public class LongestPalindromicSubseq {
    public static int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n + 1][n + 1];
        String rev = new StringBuilder(s).reverse().toString();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == rev.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[n][n];
    }

    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("bbbab")); // 4
    }
}
                                

Description: Given two strings, find the minimum number of operations (insert, delete, replace) to convert one into the other.

Example: Input: word1 = "horse", word2 = "ros"
Output: 3 (horse -> rorse -> rose -> ros)

• Technique: DP builds a 2D table comparing substrings, choosing min cost operation.
• Complexity: O(mn) time, O(mn) space.

public class EditDistance {
    public static int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros")); // 3
    }
}
                                

Description: Given n pairs of parentheses, generate all valid combinations (well-formed, balanced).

Example: Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

• Technique: Backtracking builds strings, adding open/close parens with constraints.
• Complexity: O(4^n/√n) time, O(n) space.

import java.util.*;

public class GenerateParentheses {
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }

    private static void backtrack(List<String> result, String curr, int open, int close, int max) {
        if (curr.length() == max * 2) {
            result.add(curr);
            return;
        }
        if (open < max) backtrack(result, curr + "(", open + 1, close, max);
        if (close < open) backtrack(result, curr + ")", open, close + 1, max);
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3)); // ["((()))","(()())","(())()","()(())","()()()"]
    }
}
                                

Description: Given an array where each element is the max jump length from that index, determine if you can reach the last index.

Example: Input: nums = [2,3,1,1,4]
Output: true (e.g., 2->3->4)

• Technique: Greedy tracks the maximum reachable index, checking if it covers the end.
• Complexity: O(n) time, O(1) space.

public class JumpGame {
    public static boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) return false;
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1) return true;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println(canJump(nums)); // true
    }
}
                                

Description: Given an array of points (x, y) and integer k, find the k points closest to the origin (0,0) based on Euclidean distance.

Example: Input: points = [[1,3],[-2,2],[5,8]], k = 2
Output: [[-2,2],[1,3]]

• Technique: Max heap maintains k smallest distances, popping larger ones.
• Complexity: O(n log k) time, O(k) space.

import java.util.*;

public class KClosestPoints {
    public static int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> 
            (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]));
        for (int[] point : points) {
            pq.offer(point);
            if (pq.size() > k) pq.poll();
        }
        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++) result[i] = pq.poll();
        return result;
    }

    public static void main(String[] args) {
        int[][] points = {{1,3},{-2,2},{5,8}};
        int[][] result = kClosest(points, 2);
        for (int[] p : result) System.out.println(Arrays.toString(p)); // [-2,2], [1,3]
    }
}
                                

Description: Given an array where every element appears twice except one, find that single number.

Example: Input: nums = [4,1,2,1,2]
Output: 4

• Technique: Bit manipulation uses XOR to cancel duplicates (a XOR a = 0, a XOR 0 = a).
• Complexity: O(n) time, O(1) space.

public class SingleNumber {
    public static int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) result ^= num;
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 1, 2, 1, 2};
        System.out.println(singleNumber(nums)); // 4
    }
}