Skip to content

Instantly share code, notes, and snippets.

@carefree-ladka

carefree-ladka/Blind 75 LeetCode Java.mdx

Created February 28, 2026 01:28
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save carefree-ladka/149ad7d631199c60fc20465337ab0a89 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save carefree-ladka/149ad7d631199c60fc20465337ab0a89 to your computer and use it in GitHub Desktop.
Download ZIP
Blind 75 LeetCode in Java
Raw
Blind 75 LeetCode Java.mdx

LeetCode Java Solutions: Brute Force & Optimal

Table of Contents

Array

Two Sum

Brute Force — O(n²) time, O(1) space

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++)
        for (int j = i + 1; j < nums.length; j++)
            if (nums[i] + nums[j] == target)
                return new int[]{i, j};
    return new int[]{};
}

Optimal — O(n) time, O(n) space

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement))
            return new int[]{map.get(complement), i};
        map.put(nums[i], i);
    }
    return new int[]{};
}

Best Time to Buy and Sell Stock

Brute Force — O(n²) time, O(1) space

public int maxProfit(int[] prices) {
    int max = 0;
    for (int i = 0; i < prices.length; i++)
        for (int j = i + 1; j < prices.length; j++)
            max = Math.max(max, prices[j] - prices[i]);
    return max;
}

Optimal — O(n) time, O(1) space

public 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;
}

Contains Duplicate

Brute Force — O(n²) time, O(1) space

public boolean containsDuplicate(int[] nums) {
    for (int i = 0; i < nums.length; i++)
        for (int j = i + 1; j < nums.length; j++)
            if (nums[i] == nums[j]) return true;
    return false;
}

Optimal — O(n) time, O(n) space

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

Product of Array Except Self

Brute Force — O(n²) time, O(1) space

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
        result[i] = 1;
        for (int j = 0; j < n; j++)
            if (i != j) result[i] *= nums[j];
    }
    return result;
}

Optimal — O(n) time, O(1) extra space

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

Maximum Subarray

Brute Force — O(n²) time, O(1) space

public int maxSubArray(int[] nums) {
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            max = Math.max(max, sum);
        }
    }
    return max;
}

Optimal (Kadane's) — O(n) time, O(1) space

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

Maximum Product Subarray

Brute Force — O(n²) time, O(1) space

public int maxProduct(int[] nums) {
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int product = 1;
        for (int j = i; j < nums.length; j++) {
            product *= nums[j];
            max = Math.max(max, product);
        }
    }
    return max;
}

Optimal — O(n) time, O(1) space

public int maxProduct(int[] nums) {
    int max = nums[0], min = nums[0], result = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int temp = max;
        max = Math.max(nums[i], Math.max(max * nums[i], min * nums[i]));
        min = Math.min(nums[i], Math.min(temp * nums[i], min * nums[i]));
        result = Math.max(result, max);
    }
    return result;
}

Find Minimum in Rotated Sorted Array

Brute Force — O(n) time, O(1) space

public int findMin(int[] nums) {
    int min = nums[0];
    for (int n : nums) min = Math.min(min, n);
    return min;
}

Optimal (Binary Search) — O(log n) time, O(1) space

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

Search in Rotated Sorted Array

Brute Force — O(n) time, O(1) space

public int search(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++)
        if (nums[i] == target) return i;
    return -1;
}

Optimal (Binary Search) — O(log n) time, O(1) space

public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) {
            if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

3 Sum

Brute Force — O(n³) time, O(1) space

public List<List<Integer>> threeSum(int[] nums) {
    Set<List<Integer>> result = new HashSet<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++)
        for (int j = i + 1; j < nums.length - 1; j++)
            for (int k = j + 1; k < nums.length; k++)
                if (nums[i] + nums[j] + nums[k] == 0)
                    result.add(Arrays.asList(nums[i], nums[j], nums[k]));
    return new ArrayList<>(result);
}

Optimal (Two Pointers) — O(n²) time, O(1) space

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int lo = i + 1, hi = nums.length - 1;
        while (lo < hi) {
            int sum = nums[i] + nums[lo] + nums[hi];
            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
                while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
                lo++; hi--;
            } else if (sum < 0) lo++;
            else hi--;
        }
    }
    return result;
}

Container With Most Water

Brute Force — O(n²) time, O(1) space

public int maxArea(int[] height) {
    int max = 0;
    for (int i = 0; i < height.length; i++)
        for (int j = i + 1; j < height.length; j++)
            max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
    return max;
}

Optimal (Two Pointers) — O(n) time, O(1) space

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

Binary

Sum of Two Integers

Brute Force — Using Java's built-in (for reference)

// Using + operator is trivial; bit manipulation is the challenge itself
public int getSum(int a, int b) {
    return a + b; // trivial brute force
}

Optimal (Bit Manipulation) — O(1) time, O(1) space

public int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

Number of 1 Bits

Brute Force — O(32) time, O(1) space

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        count += n & 1;
        n >>>= 1;
    }
    return count;
}

Optimal (Brian Kernighan) — O(number of set bits) time, O(1) space

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1); // clears lowest set bit
        count++;
    }
    return count;
}

Counting Bits

