LeetCode History

根據一畝三分地胖頭龍帖子順序刷題的記錄...

History

Number	Similar	Requirement	Title	Category	First attampt	Most recenet attamp	Success rate	Comments
704		Required	Binary Search	Binary Search	09/07/2022	09/07/2022	1/1	mid = left + (right - left) / 2 防止溢出
34		Core	Find First and Last Position of Element in Sorted Array	Binary Search	09/07/2022	09/07/2022	0/1	修改二分繼續查找的條件，同時更新邊界 index
702		Core	Search in a Sorted Array of Unknown Size	Binary Search	09/08/2022	09/08/2022	1/1	先確定邊界，再二分
153		Important	Find Minimum in Rotated Sorted Array	Binary Search	09/08/2022	09/08/2022	0/1	最小值左側大於 arr[-1]，最小值右側小於 arr[-1]
154		Important	Find Minimum in Rotated Sorted Array II	Binary Search	09/08/2022	09/08/2022	0/1	如果相等，直接扔掉 hi，反正有 mid 留著就行
278		Important	First Bad Version	Binary Search	09/08/2022	09/08/2022	1/1	簡單二分法
658		Important	Find K Closest Elements	Binary Search	09/10/2022	09/10/2022	0/1	雙指針/先二分找最近的
33		Required	Search in Rotated Sorted Array	Binary Search	09/10/2022	09/10/2022	1/1	分段單調之後分類討論，注意分類要分清楚
81		Required	Search in Rotated Sorted Array II	Binary Search	09/10/2022	09/10/2022	0/1	要考慮到是可以重複的, hi -= 1 即可;注意複雜度是 O(n),可能需要綫性查找全部元素
4		Core	Median of Two Sorted Arrays	Binary Search	09/10/2022	09/10/2022	0/1	雙指針很簡單，二分裏面 A[i-1] <= B[j], A[j-1] <= A[i]等價於最大的 i 使得 A[i-1]<=B[j]成立，同時注意 Java 會超過 Integer 範圍，所以要用 med 保存中間過程
74		Core	Search a 2D Matrix	Binary Search	09/12/2022	09/12/2022	1/1
240		74 Follow Up	Search a 2D Matrix II	Binary Search	09/12/2022	09/12/2022	1/1	普通對行二分注意用首尾加速；注意到矩陣元素向左變小向下變大，類似二分法
162		Core	Find Peak Element	Binary Search	09/12/2022	09/12/2022	0/1	綫性掃描注意防止 Integer 溢出，二分要説明正確性
302		Important	Smallest Rectangle Enclosing Black Pixels	Binary Search	09/14/2022	09/14/2022	0/1	暴力很簡單，BFS 或者二分理解下
852		Important	Peak Index in a Mountain Array	Binary Search	09/14/2022	09/14/2022	1/1
875		Core	Koko Eating Bananas	Binary Search	09/14/2022	09/14/2022	0/1	這個題不難，但是如果數據足夠大，時間會溢出，所以要用 long
1283		Core	Find the Smallest Divisor Given a Threshold	Binary Search	09/14/2022	09/14/2022	1/1	和 875 一樣，説明白如果 div > maxVal, sum 都是 arr.length, 取最小;同樣注意溢出，用 long
69		Important	Sqrt(x)	Binary Search	09/14/2022	09/14/2022	0/1	二分注意 mid 溢出，(long)mid * mid <= x 或者 x / mid >= mid, 但是後者 mid 不能是 0；牛頓法\(x_{n + 1} = x_n - \frac{f(x_n)}{f'(x_n)}\)
LintCode586		Important	Sqrt(x) II	Binary Search	09/14/2022	09/14/2022	1/1	注意 x < 1 的話先算 1/x
912		Required	Sort an Array	Sorting	09/18/2022	09/18/2022	1/1	merge sort/ quick sort
75		Required	Sort Colors	Sorting, Two Pointers	09/18/2022	09/18/2022	1/1	如果 p0 < p1,把 1 換出去了，還得換回來
26		Core	Remove Duplicates from Sorted Array	Two Pointers	09/19/2022	09/19/2022	1/1	我的不是最優解，j 有重複的
80		Core	Remove Duplicates from Sorted Array II	Two Pointers	09/19/2022	09/19/2022	0/1	這個可以推廣到最多保留 k 個重複
88		Core	Merge Sorted Array	Two Pointers	09/19/2022	09/19/2022	1/1	就是反向 merge
283		Core	Move Zeroes	Two Pointers	09/19/2022	09/19/2022	0/1	[0, lo - 1]是排好的，[lo, hi - 1]是 0，[hi， n - 1]是等待處理的
215		Core	Kth Largest Element in an Array	Two Pointers	09/19/2022	09/19/2022	1/1	手寫排序，然後直接求即可
347		Core	Top K Frequent Elements	Heap/ Bucket Sort	09/21/2022	09/21/2022	0/1	看到最大 k 个想到用 heap，或者桶排序
349		Core	Intersection of Two Arrays	HashTable/ Two pointers	09/22/2022	09/22/2022	1/1	用集合注意加速，用排序注意去重
350		Core	Intersection of Two Arrays II	HashTable/ Two pointers	09/23/2022	09/23/2022	1/1
845		Core	Longest Mountain in Array	Dynamic programming	09/23/2022	09/23/2022	0/1	动态规划，记录左边 l，右边 r, 如果 l > 0 && r > 0 => len = l + r + 1
845		Similar to 845	Longest Continuous Increasing Subsequence	Dynamic programming	09/23/2022	09/23/2022	1/1
42	11	Core	Trapping Rain Water	Dynamic programming	09/23/2022	09/23/2022	0/1	單純 dp，dp+雙指針加速
11		Core	Container With Most Water	Two pointers	09/24/2022	09/24/2022	0/1	雙指針更新面積即可，移動小的 height
43	415	Core	Multiply Strings	String	09/24/2022	09/24/2022	0/1	乘法，调用加法
415	2 43 989	Core	Add Strings	String	09/24/2022	09/24/2022	1/1	加法
969	NA	Important	Pancake Sorting	Two Pointers/Sorting	09/25/2022	09/25/2022	0/1	找最大，每次换到最后面去，然后考虑剩下的数组
21	NA	Important	Pancake Sorting	Two Pointers/Sorting	09/25/2022	09/25/2022	0/1	找最大，每次换到最后面去，然后考虑剩下的数组
86	NA	Core	Partition List	Two Pointers	09/25/2022	09/25/2022	1/1	注意c1.next = ge.next, c2.next = null
141	142 202	Core	Linked List Cycle	Hash Table/ Two Pointers	09/25/2022	09/25/2022	0/1	注意寫法簡潔性
160	599	Core	Intersection of Two Linked Lists	Hash Table/ Two Pointers	09/25/2022	09/25/2022	1/1
234	9 125 206	Core	Palindrome Linked List	Recursion/ Two Pointers	09/25/2022	09/25/2022	1/1
328	725	Core	Odd Even Linked List	LinkedList	09/25/2022	09/25/2022	1/1
142	141 287	Important	Linked List Cycle II	Hash Table/Two Pointers	09/25/2022	09/25/2022	0/1	f = 2s, f = s + nb;之后 f = 0, s = nb，多走 a 就相遇了
287	41 136 268 645	Important	Find the Duplicate Number	Two Pointers/Bit Manipulation	09/26/2022	09/26/2022	0/1
876	NA	Important	Middle of the Linked List	Two Pointers/LinkedList	09/26/2022	09/26/2022	1/1
Lint391	Lint821 Lint156	Required	Number of Airplanes in the Sky	Sweep Line	09/26/2022	09/26/2022	0/1	重叠區間問題標準做法: sweep line
56	57 252 253 495 616 715 759 763 986	Core	Merge Intervals	Array/Sorting	09/26/2022	09/26/2022	1/1	掃描綫 Integer 過不來了，int 可以
57	56 715	Core	Insert Interval	Array	09/26/2022	09/26/2022	1/1	掃描綫
252	56 253	Core	Meeting Rooms	Array/Sorting	09/27/2022	09/27/2022	1/1	掃描綫，排序
253	56 252 452 1094]	Core	Meeting Rooms II	Sorting/Two Pointers/Prefix Sum	09/27/2022	09/27/2022	1/1
986	56 88 759	Core	Interval List Intersections	Sorting/Two Pointers	09/28/2022	09/28/2022	0/1
5	214 226 [336] (#336) #516 647 345	Core	Longest Palindromic Substring	String/ Dynamic Programming	09/28/2022	09/28/2022	0/1
345	344 1119	Core	Reverse Vowels of a String	String/Two Pointers	09/28/2022	09/28/2022	1/1	不要用 set.contains(ch),用 str.indexOf(ch)
1119	345	Similar to 345	Remove Vowels from a String	String	09/28/2022	09/28/2022	1/1
344	345 541	Similar to 345	Reverse String	Recursion/Two Pointers	09/28/2022	09/28/2022	1/1
680	125	Core	Valid Palindrome II	Greedy/Two Pointers	09/28/2022	09/28/2022	0/1	暴力超时，思路是对的...
125	680 234	Important	Valid Palindrome	Greedy/Two Pointers	09/28/2022	09/28/2022	1/1
3	159 349 992	Required	Longest Substring Without Repeating Characters	Hash Table/Sliding Window	09/29/2022	09/29/2022	0/1	暴力超时; 学习滑动窗口模板
76	30 209 239 567 727	Core	Minimum Window Substring	Hash Table/Sliding Window	09/30/2022	09/30/2022	0/1	有重复所以用 need 和集合比; Integer 比较必须用 equals()，不能用等号
289	73	Core	Game of Life	Matrix/Simulation	10/01/2022	10/01/2022	1/1	優化空間 O(1)做法
209	76 325 718	Core	Minimum Size Subarray Sum	Array/Sliding Window	10/01/2022	10/01/2022	1/1
239	76 155 159 265	Core	Sliding Window Maximum	Heap/Monotonic Queue	10/01/2022	10/01/2022	0/1	PriorityQueue, 扔掉 window 左邊的；單調遞減隊列，後入隊的扔掉隊尾所有比它小的
713	152 325 560 1099	Core	Subarray Product Less Than K	Sliding Window	10/01/2022	10/01/2022	0/1	加入 hi 之后增加了hi-lo+1个选择
395	NA	Important	Longest Substring with At Least K Repeating Characters	HashTable	10/02/2022	10/02/2022	0/1	递归:如果有不满足的就分界，否则返回全部长度
480	295	Important	Sliding Window Median	Sliding Window/ Hash Table	10/03/2022	10/03/2022	0/1	注意数据范围，先转double; 用二分法注意如果删除了就停止
567	76 438	Important	Permutation in String	HashTable/Sliding Window	10/03/2022	10/03/2022	0/1	用 int[26]来比较是不是 permutation
295	480	Core	Find Median from Data Stream	Two Pointers/Heap	10/03/2022	10/03/2022	1/1
346	NA	Important	Moving Average from Data Stream	Queue/Array	10/03/2022	10/03/2022	1/1	注意 cnt 位置寫對
352	228 436 715	Important	Data Stream as Disjoint Intervals	Ordered Set/Binary Search	10/03/2022	10/03/2022	1/1
703	215	Important	Kth Largest Element in a Stream	BST/Heap	10/03/2022	10/03/2022	1/1
53	121 152 697 978	Important	Maximum Subarray	Divide and Conquer/Dynamic Programming	10/04/2022	10/04/2022	0/1	前项和:用滑动窗口来想，如果前项和<0,直接扔掉;
238	42 152 265	Important	Maximum Subarray	Prefix Sum	10/06/2022	10/06/2022	1/1	prefix 和 suffix;follow up 时候 suffix 只用一个就行了
303	304 307 325	Important	Range Sum Query - Immutable	Prefix Sum	10/06/2022	10/06/2022	1/1
325	209 303 525 713	Important	Maximum Size Subarray Sum Equals k	Prefix Sum	10/07/2022	10/07/2022	0/1	最前面加上 1; prefix 可以不用数组，用一个 pointer
528	398 710 497	Important	Random Pick with Weight	Prefix Sum	10/07/2022	10/07/2022	0/1
560	1 523 713 724 974	Important	Subarray Sum Equals K	Prefix Sum	10/08/2022	10/08/2022	0/1	map 保存出现次数，代表从 start 到 i 的总和为 k 的数组数量
1	15 18 167 170 560 653 1099	Important	Two Sum	Hash Table	10/09/2022	10/09/2022	1/1	HashTable 先插入则要检查重复，后插入不需要检查重复
15	1 16 18 259	Important	3Sum	Sorting/ Two pointers	10/10/2022	10/10/2022	0/1	排序，遇到重复的跳过
94	98 144 145	Required	Binary Tree Inorder Traversal	Stack/BST	11/07/2022	11/07/2022	1/1	注意 iterative approach
144	94 589 255	Required	Binary Tree Preorder Traversal	Stack/BST	11/07/2022	11/07/2022	1/1	注意 iterative approach
145	94 590	Required	Binary Tree Postorder Traversal	Stack/BST	11/07/2022	11/07/2022	1/1	注意 iterative approach
105	94 590	Required	Construct Binary Tree from Preorder and Inorder Traversal	Hash Table/BST	11/07/2022	11/07/2022	1/1
106	105	Important	Construct Binary Tree from Inorder and Postorder Traversal	Hash Table/BST	11/09/2022	11/09/2022	1/1
889		Important	Construct Binary Tree from Preorder and Postorder Traversal	Hash Table/BST	11/09/2022	11/09/2022	1/1	這個問題答案不唯一
173	94 251 281 284 285	Required	Binary Search Tree Iterator	Stack/BST	11/09/2022	11/09/2022	1/1
230	94 671	Required	Kth Smallest Element in a BST	Stack/BST	11/09/2022	11/09/2022	1/1
285	94 173 510	Important	Inorder Successor in BST	BST	11/09/2022	11/09/2022	1/1
270	222 272 700	Important	Closest Binary Search Tree Value	BST	11/09/2022	11/09/2022	1/1	注意用prev優化, 或者直接二分法
272	94 270	Important	Closest Binary Search Tree Value II	BST	11/21/2022	11/21/2022	1/1
510	285	Important	Inorder Successor in BST II	BST	11/21/2022	11/21/2022	1/1
Lint-915	Lint-67 Lint-86 Lint-448	Important	Inorder Predecessor in BST	BST	11/21/2022	11/21/2022	1/1
98	94 501	Core	Validate Binary Search Tree	BST	11/21/2022	11/21/2022	0/1	注意递归的写法,注意数据范围所以使用long
100		Core	Same Tree	BST/BFS/DFS	11/21/2022	11/21/2022	1/1
101		Core	Symmetric Tree	BST/BFS/DFS	11/21/2022	11/21/2022	1/1	注意base case别写复杂了
110	104	Core	Balanced Binary Tree	BST/BFS/DFS	11/21/2022	11/21/2022	1/1
111	102 104	Core	Minimum Depth of Binary Tree	BST/BFS/DFS	11/21/2022	11/21/2022	1/1
104	110 111 559	Important	Maximum Depth of Binary Tree	BST/BFS/DFS	11/21/2022	11/21/2022	1/1
333		Important	Largest BST Subtree	BST/DFS/BFS	11/21/2022	11/21/2022	0/1
112	113 124 129 437 666	Core	Path Sum	BST/DFS/BFS	11/21/2022	11/21/2022	0/1
113	112 257 437 666	Core	Path Sum II	BST/Backtracking	11/21/2022	11/21/2022	0/1	注意对于每一个recursive call, current需要是独立的
124	112 129 666 687	Core	Binary Tree Maximum Path Sum	BST/DP	11/21/2022	11/21/2022	0/1	不要用global variable
298	128 549	Important	Binary Tree Longest Consecutive Sequence	BST/DP	11/22/2022	11/22/2022	0/1	理解题意
549	298	Important	Binary Tree Longest Consecutive Sequence II	BST/DP	11/22/2022	11/22/2022	0/1	在递归目的和最优化目的不一致的时候用global variable
236	235 1257	Required	Lowest Common Ancestor of a Binary Tree	DFS/BT	12/15/2022	12/15/2022	1/1	postorder 更快
199	116 545	Core	Binary Tree Right Side View	DFS/BFS	12/16/2022	12/16/2022	1/1	level order拿最后一个即可，注意root是null
513		Core	Find Bottom Left Tree Value	DFS/BFS	12/16/2022	12/16/2022	1/1	level order拿最后一行第一个即可
331		Core	Verify Preorder Serialization of a Binary Tree	DFS/BFS	12/16/2022	12/16/2022	0/1	directed graph indegree = outdegree， 注意"#"的特殊情况是true，以及不到最后indegree < outdegree
449	297 652 428	Core	Serialize and Deserialize BST	DFS/BFS	12/16/2022	12/16/2022	0/1	注意list的toString分隔符是", "(有一个空格)，然后toString还包含了收尾的括号，需要去掉
114	430	Important	Flatten Binary Tree to Linked List	DFS/BFS	12/16/2022	12/16/2022	1/1	preoder即可
442	448	Core	Find All Duplicates in an Array	Array/Hash Table	12/17/2022	12/17/2022	1/1	注意取abs
48		Core	Rotate Image	Array/Math	12/18/2022	12/18/2022	0/1	顺时针90度=左右翻转+主对角线翻转(旋转270度是类似的逻辑)
54		Core	Spiral Matrix	Matrix/Simulation	12/18/2022	12/18/2022	1/1	控制左上右下然后模拟即可，注意size < n
73	289	Core	Set Matrix Zeroes	Matrix/Hash Table	12/18/2022	12/18/2022	1/1	可以用第一行/第一列当index空间复杂度是O(1)
289	73	Core	Game of Life	Matrix/Simulation	12/18/2022	12/18/2022	1/1	模拟即可
6	73	Core	Game of Life	String	12/18/2022	12/18/2022	1/1	用flag和row控制上下即可，二维数组太容易错了

Solutions

704

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

34

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        res[0] = findFirst(nums, target);
        res[1] = findLast(nums, target);
        return res;
    }

    public int findFirst(int[] nums, int target) {
        int leftIndex = -1;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - mid) / 2;
            if (nums[mid] >= target) {
                // 因爲要找到最第一個target，所以如果等於target，還要繼續往左邊找
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
            // 如果找到了，就更新leftIndex
            if (nums[mid] == target) {
                leftIndex = mid;
            }
        }
        return leftIndex;
    }

    public int findLast(int[] nums, int target) {
        int rightIndex = -1;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] <= target) {
                // 因爲要找到最最後一個target，所以如果等於target，還要繼續往右邊找
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
            // 如果找到了，就更新rightIndex
            if (nums[mid] == target) {
                rightIndex = mid;
            }
        }
        return rightIndex;
    }
}

