Grind 75

Grind 75 questions

1. 1. Two Sum

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.com/problems/two-sum/">Two Sum</a>
 */
class TwoSum {
    private final Map<Integer, Integer> cache = new HashMap<>();

    public int[] twoSum(final int[] nums, final int target) {
        for (int i = 0; i < nums.length; i++) {
            final int residual = target - nums[i];
            if (cache.containsKey(residual)) {
                return new int[]{cache.get(residual), i};
            }
            cache.put(nums[i], i);
        }
        return new int[]{};
    }

    @Test
    void givenInput1_whenCheckTheTwoSum_thenItShouldReturn0And1() {
        final int[] nums = new int[]{2, 7, 11, 15};
        final int target = 9;
        Assertions.assertArrayEquals(new int[]{0, 1}, twoSum(nums, target));
    }

    @Test
    void givenInput2_whenCheckTheTwoSum_thenItShouldReturn1And2() {
        final int[] nums = new int[]{3, 2, 4};
        final int target = 6;
        Assertions.assertArrayEquals(new int[]{1, 2}, twoSum(nums, target));
    }

    @Test
    void givenInput3_whenCheckTheTwoSum_thenItShouldReturn0And1() {
        final int[] nums = new int[]{3, 3};
        final int target = 6;
        Assertions.assertArrayEquals(new int[]{0, 1}, twoSum(nums, target));
    }
}

2. 121. Best Time to Buy and Sell Stock

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;


class MaxProfit {
    public int maxProfit(final int[] prices) {
        int maxProfit = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            }
            if (prices[i] - min > maxProfit) {
                maxProfit = prices[i] - min;
            }
        }
        return maxProfit;
    }

    @Test
    void givenInput1_whenCalculateTheMaxProfit_thenItShouldReturn5() {
        final int[] prices = new int[]{7, 1, 5, 3, 6, 4};
        assertEquals(5, maxProfit(prices));
    }

    @Test
    void givenInput2_whenCalculateTheMaxProfit_thenItShouldReturn0() {
        final int[] prices = new int[]{7, 6, 4, 3, 1};
        assertEquals(0, maxProfit(prices));
    }

}

3. 20. Valid Parentheses

import org.junit.jupiter.api.Test;

import java.util.Stack;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;

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

    @Test
    void givenInput1_whenCheckIfValid_thenReturnTrue() {
        final String input = "()";
        assertTrue(isValid(input));
    }

    @Test
    void givenInput2_whenCheckIfValid_thenReturnTrue() {
        final String input = "()[]{}";
        assertTrue(isValid(input));
    }

    @Test
    void givenInput3_whenCheckIfValid_thenReturnFalse() {
        final String input = "(]";
        assertFalse(isValid(input));
    }

    @Test
    void givenInput4_whenCheckIfValid_thenReturnFalse() {
        final String input = "]";
        assertFalse(isValid(input));
    }

}

4. 55. Jump Game

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * <a href="https://leetcode.com/problems/jump-game/">55. Jump Game</a>
 * <a href="https://mp.weixin.qq.com/s?__biz=Mzg4OTYzODM4Mw==&mid=2247485685&idx=1&sn=71d39243bccdb9023f7ce55f4948a66c&chksm=cfe99475f89e1d63e598bc3c15e44b23b2f24dffbced86fbfa404fba9ea340fc389bac179af4#rd">来见识一下贪心算法：Jump Game</a>
 */
class JumpGame {
    public boolean canJump(final int[] nums) {
        final int size = nums.length;
        if (size == 0 || size == 1)
            return true;
        int step = nums[0];
        for (final int num : nums) {
            step = Math.max(step - 1, num);
            if (step <= 0)
                return false;
        }
        return true;
    }

    @Test
    void giveInput1_whenCheckTheResult_thenItShouldBeTrue() {
        final int[] nums = new int[]{2, 3, 1, 1, 4};
        final boolean output = true;
        Assertions.assertEquals(output, canJump(nums));
    }

    @Test
    void giveInput2_whenCheckTheResult_thenItShouldBeFalse() {
        final int[] nums = new int[]{3, 2, 1, 0, 4};
        final boolean output = false;
        Assertions.assertEquals(output, canJump(nums));
    }
}