Brute Force — O(n log n) time, O(n) space

public int[] countBits(int n) {
    int[] result = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int x = i, cnt = 0;
        while (x > 0) { cnt += x & 1; x >>= 1; }
        result[i] = cnt;
    }
    return result;
}

Optimal (DP) — O(n) time, O(n) space

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

Missing Number

Brute Force — O(n²) time, O(1) space

public int missingNumber(int[] nums) {
    for (int i = 0; i <= nums.length; i++) {
        boolean found = false;
        for (int n : nums) if (n == i) { found = true; break; }
        if (!found) return i;
    }
    return -1;
}

Optimal (Gauss Formula) — O(n) time, O(1) space

public int missingNumber(int[] nums) {
    int n = nums.length, sum = n * (n + 1) / 2;
    for (int num : nums) sum -= num;
    return sum;
}

Reverse Bits

Brute Force — O(32) time, O(1) space

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;
    }
    return result;
}

Optimal (Divide & Conquer with masks) — O(1) time, O(1) space

public int reverseBits(int n) {
    n = (n >>> 16) | (n << 16);
    n = ((n & 0xff00ff00) >>> 8)  | ((n & 0x00ff00ff) << 8);
    n = ((n & 0xf0f0f0f0) >>> 4)  | ((n & 0x0f0f0f0f) << 4);
    n = ((n & 0xcccccccc) >>> 2)  | ((n & 0x33333333) << 2);
    n = ((n & 0xaaaaaaaa) >>> 1)  | ((n & 0x55555555) << 1);
    return n;
}

Dynamic Programming

Climbing Stairs

Brute Force (Recursion) — O(2ⁿ) time, O(n) space

public int climbStairs(int n) {
    if (n <= 2) return n;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

Optimal — O(n) time, O(1) space

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

Coin Change

Brute Force (Recursion) — O(S^n) time, O(n) space

public int coinChange(int[] coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
        int res = coinChange(coins, amount - coin);
        if (res >= 0 && res < min) min = res + 1;
    }
    return min == Integer.MAX_VALUE ? -1 : min;
}

Optimal (Bottom-Up DP) — O(amount × coins) time, O(amount) space

public 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 (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

Longest Increasing Subsequence

Brute Force (Recursion) — O(2ⁿ) time, O(n) space

public int lengthOfLIS(int[] nums) {
    return lis(nums, Integer.MIN_VALUE, 0);
}
private int lis(int[] nums, int prev, int idx) {
    if (idx == nums.length) return 0;
    int skip = lis(nums, prev, idx + 1);
    int take = 0;
    if (nums[idx] > prev) take = 1 + lis(nums, nums[idx], idx + 1);
    return Math.max(skip, take);
}

Optimal (Patience Sorting / Binary Search) — O(n log n) time, O(n) space

public int lengthOfLIS(int[] nums) {
    List<Integer> sub = new ArrayList<>();
    for (int num : nums) {
        int pos = Collections.binarySearch(sub, num);
        if (pos < 0) pos = -(pos + 1);
        if (pos == sub.size()) sub.add(num);
        else sub.set(pos, num);
    }
    return sub.size();
}

Longest Common Subsequence

Brute Force (Recursion) — O(2^(m+n)) time

public int longestCommonSubsequence(String text1, String text2) {
    return lcs(text1, text2, 0, 0);
}
private int lcs(String s1, String s2, int i, int j) {
    if (i == s1.length() || j == s2.length()) return 0;
    if (s1.charAt(i) == s2.charAt(j)) return 1 + lcs(s1, s2, i + 1, j + 1);
    return Math.max(lcs(s1, s2, i + 1, j), lcs(s1, s2, i, j + 1));
}

Optimal (Bottom-Up DP) — O(m×n) time, O(m×n) space

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (text1.charAt(i - 1) == text2.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    return dp[m][n];
}

Word Break Problem

Brute Force (Recursion) — O(2ⁿ) time

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> set = new HashSet<>(wordDict);
    return wb(s, set, 0);
}
private boolean wb(String s, Set<String> dict, int start) {
    if (start == s.length()) return true;
    for (int end = start + 1; end <= s.length(); end++)
        if (dict.contains(s.substring(start, end)) && wb(s, dict, end))
            return true;
    return false;
}

Optimal (DP) — O(n²) time, O(n) space

public 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()];
}

Combination Sum

Brute Force / Optimal (Backtracking) — O(N^(T/M)) time

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

House Robber

Brute Force (Recursion) — O(2ⁿ) time

public int rob(int[] nums) {
    return robFrom(nums, 0);
}
private int robFrom(int[] nums, int i) {
    if (i >= nums.length) return 0;
    return Math.max(robFrom(nums, i + 1),
                    nums[i] + robFrom(nums, i + 2));
}

Optimal — O(n) time, O(1) space

public int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;
    for (int num : nums) {
        int curr = Math.max(prev1, prev2 + num);
        prev2 = prev1; prev1 = curr;
    }
    return prev1;
}

House Robber II

Brute Force — same recursion as House Robber I applied twice

