aug - 4

 import java.util.*;

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] job = new int[n][3];
        for(int i = 0; i < n; i++){
            job[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }

        Arrays.sort(job, Comparator.comparingInt(a -> a[1]));

        int[] dp = new int[n];
        dp[0] = job[0][2];

        for(int i = 1; i < n; i++){
            int includeProfit = job[i][2];
            int l = binarySearch(job, i);

            if(l != -1){
                includeProfit += dp[l];  // ✅ FIXED
            }

            dp[i] = Math.max(dp[i - 1], includeProfit);
        }

        return dp[n - 1];
    }

    private int binarySearch(int[][] job, int index){
        int l = 0, h = index - 1;
        int res = -1;

        while(l <= h){
            int mid = l + (h - l) / 2;
            if(job[mid][1] <= job[index][0]){
                res = mid;
                l = mid + 1;
            } else {
                h = mid - 1;
            }
        }

        return res;
    }
}

import java.util.*;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), new boolean[nums.length], result);
        return result;
    }

    private void backtrack(int[] nums, List<Integer> temp, boolean[] used, List<List<Integer>> result) {
        if (temp.size() == nums.length) {
            result.add(new ArrayList<>(temp)); // Add a copy of temp
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;

            used[i] = true;
            temp.add(nums[i]);
            backtrack(nums, temp, used, result);
            temp.remove(temp.size() - 1);
            used[i] = false;
        }
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Loop until you find the split point
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                root = root.left; // LCA is in the left subtree
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right; // LCA is in the right subtree
            } else {
                return root; // This is the split point and hence the LCA
            }
        }
        return null;
    }
}

import java.util.HashSet;

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> set = new HashSet<>();
        return dfs(root, k, set);
    }

    private boolean dfs(TreeNode node, int k, HashSet<Integer> set) {
        if (node == null) return false;

        if (set.contains(k - node.val)) {
            return true;
        }

        set.add(node.val);

        return dfs(node.left, k, set) || dfs(node.right, k, set);
    }
}

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int numIslands = 0;

        // Go through each cell in the grid
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                // Found land -> start DFS
                if (grid[r][c] == '1') {
                    numIslands++;
                    dfs(grid, r, c); // mark this island's land as visited
                }
            }
        }
        return numIslands;
    }

    private void dfs(char[][] grid, int r, int c) {
        // Stop if out of bounds or water
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0'; // mark visited

        // Explore in all 4 directions
        dfs(grid, r + 1, c); // down
        dfs(grid, r - 1, c); // up
        dfs(grid, r, c + 1); // right
        dfs(grid, r, c - 1); // left
    }
}

import java.util.*;

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int allVisited = (1 << n) - 1; // All nodes visited mask (e.g., 1111 for n=4)

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][1 << n;

        // Initialize: Start from every node
        for (int i = 0; i < n; i++) {
            queue.offer(new int[]{i, 1 << i, 0}); // {node, visitedMask, distance}
            visited[i][1 << i] = true;
        }

        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int node = state[0];
            int mask = state[1];
            int dist = state[2];

            if (mask == allVisited) return dist;

            for (int neighbor : graph[node]) {
                int nextMask = mask | (1 << neighbor);
                if (!visited[neighbor][nextMask]) {
                    visited[neighbor][nextMask] = true;
                    queue.offer(new int[]{neighbor, nextMask, dist + 1});
                }
            }
        }

        return -1; // Should never reach here since the graph is connected
    }
}

class Solution {
    public int paintWalls(int[] cost, int[] time) {
        int n = cost.length;
        int[][] dp = new int[n + 1][n + 1];

        // Initialize with -1 to indicate uncomputed states
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -1;
            }
        }

        return helper(0, n, cost, time, dp);
    }

    private int helper(int i, int wallLeft, int[] cost, int[] time, int[][] dp) {
        if (wallLeft <= 0) return 0;
        if (i == cost.length) return (int) 1e9;

        if (dp[i][wallLeft] != -1) return dp[i][wallLeft];

        // Choice 1: Hire this painter
        int hire = cost[i] + helper(i + 1, wallLeft - 1 - time[i], cost, time, dp);

        // Choice 2: Skip this painter
        int skip = helper(i + 1, wallLeft, cost, time, dp);

        return dp[i][wallLeft] = Math.min(hire, skip);
    }
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // Fill with a large number (infinity substitute)
        dp[0] = 0; // Base case: 0 coins needed to make amount 0

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}