5. 70. Climbing Stairs

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * <a href="https://leetcode.com/problems/climbing-stairs/">70. Climbing Stairs</a>
 */
class ClimbStairs {

    /**
     * f(n) = f(n-1) + f(n-2)
     * f(1) = 1
     * f(0) = 1
     *
     * @param n
     * @return
     */
    public int climbStairs(final int n) {
        if (n == 1 || n == 0) {
            return 1;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    public int climbStairs2(final int n) {
        return climbStairsBetter(n)[0];
    }

    /**
     * remove the tail recursive
     *
     * @param n
     * @return
     */
    public int[] climbStairsBetter(final int n) {
        if (n <= 1) {
            return new int[]{n, 1};
        }
        final int[] temp = climbStairsBetter(n - 1);
        return new int[]{temp[0] + temp[1], temp[0]};
    }

    public int climbStairsDp(final int n) {
        final int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    @Test
    void given2Stairs_whenCheckMethods_thenItShouldBe2() {
        final int n = 2;
        final int output = 2;
        Assertions.assertEquals(output, climbStairs(n));
        Assertions.assertEquals(output, climbStairs2(n));
        Assertions.assertEquals(output, climbStairsDp(n));
    }

    @Test
    void given3Stairs_whenCheckMethods_thenItShouldBe3() {
        final int n = 3;
        final int output = 3;
        Assertions.assertEquals(output, climbStairs(n));
        Assertions.assertEquals(output, climbStairs2(n));
        Assertions.assertEquals(output, climbStairsDp(n));
    }

    @Test
    void given10Stairs_whenCheckMethodsUsingDifferentAlgo_thenTheResultShouldMatch() {
        final int n = 10;
        Assertions.assertEquals(climbStairs(n), climbStairsDp(n));
    }
}

6. 1235. Maximum Profit in Job Scheduling

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.TreeMap;

import static java.lang.Math.max;

class JobScheduling {
    // https://leetcode.com/problems/maximum-profit-in-job-scheduling/solutions/409009/java-c-python-dp-solution/
    public int jobScheduling(final int[] startTime, final int[] endTime, final int[] profit) {
        final int n = profit.length;
        final int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) {
            jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(jobs, Comparator.comparingInt(e -> e[1]));
        // key is the end time, value is the maximum profit for the end time
        final TreeMap<Integer, Integer> dp = new TreeMap<>();
        dp.put(0, 0);
        for (final int[] job : jobs) {
            final int cur = dp.floorEntry(job[0]).getValue() + job[2];
            if (cur > dp.lastEntry().getValue()) {
                dp.put(job[1], cur);
            }
        }
        return dp.lastEntry().getValue();
    }

    // https://www.youtube.com/watch?v=0C7re8lam7M
    public int jobScheduling2(final int[] startTime, final int[] endTime, final int[] profit) {
        final int n = profit.length;
        final int[][] jobs = new int[n][3];
        for (int i = 0; i < n; i++) {
            jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
        }
        Arrays.sort(jobs, Comparator.comparingInt(e -> e[1]));

        final List<int[]> dp = new ArrayList<>(); // {endTime, profit}
        int ret = 0;
        dp.add(new int[]{0, 0});
        for (final int[] job : jobs) {
            int cur = ret;
            //  mimic the upper_bound in cpp
            int ip = upperBound(dp, new int[]{job[0], Integer.MAX_VALUE});
            ip--;
            cur = max(cur, dp.get(ip)[1] + job[2]);
            dp.add(new int[]{job[1], cur});
            ret = max(ret, cur);
        }
        return ret;
    }

    // note it will exceed the time limit in leetcode
    private int upperBound(final List<int[]> dp, final int[] target) {
        for (int i = 0; i < dp.size(); i++) {
            if (dp.get(i)[0] > target[0]) {
                return i;
            }
        }
        return dp.size();
    }

    @Test
    void givenInputs1_whenRunTheJobScheduling_thenTheMaximumProfitShouldBe120() {
        final int[] startTime = new int[]{1, 2, 3, 3};
        final int[] endTime = new int[]{3, 4, 5, 6};
        final int[] profit = new int[]{50, 10, 40, 70};
        Assertions.assertEquals(120, jobScheduling(startTime, endTime, profit));
        Assertions.assertEquals(120, jobScheduling2(startTime, endTime, profit));
    }

    @Test
    void givenInputs2_whenRunTheJobScheduling_thenTheMaximumProfitShouldBe150() {
        final int[] startTime = new int[]{1, 2, 3, 4, 6};
        final int[] endTime = new int[]{3, 5, 10, 6, 9};
        final int[] profit = new int[]{20, 20, 100, 70, 60};
        Assertions.assertEquals(150, jobScheduling(startTime, endTime, profit));
        Assertions.assertEquals(150, jobScheduling2(startTime, endTime, profit));
    }

    @Test
    void givenInputs3_whenRunTheJobScheduling_thenTheMaximumProfitShouldBe6() {
        final int[] startTime = new int[]{1, 1, 1};
        final int[] endTime = new int[]{2, 3, 4};
        final int[] profit = new int[]{5, 6, 4};
        Assertions.assertEquals(6, jobScheduling(startTime, endTime, profit));
        Assertions.assertEquals(6, jobScheduling2(startTime, endTime, profit));
    }

    @Test
    void givenInputs4_whenRunTheJobScheduling_thenTheMaximumProfitShouldBe6() {
        final int[] startTime = new int[]{4, 3, 1, 2, 4, 8, 3, 3, 3, 9};
        final int[] endTime = new int[]{5, 6, 3, 5, 9, 9, 8, 5, 7, 10};
        final int[] profit = new int[]{9, 9, 5, 12, 10, 11, 10, 4, 14, 7};
        Assertions.assertEquals(37, jobScheduling(startTime, endTime, profit));
        Assertions.assertEquals(37, jobScheduling2(startTime, endTime, profit));
    }

    @Test
    void givenInputs5_whenRunTheJobScheduling_thenTheMaximumProfitShouldBe6() {
        final int[] startTime = new int[]{3, 5, 3, 7, 4};
        final int[] endTime = new int[]{10, 8, 8, 10, 9};
        final int[] profit = new int[]{10, 8, 10, 9, 9};
        Assertions.assertEquals(10, jobScheduling(startTime, endTime, profit));
        Assertions.assertEquals(10, jobScheduling2(startTime, endTime, profit));
    }
}

7. Maximum Gold

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

class MaximumGold {
    public int getMaximumGold(final int w, final int n, final int[] p, final int[] g) {
        final int[][] result = new int[n + 1][w + 1];
        for (int i = 1; i <= n; i++) { // num of mines
            for (int j = 1; j <= w; j++) { // num of workers
                if (j < p[i - 1]) {
                    result[i][j] = result[i-1][j];
                } else {
                    result[i][j] = Math.max(result[i - 1][j], result[i - 1][j - p[i - 1]] + g[i - 1]);
                }
            }
        }

        return result[n][w];
    }

    public int getMaximumGoldV2(final int w, final int n, final int[] p, final int[] g) {
        final int[] result = new int[w + 1];
        for (int i = 1; i <= n; i++) { // num of mines
            for (int j = w; j >= 1; j--) { // num of workers, note here we should calculate from right to left
                if (j >= p[i - 1]) {
                    result[j] = Math.max(result[j], result[j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        return result[w];
    }


    @Test
    void testMaximumGoldOne() {
        final int w = 10;
        final int n = 5;
        final int[] p = new int[]{5, 5, 3, 4, 3};
        final int[] g = new int[]{400, 500, 200, 300, 350};
        final int output = 900;
        Assertions.assertEquals(output, getMaximumGold(w, n, p, g));
    }

    @Test
    void testMaximumGoldTwo() {
        final int w = 10;
        final int n = 5;
        final int[] p = new int[]{5, 5, 3, 4, 3};
        final int[] g = new int[]{400, 500, 200, 300, 350};
        final int output = 900;
        Assertions.assertEquals(output, getMaximumGoldV2(w, n, p, g));
    }
}

8. 207. Course Schedule

LeetCode 207 & 210: Course Schedule I & II | Topological Sort | Kahn's algorithm

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;


class CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        final int[] courseDeps = new int[numCourses];
        for (final int[] pre : prerequisites) {
            courseDeps[pre[0]]++;
        }
        final Set<Integer> zeroDeps = new HashSet<>();
        for (int i = 0; i < numCourses; i++) {
            if (courseDeps[i] == 0) {
                zeroDeps.add(i);
            }
        }
        if (zeroDeps.isEmpty()) {
            return false;
        }
        while(!zeroDeps.isEmpty()) {
            final Iterator<Integer> it = zeroDeps.iterator();
            final int course = it.next();
            zeroDeps.remove(course);
            for (final int[] pre : prerequisites) {
                if (pre[1] == course) {
                    courseDeps[pre[0]]--;
                    if (courseDeps[pre[0]] == 0) {
                        zeroDeps.add(pre[0]);
                    }
                }
            }
        }
        for (final int i : courseDeps) {
            if (i > 0) {
                return false;
            }
        }
        return true;
    }

    @Test
    void givenInput1_whenCallCanFinish_thenItShouldReturnTrue() {
        final int numCourses = 2;
        final int[][] prerequisites = new int[][]{{1, 0}};
        assertTrue(canFinish(numCourses, prerequisites));
    }

    @Test
    void givenInput2_whenCallCanFinish_thenItShouldReturnFalse() {
        final int numCourses = 2;
        final int[][] prerequisites = new int[][]{{1, 0}, {0, 1}};
        assertFalse(canFinish(numCourses, prerequisites));
    }
}

9. 704. Binary Search

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

10. 57. Insert Interval

Insert Interval - Leetcode 57 - Python

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> results = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int[] tmp = intervals[i];
            if (intervals[i][1] < newInterval[0]) {
                results.add(tmp);
            } else if (intervals[i][0] > newInterval[1]) {
                results.add(newInterval);
                newInterval = tmp;
            } else {
                newInterval[0] = Math.min(tmp[0], newInterval[0]);
                newInterval[1] = Math.max(tmp[1], newInterval[1]);
            }
        }
        results.add(newInterval);
        return results.toArray(new int[results.size()][]);
    }
}

11. 56. Merge Intervals

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return 0;
            }
            return a[0] > b[0] ? 1 : -1;
        });
        int[] tmp = intervals[0];
        List<int[]> result = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];
            if (cur[0] > tmp[1]) {
                result.add(tmp);
                tmp = cur;
            } else if (cur[1] < tmp[0]) {
                result.add(cur);
            } else {
                tmp = new int[] {Math.min(tmp[0], cur[0]), Math.max(tmp[1], cur[1])};
            }
        }
        result.add(tmp);
        return result.toArray(new int[result.size()][]);
    }
}