public int rob(int[] nums) {
    if (nums.length == 1) return nums[0];
    return Math.max(robRange(nums, 0, nums.length - 2),
                    robRange(nums, 1, nums.length - 1));
}
private int robRange(int[] nums, int lo, int hi) {
    int prev2 = 0, prev1 = 0;
    for (int i = lo; i <= hi; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1; prev1 = curr;
    }
    return prev1;
}

Optimal — O(n) time, O(1) space (same pattern as above, already optimal)

// Identical to brute force above — the two-pass approach IS optimal for this problem

Decode Ways

Brute Force (Recursion) — O(2ⁿ) time

public int numDecodings(String s) {
    return decode(s, 0);
}
private int decode(String s, int i) {
    if (i == s.length()) return 1;
    if (s.charAt(i) == '0') return 0;
    int ways = decode(s, i + 1);
    if (i + 1 < s.length()) {
        int two = Integer.parseInt(s.substring(i, i + 2));
        if (two >= 10 && two <= 26) ways += decode(s, i + 2);
    }
    return ways;
}

Optimal (DP) — O(n) time, O(1) space

public int numDecodings(String s) {
    int n = s.length(), dp1 = 1, dp2 = 0;
    if (s.charAt(0) == '0') return 0;
    dp2 = 1;
    for (int i = 1; i < n; i++) {
        int curr = 0;
        if (s.charAt(i) != '0') curr = dp2;
        int two = Integer.parseInt(s.substring(i - 1, i + 1));
        if (two >= 10 && two <= 26) curr += dp1;
        dp1 = dp2; dp2 = curr;
    }
    return dp2;
}

Unique Paths

Brute Force (Recursion) — O(2^(m+n)) time

public int uniquePaths(int m, int n) {
    if (m == 1 || n == 1) return 1;
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}

Optimal (DP) — O(m×n) time, O(n) space

public 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];
}

Jump Game

Brute Force (Recursion) — O(2ⁿ) time

public boolean canJump(int[] nums) {
    return jump(nums, 0);
}
private boolean jump(int[] nums, int i) {
    if (i >= nums.length - 1) return true;
    for (int j = 1; j <= nums[i]; j++)
        if (jump(nums, i + j)) return true;
    return false;
}

Optimal (Greedy) — O(n) time, O(1) space

public 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]);
    }
    return true;
}

Graph

Tree node and graph node definitions used throughout:

class TreeNode { int val; TreeNode left, right; }
class Node { int val; List<Node> neighbors; }

Clone Graph

Brute Force / Optimal (BFS + HashMap) — O(V+E) time, O(V) space

public Node cloneGraph(Node node) {
    if (node == null) return null;
    Map<Node, Node> map = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();
    queue.offer(node);
    map.put(node, new Node(node.val, new ArrayList<>()));
    while (!queue.isEmpty()) {
        Node curr = queue.poll();
        for (Node neighbor : curr.neighbors) {
            if (!map.containsKey(neighbor)) {
                map.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
                queue.offer(neighbor);
            }
            map.get(curr).neighbors.add(map.get(neighbor));
        }
    }
    return map.get(node);
}

Course Schedule

Brute Force — O(V×(V+E)) cycle detection per vertex

// DFS for each node checking cycles (less efficient)
public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    for (int[] pre : prerequisites) adj.get(pre[0]).add(pre[1]);
    int[] visited = new int[numCourses]; // 0=unvisited,1=visiting,2=done
    for (int i = 0; i < numCourses; i++)
        if (hasCycle(adj, visited, i)) return false;
    return true;
}
private boolean hasCycle(List<List<Integer>> adj, int[] visited, int node) {
    if (visited[node] == 1) return true;
    if (visited[node] == 2) return false;
    visited[node] = 1;
    for (int neighbor : adj.get(node))
        if (hasCycle(adj, visited, neighbor)) return true;
    visited[node] = 2;
    return false;
}

Optimal (Topological Sort / Kahn's BFS) — O(V+E) time, O(V+E) space

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    for (int[] pre : prerequisites) { adj.get(pre[1]).add(pre[0]); inDegree[pre[0]]++; }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) if (inDegree[i] == 0) queue.offer(i);
    int count = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll(); count++;
        for (int next : adj.get(course))
            if (--inDegree[next] == 0) queue.offer(next);
    }
    return count == numCourses;
}

Pacific Atlantic Water Flow

Brute Force — O(m×n×(m×n)) time — BFS from each cell

// Run BFS/DFS from each cell; check if both oceans reachable
// Omitted for brevity — same logic as optimal but inverted direction

Optimal (Reverse BFS from oceans) — O(m×n) time, O(m×n) space

public List<List<Integer>> pacificAtlantic(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
    Queue<int[]> pq = new LinkedList<>(), aq = new LinkedList<>();
    for (int i = 0; i < m; i++) { pq.offer(new int[]{i,0}); pac[i][0]=true; aq.offer(new int[]{i,n-1}); atl[i][n-1]=true; }
    for (int j = 0; j < n; j++) { pq.offer(new int[]{0,j}); pac[0][j]=true; aq.offer(new int[]{m-1,j}); atl[m-1][j]=true; }
    bfs(heights, pq, pac); bfs(heights, aq, atl);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (pac[i][j] && atl[i][j]) result.add(Arrays.asList(i, j));
    return result;
}
private void bfs(int[][] h, Queue<int[]> q, boolean[][] visited) {
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    while (!q.isEmpty()) {
        int[] cell = q.poll(); int r = cell[0], c = cell[1];
        for (int[] d : dirs) {
            int nr = r+d[0], nc = c+d[1];
            if (nr<0||nr>=h.length||nc<0||nc>=h[0].length||visited[nr][nc]||h[nr][nc]<h[r][c]) continue;
            visited[nr][nc] = true; q.offer(new int[]{nr,nc});
        }
    }
}