702

    class Solution {
    public int search(ArrayReader reader, int target) {
        // 搜索邊界條件，不搜索的話lo = 0, hi = 可能上界10000也行...
        if (reader.get(0) == target) {
            return 0;
        }
        int lo = 0, hi = 1;
        while (reader.get(hi) < target) {
            lo = hi;
            hi *= 2;
        }
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (reader.get(mid) == target) {
                return mid;
            } else if (reader.get(mid) > target) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return -1;
    }
}

153

class Solution {
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]) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return nums[lo];
}

154

    class Solution {
    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]) {
                hi = mid;
            } else if (nums[mid] > nums[hi]) {
                lo = mid + 1;
            } else {
                hi--;
            }
        }
        return nums[lo];
    }
}

278

public class Solution {
    public int firstBadVersion(int n) {
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

658

public class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int lo = 0;
        int hi = arr.length - 1;
        int cnt = arr.length - k;
        List<Integer> res = new ArrayList<>();
        while (cnt > 0) {
            if (x - arr[lo] <= arr[hi] - x) {
                hi -= 1;
            } else {
                lo += 1;
            }
            cnt -= 1;
        }
        for (int i = lo; i <= hi; i++) {
            res.add(arr[i]);
        }
        return res;
    }
}


public class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int hi = findFirst(arr, x);
        int lo = hi - 1;
        int cnt = arr.length - k;
        List<Integer> res = new ArrayList<>();
        while (cnt > 0) {
            if (lo < 0) {
                hi += 1;
            } else if (hi >= arr.length) {
                lo -= 1;
            } else if (x - arr[lo] <= arr[hi] - x) {
                lo -= 1;
            } else {
                hi += 1;
            }
        }
        for (int i = lo + 1; i < hi; i++) {
            res.add(arr[i]);
        }
        return res;
    }

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

33

class Solution {
    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[mid] > nums[hi]) {
                if (target > nums[mid] || target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            } else {
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
        }
        return nums[lo] == target? lo: -1;
    }
}

81

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

4

// 這是O(m + n)
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int[] res = new int[m + n];
        int i = 0;
        int j = 0;
        int k = 0;
        while (i < n && j < m) {
            if (nums1[i] <= nums2[j]) {
                res[k] = nums1[i];
                i += 1;
            } else {
                res[k] = nums2[j];
                j += 1;
            }
            k += 1;
        }
        while (i < n) {
            res[k] = nums1[i];
            i += 1;
            k += 1;
        }
        while (j < m) {
            res[k] = nums2[j];
            j += 1;
            k += 1;
        }
        if ((m + n) % 2 == 0 ) {
            return 0.5 * (res[(m + n)/ 2] + res[(m + n)/ 2 - 1]);
        } else {
            return res[(m + n)/2];
        }
    }
}

// 這是O(log(min(m, n)))
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length, l2 = nums2.length;
        if (l1 > l2) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int lo = 0, hi =l1;
        int med1 = 0, med2 = 0;
        while (lo <= hi) {
            int i = lo + (hi - lo) / 2;
            int j = (l1 + l2 + 1) / 2 - i;
            int num1m = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int num1 = (i == l1 ? Integer.MAX_VALUE : nums1[i]);
            int num2m = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int num2 = (j == l2 ? Integer.MAX_VALUE : nums2[j]);
            if (num1m <= num2) {
                // 因爲上面四個值會溢出，所以要每一次算出兩個med來
                med1 = Math.max(num1m, num2m);
                med2 = Math.min(num1, num2);
                lo = i + 1;
            } else {
                hi = i - 1;
            }
        }
        if ((l1 + l2) % 2 == 0) {
            return 0.5 * (med1 + med2);
        }
        return med1;
    }
}

74

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int nrow = matrix.length;
        int ncol = matrix[0].length;

        int lo = 0, hi = nrow * ncol - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int midRow = mid / ncol;
            int midCol = mid % ncol;
            int val = matrix[midRow][midCol];
            if (target == val) {
                return true;
            } else if (target > val) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return false;
    }
}

240

// 這是O(m * log(n))
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            int[] row = matrix[i];
            if (target <row[0]) {
                break;
            }
            if (target > row[row.length - 1]) {
                continue;
            }
            if (binarySearch(row, target)) {
                return true;
            }
        }
        return false;
    }

    public boolean binarySearch(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 true;
            } else if (nums[mid] > target) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return false;
    }
}

// 這是O(m + n)
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int nrow = matrix.length;
        int ncol = matrix[0].length;

        int x = 0, y = ncol - 1;
        while (x < nrow && y >= 0) {
            int val = matrix[x][y];
            if (val == target) {
                return true;
            } else if (val > target) {
                y -= 1;
            }else {
                x += 1;
            }
        }
        return false;
    }
}

162

//  這是O(n), 注意元素取值範圍，所以需要用long
class Solution {
    public int findPeakElement(int[] nums) {
        long[] tmp = new long[nums.length + 2];
        tmp[0] = Long.MIN_VALUE;
        tmp[nums.length + 1] = Long.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            tmp[i + 1] = nums[i];
        }
        for (int j = 1; j < nums.length + 1; j++) {
            if ((tmp[j] > tmp[j - 1]) && (tmp[j] > tmp[j + 1])) {
                return j - 1;
            }
        }
        return -1;
    }
}