12. 238. Product of Array Except Self

class Solution {
    public int[] productExceptSelf(int[] nums) {
        return solution2(nums);
    }

    // Time Complexity: O(N)
    // Space Complexity: O(N)
    public int[] solution1(int[] nums) {
        int length = nums.length;
        int[] before = new int[length];
        before[0] = 1;
        for (int i = 1; i < length; i++) {
            before[i] = before[i-1] * nums[i-1];
        }
        int[] after = new int[length];
        after[length - 1] = 1;
        for (int i = length-2; i >= 0; i--) {
            after[i] = after[i+1] * nums[i+1];
        }
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            result[i] = before[i] * after[i];
        }
        return result;
    }

    // Time Complexity: O(N)
    // Space Complexity: O(1)
    public int[] solution2(int[] nums) {
        int length = nums.length;
        int[] result = new int[length];
        result[0] = 1;
        for (int i = 1; i < length; i++) {
            result[i] = result[i-1] * nums[i-1];
        }
        int after = 1;
        for (int i = length - 1; i>=0; i--) {
            result[i] = result[i] * after;
            after = nums[i] * after;
        }
        return result;
    }
}

13. 15. 3Sum

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> result = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return new ArrayList<>(result);
            }
            int head = i+1;
            int tail = nums.length - 1;
            while (head < tail) {
                int sum = nums[i] + nums[head] + nums[tail];
                if (sum == 0) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[head]);
                    tmp.add(nums[tail]);
                    result.add(tmp);
                    head++;
                } else if (sum > 0) {
                    tail--;
                } else {
                    head++;
                }
            }
        }
        return new ArrayList<>(result);
    }
}