Number of Islands

Brute Force / Optimal (DFS) — O(m×n) time, O(m×n) space

public 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 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);
}

Longest Consecutive Sequence

Brute Force — O(n³) time, O(1) space

public int longestConsecutive(int[] nums) {
    int max = 0;
    for (int num : nums) {
        int curr = num, streak = 1;
        while (contains(nums, curr + 1)) { curr++; streak++; }
        max = Math.max(max, streak);
    }
    return max;
}
private boolean contains(int[] nums, int val) {
    for (int n : nums) if (n == val) return true;
    return false;
}

Optimal — O(n) time, O(n) space

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);
    int max = 0;
    for (int n : set) {
        if (!set.contains(n - 1)) {
            int curr = n, streak = 1;
            while (set.contains(curr + 1)) { curr++; streak++; }
            max = Math.max(max, streak);
        }
    }
    return max;
}

Alien Dictionary

Optimal (Topological Sort) — O(C) where C = total chars in words

public String alienOrder(String[] words) {
    Map<Character, Set<Character>> adj = new LinkedHashMap<>();
    Map<Character, Integer> inDegree = new HashMap<>();
    for (String word : words)
        for (char c : word.toCharArray()) { adj.putIfAbsent(c, new HashSet<>()); inDegree.putIfAbsent(c, 0); }
    for (int i = 0; i < words.length - 1; i++) {
        String w1 = words[i], w2 = words[i + 1];
        if (w1.length() > w2.length() && w1.startsWith(w2)) return "";
        for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
            if (w1.charAt(j) != w2.charAt(j)) {
                if (adj.get(w1.charAt(j)).add(w2.charAt(j)))
                    inDegree.merge(w2.charAt(j), 1, Integer::sum);
                break;
            }
        }
    }
    Queue<Character> queue = new LinkedList<>();
    for (char c : inDegree.keySet()) if (inDegree.get(c) == 0) queue.offer(c);
    StringBuilder sb = new StringBuilder();
    while (!queue.isEmpty()) {
        char c = queue.poll(); sb.append(c);
        for (char next : adj.get(c))
            if (inDegree.merge(next, -1, Integer::sum) == 0) queue.offer(next);
    }
    return sb.length() == inDegree.size() ? sb.toString() : "";
}

Graph Valid Tree

Optimal (Union-Find) — O(n + e·α(n)) time

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

Number of Connected Components

Optimal (Union-Find) — O(n + e·α(n)) time

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

Interval

Insert Interval

Optimal — O(n) time, O(n) space

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0, n = intervals.length;
    while (i < n && intervals[i][1] < newInterval[0]) result.add(intervals[i++]);
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval);
    while (i < n) result.add(intervals[i++]);
    return result.toArray(new int[0][]);
}

Merge Intervals

Brute Force — O(n² log n) time

// Repeated merge passes until stable (not recommended)

Optimal — O(n log n) time, O(n) space

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> 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][]);
}

Non-overlapping Intervals

Optimal (Greedy) — O(n log n) time, O(1) space

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    int count = 0, end = Integer.MIN_VALUE;
    for (int[] interval : intervals) {
        if (interval[0] >= end) end = interval[1];
        else count++;
    }
    return count;
}

Meeting Rooms

Optimal — O(n log n) time, O(1) space

public 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;
}

Meeting Rooms II

Optimal (Min-Heap) — O(n log n) time, O(n) space

public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int[] interval : intervals) {
        if (!heap.isEmpty() && heap.peek() <= interval[0]) heap.poll();
        heap.offer(interval[1]);
    }
    return heap.size();
}

Linked List

class ListNode { int val; ListNode next; }

Reverse a Linked List

Brute Force (Extra Space) — O(n) time, O(n) space

public ListNode reverseList(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode n = head; n != null; n = n.next) vals.add(n.val);
    ListNode curr = head;
    for (int i = vals.size()-1; i >= 0; i--) { curr.val = vals.get(i); curr = curr.next; }
    return head;
}

Optimal (Iterative) — O(n) time, O(1) space

public ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

Detect Cycle in a Linked List

Brute Force — O(n) time, O(n) space

public boolean hasCycle(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    while (head != null) {
        if (!seen.add(head)) return true;
        head = head.next;
    }
    return false;
}

Optimal (Floyd's Tortoise & Hare) — O(n) time, O(1) space

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Merge Two Sorted Lists

Brute Force — collect, sort, rebuild — O(n log n) time

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    List<Integer> vals = new ArrayList<>();
    while (l1 != null) { vals.add(l1.val); l1 = l1.next; }
    while (l2 != null) { vals.add(l2.val); l2 = l2.next; }
    Collections.sort(vals);
    ListNode dummy = new ListNode(0), curr = dummy;
    for (int v : vals) { curr.next = new ListNode(v); curr = curr.next; }
    return dummy.next;
}