// 這是O(log(n))，需要説明數組存在峰值，并且二分不會錯過峰值
class Solution {
    public int findPeakElement(int[] nums) {
        int ans = 0;
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
                ans = i;
            }
        }
        return ans;
    }
}

302

// O(m * n)暴力計算
class Solution {
    public int minArea(char[][] image, int x, int y) {
        int m = image.length;
        int n = image[0].length;
        int xmin = Integer.MAX_VALUE;
        int xmax = Integer.MIN_VALUE;
        int ymin = Integer.MAX_VALUE;
        int ymax = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (image[i][j] == '1') {
                    xmin = Math.min(xmin, j);
                    xmax = Math.max(xmax, j);
                    ymin = Math.min(ymin, i);
                    ymax = Math.max(ymax, i);
                }
            }
        }
        return (xmax - xmin + 1) * (ymax - ymin + 1);
    }
}
// 二分法 O(m * log(n) + n * log(m))
class Solution {
    public int minArea(char[][] image, int x, int y) {
        int n = image.length;
        int m = image[0].length;
        int ymin = x, ymax = x, xmin = y, xmax = y;
        // calculate xmin
        int lo = 0, hi = x;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            boolean hasBlack = false;
            for (int i = 0; i < m; i ++) {
                if (image[mid][i] == '1') {
                    xmin = mid;
                    hasBlack = true;
                    hi = mid - 1;
                    break;
                }
            }
            if (!hasBlack) {
                lo = mid + 1;
            }
        }

        // calculate xmax
        lo = x;
        hi = n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            boolean hasBlack = false;
            for (int i = 0; i < m; i ++) {
                if (image[mid][i] == '1') {
                    xmax = mid;
                    hasBlack = true;
                    lo = mid + 1;
                    break;
                }
            }
            if (!hasBlack) {
                hi = mid - 1;
            }
        }

        // calculate ymin
        lo = 0;
        hi = y;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            boolean hasBlack = false;
            for (int i = 0; i < n; i++) {
                if (image[i][mid] == '1') {
                    hasBlack = true;
                    ymin = mid;
                    hi = mid - 1;
                    break;
                }
            }
            if (!hasBlack) {
                lo = mid + 1;
            }
        }

        // calculate ymax
        lo = y;
        hi = m - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            boolean hasBlack = false;
            for (int i = 0; i < n; i++) {
                if (image[i][mid] == '1') {
                    hasBlack = true;
                    ymax = mid;
                    lo = mid + 1;
                    break;
                }
            }
            if (!hasBlack) {
                hi = mid - 1;
            }
        }
        return (ymax - ymin + 1) * (xmax - xmin + 1);
    }
}

852

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

        }
        return -1;
    }
}

875

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int n = piles.length;
        int lo = 1, hi = -1;
        for (int i = 0; i < piles.length; i++) {
            if (piles[i] > hi) {
                hi = piles[i];
            }
        }
        int speed = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            long total = getTime(piles, mid);
            if (total <= h) {
                speed = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return speed;
    }

    public long getTime(int[] banana, int speed) {
        long res = 0;
        for (int i = 0; i < banana.length; i++) {
            if (banana[i] <= speed) {
                res += 1;
            } else {
                res += banana[i] / speed + (banana[i] % speed == 0? 0: 1);
            }
        }
        return res;
    }
}

1283

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int lo = 1, hi = -1;
        for (int i = 0; i < nums.length; i ++) {
            hi = Math.max(hi, nums[i]);
        }
        int res = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            long total = resSum(nums, mid);
            if (total <= threshold) {
                res = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return res;
    }

    public long resSum(int[] nums, int divisior) {
        long res = 0;
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            res += (val % divisior == 0? val / divisior : val / divisior + 1);
        }
        return res;
    }
}

69

// 暴力解法
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        for(int i = 1; i <= x; i++) {
            if (i > x / i) {
                return (int)i - 1;
            }
        }
        return -1;
    }
}
// 第一種二分法，防止溢出
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        int res = -1;
        int lo = 0, hi = x;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (x / mid >= mid) {
                res = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return res;
    }
}
// 第二種二分法，防止溢出
class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}
// 牛頓法，也是LogN，而且比二分法更快
class Solution {
    public int mySqrt(int x) {
        if (x == 0){
            return 0;
        }
        double guess = x;
        double epsilon = 1e-10
        while (Math.abs(guess * guess - x) > epsilon) {
            guess = (guess + x / guess) / 2;
        }
        return (int)guess;
    }
}

LintCode586

public class Solution {
    public double sqrt(double x) {
        double origin = x;
        double start = 0.0;
        if (x < 1.0) {
            x = 1.0 / x;
        }
        double end = x;
        double epsilon = 1e-12;
        while (Math.abs(end - start) > epsilon) {
            double mid = (start + end) / 2;
            if (mid * mid < x) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        double res = start + (end - start) / 2;
        if (origin < 1.0) {
            return 1.0 / res;
        }
        return res;
    }
}

912

// merge sort
class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        mergeSort(nums, 0, n - 1);
        return nums;
    }

    private void mergeSort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    }

    private void merge(int[] nums, int lo, int mid, int hi) {
        int n1 = mid - lo + 1;
        int n2 = hi - mid;
        int[] tmp1 = new int[n1];
        int[] tmp2 = new int[n2];
        for (int i = 0; i < n1; i++) {
            tmp1[i] = nums[lo + i];
        }
        for (int j = 0; j < n2; j++) {
            tmp2[j] = nums[mid + 1 + j];
        }
        int i = 0, j = 0, k = lo;
        while (i < n1 && j < n2) {
            if (tmp1[i] <= tmp2[j]) {
                nums[k] = tmp1[i];
                i += 1;
            } else {
                nums[k] = tmp2[j];
                j += 1;
            }
            k += 1;
        }
        while (i < n1) {
            nums[k] = tmp1[i];
            k += 1;
            i += 1;
        }
        while (j < n2) {
            nums[k] = tmp2[j];
            k += 1;
            j += 1;
        }
    }
}

// quick sort with random pivot
class Solution {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        quickSort(nums, 0, n - 1);
        return nums;
    }

    public void quickSort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int x = partition(nums, lo, hi);
        quickSort(nums, lo, x - 1);
        quickSort(nums, x + 1, hi);
    }

    public int partition(int[] nums, int lo, int hi) {
        int rd = new Random().nextInt(hi - lo + 1) + lo;
        int pivot = nums[rd];
        nums[rd] = nums[lo];
        nums[lo] = pivot;
        int i = lo;
        for (int j = lo + 1; j <= hi; j++) {
            if (nums[j] <= pivot) {
                i += 1;
                int tmp = nums[j];
                nums[j] = nums[i];
                nums[i] = tmp;
            }
        }
        int tmp = nums[i];
        nums[i] = pivot;
        nums[lo] = tmp;
        return i;
    }
}

75

// brutal force
class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int nr = 0;
        int nw = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                nr += 1;
            } else if (nums[i] == 1){
                nw += 1;
            }
        }
        for (int i = 0; i < nr; i++) {
            nums[i] = 0;
        }
        for (int i = nr; i < nr + nw; i++) {
            nums[i] = 1;
        }
        for (int i = nr + nw; i < n; i++) {
            nums[i] = 2;
        }
    }
}
// two pointers
class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0;
        int p1 = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                int tmp1 = nums[i];
                nums[i] = nums[p1];
                nums[p1] = tmp1;
                p1 += 1;
            } else if (nums[i] == 0) {
                int tmp2 = nums[i];
                nums[i] = nums[p0];
                nums[p0] = tmp2;
                if (p0 < p1) {
                    int tmp3 = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = tmp3;
                }
                p0 += 1;
                p1 += 1;
            }
        }
    }
}

26

// 這個做法的j是有重複的，不是最優解
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int cur = 0;
        while (cur < n) {
            int j = cur + 1;
            while (j < n && nums[j] <= nums[cur]) {
                j += 1;
            }
            if (j < n) {
                cur += 1;
                nums[cur] = nums[j];
            } else {
                break;
            }
        }
        return cur + 1;
    }
}
// 這個做法的j是沒有重複的，是最優解
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 1;
        }
        int lo = 1, hi = 1;
        while (hi < n) {
            if (nums[hi] != nums[hi - 1]) {
                nums[lo] = nums[hi];
                lo += 1;
            }
            hi += 1;
        }
        return lo;
    }
}

80

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= 2) {
            return n;
        }
        int lo = 2, hi = 2;
        while (hi < n) {
            if (nums[lo - 2] != nums[hi]) {
                nums[lo] = nums[hi];
                lo += 1;
            }
            hi += 1;
        }
        return lo;
    }
}
// 推廣到最多保留k個重複數字
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= k) {
            return n;
        }
        int lo = k, hi = k;
        while (hi < n) {
            if (nums[lo - k] != nums[hi]) {
                nums[lo] = nums[hi];
                lo += 1;
            }
            hi += 1;
        }
        return lo;
    }
}

88

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i -= 1;
            } else {
                nums1[k] = nums2[j];
                j -= 1;
            }
            k -= 1;
        }

        while (i >= 0) {
            nums1[k] = nums1[i];
            k -= 1;
            i -= 1;
        }
        while (j >= 0) {
            nums1[k] = nums2[j];
            k -= 1;
            j -= 1;
        }
    }
}

283

class Solution {
    public void moveZeroes(int[] nums) {
        int lo = 0, hi = 0;
        int n = nums.length;
        while (hi < n) {
            if (nums[hi] != 0) {
                int tmp = nums[lo];
                nums[lo] = nums[hi];
                nums[hi] = tmp;
                lo += 1;
            }
            hi += 1;
        }
    }
}

215

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        quickSort(nums, 0, n - 1);
        return nums[n - k];
    }

    public void quickSort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int x = partition(nums, lo, hi);
        quickSort(nums, lo, x - 1);
        quickSort(nums, x + 1, hi);
    }

    public int partition(int[] nums, int lo, int hi) {
        int rd = new Random().nextInt(hi - lo + 1) + lo;
        int pivot = nums[rd];
        swap(nums, rd, lo);
        int i = lo;
        for (int j = i + 1; j <= hi; j++) {
            if (nums[j] <= pivot) {
                i += 1;
                swap(nums, i, j);
            }
        }
        swap(nums, lo, i);
        return i;
    }

    public void swap(int[] nums, int r1, int r2) {
        int tmp = nums[r1];
        nums[r1] = nums[r2];
        nums[r2] = tmp;
    }
}

347

// bucket sort, this one is O(n)
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int val = nums[i];
            if (!map.containsKey(val)) {
                map.put(val, 1);
            } else {
                map.put(val, map.get(val) + 1);
            }
        }
        List<Integer>[] tmp = new List[n + 1];
        for (Integer val: map.keySet()) {
            int freq = map.get(val);
            if (tmp[freq] == null) {
                tmp[freq] = new ArrayList<Integer>();
            }
            tmp[freq].add(val);
        }

        int[] res = new int[k];
        int index = 0;

        for (int i = n; i >= 0; i--) {
            if (tmp[i] != null) {
                for (Integer val: tmp[i]) {
                    res[index] = val;
                    index += 1;
                }
            }
            if (index == k) {
                break;
            }
        }
        return res;
    }
}
// min heap, this is O(nlogk)
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int val = nums[i];
            if (!map.containsKey(val)) {
                map.put(val, 1);
            } else {
                map.put(val, map.get(val) + 1);
            }
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });

        int cnt = 0;
        for (Integer val: map.keySet()) {
            if (cnt < k) {
                pq.add(val);
                cnt += 1;
            } else {
                if (map.get(val) > map.get(pq.peek())) {
                    pq.remove();
                    pq.add(val);
                }
            }
        }

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.remove();
        }
        return res;
    }
}

349