14. 75. Sort Colors

class Solution {
    // Dutch National Flag algorithm
    public void sortColors(int[] nums) {
        int head = 0;
        int mid = 0;
        int tail = nums.length - 1;
        while (mid <= tail) {
            if (nums[mid] == 0 && nums[head] != 0) {
                int tmp = nums[head];
                nums[head++] = nums[mid];
                nums[mid++] = tmp;
            } else if (nums[mid] == 0 && nums[head] == 0) {
                mid++;
                head++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                int tmp = nums[tail];
                nums[tail] = nums[mid];
                nums[mid] = tmp;
                tail--;
            }
        }
    }
}

15. 236. Lowest Common Ancestor of a Binary Tree

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }

        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);

        if (l != null && r != null) {
            return root;
        } else if (l != null) {
            return l;
        } else {
            return r;
        }
    }
}

16. 542. 01 Matrix

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        return bfs(mat);
    }

    private int[][] bfs(int[][] mat) {
        int r = mat.length, c = mat[0].length;
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (mat[i][j] == 0)
                    q.offer(new int[] {i, j});
                else
                    mat[i][j] = -1;
            }
        }
        int[] directions = new int[] {-1, 0, 1, 0, -1};
        while(q.size() > 0) {
            int[] curr = q.poll();
            int m = curr[0], n = curr[1];
            for (int k = 0; k < 4; k++) {
                int nm = m + directions[k], nn = n + directions[k+1];
                if (nm < 0 || nm == r || nn < 0 || nn == c || mat[nm][nn] != -1)
                    continue;
                mat[nm][nn] = mat[m][n] + 1;
                q.offer(new int[] {nm, nn});
            }
        }
        return mat;
    }

    private int[][] dp(int[][] mat) {
        int r = mat.length, c = mat[0].length, INF = r + c;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (mat[i][j] == 0) continue;
                int top = INF, left = INF;
                if (i - 1 >= 0) top = mat[i - 1][j];
                if (j - 1 >= 0) left = mat[i][j - 1];
                mat[i][j] = Math.min(top, left) + 1;
            }
        }
        for (int i = r - 1; i >= 0; i--) {
            for (int j = c - 1; j >= 0; j--) {
                if (mat[i][j] == 0) continue;
                int bottom = INF, right = INF;
                if (i + 1 < r) bottom = mat[i + 1][j];
                if (j + 1 < c) right = mat[i][j + 1];
                mat[i][j] = Math.min(mat[i][j], Math.min(bottom, right) + 1);
            }
        }
        return mat;
    }
}