Optimal — O(n+m) time, O(1) space

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), 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;
}

Merge K Sorted Lists

Brute Force — collect all, sort, rebuild — O(N log N) time

public ListNode mergeKLists(ListNode[] lists) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode l : lists) while (l != null) { vals.add(l.val); l = l.next; }
    Collections.sort(vals);
    ListNode dummy = new ListNode(0), curr = dummy;
    for (int v : vals) { curr.next = new ListNode(v); curr = curr.next; }
    return dummy.next;
}

Optimal (Min-Heap) — O(N log k) time, O(k) space

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode l : lists) if (l != null) heap.offer(l);
    ListNode dummy = new ListNode(0), curr = dummy;
    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        curr.next = node; curr = curr.next;
        if (node.next != null) heap.offer(node.next);
    }
    return dummy.next;
}

Remove Nth Node From End Of List

Brute Force — O(n) time, two passes

public ListNode removeNthFromEnd(ListNode head, int n) {
    int len = 0;
    for (ListNode tmp = head; tmp != null; tmp = tmp.next) len++;
    ListNode dummy = new ListNode(0); dummy.next = head;
    ListNode curr = dummy;
    for (int i = 0; i < len - n; i++) curr = curr.next;
    curr.next = curr.next.next;
    return dummy.next;
}

Optimal (One Pass — Two Pointers) — O(n) time, O(1) space

public 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; i++) fast = fast.next;
    while (fast != null) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;
    return dummy.next;
}

Reorder List

Brute Force — collect in array, reorder — O(n) time, O(n) space

public void reorderList(ListNode head) {
    List<ListNode> nodes = new ArrayList<>();
    for (ListNode n = head; n != null; n = n.next) nodes.add(n);
    int lo = 0, hi = nodes.size() - 1;
    while (lo < hi) {
        nodes.get(lo).next = nodes.get(hi);
        if (++lo == hi) break;
        nodes.get(hi).next = nodes.get(lo);
        hi--;
    }
    nodes.get(lo).next = null;
}

Optimal (Find Mid + Reverse + Merge) — O(n) time, O(1) space

public void reorderList(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode second = slow.next; slow.next = null;
    // Reverse second half
    ListNode prev = null, curr = second;
    while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; }
    // Merge
    ListNode first = head; second = prev;
    while (second != null) {
        ListNode tmp1 = first.next, tmp2 = second.next;
        first.next = second; second.next = tmp1;
        first = tmp1; second = tmp2;
    }
}

Matrix

Set Matrix Zeroes

Brute Force (Extra Space) — O(m×n) time, O(m+n) space (tracking set)

public void setZeroes(int[][] matrix) {
    Set<Integer> rows = new HashSet<>(), cols = new HashSet<>();
    for (int i = 0; i < matrix.length; i++)
        for (int j = 0; j < matrix[0].length; j++)
            if (matrix[i][j] == 0) { rows.add(i); cols.add(j); }
    for (int i = 0; i < matrix.length; i++)
        for (int j = 0; j < matrix[0].length; j++)
            if (rows.contains(i) || cols.contains(j)) matrix[i][j] = 0;
}

Optimal (In-place markers) — O(m×n) time, O(1) space

public void setZeroes(int[][] matrix) {
    boolean firstRow = false, firstCol = false;
    for (int j = 0; j < matrix[0].length; j++) if (matrix[0][j] == 0) firstRow = true;
    for (int i = 0; i < matrix.length; i++) if (matrix[i][0] == 0) firstCol = true;
    for (int i = 1; i < matrix.length; i++)
        for (int j = 1; j < matrix[0].length; j++)
            if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; }
    for (int i = 1; i < matrix.length; i++)
        for (int j = 1; j < matrix[0].length; j++)
            if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
    if (firstRow) Arrays.fill(matrix[0], 0);
    if (firstCol) for (int i = 0; i < matrix.length; i++) matrix[i][0] = 0;
}

Spiral Matrix

Optimal — O(m×n) time, O(1) space

public 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;
}

Rotate Image

Brute Force — O(n²) time, O(n²) extra space

public void rotate(int[][] matrix) {
    int n = matrix.length;
    int[][] copy = new int[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            copy[i][j] = matrix[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            matrix[j][n-1-i] = copy[i][j];
}

Optimal (Transpose + Reverse) — O(n²) time, O(1) space

public void rotate(int[][] matrix) {
    int n = matrix.length;
    // Transpose
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++) { int tmp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = tmp; }
    // Reverse each row
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = n-1;
        while (lo < hi) { int tmp = matrix[i][lo]; matrix[i][lo] = matrix[i][hi]; matrix[i][hi] = tmp; lo++; hi--; }
    }
}

Word Search

Optimal (Backtracking DFS) — O(m×n×4^L) time

public boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; i++)
        for (int j = 0; j < board[0].length; j++)
            if (dfs(board, word, i, j, 0)) return true;
    return false;
}
private boolean dfs(char[][] board, String word, int i, int j, int k) {
    if (k == word.length()) return true;
    if (i<0||i>=board.length||j<0||j>=board[0].length||board[i][j]!=word.charAt(k)) return false;
    char tmp = board[i][j]; board[i][j] = '#';
    boolean found = dfs(board,word,i+1,j,k+1)||dfs(board,word,i-1,j,k+1)||
                    dfs(board,word,i,j+1,k+1)||dfs(board,word,i,j-1,k+1);
    board[i][j] = tmp;
    return found;
}

String

Longest Substring Without Repeating Characters

Brute Force — O(n³) time, O(min(n,m)) space

public int lengthOfLongestSubstring(String s) {
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        Set<Character> set = new HashSet<>();
        for (int j = i; j < s.length(); j++) {
            if (!set.add(s.charAt(j))) break;
            max = Math.max(max, j - i + 1);
        }
    }
    return max;
}

Optimal (Sliding Window) — O(n) time, O(min(n,m)) space

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int max = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (map.containsKey(c)) left = Math.max(left, map.get(c) + 1);
        map.put(c, right);
        max = Math.max(max, right - left + 1);
    }
    return max;
}

Longest Repeating Character Replacement

Brute Force — O(n² × 26) time

public int characterReplacement(String s, int k) {
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        int[] count = new int[26]; int maxCount = 0;
        for (int j = i; j < s.length(); j++) {
            maxCount = Math.max(maxCount, ++count[s.charAt(j)-'A']);
            if ((j - i + 1) - maxCount <= k) max = Math.max(max, j - i + 1);
            else break;
        }
    }
    return max;
}

Optimal (Sliding Window) — O(n) time, O(1) space

public int characterReplacement(String s, int k) {
    int[] count = new int[26]; int maxCount = 0, max = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        maxCount = Math.max(maxCount, ++count[s.charAt(right)-'A']);
        if ((right - left + 1) - maxCount > k) count[s.charAt(left++)-'A']--;
        max = Math.max(max, right - left + 1);
    }
    return max;
}

Minimum Window Substring

Brute Force — O(n² × |charset|) time

public String minWindow(String s, String t) {
    String result = "";
    for (int i = 0; i < s.length(); i++)
        for (int j = i; j < s.length(); j++) {
            String sub = s.substring(i, j+1);
            if (contains(sub, t) && (result.isEmpty() || sub.length() < result.length()))
                result = sub;
        }
    return result;
}
private boolean contains(String window, String t) {
    int[] count = new int[128];
    for (char c : t.toCharArray()) count[c]++;
    for (char c : window.toCharArray()) count[c]--;
    for (int c : count) if (c > 0) return false;
    return true;
}

Optimal (Sliding Window) — O(n) time, O(|charset|) space

public String minWindow(String s, String t) {
    int[] need = new int[128]; int have = 0, required = 0;
    for (char c : t.toCharArray()) { if (need[c]++ == 0) required++; }
    int left = 0, minLen = Integer.MAX_VALUE, start = 0;
    int[] window = new int[128];
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (++window[c] == need[c]) have++;
        while (have == required) {
            if (right - left + 1 < minLen) { minLen = right - left + 1; start = left; }
            if (--window[s.charAt(left)] < need[s.charAt(left)]) have--;
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

Valid Anagram

Brute Force — O(n log n) time

public boolean isAnagram(String s, String t) {
    char[] a = s.toCharArray(), b = t.toCharArray();
    Arrays.sort(a); Arrays.sort(b);
    return Arrays.equals(a, b);
}

Optimal — O(n) time, O(1) space

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (char c : s.toCharArray()) count[c-'a']++;
    for (char c : t.toCharArray()) if (--count[c-'a'] < 0) return false;
    return true;
}

Group Anagrams

Brute Force — O(n² × k log k) time

// Compare all pairs — impractical for large inputs

Optimal — O(n × k log k) time, O(n×k) space

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] arr = s.toCharArray(); Arrays.sort(arr);
        String key = new String(arr);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

Valid Parentheses

Optimal (Stack) — O(n) time, O(n) space

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

Valid Palindrome

Brute Force — O(n) time, O(n) space

public boolean isPalindrome(String s) {
    String clean = s.toLowerCase().replaceAll("[^a-z0-9]","");
    return clean.equals(new StringBuilder(clean).reverse().toString());
}

Optimal (Two Pointers) — O(n) time, O(1) space

public boolean isPalindrome(String s) {
    int lo = 0, hi = s.length()-1;
    while (lo < hi) {
        while (lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) lo++;
        while (lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) hi--;
        if (Character.toLowerCase(s.charAt(lo)) != Character.toLowerCase(s.charAt(hi))) return false;
        lo++; hi--;
    }
    return true;
}

Longest Palindromic Substring

Brute Force — O(n³) time, O(1) space

public String longestPalindrome(String s) {
    String res = "";
    for (int i = 0; i < s.length(); i++)
        for (int j = i; j < s.length(); j++) {
            String sub = s.substring(i, j+1);
            if (isPalin(sub) && sub.length() > res.length()) res = sub;
        }
    return res;
}
private boolean isPalin(String s) {
    int lo = 0, hi = s.length()-1;
    while (lo < hi) if (s.charAt(lo++) != s.charAt(hi--)) return false;
    return true;
}