//  time complexity O(m + n), space complexity O(m + n)
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> s1 = new HashSet<>();
        for (int i = 0; i < nums1.length; i++) {
            s1.add(nums1[i]);
        }
        Set<Integer> s2 = new HashSet<>();
        for (int i =0; i < nums2.length; i++) {
            s2.add(nums2[i]);
        }
        // speed up by looping on the smaller set
        return getIntersect(s1, s2);
    }

    public int[] getIntersect(Set<Integer> s1, Set<Integer> s2) {
        if (s1.size() > s2.size()) {
            return getIntersect(s2, s1);
        }
        Set<Integer> intersect = new HashSet<>();
        for (Integer val: s1) {
            if (s2.contains(val)) {
                intersect.add(val);
            }
        }
        int[] res = new int[intersect.size()];
        int cnt = 0;
        for (Integer val: intersect) {
            res[cnt] = val;
            cnt += 1;
        }
        return res;
    }
}

// time complexity: O(mlogm + nlogn), space complexity: O(m + n)
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] tmp = new int[1000];
        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i += 1;
            } else if (nums1[i] > nums2[j]) {
                j += 1;
            } else {
                tmp[k] = nums1[i];
                k += 1;
                i += 1;
                j += 1;
                while ( i < nums1.length && nums1[i] == nums1[i - 1]) {
                    i += 1;
                }
                while (j < nums2.length && nums2[j] == nums2[j - 1]) {
                    j += 1;
                }
            }
        }
        int[] res = new int[k];
        for (int l = 0; l < k; l++) {
            res[l] = tmp[l];
        }
        return res;
    }
}

350

// time complexity: O(m + n), space complexity: O(m + n)
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> m1 = new HashMap<>();
        for (int n : nums1) {
            if (m1.containsKey(n)) {
                m1.put(n, m1.get(n) + 1);
            } else {
                m1.put(n, 1);
            }
        }
        Map<Integer, Integer> m2 = new HashMap<>();
        for (int n : nums2) {
            if (m2.containsKey(n)) {
                m2.put(n, m2.get(n) + 1);
            } else {
                m2.put(n, 1);
            }
        }
        Set<Integer> set = m1.keySet();
        set.retainAll(m2.keySet());
        List<Integer> tmp = new ArrayList<>();
        for (int n: set) {
            int freq = Math.min(m1.get(n), m2.get(n));
            for (int i = 0; i < freq; i++) {
                tmp.add(n);
            }
        }
        int[] res = new int[tmp.size()];
        int index = 0;
        for (int n : tmp) {
            res[index] = n;
            index += 1;
        }
        return res;
    }
}

// time complexity: O(mlogm + nlogn), space complexity: O(m + n)
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int[] tmp = new int[nums1.length + nums2.length];
        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i += 1;
            } else if (nums1[i] > nums2[j]) {
                j += 1;
            } else {
                tmp[k] = nums1[i];
                i += 1;
                j += 1;
                k += 1;
            }
        }
        int[] res = new int[k];
        for (int l = 0; l < k; l ++) {
            res[l] = tmp[l];
        }
        return res;
    }
}

845

class Solution {
    public int longestMountain(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return 0;
        }
        int[] asc = new int[n];
        asc[0] = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                asc[i] = asc[i - 1] + 1;
            } else {
                asc[i] = 0;
            }
        }
        int[] des = new int[n];
        des[n - 1] = 0;
        for (int j = n - 2; j >= 0; j--) {
            if (arr[j] > arr[j + 1]) {
                des[j] = des[j + 1] + 1;
            } else {
                des[j] = 0;
            }
        }
        int maxLen = 0;
        for (int k = 0; k < n; k++) {
            if (asc[k] > 0 && des[k] > 0) {
                maxLen = Math.max(maxLen, asc[k] + des[k] + 1);
            }
        }
        return maxLen;
    }
}

674

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return n;
        }
        int[] asc = new int[n];
        asc[0] = 1;
        int res = 1;
        for (int i = 1; i < n; i ++) {
            if (nums[i] > nums[i - 1]) {
                asc[i] = asc[i - 1] + 1;
            } else {
                asc[i] = 1;
            }
            res = Math.max(res, asc[i]);
        }
        return res;
    }
}

42

// time complexity: O(n), space complexity: O(n)
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n <= 1) {
            return 0;
        }
        // calculate the highest bar on the left
        int[] left = new int[n];
        left[0] = 0;
        for (int i = 1; i < n; i++) {
            left[i] = Math.max(left[i - 1], height[i - 1]);
        }
        // calculate the highest bar on the right
        int[] right = new int[n];
        right[n - 1] = 0;
        for (int j = n - 2; j >= 0; j--) {
            right[j] = Math.max(right[j + 1], height[j + 1]);
        }
        // the water is determined by the lowest bar on the left and right
        int res = 0;
        for (int k = 1; k < n - 1; k++) {
            int low = Math.min(left[k], right[k]);
            if (height[k] < low) {
                res += low - height[k];
            }
        }
        return res;
    }
}
// time complexity: O(n), space complexity: O(1)
class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n <= 1) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int lo = 1;
        int hi = n - 2;
        int res = 0;
        for (int i = 1; i < n - 1; i ++) {
            if (height[lo - 1] < height[hi + 1]) {
                // left < right, so only update left
                left = Math.max(left, height[lo - 1]);
                if (height[lo] < left) {
                    res += (left - height[lo]);
                }
                lo += 1;
            } else {
                // left >= right, so only update right
                right = Math.max(right, height[hi + 1]);
                if (height[hi] < right) {
                    res += (right - height[hi]);
                }
                hi -= 1;
            }
        }
        return res;
    }
}

11

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

43

class Solution {
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        int len1 = num1.length();
        int len2 = num2.length();
        String res = "0";
        for (int i = len2 - 1; i >= 0; i--) {
            StringBuffer buffer = new StringBuffer();
            int item = num2.charAt(i) - '0';
            for (int j = len2 - 1; j > i; j--) {
                buffer.append('0');
            }
            int carry = 0;
            for (int k = len1 - 1; k >= 0; k--) {
                int itemk = num1.charAt(k) - '0';
                int total = item * itemk + carry;
                buffer.append(total % 10);
                carry = total / 10;
            }
            if (carry != 0) {
                buffer.append(carry);
            }
            res = addNum(res, buffer.reverse().toString());
        }
        return res;
    }

    public String addNum(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        if (len1 == 0 && len2 == 0) {
            return "";
        } else if (len1 == 0) {
            return num2;
        } else if (len2 == 0) {
            return num1;
        }
        StringBuffer buffer = new StringBuffer();
        int i = len1 - 1, j = len2 - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry != 0) {
            int n1 = i >= 0? num1.charAt(i) - '0' : 0;
            int n2 = j >= 0? num2.charAt(j) - '0' : 0;
            int total = n1 + n2 + carry;
            buffer.append(total % 10);
            carry = total / 10;
            i -= 1;
            j -= 1;
        }
        return buffer.reverse().toString();
    }
}

415

class Solution {
    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || carry != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + carry;
            ans.append(result % 10);
            carry = result / 10;
            i -= 1;
            j -= 1;
        }
        return ans.reverse().toString();
    }
}

969

class Solution {
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> res = new ArrayList<>();
        for (int n = arr.length; n >= 1; n--) {
            int index = 0;
            for (int i = 0; i < n; i++) {
                if (arr[i] >= arr[index]) {
                    index = i;
                }
            }
            if (index == n - 1) {
                continue;
            }
            reverse(arr, index);
            res.add(index + 1);
            reverse(arr, n - 1);
            res.add(n);
        }
        return res;
    }

    public void reverse(int[] arr, int hi) {
        int lo = 0;
        while (lo < hi) {
            int tmp = arr[lo];
            arr[lo] = arr[hi];
            arr[hi] = tmp;
            lo += 1;
            hi -= 1;
        }
    }
}

21

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode t1 = list1;
        ListNode t2 = list2;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (t1 != null && t2 != null) {
            if (t1.val < t2.val) {
                cur.next = t1;
                t1 = t1.next;
            } else {
                cur.next = t2;
                t2 = t2.next;
            }
            cur = cur.next;
        }
        if (t1 != null) {
            cur.next = t1;
        }
        if (t2 != null) {
            cur.next = t2;
        }
        return dummy.next;
    }
}

86

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode lt = new ListNode(-1);
        ListNode ge = new ListNode(-1);
        ListNode c1 = lt;
        ListNode c2 = ge;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                c1.next = cur;
                c1 = c1.next;
            } else {
                c2.next = cur;
                c2 = c2.next;
            }
            cur = cur.next;
        }
        c1.next = ge.next;
        c2.next = null;
        return lt.next;
    }
}

141

// time complexity O(n), space complexity O(1)
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}

// time complexity O(n), space complexity O(n)
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        ListNode cur = head;
        while (cur != null) {
            if (seen.contains(cur)) {
                return true;
            }
            seen.add(cur);
            cur = cur.next;
        }
        return false;
    }
}

160

// time complexity O(n + m), space complexity O(1)
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode c1 = headA;
        ListNode c2 = headB;
        while (c1 != c2) {
            if (c1 == null) {
                c1 = headB;
            } else {
                c1 = c1.next;
            }
            if (c2 == null) {
                c2 = headA;
            } else {
                c2 = c2.next;
            }
        }
        return c1;
    }
}

// time complexity O(n + m), space complexity O(n)
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> nodes = new HashSet<>();
        ListNode c1 = headA;
        while (c1 != null) {
            nodes.add(c1);
            c1 = c1.next;
        }
        ListNode c2 = headB;
        while (c2 != null) {
            if (nodes.contains(c2)) {
                return c2;
            }
            c2 = c2.next;
        }
        return null;
    }
}

234

// time complexity O(n), space complexity O(n)
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> values = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            values.add(cur.val);
            cur = cur.next;
        }
        int i = 0, j = values.size() - 1;
        while (i < j) {
            if (values.get(i) != values.get(j)) {
                return false;
            }
            i += 1;
            j -= 1;
        }
        return true;
    }
}

// time complexity O(n), space complexity O(1)
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode lo = head;
        ListNode hi = head.next;
        while (hi != null && hi.next != null) {
            lo = lo.next;
            hi = hi.next.next;
        }
        ListNode tmp = lo;
        lo = lo.next;
        ListNode half = reverse(lo);
        ListNode c1 = half;
        ListNode c2 = head;
        while (c1 != null) {
            if (c1.val != c2.val) {
                return false;
            }
            c1 = c1.next;
            c2 = c2.next;
        }
        tmp.next = reverse(half);
        return true;
    }

    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

328

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odds = new ListNode(-1);
        ListNode evens = new ListNode(-2);
        ListNode c1 = odds;
        ListNode c2 = evens;
        ListNode cur = head;
        boolean odd = true;
        while (cur != null) {
            if (odd) {
                c1.next = cur;
                c1 = c1.next;
                odd = !odd;
            } else {
                c2.next = cur;
                c2 = c2.next;
                odd = !odd;
            }
            cur = cur.next;
        }
        c1.next = evens.next;
        c2.next = null;
        return odds.next;
    }
}

142

// time complexity O(n), space complexity O(n)
public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        ListNode cur = head;
        while (cur != null) {
            if (seen.contains(cur)) {
                return cur;
            } else {
                seen.add(cur);
                cur = cur.next;
            }
        }
        return null;
    }
}
// time complexity O(n), space complexity O(1)
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode lo = head;
        ListNode hi = head;
        while (hi != null && hi.next != null) {
            lo = lo.next;
            hi = hi.next.next;
            if (lo == hi) {
                hi = head;
                while (lo != hi) {
                    lo = lo.next;
                    hi = hi.next;
                }
                return lo;
            }
        }
        return null;
    }
}

287

// brute force, time complexity O(n^2), space complexity O(1)
public class Solution {
    public int findDuplicate(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 nums[i];
                }
            }
        }
        return -1;
    }
}

// count, time complexity O(n), space complexity O(n)
public class Solution {
    public int findDuplicate(int[] nums) {
        int[] count = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            count[nums[i]] += 1;
            if (count[nums[i]] > 1) {
                return nums[i];
            }
        }
        return -1;
    }
}