17. 199. Binary Tree Right Side View

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Map<Integer, Boolean> marked = new HashMap<>();
        rightSideRecursive(result, root, marked, 0);
        return result;
    }

    public void rightSideRecursive(List<Integer> result, TreeNode cur, Map<Integer, Boolean> marked, int level) {
        if (cur == null) {
            return;
        }
        if (!marked.getOrDefault(level, false)) {
            marked.put(level, true);
            result.add(cur.val);
        }
        rightSideRecursive(result, cur.right, marked, level+1);
        rightSideRecursive(result, cur.left, marked, level+1);
    }
}

18. 133. Clone Graph

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) 
            return null;
        if (node.neighbors.size() == 0) 
            return new Node(node.val);
        return dfs(node, new HashMap<>());
    }

    private Node dfs(Node cur, Map<Node, Node> map) {
        Node clone = new Node(cur.val);
        map.put(cur, clone);
        for (Node n : cur.neighbors) {
            if (map.get(n) != null) {
                clone.neighbors.add(map.get(n));
            } else {
                clone.neighbors.add(dfs(n, map));
            }
        }
        return clone;
    }
}

19. 230. Kth Smallest Element in a BST

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int K;
    public int kthSmallest(TreeNode root, int k) {
        K = k;
        return inorder(root);
    }

    private Integer inorder(TreeNode cur) {
        if (cur == null)
            return null;
        Integer left = inorder(cur.left);
        if (left == null) {
            if (--K == 0)
                return cur.val;
            else
                return inorder(cur.right);
        }
        return left;
    }
}

20. 3. Longest Substring Without Repeating Characters

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0, left = 0, right = 0;
        HashSet<Character> cache = new HashSet<>();
        for (;right < s.length(); right++) {
            char c = s.charAt(right);
            if (cache.contains(c)) {
                do {
                    char l = s.charAt(left);
                    cache.remove(l);
                    left++;
                } while (cache.contains(c));
                cache.add(c);
            } else {
                cache.add(c);
                maxLength = Math.max(maxLength, cache.size());
            }
        }
        return maxLength;
    }
}