Optimal (Expand Around Center) — O(n²) time, O(1) space

public String longestPalindrome(String s) {
    int start = 0, maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int len : new int[]{expand(s,i,i), expand(s,i,i+1)}) {
            if (len > maxLen) { maxLen = len; start = i - (len-1)/2; }
        }
    }
    return s.substring(start, start + maxLen);
}
private int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

Palindromic Substrings

Brute Force — O(n³) time, O(1) space

public int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++)
        for (int j = i; j < s.length(); j++)
            if (isPalin(s, i, j)) count++;
    return count;
}
private boolean isPalin(String s, int l, int r) {
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

Optimal (Expand Around Center) — O(n²) time, O(1) space

public int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        count += expand(s, i, i);
        count += expand(s, i, i+1);
    }
    return count;
}
private int expand(String s, int l, int r) {
    int count = 0;
    while (l >= 0 && r < s.length() && s.charAt(l--) == s.charAt(r++)) count++;
    return count;
}

Encode and Decode Strings

Optimal — O(n) encode and decode

public class Codec {
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) sb.append(s.length()).append('#').append(s);
        return sb.toString();
    }
    public List<String> decode(String s) {
        List<String> result = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int j = s.indexOf('#', i);
            int len = Integer.parseInt(s.substring(i, j));
            result.add(s.substring(j+1, j+1+len));
            i = j + 1 + len;
        }
        return result;
    }
}

Tree

class TreeNode { int val; TreeNode left, right; }

Maximum Depth of Binary Tree

Brute Force / Optimal (Recursion) — O(n) time, O(h) space

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

Same Tree

Optimal (Recursion) — O(n) time, O(h) space

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

Invert Binary Tree

Optimal (Recursion) — O(n) time, O(h) space

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

Binary Tree Maximum Path Sum

Optimal (PostOrder DFS) — O(n) time, O(h) space

int maxSum;
public int maxPathSum(TreeNode root) {
    maxSum = Integer.MIN_VALUE;
    dfs(root); return maxSum;
}
private int dfs(TreeNode node) {
    if (node == null) return 0;
    int left = Math.max(0, dfs(node.left));
    int right = Math.max(0, dfs(node.right));
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
}

Binary Tree Level Order Traversal

Optimal (BFS) — O(n) time, O(n) space

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int 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;
}

Serialize and Deserialize Binary Tree

Optimal (BFS) — O(n) time, O(n) space

public String serialize(TreeNode root) {
    if (root == null) return "";
    StringBuilder sb = new StringBuilder();
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        if (node == null) { sb.append("null,"); continue; }
        sb.append(node.val).append(',');
        q.offer(node.left); q.offer(node.right);
    }
    return sb.toString();
}
public TreeNode deserialize(String data) {
    if (data.isEmpty()) return null;
    String[] vals = data.split(",");
    TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int i = 1;
    while (!q.isEmpty() && i < vals.length) {
        TreeNode node = q.poll();
        if (!vals[i].equals("null")) { node.left = new TreeNode(Integer.parseInt(vals[i])); q.offer(node.left); }
        i++;
        if (i < vals.length && !vals[i].equals("null")) { node.right = new TreeNode(Integer.parseInt(vals[i])); q.offer(node.right); }
        i++;
    }
    return root;
}

Subtree of Another Tree

Brute Force / Optimal — O(m×n) time, O(h) space

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (root == null) return false;
    if (isSame(root, subRoot)) return true;
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean isSame(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null || a.val != b.val) return false;
    return isSame(a.left, b.left) && isSame(a.right, b.right);
}

Construct Binary Tree from Preorder and Inorder

Optimal (HashMap index lookup) — O(n) time, O(n) space

public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> idx = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);
    return build(preorder, 0, 0, inorder.length-1, idx);
}
int[] preorder; // store as field or pass as param
private TreeNode build(int[] pre, int preIdx, int inLeft, int inRight, Map<Integer,Integer> idx) {
    if (inLeft > inRight) return null;
    TreeNode root = new TreeNode(pre[preIdx]);
    int mid = idx.get(pre[preIdx]);
    root.left  = build(pre, preIdx + 1, inLeft, mid - 1, idx);
    root.right = build(pre, preIdx + (mid - inLeft) + 1, mid + 1, inRight, idx);
    return root;
}

Validate Binary Search Tree

Brute Force — O(n²) time — check BST property for each node independently

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

Kth Smallest Element in a BST

Brute Force — collect inorder, return kth — O(n) time, O(n) space

public int kthSmallest(TreeNode root, int k) {
    List<Integer> inorder = new ArrayList<>();
    inorderTraversal(root, inorder);
    return inorder.get(k - 1);
}
private void inorderTraversal(TreeNode node, List<Integer> list) {
    if (node == null) return;
    inorderTraversal(node.left, list);
    list.add(node.val);
    inorderTraversal(node.right, list);
}