// mark visited, time complexity O(n), space complexity O(1)
public class Solution {
    public int findDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int idx = Math.abs(nums[i]);
            if (nums[idx] < 0) {
                return idx;
            }
            nums[idx] = -nums[idx];
        }
        return -1;
    }
}

876

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode lo = head;
        ListNode hi = head;
        while (hi != null && hi.next != null) {
            hi = hi.next.next;
            lo = lo.next;
        }
        return lo;
    }
}

Lint391

// HashMap, time complexity O(n * max(interval)), space complexity O(n)
public class Solution {
    public int countOfAirplanes(List<Interval> airplanes) {
        if (airplanes == null || airplanes.size() == 0) {
            return 0;
        }
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (Interval intv: airplanes) {
            int start = intv.start;
            int end = intv.end;
            for (int i = start; i < end; i++) {
                map.put(i, map.getOrDefault(i, 0) + 1);
                res = Math.max(res, map.get(i));
            }
        }
        return res;
    }
}

// sweep line, time complexity O(nlogn), space complexity O(n)
public class Solution {
    public int countOfAirplanes(List<Interval> airplanes) {
        List<Integer[]> times = new ArrayList<>();
        for (Interval intv: airplanes) {
            times.add(new Integer[] {intv.start, 1});
            times.add(new Integer[] {intv.end, -1});
        }
        Collections.sort(times, new Comparator<Integer[]>() {
            public int compare(Integer[] a, Integer[] b) {
                if (a[0] == b[0]) {
                    return a[1] - b[1];
                }
                return a[0] - b[0];
            }
        });
        int res = 0;
        int sum = 0;
        for (Integer[] item : times) {
            sum += item[1];
            res = Math.max(res, sum);
        }
        return res;
    }
}

56

// time complexity O(nlogn), space complexity O(n)
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> times = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int[] interval = intervals[i];
            times.add(new int[] {interval[0], 1});
            times.add(new int[] {interval[1], -1});
        }
        Collections.sort(times, new Comparator<>() {
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0]) {
                    return -a[1] + b[1];
                }
                return a[0] - b[0];
            }
        });
        List<int[]> tmp = new ArrayList<>();
        int cnt = 0;
        int i = 0;
        int start = -1;
        int end = -1;
        while (i < times.size()) {
            if (times.get(i)[1] > 0) {
                cnt += 1;
                if (cnt == 1) {
                    start = times.get(i)[0];
                }
            } else {
                cnt -= 1;
                if (cnt == 0) {
                    end = times.get(i)[0];
                    tmp.add(new int[] {start, end});
                }
            }
            i += 1;
        }
        int[][] res = new int[tmp.size()][2];
        for (int k = 0; k < tmp.size(); k++) {
            res[k] = new int[2];
            res[k][0] = tmp.get(k)[0];
            res[k][1] = tmp.get(k)[1];
        }
        return res;
    }
}

// time complexity O(nlogn), space complexity O(n)
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        List<int[]> tmp = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            if (tmp.size() == 0 || tmp.get(tmp.size() - 1)[1] < start) {
                tmp.add(new int[] {start, end});
            } else {
                tmp.get(tmp.size() - 1)[1] = Math.max(tmp.get(tmp.size() - 1)[1], end);
            }
        }
        int[][] res = new int[tmp.size()][2];
        for (int i = 0; i < res.length; i++) {
            res[i] = new int[2];
            res[i][0] = tmp.get(i)[0];
            res[i][1] = tmp.get(i)[1];
        }
        return res;
    }
}

57

// sweep line, time complexity O(nlogn), space complexity O(n)
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] tmp = new int[intervals.length * 2 + 2][2];
        for (int i = 0; i < intervals.length; i++) {
            tmp[2 * i][0] = intervals[i][0];
            tmp[2 * i][1] = 1;
            tmp[2 * i + 1][0] = intervals[i][1];
            tmp[2 * i + 1][1] = -1;
        }
        tmp[tmp.length - 2] = new int[]{newInterval[0], 1};
        tmp[tmp.length - 1] = new int[]{newInterval[1], -1};
        Arrays.sort(tmp, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0]) {
                    return b[1] - a[1];
                }
                return a[0] - b[0];
            }
        });
        List<int[]> list = new ArrayList<>();
        int cnt = 0;
        int start = -1;
        int end = -1;
        int i = 0;
        while (i < tmp.length) {
            if (tmp[i][1] > 0) {
                cnt += 1;
                if (cnt == 1) {
                    start = tmp[i][0];
                }
            } else {
                cnt -= 1;
                if (cnt == 0) {
                    end = tmp[i][0];
                    list.add(new int[] {start, end});
                }
            }
            i += 1;
        }
        int[][] res = new int[list.size()][2];
        for (int k = 0; k < res.length; k++) {
            res[k] = list.get(k);
        }
        return res;
    }
}

// sort, time complexity O(nlogn), space complexity O(n)
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int lo = newInterval[0];
        int hi = newInterval[1];
        List<int[]> list = new ArrayList<>();
        boolean inserted = false;
        for (int[] interval : intervals) {
            // boolean cond1 = interval[0] < lo && interval[1] >= lo;
            // boolean cond2 = interval[0] <= hi && interval[1] > hi;
            // boolean cond3 = interval[0]<= lo && interval[1] >= hi;
            // boolean cond4 = interval[0] >= lo && interval[1] <= hi;
            // boolean cond = cond1 || cond2 || cond3 || cond4;
            if (interval[1] < lo) {
                list.add(interval);
            } else if (interval[0] > hi) {
                if (!inserted) {
                    list.add(new int[] {lo, hi});
                    inserted = true;
                }
                list.add(interval);
            // } else if (cond) { there are four conditions where the intervals are overlapped, so use else here
            } else {
                lo = Math.min(lo, interval[0]);
                hi = Math.max(hi, interval[1]);
            }
        }
        // if no interval is on the right side, add the new interval (possibly merged with overlapped intervals) to the end
        if (!inserted) {
            list.add(new int[] {lo, hi});
        }
        int[][] res  = new int[list.size()][2];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

252

// sweep line, time complexity O(nlogn), space complexity O(n)
class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        int n = intervals.length;
        int[][] tmp = new int[n * 2][2];
        for (int i = 0; i < n; i++) {
            tmp[2 * i] = new int[] {intervals[i][0], 1};
            tmp[2 * i + 1] = new int[] {intervals[i][1], -1};
        }
        Arrays.sort(tmp, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                if (a[0] == b[0]) {
                    return a[1] - b[1];
                }
                return a[0] - b[0];
            }
        });
        int k = 0;
        int cnt = 0;
        while (k < tmp.length) {
            if (tmp[k][1] > 0) {
                cnt += 1;
                if (cnt > 1) {
                    return false;
                }
            } else {
                cnt -= 1;
            }
            k += 1;
        }
        return true;
    }
}

// sort, time complexity O(nlogn), space complexity O(1)
class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });

        for (int i = 0; i < intervals.length; i++) {
            if (i < intervals.length - 1 && intervals[i][1] > intervals[i + 1][0]) {
                return false;
            }
        }
        return true;
    }
}

253

// sorting + heap, time complexity O(nlogn), space complexity O(n)
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        int cnt = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int[] interval: intervals) {
            if (pq.size() == 0) {
                cnt += 1;
                pq.add(interval[1]);
            } else {
                int end = pq.peek();
                if (interval[0] < end) {
                    cnt += 1;
                    pq.add(interval[1]);
                } else {
                    pq.remove();
                    pq.add(interval[1]);
                }
            }
        }
        return cnt;
    }
}

986

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
    int m = firstList.length;
    int n = secondList.length;
    int i = 0, j = 0;
    List<int[]> tmp = new ArrayList<>();
    while (i < m && j < n) {
        int start = Math.max(firstList[i][0], secondList[j][0]);
        int end = Math.min(firstList[i][1], secondList[j][1]);
        if (start <= end) {
            tmp.add(new int[] {start, end});
        }
        if (firstList[i][1] < secondList[j][1]) {
            i += 1;
        } else {
            j += 1;
        }
    }
    int[][] res = new int[tmp.size()][2];
    for (int k = 0; k < res.length; k++) {
        res[k] = tmp.get(k);
    }
    return res;
    }
}

5

class Solution {
    public String longestPalindrome(String s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                // if len is odd, i is the center index, if len is even, i is last index of the first half
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

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

345

class Solution {
    public boolean isVowel(char c) {
        return "aeiouAEIOU".indexOf(c) >= 0;
    }

    public String reverseVowels(String s) {
        char[] chars = new char[s.length()];
        for (int i = 0; i < s.length(); i++) {
            chars[i] = s.charAt(i);
        }
        int i = 0, j = s.length() - 1;
        while (i < j) {
            boolean cond1 = isVowel(chars[i]);
            boolean cond2 = isVowel(chars[j]);
            if (cond1 && cond2) {
                char tmp = chars[i];
                chars[i] = chars[j];
                chars[j] = tmp;
                i += 1;
                j -= 1;
            } else if (cond1) {
                j -= 1;
            } else if (cond2) {
                i += 1;
            } else {
                i += 1;
                j -= 1;
            }
        }
        return new String(chars);
    }
}

680

class Solution {
    public boolean validPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return isP(s, i + 1, j) || isP(s, i, j - 1);
            }
            i += 1;
            j -= 1;
        }
        return true;
    }

    public boolean isP(String input, int lo, int hi) {
        int i = lo, j = hi;
        while (i < j) {
            if (input.charAt(i) != input.charAt(j)) {
                return false;
            }
            i += 1;
            j -= 1;
        }
        return true;
    }
}

125

class Solution {
    public boolean isPalindrome(String s) {
        s = s.toLowerCase();
        int n = s.length();
        int i = 0, j = n - 1;
        while (i < j) {
            boolean cond1 = Character.isLetterOrDigit(s.charAt(i));
            boolean cond2 = Character.isLetterOrDigit(s.charAt(j));
            if (cond1 && cond2) {
                if (s.charAt(i) != s.charAt(j)) {
                    return false;
                } else {
                    i += 1;
                    j -= 1;
                }
            } else if (cond1) {
                j -= 1;
            } else if (cond2) {
                i += 1;
            } else {
                i += 1;
                j -= 1;
            }
        }
        return true;
    }
}

3

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) {
            return s.length();
        }
        Set<Character> set = new HashSet<>();
        int len = 0;
        int start = 0, end = 0;
        while (end < s.length()) {
            while (set.contains(s.charAt(end))) {
                set.remove(s.charAt(start));
                start += 1;
            }
            set.add(s.charAt(end));
            len = Math.max(len, end - start + 1);
            end += 1;
        }
        return len;
    }
}

76

class Solution {
    public String minWindow(String s, String t) {
        if (t.length() > s.length()) {
            return "";
        }

        Map<Character, Integer> mapT = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            mapT.put(t.charAt(i), mapT.getOrDefault(t.charAt(i), 0) + 1);
        }

        int l = 0, r = 0;
        int minLen = Integer.MAX_VALUE, start = 0;
        // Since there can be duplicates, compare have and the size of mapT
        int have = 0, need = mapT.size();
        Map<Character, Integer> mapS = new HashMap<>();

        while (r < s.length()) {
            char c1 = s.charAt(r);
            mapS.put(c1, mapS.getOrDefault(c1, 0) + 1);
            // Use equals to compare Integer
            // use mapS.get(c1) first to avoid NPE
            if (mapS.get(c1).equals(mapT.get(c1))) {
                have += 1;
            }
            while (have == need) {
                char c2 = s.charAt(l);
                if (r - l + 1< minLen) {
                    minLen = r - l + 1;
                    start = l;
                }
                if (mapS.get(c2).equals(mapT.get(c2))) {
                    have -= 1;
                }
                mapS.put(c2, mapS.get(c2) - 1);
                l += 1;
            }
            r += 1;
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

289

// time complexity O(mn), space complexity O(mn)
class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[][] tmp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0 ; j < n; j++) {
                tmp[i][j] = board[i][j];
            }
        }
        for (int i = 0; i < m ; i++) {
            for (int j = 0; j < n; j++) {
                int liveNbr = liveNeighbor(tmp, i, j);
                if (tmp[i][j] == 1) {
                    if (liveNbr == 2 || liveNbr == 3) {
                        board[i][j] = 1;
                    } else {
                        board[i][j] = 0;
                    }
                } else {
                    if (liveNbr == 3) {
                        board[i][j] = 1;
                    } else {
                        board[i][j] = 0;
                    }
                }
            }
        }

    }

    public int liveNeighbor(int[][] input, int row, int col) {
        int m = input.length;
        int n = input[0].length;
        int cnt = 0;
        for (int i = -1; i < 2; i++) {
            for (int j = -1; j < 2; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                if (valid(m, n, row + i, col + j)) {
                    cnt += input[row + i][col + j];
                }
            }
        }
        return cnt;
    }
    public boolean valid(int m , int n, int  row, int col) {
        return 0 <= row && row < m && col >= 0 && col < n;
    }
}

// time complexity O(mn), space complexity O(1)
class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m ; i++) {
            for (int j = 0; j < n; j++) {
                int liveNbr = 0;
                for (int k = -1; k < 2; k++) {
                    for (int l = -1; l < 2; l++) {
                        if (k == 0 && l == 0) {
                            continue;
                        }
                        if (valid(m, n, i + k, j + l)) {
                            if (Math.abs(board[i + k][j + l]) == 1) {
                                liveNbr += 1;
                            }
                        }
                    }
                }
                if (board[i][j] == 1 && (liveNbr < 2 || liveNbr > 3)) {
                    board[i][j] = -1;
                }
                if (board[i][j] == 0 && liveNbr == 3) {
                    board[i][j] = 2;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] > 0) {
                    board[i][j] = 1;
                } else {
                    board[i][j] = 0;
                }
            }
        }
    }

    public boolean valid(int m , int n, int  row, int col) {
        return 0 <= row && row < m && col >= 0 && col < n;
    }
}

209

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLen = Integer.MAX_VALUE, start = 0;
        int lo = 0, hi = 0;
        int total = 0;
        while (hi < nums.length) {
            total += nums[hi];
            while (total >= target) {
                if (hi - lo + 1 < minLen) {
                    start = lo;
                    minLen = hi - lo + 1;
                }
                total -= nums[lo];
                lo += 1;
            }
            hi += 1;
        }
        return minLen == Integer.MAX_VALUE ? 0: minLen;
    }
}

239

// Heap: time complexity O(nlogn), space complexity O(k)
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        PriorityQueue<int[]> pq = new PriorityQueue<>(k, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                if (a[0] != b[0]) {
                    return b [0] - a[0];
                }
                return b[1] - a[1];
            }
        });
        for (int i = 0; i < k; i++) {
            pq.add(new int[] {nums[i], i});
        }
        res[0] = pq.peek()[0];
        for (int i = k; i < n; i++) {
            pq.add(new int[] {nums[i], i});
            while (pq.peek()[1] < i - k + 1) {
                pq.remove();
            }
            res[i - k + 1] = pq.peek()[0];
        }
        return res;
    }
}

// Deque: time complexity O(n), space complexity O(k)
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        // store index, because we need to check if the maximum is inside the sliding window
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < k; i++) {
            while (dq.size() != 0 && nums[dq.peekLast()] < nums[i]) {
                dq.removeLast();
            }
            dq.addLast(i);
        }
        res[0] = nums[dq.peekFirst()];
        for (int i = k; i < n; i++) {
            while (dq.size() != 0 && nums[dq.peekLast()] < nums[i]) {
                dq.removeLast();
            }
            dq.addLast(i);
            while (dq.peekFirst() < i - k + 1) {
                dq.removeFirst();
            }
            res[i - k + 1] = nums[dq.peekFirst()];
        }
        return res;
    }
}

713

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) {
            return 0;
        }
        int lo = 0, hi = 0;
        int prod = 1, res = 0;
        while (hi < nums.length) {
            prod *= nums[hi];
            while (prod >= k) {
                prod /= nums[lo];
                lo += 1;
            }
            // The sub-arrays are: [hi], [hi-1, hi], ..., [lo, ..., hi], there are hi - lo + 1 sub-arrays
            res += hi - lo + 1;
            hi += 1;
        }
        return res;
    }
}

395

class Solution {
    public int longestSubstring(String s, int k) {
        if (s.length() < k) {
            return 0;
        }
        Map<Character, Integer> freq = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            freq.put(s.charAt(i), freq.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (Character key: freq.keySet()) {
            // there is one layer of recursion for each character that has frequency less than k
            if (freq.get(key) < k) {
                int res = 0;
                String[] tmp = s.split("" + key);
                for (String item: tmp) {
                    res = Math.max(res, longestSubstring(item, k));
                }
                return res;
            }
        }
        // if all frequencies are equal to or greater than k
        return s.length();
    }
}

480

// Brute force: time complexity  O(nklogk), space complexity O(nk)
class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    double[] res = new double[n - k + 1];
    long[] tmp = new long[k];
    for (int i = 0; i < n - k + 1; i++) {
        for (int j = 0; j < k; j++) {
            tmp[j] = nums[i + j];
        }
        Arrays.sort(tmp);
        res[i] =  0.5 * (tmp[k / 2] + tmp[(k - 1) / 2]);
    }
    return res;
    }
}

// Binary search tree: time complexity O(nk), space complexity O(k)
class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int lo = 0, hi = 0;
        double[] res = new double[n - k + 1];
        List<Integer> tmp = new ArrayList<>();
        while (hi < n) {
            int val1 = nums[hi];
            insert(tmp, val1);
            if (tmp.size() == k) {
                res[lo] = 0.5 * ((double) tmp.get(k / 2) + (double)tmp.get((k - 1) / 2));
                int val2 = nums[lo];
                remove(tmp, val2);
                lo += 1;
            }
            hi += 1;
        }
        return res;
    }

    private void insert(List<Integer> list, int val) {
        int lo = 0, hi = list.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (list.get(mid) < val) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        // shift is involved here, so this is O(k) rather than O(logk)
        list.add(lo, val);
    }

    private void remove(List<Integer> list, int val) {
        int lo = 0, hi = list.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (list.get(mid).equals(val)) {
                // shift is involved here, so this is O(k) rather than O(logk)
                list.remove(mid);
                // if val is removed, no further search is needed
                break;
            } else if (list.get(mid) < val) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
    }
}

567

// time complexity O(n), space complexity O(1)
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < n; ++i) {
            cnt1[s1.charAt(i) - 'a'] += 1;
            cnt2[s2.charAt(i) - 'a'] += 1;
        }
        if (Arrays.equals(cnt1, cnt2)) {
            return true;
        }
        for (int i = n; i < m; ++i) {
            cnt2[s2.charAt(i) - 'a'] += 1;
            cnt2[s2.charAt(i - n) - 'a'] -= 1;
            if (Arrays.equals(cnt1, cnt2)) {
                return true;
            }
        }
        return false;
    }
}

295

// Heap: time complexity O(logn), space complexity O(n)
class MedianFinder {
    private PriorityQueue<Integer> small;
    private PriorityQueue<Integer> large;

    public MedianFinder() {
        this.small = new PriorityQueue<>(new Comparator<>() {
            public int compare(Integer a, Integer b) {
                return b - a;
            }
        });
        this.large = new PriorityQueue<>(new Comparator<>() {
            public int compare(Integer a, Integer b) {
                return a - b;
            }
        });
    }

    public void addNum(int num) {
        if (small.size() == 0 || num <= small.peek()) {
            small.add(num);
            if (small.size() > large.size() + 1) {
                large.add(small.poll());
            }
        } else {
            large.add(num);
            if (large.size() > small.size()) {
                small.add(large.poll());
            }
        }
    }

    public double findMedian() {
        if (small.size() > large.size()) {
            return 1.0 * small.peek();
        }
        return 0.5 * (small.peek() + large.peek());
    }
}

// Binary search tree: time complexity O(n), space complexity O(n)
class MedianFinder {
    private List<Integer> list;
    public MedianFinder() {
        this.list = new ArrayList<>();
    }

    public void addNum(int num) {
        int lo = 0, hi = list.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (list.get(mid) < num) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        // shift is involved here, so this is O(n) rather than O(logn)
        list.add(lo, num);
    }

    public double findMedian() {
        int k = list.size();
        return 0.5 * (list.get(k / 2) + list.get((k - 1) / 2));
    }
}

346

class MovingAverage {
    private List<Integer> vals;
    private int size;
    private int cnt;
    public MovingAverage(int size) {
        vals = new ArrayList<>();
        this.size = size;
        cnt = 0;
    }

    public double next(int val) {
        if (cnt == 0) {
            vals.add(val);
        } else {
            int t = vals.get(cnt - 1);
            vals.add(t + val);
        }
        cnt += 1;
        if (cnt <= size) {
            return vals.get(cnt - 1) * 1.0 / cnt;
        } else {
            return (vals.get(cnt- 1) - vals.get(cnt - 1 - size)) / (1.0 * size);
        }
    }
}

352

class SummaryRanges {
    private Set<Integer> vals;
    int max = -1;

    public SummaryRanges() {
        vals = new HashSet<>();
    }

    public void addNum(int value) {
        vals.add(value);
        if (value > max) {
            max = value;
        }
    }
    public int[][] getIntervals() {
        int start = -1, end = -1;
        List<int[]> tmp = new ArrayList<>();
        int index = 0;
        int i = 0;
        while (i <= max) {
            while (i <= max && (!vals.contains(i))) {
                i += 1;
            }
            start = i;
            while (i <= max && vals.contains(i)) {
                i += 1;
            }
            if (i > max) {
                end = max;
            } else {
                end = i - 1;
            }
            tmp.add(new int[] {start, end});
            index += 1;
        }
        int[][] res = new int[tmp.size()][2];
        for (int j = 0; j < res.length; j++) {
            res[j] = tmp.get(j);
        }
        return res;
    }
}

703

class KthLargest {
    private PriorityQueue<Integer> pq;
    private int size;
    public KthLargest(int k, int[] nums) {
        pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return a - b;
            }
        });
        size = k;
        for (int n: nums) {
            add(n);
        }
    }

    public int add(int val) {
        if (pq.size() < size) {
            pq.add(val);
        } else {
            if (pq.peek() < val) {
                pq.poll();
                pq.add(val);
            }
        }
        return pq.peek();
    }
}

53

// Prefix sum: time complexity O(n), space complexity O(1)
class Solution {
    public int maxSubArray(int[] nums) {
        // result
        int res = nums[0];
        // prefix sum
        int curSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (curSum < 0) {
                curSum = 0;
            }
            curSum += nums[i];
            res = Math.max(curSum, res);
        }
        return res;
    }
}

238

// Both prefix and suffix
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        prefix[0] = nums[0];
        suffix[n - 1] = nums[n - 1];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i];
        }
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i];
        }
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                res[i] = 1 * suffix[i  + 1];
            } else if (i == n - 1) {
                res[i] = 1 * prefix[i - 1];
            } else {
                res[i] = suffix[i + 1] * prefix[i - 1];
            }
        }
        return res;
    }
}

//Prefix array and only pointer
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            answer[i] = answer[i] * R;
            R *= nums[i];
        }
        return answer;
    }
}

303

class NumArray {

    private int[] prefix;

    public NumArray(int[] nums) {
        int n  = nums.length;
        prefix = new int[n];
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        if (left == 0) {
            return  prefix[right];
        } else {
            return prefix[right] - prefix[left - 1];
        }
    }
}

325

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
            if (map.containsKey(sum - k)) {
                len = Math.max(len, i - map.get(sum - k));
            }
        }
        return len;
    }
}

325

class Solution {
    int[] pre;

    public Solution(int[] w) {
        pre = new int[w.length];
        pre[0] = w[0];
        for (int i = 1; i < w.length; ++i) {
            pre[i] = pre[i - 1] + w[i];
        }
    }

    public int pickIndex() {
        int x = (int) (Math.random() * pre[pre.length - 1]) + 1;
        return binarySearch(x);
    }

    private int binarySearch(int x) {
        int low = 0, high = pre.length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (pre[mid] < x) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

560

// Simulation: time complexity O(n^2), space complexity O(1)
class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j >= 0; j--) {
                sum += nums[j];
                if (sum == k) {
                    res += 1;
                }
            }
        }
        return res;
    }
}

// Prefix sum: time complexity O(n), space complexity O(n)
class Solution {
    public int subarraySum(int[] nums, int k) {
        int sum = 0;
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            // find the amount of start index, the end index is i
            if (map.containsKey(sum - k)) {
                res += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}

1</1>

// Brute force: time complexity O(n^2), space complexity O(1)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
        return null;
    }
}

// Use hash table: time complexity O(n), space complexity O(n)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // if we check this first, we need to avoid duplicate
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);
            }
            if (map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i) {
                res[0] = map.get(target - nums[i]);
                res[1] = i;
                return res;
            }
        }
        return res;
    }
}

// An variation of hash table
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                res[0] = map.get(target - nums[i]);
                res[1] = i;
                return res;
            }
            map.put(nums[i], i);
        }
        return res;
    }
}

15

// time complexity O(n^2), space complexity O(1)
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return res;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int lo = i + 1;
            int hi = nums.length - 1;
            while(lo < hi) {
                int val = nums[i] + nums[lo] + nums[hi];
                if (val == 0) {
                    List<Integer> comb = new ArrayList<>();
                    comb.add(nums[i]);
                    comb.add(nums[lo]);
                    comb.add(nums[hi]);
                    res.add(comb);
                    while(lo < hi && nums[lo] == nums[lo + 1]) {
                        lo += 1;
                    }
                    while(lo < hi && nums[hi] == nums[hi - 1]) {
                        hi -= 1;
                    }
                    lo += 1;
                    hi -= 1;
                } else if (val > 0) {
                    hi -= 1;
                } else {
                    lo += 1;
                }
            }
        }
        return res;
    }
}

18

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if (i + 3 < nums.length && (long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if (i < nums.length - 3 && (long)nums[i] + nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] < target) {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int lo = j + 1, hi = nums.length - 1;
                while (lo < hi) {
                    long val = (long)nums[i] + nums[j] + nums[lo] + nums[hi];
                    if (val == target) {
                        List<Integer> tmp = new ArrayList<>();
                        tmp.add(nums[i]);
                        tmp.add(nums[j]);
                        tmp.add(nums[lo]);
                        tmp.add(nums[hi]);
                        res.add(tmp);
                        while (lo < hi && nums[lo] == nums[lo + 1]) {
                            lo += 1;
                        }
                        while (hi > lo && nums[hi] == nums[hi - 1]) {
                            hi -= 1;
                        }
                        lo += 1;
                        hi -= 1;
                    } else if (val < target) {
                        lo += 1;
                    } else if (val > target) {
                        hi -= 1;
                    }
                }
            }
        }
        return res;
    }
}

94

// iterative approach
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    Deque<TreeNode> nodes = new LinkedList<>();
    while (root != null || !nodes.isEmpty()) {
        while (root != null) {
            nodes.push(root);
            root = root.left;
        }
        root = nodes.pop();
        res.add(root.val);
        root = root.right;
    }
    return res;
    }
}

144

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> nodes = new LinkedList<>();
        nodes.push(root);
        while (!nodes.isEmpty()) {
            TreeNode top = nodes.poll();
            res.add(top.val);
            if (top.right != null) {
                nodes.push(top.right);
            }
            if (top.left != null) {
                nodes.push(top.left);
            }
        }
        return res;
    }
}

145

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.peek();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                stack.pop();
                prev = root;
                root = null;
            } else {
                root = root.right;
            }
        }
        return res;
    }
}

105

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int index = 0;
        while (index < inorder.length) {
            if (inorder[index] == preorder[0]) {
                break;
            } else {
                index += 1;
            }
        }
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, index + 1), Arrays.copyOfRange(inorder, 0, index));
        root.right = buildTree(Arrays.copyOfRange(preorder, index + 1, preorder.length), Arrays.copyOfRange(inorder, index + 1, inorder.length));
        return root;
    }
}

106

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) {
            return null;
        }
        int rootVal = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootVal);
        int index = 0;
        while (index < inorder.length) {
            if (rootVal == inorder[index]) {
                break;
            } else {
                index += 1;
            }
        }
        root.left = buildTree(Arrays.copyOfRange(inorder, 0, index), Arrays.copyOfRange(postorder, 0, index));
        root.right = buildTree(Arrays.copyOfRange(inorder, index + 1, inorder.length), Arrays.copyOfRange(postorder, index, postorder.length - 1));
        return root;
        
    }
}

889

class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        if (preorder.length == 0) {
            return null;
        }
        if (preorder.length == 1) {
            return new TreeNode (preorder[0]);
        }
        TreeNode root = new TreeNode(preorder[0]);
        int right = postorder[postorder.length - 2];
        int index = 0;
        while (index < preorder.length) {
            if (right == preorder[index]) {
                break; 
            } else {
                index += 1;
            }
        }
        root.right = constructFromPrePost(Arrays.copyOfRange(preorder, index, preorder.length), Arrays.copyOfRange(postorder, index - 1, postorder.length - 1 ));
        root.left = constructFromPrePost(Arrays.copyOfRange(preorder, 1, index), Arrays.copyOfRange(postorder, 0, index - 1));
        return root;
        
    }
}

173

class BSTIterator {
    private List<TreeNode> nodes;
    private Iterator<TreeNode> iter;

    public BSTIterator(TreeNode root) {
        this.nodes = new LinkedList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        while (root != null || !deque.isEmpty()) {
            while (root != null) {
                deque.push(root);
                root = root.left;
            }
            root = deque.pop();
            nodes.add(root);
            root = root.right;
        }
        this.iter = nodes.iterator();
    }
    
    public int next() {
        return iter.next().val;
    }
    
    public boolean hasNext() {
        return iter.hasNext();
    }
}

230

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        TreeNode cur = root;
        Deque<TreeNode> nodes = new LinkedList<>();
        while (cur != null || !nodes.isEmpty()) {
            while (cur != null) {
                nodes.push(cur);
                cur = cur.left;
            }
            cur = nodes.pop();
            k -= 1;
            if (k == 0) {
                break;
            }
            cur = cur.right;
        }
        return cur.val;
    }
}

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode prev = null;
        TreeNode cur = root;
        Deque<TreeNode> nodes = new LinkedList<>();
        while (cur != null || !nodes.isEmpty()) {
            while (cur != null) {
                nodes.push(cur);
                cur = cur.left;
            }
            cur = nodes.pop();
            if ((prev != null) && (prev.val == p.val)) {
                return cur;
            }
            prev = cur;
            cur = cur.right;
        }
        return null;
    }
}

270

// simple inorder traversal: O(n) time, O(n) space
class Solution {
    public int closestValue(TreeNode root, double target) {
        double diff = Integer.MAX_VALUE;
        int val = root.val;
        Deque<TreeNode> nodes = new LinkedList<>();
        while (root != null || !nodes.isEmpty()) {
            while (root != null) {
                nodes.push(root);
                root = root.left;
            }
            root = nodes.pop();
            double curDiff = Math.abs(root.val - target);
            if (curDiff < diff) {
                diff = curDiff;
                val = root.val;
            }
            root = root.right;
        }
        return val;
    }
}

// a pruning version: time O(index), space O(n)
class Solution {
    public int closestValue(TreeNode root, double target) {
        int prev = Integer.MIN_VALUE;
        TreeNode cur = root;
        Deque<TreeNode> nodes = new LinkedList<>();
        while (cur != null || !nodes.isEmpty()) {
            while (cur != null) {
                nodes.push(cur);
                cur = cur.left;
            }
            cur = nodes.pop();
            if (prev <= target && target <= cur.val) {
                return Math.abs(prev - target) < Math.abs(cur.val - target) ? prev : cur.val;
            }
            prev = cur.val;
            cur = cur.right;
        }
        // if target is larger than all nodes, the prev becomes the larget one, just return it
        return prev;
    }
}
// binary search like: time O(logn), space O(1)
class Solution {
    public int closestValue(TreeNode root, double target) {
        int val, closest = root.val;
        while (root != null) {
        val = root.val;
        closest = Math.abs(val - target) < Math.abs(closest - target) ? val : closest;
        root =  target < root.val ? root.left : root.right;
        }
        return closest;
    }
}

272

// inorder traversal + linear search
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> vals = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            vals.add(cur.val);
            cur = cur.right;
        }
        int index = 0;
        for (index = 0; index < vals.size(); index++) {
            if (vals.get(index) >= target) {
                break;
            }
        }
        List<Integer> res = new ArrayList<>();
        int lo = index - 1;
        int hi = index;
        while (lo >= 0 && hi < vals.size() && k > 0) {
            int v1 = vals.get(lo);
            int v2 = vals.get(hi);
            if (target - v1 <= v2 - target) {
                res.add(v1);
                lo -= 1;
            } else {
                res.add(v2);
                hi += 1;
            }
            k -= 1;
        }
        while (k > 0 && lo >= 0) {
            res.add(vals.get(lo));
            lo -= 1;
            k -= 1;
        }
        while (k > 0 && hi < vals.size()) {
            res.add(vals.get(hi));
            hi += 1;
            k -= 1;
        }
        return res;
    }
}

// linear traversal + queue  
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        Queue<Integer> tmp = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null ||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (tmp.size() == k) {
                if (Math.abs(tmp.peek() - target) >= Math.abs(cur.val - target)) {
                    tmp.poll();
                    tmp.offer(cur.val);
                } else {
                    // the rest of the tree is larger than cur.val, and the distance will be increasing
                    break;
                }
            } else {
                tmp.offer(cur.val);
            }
            cur = cur.right;
        }
        return new ArrayList<Integer>(tmp);
    }
}

510

class Solution {
    public Node inorderSuccessor(Node node) {
    if (node.right != null) {
        Node tmp = node.right;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        return tmp; 
    } else {
        Node tmp = node;
        while (tmp.parent != null && tmp == tmp.parent.right) {
            tmp = tmp.parent;
        }
        return tmp.parent;
    }
    }
}

Lint-915

public class Solution {
    public TreeNode inorderPredecessor(TreeNode root, TreeNode p) {
        TreeNode prev = null;
        TreeNode cur = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (cur == p) {
                return prev;
            } else {
                prev = cur;
                cur = cur.right;
            }
        }
        return prev;
    }
}

98

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 数据可以取到Integer.MIN_VALUE,所以这里使用long
        long prev = Long.MIN_VALUE;
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode curNode = root;
        while (curNode != null || !stack.isEmpty()) {
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.pop();
            if (prev >= curNode.val) {
                return false;
            }
            prev = curNode.val;
            curNode = curNode.right;
        } 
        return true;
    }
}


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

    private boolean validateHelper(TreeNode root, long lo, long hi) {
        if (root == null) {
            return true;
        }
        if (root.val <= lo || root.val >= hi) {
            return false;
        }
        return helper(root.left, lo, root.val) && helper(root.right, root.val, hi);
    }
}

100

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

101

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root, root);
    }

    private boolean isSymmetric(TreeNode p, TreeNode q) {
        // both null
        if (p == null && q == null) {
            return true;
        }
        // exactly one is null
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
    }
}

110

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

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

111

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        if (root.left == null) {
            return 1 + minDepth(root.right);
        }
        
        if (root.right == null) {
            return 1 + minDepth(root.left);
        }

        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }
}

104

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

333

class Solution {
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (isBST(root)) {
            return amount(root);
        }
        return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
    }

    private int amount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + amount(root.left) + amount(root.right);
    }

    private boolean isBST(TreeNode root) {
        return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean isBST(TreeNode root, int lo, int hi) {
        if (root == null) {
            return true;
        }
        if (root.val <= lo || root.val >= hi) {
            return false;
        }
        return isBST(root.left, lo, root.val) && isBST(root.right, root.val, hi);
    }
}

112

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return hasPath(root, targetSum, 0);
    }

    private boolean hasPath(TreeNode root, int target, int cur) {
        if (root == null) {
        return false;
        }
        if (root.left == null && root.right == null) {
            return cur + root.val == target;
        }
        return hasPath(root.left, target, cur + root.val) || hasPath(root.right, target, cur + root.val);
    }
}

113

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> paths = new ArrayList<>();
        findPath(root, targetSum, new ArrayList<Integer>(), paths);
        return paths;
    }

    public void findPath(TreeNode root, int sum, List<Integer> current, List<List<Integer>> paths) {
        if (root == null) {
            return;
        }
        current.add(root.val);
        if (root.left == null && root.right == null && root.val == sum) {
            paths.add(current);
            return;
        }
        // You need to pass separate lists to recursive calls, i.e. new ArrayList<>(current)
        findPath(root.left, sum - root.val, new ArrayList<>(current), paths);
        findPath(root.right, sum - root.val, new ArrayList<>(current), paths);
    }
}

// use field
class Solution {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return ret;
    }

    public void dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        path.pollLast();
    }
}

124

class Solution {
    public int maxPathSum(TreeNode root) {
        int[] res = new int[] {root.val};
        calculate(root, res);
        return res[0];
    }

    public int calculate(TreeNode root, int[] res) {
        if (root == null) {
            return 0;
        }
        int left = Math.max(0, calculate(root.left, res));
        int right = Math.max(0, calculate(root.right, res));
        // this is the larget path sum that includes the current node or passes below the current node
        res[0] = Math.max(res[0], root.val + left + right);
        // the returned value is the contribution of the current node, so it should contain the root.val
        return root.val + Math.max(left, right);
    }
}

298

class Solution {
    public int longestConsecutive(TreeNode root) {
        int[] res = new int[] {1};
        calculate(root, res);
        return res[0];
    }

    public int calculate(TreeNode root, int[] res) {
        if (root == null) {
            return 0;
        }
        int left = calculate(root.left, res);
        int right = calculate(root.right, res);
        if (root.left != null && root.val + 1 == root.left.val) {
            left += 1;
        } else {
            left = 1;
        }
        if (root.right != null && root.val + 1 == root.right.val) {
            right += 1;
        } else {
            right = 1;
        }
        res[0] = Math.max(res[0], Math.max(left, right));
        return Math.max(left, right);
    }
}

549

class Solution {
    private int len;

    public int longestConsecutive(TreeNode root) {
        calc(root);
        return len;
    }

    private int[] calc(TreeNode root) {
        if (root == null) {
            return new int[] {0, 0};
        }
        int[] res = new int[] {1, 1};
        int[] left = calc(root.left);
        int[] right = calc(root.right);

        if (root.left != null) {
            if (root.left.val == root.val + 1) {
                res[0] = Math.max(res[0], left[0] + 1);
            } else if (root.left.val == root.val - 1) {
                res[1] = Math.max(res[1], left[1] + 1);
            }
        } 

        if (root.right != null) {
            if (root.right.val == root.val + 1) {
                res[0] = Math.max(res[0], right[0] + 1);
            } else if (root.right.val == root.val - 1) {
                res[1] = Math.max(res[1], right[1] + 1);
            }
        }
        len = Math.max(len, res[0] + res[1] - 1);
        return res;
    }
}

236

// simple approach, O(n^2)
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.left != null && inside(root.left, p) && inside(root.left, q)) {
            return lowestCommonAncestor(root.left, p ,q);
        }
        if (root.right != null && inside(root.right, p) && inside(root.right, q)) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }

    public boolean inside(TreeNode root, TreeNode p) {
        if (root == null) {
            return false;
        }
        if (root.val == p.val) {
            return true;
        }
        return inside(root.left, p) ||inside(root.right, p);
    }
}

// time complexity O(n)
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }
}

199

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        List<Integer> res = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            int n = que.size();
            for (int i = 0; i < n; i++) {
                TreeNode tmp = que.poll();
                if (i == n - 1) {
                    res.add(tmp.val);
                }
                if (tmp.left != null) {
                    que.offer(tmp.left);
                }
                if (tmp.right != null) {
                    que.offer(tmp.right);
                }
            }
        }
        return res;
    }
}

513

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int val = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode tmp = queue.poll();
                if (i == 0) {
                    val = tmp.val;
                }
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                }
            }
        } 
        return val;
    }
}

331

class Solution {
    public boolean isValidSerialization(String preorder) {
        int in = 0;
        int out = 0;
        String[] tmp = preorder.split(",");
        if (tmp.length == 1 && "#".equals(tmp[0])) {
            return true;
        }
        for (int i = 0; i < tmp.length; i++) {
            if (i == 0) {
                if ("#".equals(tmp[0])) {
                    return false;
                }
                out += 2;
            } else if ("#".equals(tmp[i])) {
                in += 1;
            } else {
                in += 1;
                out += 2;
            }
            if (i < tmp.length - 1 && in >= out) {
                return false;
            }
        }
        return in == out;
    }
}

449

// preOrder
public class Codec {

    public String serialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<Integer> tmp = new ArrayList<>();
        preOrder(root, tmp);
        String res = tmp.toString();
        return res.substring(1, res.length() - 1);
    }

    public void preOrder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preOrder(root.left, res);
        preOrder(root.right, res);
    }

    public TreeNode deserialize(String data) {
        if (data == null) {
            return null;
        }
        String[] tmp = data.split(", ");
        return construct(0, tmp.length - 1, tmp);
        
    }

    public TreeNode construct(int lo, int hi, String[] tmp) {
        if (lo > hi) {
            return null;
        }
        int val = Integer.parseInt(tmp[lo]);
        TreeNode root = new TreeNode(val);
        int j = lo + 1;
        while (j <= hi && Integer.parseInt(tmp[j]) <= val) {
            j += 1;
        }
        root.left = construct(lo + 1, j - 1, tmp);
        root.right = construct(j, hi, tmp);
        return root;
    }
}

// postOrder
public class Codec {

    public String serialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<Integer> list = new ArrayList<>();
        postOrder(root, list);
        String tmp = list.toString();
        return tmp.substring(1, tmp.length() - 1);

    }

    public void postOrder(TreeNode root, List<Integer> tmp) {
        if (root == null) {
            return;
        }
        postOrder(root.left, tmp);
        postOrder(root.right, tmp);
        tmp.add(root.val);
    }

    public TreeNode deserialize(String data) {
        if (data == null) {
            return null;
        }
        String[] list = data.split(", ");
        TreeNode root = construct(0, list.length - 1, list);
        return root;
    }

    public TreeNode construct(int lo, int hi, String[] list) {
        if (lo > hi) {
            return null;
        }
        int val = Integer.parseInt(list[hi]);
        TreeNode root = new TreeNode(val);
        int j = lo;
        while (j < hi && Integer.parseInt(list[j]) < val) {
            j += 1;
        }
        root.left = construct(lo, j - 1, list);
        root.right = construct(j, hi - 1, list);
        return root;
    }
}

114

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        List<TreeNode> list = new ArrayList<>();
        preOrder(root, list);
        for (int i = 0; i < list.size(); i++) {
            TreeNode node = list.get(i);
            node.left = null;
            if (i < list.size() - 1) {
                node.right = list.get(i + 1);
            }
        }
    }

    public void preOrder(TreeNode root, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        list.add(root);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }
}

442

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0 ; i < nums.length; i++) {
            int val = Math.abs(nums[i]);
            if (nums[val - 1] < 0) {
                res.add(val);
            }
            nums[val - 1] = - nums[val - 1]; 
        }
        return res;
    }
}

48

class Solution {
    public void rotate(int[][] matrix) {
        int nrow = matrix.length;
        int ncol = matrix[0].length;
        for (int i = 0; i < nrow; i++) {
            for (int j = 0; j < ncol / 2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][ncol - 1 - j];
                matrix[i][ncol - 1 - j] = tmp;
            }
        }
        for (int i = 0; i < nrow - 1; i++) {
            for (int j = 0; j + i < ncol - 1; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[nrow - 1 - j][ncol - 1 - i];
                matrix[nrow - 1 - j][ncol - 1 - i] = tmp;
            }
        }
    }
}

54

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int[] tl = new int[] {0, 0};
        int[] br = new int[] {matrix.length - 1, matrix[0].length - 1};
        int n = matrix.length * matrix[0].length;
        int size = 0;
        while (size < n) {
            for (int i = tl[1]; i <= br[1] && size < n; i++) {
                res.add(matrix[tl[0]][i]);
                size += 1;
            }
            for (int i = tl[0] + 1; i < br[0] && size < n; i++) {
                res.add(matrix[i][br[1]]);
                size += 1;
            }
            for (int i = br[1]; i >= tl[1] && size < n; i--) {
                res.add(matrix[br[0]][i]);
                size += 1;
            }
            for (int i = br[0] - 1; i > tl[0] && size < n; i--) {
                res.add(matrix[i][tl[1]]);
                size += 1;
            }
            tl[0] += 1;
            tl[1] += 1;
            br[0] -= 1;
            br[1] -= 1;
        }
        return res;
    }
}

73

// space complexity: O(m + n)
class Solution {
    public void setZeroes(int[][] matrix) {
        Set<Integer> rows = new HashSet<>();
        Set<Integer> cols = new HashSet<>();
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rows.contains(i) || cols.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

// space complexity: O(1)
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRow = false;
        boolean firstCol = false;
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == 0) {
                firstRow = true;
                break;
            }
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstCol = true;
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (firstCol) {
            for (int i = 0 ; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (firstRow) {
            for (int i = 0; i < n; i ++) {
                matrix[0][i] = 0;
            }
        }
    }
}

289

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[] states = new int[] {-1, 0, 1};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int cnt = 0;
                for (int a = 0; a < 3; a++) {
                    for (int b = 0; b < 3; b++) {
                        int newX = i + states[a];
                        int newY = j + states[b];
                        if(valid(newX, newY, m, n) && (newX != i || newY != j)) {
                            if (board[newX][newY] == 1 || board[newX][newY] == -2) {
                                cnt += 1;
                            }
                        }
                    }
                }
                if (board[i][j] == 0 && cnt == 3) {
                    board[i][j] = -1;
                } else if (board[i][j] == 1 && (cnt <2 || cnt > 3)) {
                    board[i][j] = -2;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == -1) {
                    board[i][j] = 1;
                }
                if (board[i][j] == -2) {
                    board[i][j] = 0;
                }
            }
        }
    }

    public boolean valid(int x, int y, int m, int n) {
        if (x < 0 || x >= m || y < 0 || y >= n) {
            return false;
        }
        return true;
    }
}

6

class Solution {
    public String convert(String s, int numRows) {
    if (numRows < 2) {
        return s;
    }
    StringBuilder[] builders = new StringBuilder[numRows];
    for (int i = 0; i < numRows; i++) {
        builders[i] = new StringBuilder();
    }
    // use row to indicate the current row
    int row = 0;
    // use up to indicate the direction, 1 means down, -1 means up
    // because we need to change direction when row = 0 or row = numRows - 1
    // the initial value of up should be -1
    int up = -1;
    for (int i = 0; i < s.length(); i++) {
        if (row == 0 || row == numRows - 1) {
            up = -up;
        }
        builders[row].append(s.charAt(i));
        row += up;
    }
    StringBuilder resBuilder = new StringBuilder();
    for (StringBuilder builder: builders) {
        resBuilder.append(builder);
    }
    return resBuilder.toString();
    }
}

Insertion mark

1119

class Solution {
    public String removeVowels(String s) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (!isVowel(s.charAt(i))) {
                builder.append(s.charAt(i));
            }
        }
        return builder.toString();
    }

    public boolean isVowel(char ch) {
        return "aeiou".indexOf(ch) >= 0;
    }
}

344

class Solution {
    public void reverseString(char[] s) {
        for (int i = 0; i < s.length / 2; i ++) {
            char tmp = s[i];
            s[i] = s[s.length - 1 - i];
            s[s.length - 1 - i] = tmp;
        }
    }
}