21. 150. Evaluate Reverse Polish Notation

class Solution {
    public int evalRPN(String[] tokens) {
        List<String> operands = List.of("+", "-", "*", "/");
        Stack<String> stack = new Stack<>();
        for (String t : tokens) {
            if (operands.contains(t)) {
                String b = stack.pop();
                String a = stack.pop();
                if (t.equals("+")) {
                    stack.push(String.valueOf(Integer.valueOf(a) + Integer.valueOf(b)));
                } else if (t.equals("-")) {
                    stack.push(String.valueOf(Integer.valueOf(a) - Integer.valueOf(b)));
                } else if (t.equals("*")) {
                    stack.push(String.valueOf(Integer.valueOf(a) * Integer.valueOf(b)));
                } else {
                    stack.push(String.valueOf(Integer.valueOf(a) / Integer.valueOf(b)));
                }
            } else {
                stack.push(t);
            }
        }
        return Integer.valueOf(stack.pop());
    }
}

22. 226. Invert Binary Tree

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

23. 84. Largest Rectangle in Histogram

class Solution {
    public int largestRectangleArea(int[] heights) {
        return stackSolution(heights);
    }

    // https://leetcode.com/problems/largest-rectangle-in-histogram/solutions/28902/5ms-o-n-java-solution-explained-beats-96/
    private int regularSolution(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int[] lessFromLeft = new int[heights.length];
        int[] lessFromRight = new int[heights.length];
        lessFromLeft[0] = -1;
        lessFromRight[heights.length - 1] = heights.length;

        for (int i = 1; i < heights.length; i++) {
            int p = i - 1;
            while (p >= 0 && heights[p] >= heights[i]) {
                p = lessFromLeft[p];
            }
            lessFromLeft[i] = p;
        }

        for (int i = heights.length - 2; i >= 0; i--) {
            int p = i + 1;
            while (p < heights.length && heights[p] >= heights[i]) {
                p = lessFromRight[p];
            }
            lessFromRight[i] = p;
        }

        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            maxArea = Math.max(maxArea, heights[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
        }

        return maxArea;
    }

    // https://leetcode.com/problems/largest-rectangle-in-histogram/solutions/995249/python-increasing-stack-explained/
    private int stackSolution(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        for(int i = 0; i <= heights.length; i++) {
            int height = i == heights.length ? 0 : heights[i];
            while(!stack.empty() && heights[stack.peek()] > height) {
                int h = heights[stack.pop()];
                int w = stack.empty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, h * w);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

24. 21. Merge Two Sorted Lists

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

25. 322. Coin Change

class Solution {
    public int coinChange(int[] coins, int amount) {
        // Unknown: -1; Yes: 1; No: 0
        int[] dp = new int[amount+1];
        Arrays.fill(dp, -1);
        int result = helper(coins, amount, dp);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int helper(int[] coins, int amount, int[] dp) {
        if (amount == 0) {
            return 0;
        }

        if (amount < 0) {
            return Integer.MAX_VALUE;
        }

        if (dp[amount] != -1) {
            return dp[amount];
        }

        int steps = Integer.MAX_VALUE;
        for (int coin : coins) {
            int ans = helper(coins, amount - coin, dp);

            if (ans != Integer.MAX_VALUE) {
                steps = Math.min(ans + 1, steps);
            }
        }

        dp[amount] = steps;
        return dp[amount];
    }
}

26. 994. Rotting Oranges

Note that in Graph BFS, compared with Tree BFS, we need to mark the visited node as visited to prevent infinite loop.

// https://leetcode.com/problems/rotting-oranges/
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n  = grid[0].size();

        vector<vector<int>> visited = grid;
        queue<pair<int, int>> q;

        int countFreshOrange = 0;
        for (int i = 0; i < m; i++) {
            for (int j =0; j < n; j++) {
                if (visited[i][j] == 2) {
                    q.push({i, j});
                }
                if (visited[i][j] == 1) {
                    countFreshOrange++;
                }
            }
        }
        //q.empty() means there is no rotten orange in the grid and countFreshOrange = 0 means we will rotten the freshoranges in 0 mins
        if (countFreshOrange == 0)
            return 0;
        if (q.empty())
            return -1;

        int minutes = -1;
        int directions[] = {-1, 0, 1, 0, -1};
        while(!q.empty()) {
            int size = q.size();
            while (size--) { // so that we can count the steps
                auto [i, j] = q.front();
                q.pop();
                for (int k = 0; k < 4; k++) {
                    int ni = i + directions[k];
                    int nj = j + directions[k+1];
                    if (ni >=0 && ni < m && nj >= 0 && nj < n && visited[ni][nj] == 1) {
                        visited[ni][nj] = 2;
                        countFreshOrange--;
                        q.push({ni, nj});
                    }
                }
            }
            minutes++;
        }

        if (countFreshOrange == 0)
            return minutes;
        return -1;
    }
};

27. 733. Flood Fill

// https://leetcode.com/problems/flood-fill/solutions/4745988/easy-dfs-solution-c/
class Solution {
public:
    Solution() : directions{-1, 0, 1, 0, -1} {}

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        vector<vector<int>> ans = image; // equivalent to the visited marker
        dfs(sr, sc, color, image[sr][sc], ans, image);
        //dfs(sr, sc, color, image[sr][sc], ans, image, this->directions);
        return ans;
    }

    void dfs(int row, int col, int color, int initColor, vector<vector<int>>& ans, vector<vector<int>>& image) {
        ans[row][col] = color;
        int m = image.size();
        int n = image[0].size();
        for (int i=0; i<4; i++) {
            int nRow = row + this->directions[i]; 
            int nCol = col + this->directions[i+1];
            if (nRow >= 0 && nRow < m && nCol >= 0 && nCol < n && image[nRow][nCol] == initColor && ans[nRow][nCol] != color) {
                dfs(nRow, nCol, color, initColor, ans, image);
            }
        }
    }

    // just to demo the usage of reference to an array: 
    // https://stackoverflow.com/questions/32732957/syntax-for-returning-an-array-reference-in-c
    void dfs(int row, int col, int color, int initColor, vector<vector<int>>& ans, vector<vector<int>>& image, const int (&dirs)[5]) {
        ans[row][col] = color;
        int m = image.size();
        int n = image[0].size();
        for (int i=0; i<4; i++) {
            int nRow = row + dirs[i]; 
            int nCol = col + dirs[i+1];
            if (nRow >= 0 && nRow < m && nCol >= 0 && nCol < n && image[nRow][nCol] == initColor && ans[nRow][nCol] != color) {
                dfs(nRow, nCol, color, initColor, ans, image, dirs);
            }
        }
    }
    
    const int (&getDirections() const)[3] { // Getter function to return const reference to the array
        return directions;
    }
private: 
    const int directions[5];
};

Note that for the primitive array, e.g., int a[3],

1. the a is a const pointer to the first element in the array, which means a = b is not allow

2. it's allocated in the stack, as opposed to const int b[] = new int[3]

3. to free the memory of the array b, and the objects contained in b, delete [] b should be used

4. note that in char name[] = "hello", the name is an array of 6 chars, including the \0 as the null terminator

28. 146. LRU Cache

class LRUCache {
public:
    LRUCache(int capacity): cap(capacity), head(new Node(-1, -1)), tail(new Node(-1, -1)) {
        head->next = tail;
        head->prev = nullptr;
        tail->prev = head;
        tail->next = nullptr;
    }

    LRUCache(const LRUCache&) = delete; // disable copy
    LRUCache& operator=(const LRUCache&) = delete; // disable copy
    
    int get(int key) {
        if (m.find(key) != m.end()) {
            Node* curr = m[key];
            int ans = curr->val;
            
            deleteNode(curr);
            addNode(curr); // add to the first

            return ans;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if (m.find(key) != m.end()) {
            Node* curr = m[key];
            m.erase(key);
            deleteNode(curr);
            delete curr;
        }

        if (m.size() == cap) {
            Node* last = tail->prev;
            m.erase(last->key);
            deleteNode(last);
            delete last;
        }

        addNode(new Node(key, value));
        m[key] = head->next;
    }

    ~LRUCache() {
        Node* d = head;
        while(d->next != nullptr) {
            Node* tmp = d->next;
            delete d;
            d = tmp;
        }
    }
private: 
    // private members of the nested classes are not visible from instances of the enclosing class
    class Node { 
    public:
        Node(int k, int v): key(k), val(v) {}     
    private:
        Node* prev;
        Node* next;
        int key;
        int val;  

        friend class LRUCache;
    };   

    int cap;
    unordered_map<int, Node*> m;
    Node* head;
    Node* tail;

    void addNode(Node* newNode) {
        Node* temp = head->next;
        newNode->next = temp;
        newNode->prev = head;
        temp->prev = newNode;
        head->next = newNode;
    } 

    void deleteNode(Node* delNode) {
        Node* prevv = delNode->prev;
        Node* nextt = delNode->next;
        prevv->next = nextt;
        nextt->prev = prevv;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

29. 621. Task Scheduler

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int freq[26];
        for (char task : tasks) {
            freq[task - 'A']++;
        }
        sort(begin(freq), end(freq));
        int chunk = freq[25] - 1;
        int slots = chunk * n;
        for (int i = 24; i>=0; i--){
            slots -= min(chunk, freq[i]);
        }
        // note that the slots might be negative when types of tasks are more than the n
        // and total number of tasks is larger than chunk * n.
        // eg., n = 2, tasks = ['A','A','A','B','B','B','C','C','C']
        return max(tasks.size(), tasks.size() + slots);
    }
};

30. 232. Implement Queue using Stacks

class MyQueue {
public:
    MyQueue() {
    }
    
    void push(int x) {
        pushStack.push(x);
    }
    
    int pop() {
        pushStackToPopStackIfNecessary();
        int result = popStack.top();
        popStack.pop();
        return result;
    }
    
    int peek() {
        pushStackToPopStackIfNecessary();
        return popStack.top();
    }
    
    bool empty() {
        return popStack.empty() && pushStack.empty();
    }
private: 
    stack<int> popStack, pushStack;
    void pushStackToPopStackIfNecessary() {
        if (popStack.empty()) {
            while (!pushStack.empty()) {
                popStack.push(pushStack.top());
                pushStack.pop();
            }
        }
    }    
};

31. 8. String to Integer (atoi)

class Solution {
public:
    int myAtoi(string s) {
        int i = 0;
        int sign = 1; 
        long ans = 0;
        while (i < s.length() && s[i] == ' ') {
            i++;
        }
        if (s[i] == '-') {
            sign = -1;
            i++;
        } else if (s[i] == '+') {
            i++;
        }
        while (i < s.length()) {
            if (s[i] >= '0' && s[i] <= '9') {
                ans = ans*10 + (s[i] - '0');
                if (ans > INT_MAX && sign == -1) {
                    return INT_MIN;
                } else if (ans > INT_MAX && sign == 1) {
                    return INT_MAX;
                }
                i++;
            } else {
                return ans * sign;
            }
        }
        return ans * sign;
    }
};

32. 981. Time Based Key-Value Store

class TimeMap {
public:
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
        map[key].emplace_back(timestamp, value);
    }
    
    string get(string key, int timestamp) {
        if (map.find(key) == map.end()) {
            return "";
        }
        int low = 0;
        int high = map[key].size() - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (map[key][mid].first < timestamp) {
                low = mid + 1;
            } else if (map[key][mid].first > timestamp) {
                high = mid - 1;
            } else {
                return map[key][mid].second;
            }
        }

        if (high >= 0) {
            return map[key][high].second;
        } else {
            return "";
        }
    }
private:
    unordered_map<string, vector<pair<int, string>>> map;
};

33. 54. Spiral Matrix

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int top = 0;
        int left = 0;
        int bottom = matrix.size() - 1;
        int right = matrix[0].size() - 1;
        vector<int> result;
        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; i++) {
                result.push_back(matrix[top][i]);
            }
            top++;

            for (int i = top; i <= bottom; i++) {
                result.push_back(matrix[i][right]);
            }
            right--;

            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result.push_back(matrix[bottom][i]);
                }
                bottom--;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.push_back(matrix[i][left]);
                }
                left++;
            }
        }
        return result;
    }
};

34. 141. Linked List Cycle

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
                return true;
        }
        return false;
    }
};

More,

1. How to get the length of the circle?

2. How to get the entry point of the circle?

35. 76. Minimum Window Substring

36. 11. Container With Most Water