Optimal (Iterative Inorder — early stop) — O(h + k) time, O(h) space

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) { stack.push(curr); curr = curr.left; }
        curr = stack.pop();
        if (--k == 0) return curr.val;
        curr = curr.right;
    }
    return -1;
}

Lowest Common Ancestor of BST

Brute Force — O(n) time, find paths from root, compare

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
    if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
    return root;
}

Implement Trie

Optimal — O(m) insert/search/startsWith where m = word length

class Trie {
    private TrieNode root = new TrieNode();

    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c-'a'] == null) node.children[c-'a'] = new TrieNode();
            node = node.children[c-'a'];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c-'a'] == null) return false;
            node = node.children[c-'a'];
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.children[c-'a'] == null) return false;
            node = node.children[c-'a'];
        }
        return true;
    }
}

Add and Search Word

Optimal (Trie + DFS for wildcards) — O(m) average, O(26^m) worst

class WordDictionary {
    private TrieNode root = new TrieNode();
    class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd; }

    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.children[c-'a'] == null) node.children[c-'a'] = new TrieNode();
            node = node.children[c-'a'];
        }
        node.isEnd = true;
    }

    public boolean search(String word) { return dfs(word, 0, root); }

    private boolean dfs(String word, int i, TrieNode node) {
        if (i == word.length()) return node.isEnd;
        char c = word.charAt(i);
        if (c == '.') {
            for (TrieNode child : node.children)
                if (child != null && dfs(word, i+1, child)) return true;
            return false;
        }
        if (node.children[c-'a'] == null) return false;
        return dfs(word, i+1, node.children[c-'a']);
    }
}

Word Search II

Optimal (Trie + Backtracking) — O(m × n × 4^L) time

public List<String> findWords(char[][] board, String[] words) {
    TrieNode root = buildTrie(words);
    List<String> result = new ArrayList<>();
    for (int i = 0; i < board.length; i++)
        for (int j = 0; j < board[0].length; j++)
            dfs(board, i, j, root, result);
    return result;
}
private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
    if (i<0||i>=board.length||j<0||j>=board[0].length||board[i][j]=='#') return;
    char c = board[i][j];
    TrieNode next = node.children[c-'a'];
    if (next == null) return;
    if (next.word != null) { result.add(next.word); next.word = null; }
    board[i][j] = '#';
    dfs(board,i+1,j,next,result); dfs(board,i-1,j,next,result);
    dfs(board,i,j+1,next,result); dfs(board,i,j-1,next,result);
    board[i][j] = c;
}
private TrieNode buildTrie(String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {
        TrieNode node = root;
        for (char c : w.toCharArray()) {
            if (node.children[c-'a'] == null) node.children[c-'a'] = new TrieNode();
            node = node.children[c-'a'];
        }
        node.word = w;
    }
    return root;
}
class TrieNode { TrieNode[] children = new TrieNode[26]; String word; }

Heap

Top K Frequent Elements

Brute Force — O(n log n) time — sort by frequency

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer,Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);
    return freq.entrySet().stream()
        .sorted((a,b) -> b.getValue()-a.getValue())
        .limit(k).mapToInt(Map.Entry::getKey).toArray();
}

Optimal (Min-Heap) — O(n log k) time, O(n) space

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer,Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);
    PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> freq.get(a)-freq.get(b));
    for (int key : freq.keySet()) {
        heap.offer(key);
        if (heap.size() > k) heap.poll();
    }
    int[] result = new int[k];
    for (int i = k-1; i >= 0; i--) result[i] = heap.poll();
    return result;
}

Most Optimal (Bucket Sort) — O(n) time, O(n) space

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer,Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);
    List<Integer>[] buckets = new List[nums.length + 1];
    for (int key : freq.keySet()) {
        int f = freq.get(key);
        if (buckets[f] == null) buckets[f] = new ArrayList<>();
        buckets[f].add(key);
    }
    int[] result = new int[k]; int idx = 0;
    for (int i = buckets.length-1; i >= 0 && idx < k; i--)
        if (buckets[i] != null) for (int n : buckets[i]) { result[idx++] = n; if (idx==k) break; }
    return result;
}

Find Median from Data Stream

Brute Force — O(n) insert, O(n log n) or O(n) find median

class MedianFinder {
    List<Integer> data = new ArrayList<>();
    public void addNum(int num) { data.add(num); }
    public double findMedian() {
        Collections.sort(data);
        int n = data.size();
        return n%2==0 ? (data.get(n/2-1)+data.get(n/2))/2.0 : data.get(n/2);
    }
}

Optimal (Two Heaps) — O(log n) insert, O(1) findMedian

class MedianFinder {
    PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
    PriorityQueue<Integer> hi = new PriorityQueue<>(); // min-heap

    public void addNum(int num) {
        lo.offer(num);
        hi.offer(lo.poll());
        if (lo.size() < hi.size()) lo.offer(hi.poll());
    }

    public double findMedian() {
        return lo.size() > hi.size() ? lo.peek() : (lo.peek() + hi.peek()) / 2.0;
    }
}

Legend: All time complexities use standard Big-O notation. N = total elements, n/m = string/array length, h = tree height, k = number of lists/elements, L = word length.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment