- 2020-07-16
- 1358. Number of Substrings Containing All Three Characters
- 285. Inorder Successor in BST
- 510. Inorder Successor in BST II
- 1143. Longest Common Subsequence
- 494. Target Sum
- 1375. Bulb Switcher III
- 871. Minimum Number of Refueling Stops
- 628. Maximum Product of Three Numbers
- 1095. Find in Mountain Array

- 2020-07-17
- 2020-07-19
- 2020-07-20
- 2020-07-21
- 2020-07-22
- 2020-07-23
- 2020-07-24
- 2020-07-25
- 2020-07-26
- 2020-07-27
- 2020-07-28
- 2020-07-29
- 2020-07-30
- 2020-07-31

# 2020-07-16

## 1358. Number of Substrings Containing All Three Characters

### Description

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

```
Example 1:
Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).
Example 2:
Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".
Example 3:
Input: s = "abc"
Output: 1
```

### Solution

```
class Solution {
public int numberOfSubstrings(String s) {
int[] count = new int[3];
int res = 0;
int i = 0;
char[] strArr = s.toCharArray();
for (int j = 0; j < strArr.length; j++) {
count[strArr[j] - 'a']++;
while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
count[strArr[i++] - 'a']--;
}
//For left in range [0, i - 1], all substring A[left]-A[right] work.
res += i;
}
return res;
}
}
```

## 285. Inorder Successor in BST

### Description

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

The successor of a node p is the node with the smallest key greater than p.val.

```
Example 1:
Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.
Example 2:
Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.
Note:
If the given node has no in-order successor in the tree, return null.
It's guaranteed that the values of the tree are unique.
```

### Solution

```
import java.util.Stack;
/**
inorder successor is minimum value(leftmost value) in it's right subbtree
or if right subtree doesn't exist, it will be first left node from current node till root
*/
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode succ = null;
//try to find the min value which is larger than p.
while (root != null) {
if (p.val < root.val) {
succ = root;
root = root.left;
} else {
root = root.right;
}
}
return succ;
}
}
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
// inorder successor is minimum value(leftmost value) in it's right subbtree
// or if right subtree doesn't exist, it will be first left node from current node
// till root
// CASE 1: node has right subtree
if (p.right != null) {
TreeNode successor = p.right;
while(successor.left != null) successor = successor.left;
return successor;
}
TreeNode ancestor = root;
TreeNode successor = null;
while(ancestor != null) {
if (p.val < ancestor.val) {
// p is in left subtree
successor = ancestor;
ancestor = ancestor.left;
} else {
// p is in right subtree
ancestor = ancestor.right;
}
}
return successor;
}
```

## 510. Inorder Successor in BST II

### Description

Given a node in a binary search tree, find the in-order successor of that node in the BST.

If that node has no in-order successor, return null.

The successor of a node is the node with the smallest key greater than node.val.

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node. Below is the definition for Node:

```
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}
```

Follow up:

Could you solve it without looking up any of the node’s values?

```
Example 1:
```

```
Input: tree = [2,1,3], node = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both the node and the return value is of Node type.
Example 2:
```

```
Input: tree = [5,3,6,2,4,null,null,1], node = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.
Example 3:
```

```
Input: tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 15
Output: 17
Example 4:
```

```
Input: tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 13
Output: 15
Example 5:
Input: tree = [0], node = 0
Output: null
Constraints:
-10^5 <= Node.val <= 10^5
1 <= Number of Nodes <= 10^4
All Nodes will have unique values.
```

### Solution

```
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
};
*/
class Solution {
public Node inorderSuccessor(Node node) {
if(node==null){
return null;
}
if(node.right!=null){
Node temp = node.right;
while(temp!=null && temp.left!=null){
temp = temp.left;
}
return temp;
}
Node temp = node;
//only when cur is left subtree of parent.
while(temp.parent!=null && temp.parent.left!=temp){
temp = temp.parent;
}
temp = temp.parent;
return temp;
}
}
```

## 1143. Longest Common Subsequence

### Description

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

```
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
Constraints:
1 <= text1.length <= 1000
1 <= text2.length <= 1000
The input strings consist of lowercase English characters only.
```

### Solution

```
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
//swap so less space was used.
int len1 = text1.length(), len2 = text2.length();
if(len1<len2){
String temp = text2;
text2 = text1;
text1 = temp;
int swap = len1;
len1 = len2;
len2 = swap;
}
//use two arrays instead of int[][] as dp to save space.
int[] dp = new int[len2+1];
int[] pre = null;
for(int i = 1;i<=len1;i++){
pre = Arrays.copyOf(dp,dp.length);
for(int j = 1;j<=len2;j++){
if(text1.charAt(i-1)==text2.charAt(j-1)){
dp[j] = pre[j-1]+1;
}else{
dp[j] = Math.max(pre[j],dp[j-1]);
}
}
}
return dp[len2];
}
}
```

## 494. Target Sum

### Description

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

```
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
```

### Solution

DP Solution using arrays

```
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int i : nums) {
sum += i;
}
if (S > sum || S < -sum) {
return 0;
}
int[] dp = new int[2 * sum + 1];
dp[0 + sum] = 1;
for (int i = 0; i < nums.length; i++) {
int[] next = new int[2 * sum + 1];
for (int k = 0; k < 2 * sum + 1; k++) {
if(dp[k]!=0){
next[k-nums[i]] += dp[k];
next[k+nums[i]] += dp[k];
}
}
dp = next;
}
return dp[sum+S];
}
}
```

Use HashMap to store all previous values.

```
class Solution {
public int findTargetSumWays(int[] nums, int S) {
ConcurrentHashMap<Integer,Integer> set = new ConcurrentHashMap<>();
set.put(0,1);
for(int num:nums){
ConcurrentHashMap<Integer,Integer> temp = new ConcurrentHashMap<>();
for(int n:set.keySet()){
temp.put(n-num,temp.getOrDefault(n-num,0)+set.get(n));
temp.put(n+num,temp.getOrDefault(n+num,0)+set.get(n));
}
set = temp;
}
return set.getOrDefault(S,0);
}
}
```

## 1375. Bulb Switcher III

### Description

There is a room with n bulbs, numbered from 1 to n, arranged in a row from left to right. Initially, all the bulbs are turned off.

At moment k (for k from 0 to n - 1), we turn on the light[k] bulb. A bulb change color to blue only if it is on and all the previous bulbs (to the left) are turned on too.

Return the number of moments in which all turned on bulbs are blue.

```
Example 1:
```

```
Input: light = [2,1,3,5,4]
Output: 3
Explanation: All bulbs turned on, are blue at the moment 1, 2 and 4.
Example 2:
Input: light = [3,2,4,1,5]
Output: 2
Explanation: All bulbs turned on, are blue at the moment 3, and 4 (index-0).
Example 3:
Input: light = [4,1,2,3]
Output: 1
Explanation: All bulbs turned on, are blue at the moment 3 (index-0).
Bulb 4th changes to blue at the moment 3.
Example 4:
Input: light = [2,1,4,3,6,5]
Output: 3
Example 5:
Input: light = [1,2,3,4,5,6]
Output: 6
Constraints:
n == light.length
1 <= n <= 5 * 10^4
light is a permutation of [1, 2, ..., n]
```

### Solution

```
/**
right is the number of the right most lighted bulb.
Iterate the input light A,
update right = max(right, A[i]).
Now we have lighted up i + 1 bulbs,
if right == i + 1,
it means that all the previous bulbs (to the left) are turned on too.
Then we increment res
*/
class Solution {
public int numTimesAllBlue(int[] light) {
int rightMost = 0;
int count = 0;
for(int i=0;i<light.length;i++){
rightMost = Math.max(rightMost,light[i]);
count += rightMost==i+1?1:0;
}
return count;
}
}
```

## 871. Minimum Number of Refueling Stops

### Description

```
A car travels from a starting position to a destination which is target miles east of the starting position.
Along the way, there are gas stations. Each station[i] represents a gas station that is station[i][0] miles east of the starting position, and has station[i][1] liters of gas.
The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses 1 liter of gas per 1 mile that it drives.
When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.
What is the least number of refueling stops the car must make in order to reach its destination? If it cannot reach the destination, return -1.
Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.
Example 1:
Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.
Example 2:
Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can't reach the target (or even the first gas station).
Example 3:
Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation:
We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.
Note:
1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target
```

### Solution

```
/**
dp[t] means the furthest distance that we can get with t times of refueling.
So for every station s[i],
if the current distance dp[t] >= s[i][0], we can refuel:
dp[t + 1] = max(dp[t + 1], dp[t] + s[i][1])
In the end, we'll return the first t with dp[i] >= target,
otherwise we'll return -1.
*/
class Solution {
public int minRefuelStops(int target, int startFuel, int[][] stations) {
long[] dp = new long[stations.length+1];
dp[0] = startFuel;
//for every station
for(int i = 0;i<stations.length;i++){
//try use station as less as possibe
//only when dp[t] can reach the station we can refule, otherwise skip.
for(int t = i;t>=0 && dp[t] >= stations[i][0];t--){
dp[t+1] = Math.max(dp[t+1],dp[t]+stations[i][1]);
}
}
for(int i = 0; i< dp.length;i++){
if(dp[i] >= target){
return i;
}
}
return -1;
}
}
```

## 628. Maximum Product of Three Numbers

### Description

Given an integer array, find three numbers whose product is maximum and output the maximum product.

```
Example 1:
Input: [1,2,3]
Output: 6
Example 2:
Input: [1,2,3,4]
Output: 24
Note:
The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.
```

### Solution

```
class Solution {
public int maximumProduct(int[] nums) {
int min1 =Integer.MAX_VALUE, min2 = Integer.MAX_VALUE, min3 = Integer.MAX_VALUE;
int max1 =Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
int tempMax,tempMin;
//must update 3 then 2 then 1 in order.
for(int num : nums){
//find max/min for three number based on previous two and current number.
if(min2!=Integer.MAX_VALUE && max2!=Integer.MIN_VALUE){
tempMax = max2*num;
tempMin = min2*num;
max3 = Math.max(max3,Math.max(tempMax,tempMin));
min3 = Math.min(min3,Math.min(tempMax,tempMin));
}
//assuming using cur number, see if can reach more than max or less than min.
//based on the smallest number till then.
if(min1!=Integer.MAX_VALUE && max1!=Integer.MIN_VALUE){
tempMax = max1*num;
tempMin = min1*num;
max2 = Math.max(max2,Math.max(tempMax,tempMin));
min2 = Math.min(min2,Math.min(tempMax,tempMin));
}
min1 = Math.min(min1,num);
max1 = Math.max(max1,num);
}
return max3;
}
}
```

## 1095. Find in Mountain Array

### Description

(This problem is an interactive problem.)

```
You may recall that an array A is a mountain array if and only if:
A.length >= 3
There exists some i with 0 < i < A.length - 1 such that:
A[0] < A[1] < ... A[i-1] < A[i]
A[i] > A[i+1] > ... > A[A.length - 1]
Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index doesn't exist, return -1.
You can't access the mountain array directly. You may only access the array using a MountainArray interface:
MountainArray.get(k) returns the element of the array at index k (0-indexed).
MountainArray.length() returns the length of the array.
Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.
Example 1:
Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.
Example 2:
Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.
Constraints:
3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9
```

### Solution

```
/**
* // This is MountainArray's API interface. // You should not implement it, or speculate about its implementation interface MountainArray { public int get(int
* index) {} public int length() {} }
*/
class Solution {
int findInMountainArray(int target, MountainArray A) {
int n = A.length(), l, r, m, peak = 0;
// find index of peak
l = 0;
r = n - 1;
while (l < r) {
m = (l + r) / 2;
if (A.get(m) < A.get(m + 1)) {
l = peak = m + 1;
} else {
r = m;
}
}
// find target in the left of peak
l = 0;
r = peak;
while (l <= r) {
m = (l + r) / 2;
if (A.get(m) < target) {
l = m + 1;
} else if (A.get(m) > target) {
r = m - 1;
} else {
return m;
}
}
// find target in the right of peak
l = peak;
r = n - 1;
while (l <= r) {
m = (l + r) / 2;
if (A.get(m) > target) {
l = m + 1;
} else if (A.get(m) < target) {
r = m - 1;
} else {
return m;
}
}
return -1;
}
}
```

# 2020-07-17

## 1172. Dinner Plate Stacks

### Description

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.

```
Implement the DinnerPlates class:
DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks.
void push(int val) pushes the given positive integer val into the leftmost stack with size less than capacity.
int pop() returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all stacks are empty.
int popAtStack(int index) returns the value at the top of the stack with the given index and removes it from that stack, and returns -1 if the stack with that given index is empty.
Example:
Input:
["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
Output:
[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]
Explanation:
DinnerPlates D = DinnerPlates(2); // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5); // The stacks are now: 2 4
1 3 5
﹈ ﹈ ﹈
D.popAtStack(0); // Returns 2. The stacks are now: 4
1 3 5
﹈ ﹈ ﹈
D.push(20); // The stacks are now: 20 4
1 3 5
﹈ ﹈ ﹈
D.push(21); // The stacks are now: 20 4 21
1 3 5
﹈ ﹈ ﹈
D.popAtStack(0); // Returns 20. The stacks are now: 4 21
1 3 5
﹈ ﹈ ﹈
D.popAtStack(2); // Returns 21. The stacks are now: 4
1 3 5
﹈ ﹈ ﹈
D.pop() // Returns 5. The stacks are now: 4
1 3
﹈ ﹈
D.pop() // Returns 4. The stacks are now: 1 3
﹈ ﹈
D.pop() // Returns 3. The stacks are now: 1
﹈
D.pop() // Returns 1. There are no stacks.
D.pop() // Returns -1. There are still no stacks.
```

### Solution

```
import java.util.*;
class DinnerPlates {
TreeMap<Integer, Deque<Integer>> map;
TreeSet<Integer> avail;
int capacity;
public DinnerPlates(int capacity) {
map = new TreeMap<>();
avail = new TreeSet<>();
this.capacity = capacity;
}
public void push(int val) {
int index = 0;
//if no available stack,, just add one.
if(avail.isEmpty()){
//if map is empty will use index 0.
if(!map.isEmpty()){
index = map.lastKey()+1;
}
avail.add(index);
}else{
index = avail.first();
}
map.putIfAbsent(index,new ArrayDeque<>());
map.get(index).push(val);
//in case the stack is empty.
if(map.get(index).size()==capacity){
avail.remove(index);
}
}
public int pop() {
//nothing to pop();
if(map.isEmpty()){
return -1;
}
return popAtStack(map.lastKey());
}
public int popAtStack(int index) {
if(!map.containsKey(index)){
return -1;
}
//pop the target stack.
int res = map.get(index).pop();
//remove if empty, so we can confirm nothing to pop when map.isEmpty;
if(map.get(index).size()==0){
map.remove(index);
}
//cur stack is definitely available after pop.
avail.add(index);
return res;
}
}
/**
* Your DinnerPlates object will be instantiated and called as such: DinnerPlates obj = new DinnerPlates(capacity); obj.push(val); int param_2 = obj.pop(); int
* param_3 = obj.popAtStack(index);
*/
```

# 2020-07-19

## 427. Construct Quad Tree

### Description

Given a n * n matrix grid of 0’s and 1’s only. We want to represent the grid with a Quad-Tree.

Return the root of the Quad-Tree representing the grid.

Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

```
val: True if the node represents a grid of 1's or False if the node represents a grid of 0's.
isLeaf: True if the node is leaf node on the tree or False if the node has the four children.
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
We can construct a Quad-Tree from a two-dimensional area using the following steps:
```

If the current grid has the same value (i.e all 1’s or all 0’s) set isLeaf True and set val to the value of the grid and set the four children to Null and stop. If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo. Recurse for each of the children with the proper sub-grid.

If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.

Example 1:

```
Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.
```

Example 2:

```
Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:
```

Example 3:

```
Input: grid = [[1,1],[1,1]]
Output: [[1,1]]
Example 4:
Input: grid = [[0]]
Output: [[1,0]]
Example 5:
Input: grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
Output: [[0,1],[1,1],[1,0],[1,0],[1,1]]
Constraints:
1 <= capacity <= 20000
1 <= val <= 20000
0 <= index <= 100000
At most 200000 calls will be made to push, pop, and popAtStack.
```

### Solution

```
class Solution {
public Node construct(int[][] grid) {
int size = grid.length;
return helper(grid, size / 2, size / 2, size);
}
public Node helper(int[][] grid, int i, int j, int size) {
Node res = new Node();
if (size < 2) {
res.val = grid[i][j] == 1;
res.isLeaf = true;
return res;
}
if (size == 2) {
if (grid[i - 1][j - 1] == grid[i][j - 1] &&
grid[i][j - 1] == grid[i - 1][j] &&
grid[i - 1][j] == grid[i][j]) {
res.val = grid[i][j] == 1;
res.isLeaf = true;
return res;
} else {
res.topLeft = new Node((grid[i - 1][j - 1] == 1), true);
res.topRight = new Node((grid[i - 1][j] == 1), true);
res.bottomLeft = new Node((grid[i][j - 1] == 1), true);
res.bottomRight = new Node((grid[i][j] == 1), true);
res.isLeaf = false;
return res;
}
}
size /= 2;
res.isLeaf = false;
res.topLeft = helper(grid, i - size / 2, j - size / 2, size);
res.topRight = helper(grid, i - size / 2, j + size / 2, size);
res.bottomLeft = helper(grid, i + size / 2, j - size / 2, size);
res.bottomRight = helper(grid, i + size / 2, j + size / 2, size);
if (res.topLeft.val == res.topRight.val && res.topRight.val == res.bottomLeft.val && res.bottomLeft.val == res.bottomRight.val
&& res.topLeft.isLeaf
&& res.topRight.isLeaf
&& res.bottomLeft.isLeaf
&& res.bottomRight.isLeaf) {
res.val = res.topLeft.val;
res.isLeaf = true;
res.topLeft = null;
res.topRight = null;
res.bottomLeft = null;
res.bottomRight = null;
}
return res;
}
}
```

## 421. Maximum XOR of Two Numbers in an Array

### Description

```
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:
Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.
```

### Solution

```
import java.util.*;
class Solution {
public int findMaximumXOR(int[] nums) {
int maxResult = 0;
int mask = 0;
/*The maxResult is a record of the largest XOR we got so far. if it's 11100 at i = 2, it means
before we reach the last two bits, 11100 is the biggest XOR we have, and we're going to explore
whether we can get another two '1's and put them into maxResult
This is a greedy part, since we're looking for the largest XOR, we start
from the very begining, aka, the 31st postition of bits. */
for (int i = 31; i >= 0; i--) {
//The mask will grow like 100..000 , 110..000, 111..000, then 1111...111
//for each iteration, we only care about the left parts
mask = mask | (1 << i);
Set<Integer> set = new HashSet<>();
for (int num : nums) {
/* we only care about the left parts, for example, if i = 2, then we have
{1100, 1000, 0100, 0000} from {1110, 1011, 0111, 0010}*/
int leftPartOfNum = num & mask;
set.add(leftPartOfNum);
}
// if i = 1 and before this iteration, the maxResult we have now is 1100,
// my wish is the maxResult will grow to 1110, so I will try to find a candidate
// which can give me the greedyTry;
int greedyTry = maxResult | (1 << i);
for (int leftPartOfNum : set) {
//This is the most tricky part, coming from a fact that if a ^ b = c, then a ^ c = b;
// now we have the 'c', which is greedyTry, and we have the 'a', which is leftPartOfNum
// If we hope the formula a ^ b = c to be valid, then we need the b,
// and to get b, we need a ^ c, if a ^ c exisited in our set, then we're good to go
int anotherNum = leftPartOfNum ^ greedyTry;
if (set.contains(anotherNum)) {
maxResult = greedyTry;
break;
}
}
// If unfortunately, we didn't get the greedyTry, we still have our max,
// So after this iteration, the max will stay at 1100.
}
return maxResult;
}
}
```

## 402. Remove K Digits

### Description

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

```
Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
```

### Solution

```
class Solution {
public String removeKdigits(String num, int k) {
Deque<Character> stack = new ArrayDeque<>();
int len = num.length();
if(len==k){
return "0";
}
int i = 0;
while(i < len){
//if the previous is larger, poll it.
while(k>0 && !stack.isEmpty() && stack.peekFirst() > num.charAt(i)){
stack.pollFirst();
k--;
}
stack.addFirst(num.charAt(i++));
}
//if k is not 0, remove the last digit as it's larger than previous.
while(k>0){
stack.pollFirst();
k--;
}
//remove head 0.
while(!stack.isEmpty() && stack.peekLast()=='0'){
stack.pollLast();
}
//construct the number from the stack
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty())
sb.append(stack.pollLast());
//in case sb is 0.
return sb.length()==0?"0":sb.toString();
}
}
```

## 769. Max Chunks To Make Sorted

### Description

Given an array arr that is a permutation of [0, 1, …, arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

```
Example 1:
Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.
Example 2:
Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.
Note:
arr will have length in range [1, 10].
arr[i] will be a permutation of [0, 1, ..., arr.length - 1].
```

### Solution

```
/**
If the current max so far is equals to the current index
1,0 for index 1 means previous arr can be sorted in range.
*/
class Solution {
public int maxChunksToSorted(int[] arr) {
int maxSoFar = arr[0];
int count = 0;
for (int i = 0; i < arr.length; i++) {
maxSoFar = Math.max(maxSoFar, arr[i]);
if (maxSoFar == i) {
count++;
}
}
return count;
}
}
```

# 2020-07-20

## 187. Repeated DNA Sequences

### Description

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

Example:

Input: s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”

Output: [“AAAAACCCCC”, “CCCCCAAAAA”]

### Solution

```
/**
due to the characteristic, we can see each char, ACGT as a number from 0-3, which can be store using 2 digit.
so hash the current len 10 string to a integer to see if it's duplicated.
*/
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> result = new ArrayList<>();
Set<Integer> word = new HashSet<>();
Set<Integer> secondWord = new HashSet<>();
int[] map = new int[26];
map['C' - 'A'] = 1;
map['G' - 'A'] = 2;
map['T' - 'A'] = 3;
int value = 0;
for (int i = 0; i < s.length(); i++) {
value <<= 2;
value |= map[s.charAt(i) - 'A'];
//mask, so the last 20 digit will be 1 and others will be 0.
//so only the last 20 digit was compared.
value &= 0xfffff;
if (i < 9) {
continue;
}
if (!word.add(value) && secondWord.add(value)) {
result.add(s.substring(i - 9, i + 1));
}
}
return result;
}
}
```

## 1029. Two City Scheduling

### Description

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

```
Example 1:
Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110
Explanation:
The first person goes to city A for a cost of 10.
The second person goes to city A for a cost of 30.
The third person goes to city B for a cost of 50.
The fourth person goes to city B for a cost of 20.
The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.
Note:
1 <= costs.length <= 100
It is guaranteed that costs.length is even.
1 <= costs[i][0], costs[i][1] <= 1000
```

### Solution

```
/**
First buy everyone a ticket to A
then count for everyone if arrange it to B, how much it can refund.
Find the max refund, then the cost would be minimum.
*/
class Solution {
public int twoCitySchedCost(int[][] costs) {
int len = costs.length;
int sum = 0;
int[] refund = new int[len];
for(int i = 0;i<len;i++){
sum += costs[i][0];
//if arrange i to B, how much we can get back.
refund[i] = costs[i][1] - costs[i][0];
}
Arrays.sort(refund);
for (int i = 0; i < costs.length / 2; i++) {
sum += refund[i];
}
return sum;
}
}
```

## 201. Bitwise AND of Numbers Range

### Description

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

```
Example 1:
Input: [5,7]
Output: 4
Example 2:
Input: [0,1]
Output: 0
```

### Solution

```
/**
The idea is very simple:
last bit of (odd number & even number) is 0.
when m != n, There is at least an odd number and an even number, so the last bit position result is 0.
Move m and n rigth a position.
Keep doing step 1,2,3 until m equal to n, use a factor to record the iteration time.
*/
class Solution {
public int rangeBitwiseAnd(int m, int n) {
if(m==0){
return 0;
}
int i = 0;
while(m!=n){
m>>=1;
n>>=1;
i++;
}
return m<<i;
}
}
```

## 1353. Maximum Number of Events That Can Be Attended

### Description

Given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.

You can attend an event i at any day d where startTimei <= d <= endTimei. Notice that you can only attend one event at any time d.

Return the maximum number of events you can attend.

Example 1:

```
Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.
Example 2:
Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4
Example 3:
Input: events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
Output: 4
Example 4:
Input: events = [[1,100000]]
Output: 1
Example 5:
Input: events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
Output: 7
Constraints:
1 <= events.length <= 10^5
events[i].length == 2
1 <= events[i][0] <= events[i][1] <= 10^5
```

### Solution

```
/**
Greedy find the event that start earliest.
*/
class Solution {
public int maxEvents(int[][] events) {
if (events.length == 0) {
return 0;
}
int n = events.length;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
Arrays.sort(events, (a, b) -> (a[0] - b[0]));
int maxDay = Arrays.stream(events).mapToInt(a -> a[1]).max().getAsInt();
int count = 0;
int i = 0;
for (int d = 1; d <= maxDay; d++) {
// Add new events that can attend on day `d`
while (i < n && events[i][0] == d) {
pq.offer(events[i++][1]);
}
// Remove events that are already closed
while (!pq.isEmpty() && pq.peek() < d) {
pq.poll();
}
// Use day `d` to attend to the event that closes earlier
if (!pq.isEmpty()) {
count++;
pq.poll();
}
}
return count;
}
}
```

## 496. Next Greater Element I

### Description

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

```
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Note:
All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.
```

### Solution

```
/**
Use stack to store the previous number, once found a greater one, push all previous number that is less that it.
and put into a map so can look up.
*/
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> index = new HashMap<>();
ArrayDeque<Integer> stack = new ArrayDeque<>();
for(int num:nums2){
while(!stack.isEmpty() && stack.peek()<num){
index.put(stack.pop(),num);
}
stack.push(num);
}
int[] res = new int[nums1.length];
for(int i = 0;i<nums1.length;i++){
res[i] = index.getOrDefault(nums1[i],-1);
}
return res;
}
}
```

## 503. Next Greater Element II

### Description

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number.

```
Example 1:
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2;
The number 2 can't find next greater number;
The second 1's next greater number needs to search circularly, which is also 2.
Note: The length of given array won't exceed 10000.
```

### Solution

```
import java.util.*;
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] next = new int[n];
Arrays.fill(next, -1);
ArrayDeque<Integer> stack = new ArrayDeque<>();
// index stack
for (int i = 0; i < n * 2; i++) {
int num = nums[i % n];
while (!stack.isEmpty() && nums[stack.peek()] < num) {
next[stack.pop()] = num;
}
//only when i is in the original array is i need to push to stack.
if (i < n) {
stack.push(i);
}
}
return next;
}
}
```

## 1088. Confusing Number II

### Description

We can rotate digits by 180 degrees to form new digits. When 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6 respectively. When 2, 3, 4, 5 and 7 are rotated 180 degrees, they become invalid.

A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.(Note that the rotated number can be greater than the original number.)

Given a positive integer N, return the number of confusing numbers between 1 and N inclusive.

```
Example 1:
Input: 20
Output: 6
Explanation:
The confusing numbers are [6,9,10,16,18,19].
6 converts to 9.
9 converts to 6.
10 converts to 01 which is just 1.
16 converts to 91.
18 converts to 81.
19 converts to 61.
Example 2:
Input: 100
Output: 19
Explanation:
The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].
Note:
1 <= N <= 10^9
```

### Solution

```
class Solution {
Map<Integer, Integer> map;
int N;
int res;
public int confusingNumberII(int N) {
map = new HashMap<>();
map.put(0, 0);
map.put(1, 1);
map.put(6, 9);
map.put(8, 8);
map.put(9, 6);
res = 0;
//1^9 itself is a confising number, but we only count number has less than 9 digits.
if (N == 1000000000) {
res++;
N--;
}
this.N = N;
search(0, 0);
return res;
}
private void search(int p, int cur) {
//not to continue with number larger than 1^9.
if (p > 9 || cur > N) {
return;
}
if (isConfusing(cur)) {
res++;
}
//no matter if it's confusing we all need to continue.
//as 1 is not confusing but 16 and 19 is.
for (Integer d : map.keySet()) {
//00 is not an option.
if (p == 0 && d == 0) {
continue;
}
//add new potential digit to last position.
search(p + 1, cur * 10 + d);
}
}
private boolean isConfusing(int n) {
long rot = 0;
int tmp = n;
while (n > 0) {
rot = rot * 10 + map.get(n % 10);
n /= 10;
}
//after rotate, the number should not equal to itslef.
return rot != tmp;
}
}
```

## 886. Possible Bipartition

### Description

Given a set of N people (numbered 1, 2, …, N), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.

Return true if and only if it is possible to split everyone into two groups in this way.

```
Example 1:
Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]
Example 2:
Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Example 3:
Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false
Constraints:
1 <= N <= 2000
0 <= dislikes.length <= 10000
dislikes[i].length == 2
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].
```

### Solution

```
class Solution {
public boolean possibleBipartition(int N, int[][] dislikes) {
int[] color = new int[N+1];
HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
for(int i = 1;i<=N;i++){
graph.put(i,new HashSet<>());
}
for(int[] edge:dislikes){
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
for(int i = 1;i<=N;i++){
if(color[i]==0){
color[i] = 1;
if(!dfs(i,graph,color)){
return false;
}
}
}
return true;
}
public boolean dfs(int node, HashMap<Integer, HashSet<Integer>> graph, int[] color){
boolean res = true;
for(int neighbor:graph.get(node)){
if(color[neighbor]!=0){
if(color[neighbor]==color[node]){
return false;
}
}else{
color[neighbor] = -color[node];
res &= dfs(neighbor,graph,color);
}
}
return res;
}
}
```

## 1274. Number of Ships in a Rectangle

### Description

(This problem is an interactive problem.)

On the sea represented by a cartesian plane, each ship is located at an integer point, and each integer point may contain at most 1 ship.

You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true if and only if there is at least one ship in the rectangle represented by the two points, including on the boundary.

Given two points, which are the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle. It is guaranteed that there are at most 10 ships in that rectangle.

Submissions making more than 400 calls to hasShips will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example :

```
Input:
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.
Constraints:
On the input ships is only given to initialize the map internally. You must solve this problem "blindfolded". In other words, you must find the answer using the given hasShips API, without knowing the ships position.
0 <= bottomLeft[0] <= topRight[0] <= 1000
0 <= bottomLeft[1] <= topRight[1] <= 1000
```

### Solution

```
class Solution {
public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
if (!sea.hasShips(topRight, bottomLeft)) return 0;
if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1]) return 1;
int midX = (topRight[0] + bottomLeft[0])/2;
int midY = (topRight[1] + bottomLeft[1])/2;
//need to take care of the boundaries so no dup.
return countShips(sea, new int[]{midX, midY}, bottomLeft) +
countShips(sea, topRight, new int[]{midX+1, midY+1}) +
countShips(sea, new int[]{midX, topRight[1]}, new int[]{bottomLeft[0], midY+1}) +
countShips(sea, new int[]{topRight[0], midY}, new int[]{midX+1, bottomLeft[1]});
}
}
```

# 2020-07-21

## 1244. Design A Leaderboard

### Description

```
Design a Leaderboard class, which has 3 functions:
addScore(playerId, score): Update the leaderboard by adding score to the given player's score. If there is no player with such id in the leaderboard, add him to the leaderboard with the given score.
top(K): Return the score sum of the top K players.
reset(playerId): Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.
Initially, the leaderboard is empty.
Example 1:
Input:
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output:
[null,null,null,null,null,null,73,null,null,null,141]
Explanation:
Leaderboard leaderboard = new Leaderboard ();
leaderboard.addScore(1,73); // leaderboard = [[1,73]];
leaderboard.addScore(2,56); // leaderboard = [[1,73],[2,56]];
leaderboard.addScore(3,39); // leaderboard = [[1,73],[2,56],[3,39]];
leaderboard.addScore(4,51); // leaderboard = [[1,73],[2,56],[3,39],[4,51]];
leaderboard.addScore(5,4); // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]];
leaderboard.top(1); // returns 73;
leaderboard.reset(1); // leaderboard = [[2,56],[3,39],[4,51],[5,4]];
leaderboard.reset(2); // leaderboard = [[3,39],[4,51],[5,4]];
leaderboard.addScore(2,51); // leaderboard = [[2,51],[3,39],[4,51],[5,4]];
leaderboard.top(3); // returns 141 = 51 + 51 + 39;
Constraints:
1 <= playerId, K <= 10000
It's guaranteed that K is less than or equal to the current number of players.
1 <= score <= 100
There will be at most 1000 function calls.
```

### Solution

```
/**
Use two Treemap to store player to score and score to players.
*/
class Leaderboard {
TreeMap<Integer, Integer> player2score;
TreeMap<Integer, HashSet<Integer>> score2player;
public Leaderboard() {
player2score = new TreeMap<>();
score2player = new TreeMap<>();
}
public void addScore(int playerId, int score) {
int orig = player2score.getOrDefault(playerId, 0);
player2score.put(playerId, orig + score);
if (orig != 0) {
score2player.get(orig).remove(playerId);
}
score2player.putIfAbsent(orig + score, new HashSet<>());
score2player.get(orig + score).add(playerId);
}
public int top(int K) {
int sum = 0;
Integer key = score2player.lastKey();
while (K > 0) {
HashSet<Integer> temp = score2player.get(key);
if (K >= temp.size()) {
sum += key * temp.size();
K -= temp.size();
} else {
sum += key * K;
K = 0;
}
key = score2player.floorKey(key - 1);
if(key==null){
break;
}
}
return sum;
}
public void reset(int playerId) {
if (!player2score.containsKey(playerId)) {
return;
}
int orig = player2score.get(playerId);
player2score.remove(playerId);
score2player.get(orig).remove(playerId);
}
}
```

## 734. Sentence Similarity

### Description

```
Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.
For example, "great acting skills" and "fine drama talent" are similar, if the similar word pairs are pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]].
Note that the similarity relation is not transitive. For example, if "great" and "fine" are similar, and "fine" and "good" are similar, "great" and "good" are not necessarily similar.
However, similarity is symmetric. For example, "great" and "fine" being similar is the same as "fine" and "great" being similar.
Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.
Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].
Note:
The length of words1 and words2 will not exceed 1000.
The length of pairs will not exceed 2000.
The length of each pairs[i] will be 2.
The length of each words[i] and pairs[i][j] will be in the range [1, 20].
```

### Solution

```
/**
Use HashSet to store all possible transitions, there might be multiples like meal->dinner, meal -> supper
so a map would not work
*/
class Solution {
public boolean areSentencesSimilar(String[] words1, String[] words2, List<List<String>> pairs) {
if (words1.length != words2.length) {
return false;
}
HashSet<String> set = new HashSet<>();
for (List<String> pair : pairs) {
set.add(pair.get(0)+"->"+pair.get(1));
set.add(pair.get(1)+"->"+pair.get(0));
}
for (int i = 0; i < words1.length; i++) {
if(!words2[i].equals(words1[i]) && !set.contains(words1[i]+"->"+words2[i])){
return false;
}
}
return true;
}
}
```

### Description

```
Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.
For example, words1 = ["great", "acting", "skills"] and words2 = ["fine", "drama", "talent"] are similar, if the similar word pairs are pairs = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]].
Note that the similarity relation is transitive. For example, if "great" and "good" are similar, and "fine" and "good" are similar, then "great" and "fine" are similar.
Similarity is also symmetric. For example, "great" and "fine" being similar is the same as "fine" and "great" being similar.
Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.
Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].
Note:
The length of words1 and words2 will not exceed 1000.
The length of pairs will not exceed 2000.
The length of each pairs[i] will be 2.
The length of each words[i] and pairs[i][j] will be in the range [1, 20].
```

### Solution

```
/**
Use union to find a group of words with similar meaning.
*/
class Solution {
public boolean areSentencesSimilarTwo(String[] words1, String[] words2, List<List<String>> pairs) {
if(words1.length != words2.length){
return false;
}
HashMap<String, String> parent = new HashMap<>();
for(List<String> pair:pairs){
union(pair.get(0),pair.get(1),parent);
}
for(int i = 0;i<words1.length;i++){
if(!findParent(words1[i],parent).equals(findParent(words2[i],parent))){
return false;
}
}
return true;
}
public String findParent(String word, HashMap<String, String> parent) {
parent.putIfAbsent(word,word);
if (!parent.get(word).equals(word)) {
parent.put(word, findParent(parent.get(word), parent));
}
return parent.get(word);
}
public void union(String word1, String word2, HashMap<String, String> parent){
String p1 = findParent(word1,parent);
String p2 = findParent(word2,parent);
if(!p1.equals(p2)){
parent.put(p1,p2);
}
}
}
```

## 1405. Longest Happy String

### Description

```
A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a substring.
Given three integers a, b and c, return any string s, which satisfies following conditions:
s is happy and longest possible.
s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
s will only contain 'a', 'b' and 'c' letters.
If there is no such string s return the empty string "".
Example 1:
Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.
Example 2:
Input: a = 2, b = 2, c = 1
Output: "aabbc"
Example 3:
Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.
Constraints:
0 <= a, b, c <= 100
a + b + c > 0
```

### Solution

```
/**
greedy way to construct the string.
For the letter has the max count, we greedily take 2 chars.
But for the letter didn't has the max count, we just take 1 char.
The reason is, the letter with less count, would be used as delimiter. To have the longest happy string, we want to greedily do two things.
* Use as many as possible chars which has the max count.
* To achieve 1, we need to have as many as much delimiter.
For each loop, after appending the letters to result, we re-evaluating which letter has the max count. If it is max, follow 1, append two chars, otherwise, follow 2, just append one. Then reordering the count of all letters. Doing the same until we used up all letters with less count.
*/
class Solution {
public String longestDiverseString(int a, int b, int c) {
PriorityQueue<Pair<Character, Integer>> pq = new PriorityQueue<>(3, (p1, p2) -> (p2.getValue() - p1.getValue()));
//if there's 0 available, should not put into the pq.
if (a > 0) {
pq.add(new Pair<>('a', a));
}
if (b > 0) {
pq.add(new Pair<>('b', b));
}
if (c > 0) {
pq.add(new Pair<>('c', c));
}
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) {
Pair<Character, Integer> first = pq.poll();
//if the current one is duplicated, then we use the next one.
//but only use once to get longest.
if (sb.length() != 0 && sb.charAt(sb.length() - 1) == first.getKey()) {
//there's no second option, means there's only one available
//so there's no way to contruct, just break;
if (pq.isEmpty()) {
return sb.toString();
}
//get the second most number.
Pair<Character, Integer> second = pq.poll();
sb.append(second.getKey());
///if it's 0, no need to push to pq.
if (second.getValue() > 1) {
pq.offer(new Pair<Character, Integer>(second.getKey(), second.getValue() - 1));
}
pq.offer(first);
} else {
//always push as much as possible if it's the most number and is not equal to previous one.
int limit = Math.min(2, first.getValue());
for (int i = 0; i < limit; i++) {
sb.append(first.getKey());
}
if (first.getValue() - limit > 0) {
pq.offer(new Pair<>(first.getKey(), first.getValue() - limit));
}
}
}
return sb.toString();
}
}
```

## 400. Nth Digit

### Description

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

```
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).
Example 1:
Input:
3
Output:
3
Example 2:
Input:
11
Output:
0
Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
```

### Solution

```
class Solution {
public int findNthDigit(int n) {
long cur = 1;
int len =1;
long count = 9;
while(n > len*count){
n -= len * count;
len++;
count *= 10;
cur *= 10;
}
cur += (n-1)/len;
String s = Long.toString(cur);
return s.charAt((n-1)%len)-'0';
}
}
```

# 2020-07-22

## 192. Word Frequency

### Description

```
Write a bash script to calculate the frequency of each word in a text file words.txt.
For simplicity sake, you may assume:
words.txt contains only lowercase characters and space ' ' characters.
Each word must consist of lowercase characters only.
Words are separated by one or more whitespace characters.
Example:
Assume that words.txt has the following content:
the day is sunny the the
the sunny is is
Your script should output the following, sorted by descending frequency:
the 4
is 3
sunny 2
day 1
```

### Solution

```
cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -r | awk '{print $2,$1}'
```

```
tr -s: truncate the string with target string, but only remaining one instance (e.g. multiple whitespaces)
sort: To make the same string successive so that uniq could count the same string fully and correctly.
uniq -c: uniq is used to filter out the repeated lines which are successive, -c means counting
sort -r: -r means sorting in descending order
awk '{ print $2, $1 }': To format the output, see here.
```

## 724. Find Pivot Index

### Description

```
Given an array of integers nums, write a method that returns the "pivot" index of this array.
We define the pivot index as the index where the sum of all the numbers to the left of the index is equal to the sum of all the numbers to the right of the index.
If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.
Example 1:
Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.
Example 2:
Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.
Constraints:
The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].
```

### Solution

```
class Solution {
public int pivotIndex(int[] nums) {
if(nums.length <=2){
return -1;
}
int sum = Arrays.stream(nums).sum();
int left = 0;
for(int i = 0;i<nums.length;i++){
if(left*2+nums[i]==sum){
return i;
}
left+=nums[i];
}
return -1;
}
}
```

## 688. Knight Probability in Chessboard

### Description

```
On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exactly K moves. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N-1, N-1).
A chess knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.
```

```
Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.
The knight continues moving until it has made exactly K moves or has moved off the chessboard. Return the probability that the knight remains on the board after it has stopped moving.
Example:
Input: 3, 2, 0, 0
Output: 0.0625
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.
Note:
N will be between 1 and 25.
K will be between 0 and 100.
The knight always initially starts on the board.
```

### Solution

```
class Solution {
private int[][] dirs = new int[][][[-2, -1], [-1, -2], [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1]];
double[][][] dp;
public double knightProbability(int N, int K, int r, int c) {
dp = new double[N][N][K + 1];
return find(N, K, r, c);
}
public double find(int N, int K, int r, int c) {
if (r < 0 || r >= N || c < 0 || c >= N) {
return 0;
}
if (K == 0) {
return 1;
}
if (dp[r][c][K] != 0) {
return dp[r][c][K];
}
double rate = 0d;
for (int[] dir : dirs) {
rate += 0.125 * find(N, K - 1, r + dir[0], c + dir[1]);
}
dp[r][c][K] = rate;
return rate;
}
}
```

# 2020-07-23

## 1277. Count Square Submatrices with All Ones

### Description

```
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:
Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output: 15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is 1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
Example 2:
Input: matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
Output: 7
Explanation:
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7.
Constraints:
1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1
```

### Solution

```
class Solution {
public int countSquares(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int[][] res = new int[matrix.length][matrix[0].length];
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[i].length; j++) {
if (matrix[i][j] != 0 && matrix[i - 1][j - 1] != 0 && matrix[i][j - 1] != 0 && matrix[i - 1][j] != 0) {
matrix[i][j] = Math.min(matrix[i - 1][j - 1], Math.min(matrix[i][j - 1], matrix[i - 1][j])) + 1;
}
}
}
int sum = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
sum += matrix[i][j];
}
}
return sum;
}
}
```

## 777. Swap Adjacent in LR String

### Description

```
In a string composed of 'L', 'R', and 'X' characters, like "RXXLRXRXL", a move consists of either replacing one occurrence of "XL" with "LX", or replacing one occurrence of "RX" with "XR". Given the starting string start and the ending string end, return True if and only if there exists a sequence of moves to transform one string to the other.
Example:
Input: start = "RXXLRXRXL", end = "XRLXXRRLX"
Output: True
Explanation:
We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX
Constraints:
1 <= len(start) == len(end) <= 10000.
Both start and end will only consist of characters in {'L', 'R', 'X'}.
```

### Solution

```
/**
Conditions:
L can only move left, and R can only move right, and they may not across
1. their order are not able to change duo to no cross constrain XLRX has no valid move.
2. L can only move left, so the L with same order, say second L,
index of the second L in start should be larger than the index of the second L in end.
same for R.
*/
class Solution {
public boolean canTransform(String start, String end) {
if(!start.replace("X","").equals(end.replace("X",""))){
return false;
}
List<Integer> leftStart = new ArrayList<>();
List<Integer> leftEnd = new ArrayList<>();
List<Integer> rightStart = new ArrayList<>();
List<Integer> rightEnd = new ArrayList<>();
for (int i = 0; i < start.length(); i++) {
if (start.charAt(i) == 'L') {
leftStart.add(i);
}
if (start.charAt(i) == 'R') {
rightStart.add(i);
}
if (end.charAt(i) == 'L') {
leftEnd.add(i);
}
if (end.charAt(i) == 'R') {
rightEnd.add(i);
}
}
if (leftStart.size() != leftEnd.size() || rightStart.size()!=rightEnd.size()) {
return false;
}
for(int i=0;i<leftStart.size();i++){
if(leftStart.get(i) <leftEnd.get(i)){
return false;
}
}
for(int i=0;i<rightEnd.size();i++){
if(rightStart.get(i) > rightEnd.get(i)){
return false;
}
}
return true;
}
}
```

## 1275. Find Winner on a Tic Tac Toe Game

### Description

```
Tic-tac-toe is played by two players A and B on a 3 x 3 grid.
Here are the rules of Tic-Tac-Toe:
Players take turns placing characters into empty squares (" ").
The first player A always places "X" characters, while the second player B always places "O" characters.
"X" and "O" characters are always placed into empty squares, never on filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.
Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.
Return the winner of the game if it exists (A or B), in case the game ends in a draw return "Draw", if there are still movements to play return "Pending".
You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.
Example 1:
Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X " "X " "X " "X " "X "
" " -> " " -> " X " -> " X " -> " X "
" " "O " "O " "OO " "OOX"
Example 2:
Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: "B" wins.
"X " "X " "XX " "XXO" "XXO" "XXO"
" " -> " O " -> " O " -> " O " -> "XO " -> "XO "
" " " " " " " " " " "O "
Example 3:
Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"
Example 4:
Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.
"X "
" O "
" "
Constraints:
1 <= moves.length <= 9
moves[i].length == 2
0 <= moves[i][j] <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.
```

### Solution

```
/**
Use rows, cols and diag and antidiag to store the current state.
only if the sum is 3 or -3 means there's a winner.
*/
class Solution {
public String tictactoe(int[][] moves) {
int size = 3;
int player = 1;
int[] rows = new int[3];
int[] cols = new int[3];
int diag=0, antiDiag = 0;
for(int[] move : moves){
rows[move[1]] += player;
if(Math.abs(rows[move[1]])==3){
return rows[move[1]]>0?"A":"B";
}
cols[move[0]] += player;
if(Math.abs(cols[move[0]])==3){
return cols[move[0]]>0?"A":"B";
}
if(move[0]==move[1]){
diag += player;
if(Math.abs(diag)==3){
return diag>0?"A":"B";
}
}
if(move[0]+move[1]==2){
antiDiag += player;
if(Math.abs(antiDiag)==3){
return antiDiag>0?"A":"B";
}
}
player = -player;
}
if(moves.length==9){
return "Draw";
}else{
return "Pending";
}
}
}
```

## 912. Sort an Array

### Description

```
Given an array of integers nums, sort the array in ascending order.
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Constraints:
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000
```

### Solution

```
import java.util.Arrays;
class Solution {
public int[] sortArray(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
return nums;
}
public void mergeSort(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int pivot = nums[end];
int k = start;
int i = start;
//k is the tail with previous valid subarray where all items are smaller than pivot.
while (i < end) {
if (nums[i] < pivot) {
swap(nums, i, k);
k++;
}
i++;
}
swap(nums, k, end);
mergeSort(nums, start, k - 1);
mergeSort(nums, k + 1, end);
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
```

## 1297. Maximum Number of Occurrences of a Substring

### Description

```
Given a string s, return the maximum number of ocurrences of any substring under the following rules:
The number of unique characters in the substring must be less than or equal to maxLetters.
The substring size must be between minSize and maxSize inclusive.
Example 1:
Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 ocurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).
Example 2:
Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.
Example 3:
Input: s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
Output: 3
Example 4:
Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
Output: 0
Constraints:
1 <= s.length <= 10^5
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s only contains lowercase English letters.
```

### Solution

```
/**
Key point: only need to take care of the string with minSize greedily.
The greedy part of the solution is that, we also notice that we only need minSize since if the minSize satisfies the constraints to have distinct letters <= maxLetters any substring greater than that size would only add at max a new distinct letter.
Which esentially means that since the substring of size greater than minSize starisfies the constraint of distinct letters <= maxLetters there will be a substring of this selected substring of size minSize that'll satisfy the same constraint and the frequency of this substring will be atleast as much as the parent substring.
We also know that number of shorter substrings are more than the longer ones , thus we only need to check for substrings of minSize satisfying the condition.
*/
class Solution {
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
int left = 0;
int max_res = 0;
HashMap<Character, Integer> count = new HashMap<>();
HashMap<String, Integer> sMap = new HashMap<>();
for(int i =0;i<s.length();i++){
char c = s.charAt(i);
count.put(c,count.getOrDefault(c,0)+1);
while(left < i && i-left+1>minSize){
char c2 = s.charAt(left);
count.put(c2,count.get(c2)-1);
if(count.get(c2)==0){
count.remove(c2);
}
left++;
}
if(i-left+1==minSize && count.size()<=maxLetters){
String str = s.substring(left,i+1);
sMap.put(str,sMap.getOrDefault(str,0)+1);
}
}
if(sMap.size()==0){
return 0;
}
return sMap.values().stream().max((a,b)->(a-b)).get();
}
}
```

# 2020-07-24

## 467. Unique Substrings in Wraparound String

### Description

```
Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.
Note: p consists of only lowercase English letters and the size of p might be over 10000.
Example 1:
Input: "a"
Output: 1
Explanation: Only the substring "a" of string "a" is in the string s.
Example 2:
Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.
Example 3:
Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.
```

### Solution

```
/**
Key idea is that we only need to count the max length ending with certain char.
e.g. abcd -> d, 4 -> d, cd, bcd, abcd
so it can prevent duplication.
*/
class Solution {
public int findSubstringInWraproundString(String p) {
int[] count = new int[26];
int max = 0;
for (int i = 0; i < p.length(); i++) {
if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || p.charAt(i - 1) - p.charAt(i) == 25)) {
max++;
} else {
max = 1;
}
int ind = p.charAt(i) - 'a';
count[ind] = Math.max(count[ind], max);
}
int sum = 0;
for (int i = 0; i < 26; i++) {
sum += count[i];
}
return sum;
}
}
```

# 2020-07-25

## 1123. Lowest Common Ancestor of Deepest Leaves

### Description

```
Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.
Recall that:
The node of a binary tree is a leaf if and only if it has no children
The depth of the root of the tree is 0, and if the depth of a node is d, the depth of each of its children is d+1.
The lowest common ancestor of a set S of nodes is the node A with the largest depth such that every node in S is in the subtree with root A.
Example 1:
Input: root = [1,2,3]
Output: [1,2,3]
Explanation:
The deepest leaves are the nodes with values 2 and 3.
The lowest common ancestor of these leaves is the node with value 1.
The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]".
Example 2:
Input: root = [1,2,3,4]
Output: [4]
Example 3:
Input: root = [1,2,3,4,5]
Output: [2,4,5]
Constraints:
The given tree will have between 1 and 1000 nodes.
Each node of the tree will have a distinct value between 1 and 1000.
```

### Solution

```
/**
helper function will return the deepest level in this subtree
if and only if when the deepest is the same can we find a common node.
*/
class Solution {
TreeNode res = null;
int deepest = 0;
public TreeNode lcaDeepestLeaves(TreeNode root) {
deepest = 0;
helper(root, 0);
return res;
}
private int helper(TreeNode root, int level) {
deepest = Math.max(deepest,level);
if (root == null) {
return level;
}
int leftDepth = helper(root.left, level + 1);
int rightDepth = helper(root.right, level + 1);
if (leftDepth == deepest && rightDepth==deepest) {
res = root;
}
return Math.max(leftDepth, rightDepth);
}
}
```

## 1008. Construct Binary Search Tree from Preorder Traversal

### Description

```
Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.
Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
```

### Solution

```
/**
Define a boundary and if exceed it will return.
*/
class Solution {
int i = 0;
public TreeNode bstFromPreorder(int[] A) {
return bstFromPreorder(A, Integer.MAX_VALUE);
}
public TreeNode bstFromPreorder(int[] A, int bound) {
if (i == A.length || A[i] > bound) {
return null;
}
TreeNode root = new TreeNode(A[i++]);
root.left = bstFromPreorder(A, root.val);
root.right = bstFromPreorder(A, bound);
return root;
}
}
```

## 1254. Number of Closed Islands

### Description

```
Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.
Return the number of closed islands.
Example 1:
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1s).
Example 2:
Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1
Example 3:
Input: grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
Output: 2
```

### Solution

```
/**
get rid of the island stick to the boarder.
the left are closed island.
*/
class Solution {
public int closedIsland(int[][] grid) {
int row = grid.length, col = grid[0].length;
for (int i = 0; i < row; i++) {
if (grid[i][0] == 0) {
dfs(grid, i, 0);
}
if (grid[i][col - 1] == 0) {
dfs(grid, i, col - 1);
}
}
for (int i = 0; i < col; i++) {
if (grid[0][i] == 0) {
dfs(grid, 0, i);
}
if (grid[row - 1][i] == 0) {
dfs(grid, row - 1, i);
}
}
int count = 0;
for (int i = 1; i < row - 1; i++) {
for (int j = 1; j < col - 1; j++) {
if (grid[i][j] == 0) {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
public void dfs(int[][] grid, int i, int j) {
grid[i][j] = 1;
for (int[] dir : dirs) {
int i_next = i + dir[0];
int j_next = j + dir[1];
if (i_next >= 0 && i_next < grid.length && j_next >= 0 && j_next < grid[0].length && grid[i_next][j_next] == 0) {
dfs(grid, i_next, j_next);
}
}
}
}
```

# 2020-07-26

## 493. Reverse Pairs

### Description

```
Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2\*nums[j].
You need to return the number of important reverse pairs in the given array.
Example1:
Input: [1,3,2,3,1]
Output: 2
Example2:
Input: [2,4,3,5,1]
Output: 3
Note:
The length of the given array will not exceed 50,000.
All the numbers in the input array are in the range of 32-bit integer.
```

### Solution

```
class Solution {
public int reversePairs(int[] nums) {
return mergePairs(nums,0,nums.length-1);
}
private int mergePairs(int[] nums, int start, int end) {
if (start >= end) {
return 0;
}
int mid = start + (end - start) / 2;
int count = mergePairs(nums, start, mid) + mergePairs(nums, mid + 1, end);
//after each range has been processed, we know range [start,mid] and [mid+1,end] has been sorted.
//so we can use two pointer to explore.
for(int i = start, j = mid+1;i<=mid;i++){
while(j<=end && nums[i]/2.0 > nums[j]){
j++;
}
//j is invalid now, so (j-1) - (mid+1) + 1
count+=(j-mid-1);
}
//range [start, end] has been explored, no need to keep original orders.
//also sort for previous call to travers since we assuming after the subproblem
//the range has been sorted.
Arrays.sort(nums,start,end+1);
return count;
}
}
```

## 315. Count of Smaller Numbers After Self

### Description

```
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
```

### Solution

```
/**
to solve problem in range [start, end]
split using mid to [start, mid] and [mid+1, end]
subproblem will find all pairs that i<\j and nums[i] > nums[j] for i and j both in start and end
so after solveing the sub problems, only need to count that
i in [start, mid], \j in [mid+1, end] and nums[i] < nums[j]
and use array to store the result.
*/
class Solution {
public List<Integer> countSmaller(int[] nums) {
int len = nums.length;
Pair[] arr = new Pair[len];
Integer[] smaller = new Integer[len];
Arrays.fill(smaller,0);
for (int i = 0; i < len; i++) {
arr[i] = new Pair(nums[i], i);
}
mergeArray(arr,smaller,0,len-1);
return new ArrayList<>(Arrays.asList(smaller));
}
private void mergeArray(Pair[] arr, Integer[] smaller, int start, int end) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
mergeArray(arr, smaller, start, mid);
mergeArray(arr, smaller, mid + 1, end);
for (int i = start, j = mid + 1; i <= mid; i++) {
while (j <= end && arr[j].val < arr[i].val){
j++;
}
smaller[arr[i].index] += (j-mid-1);
}
Arrays.sort(arr,start,end+1, Comparator.comparingInt(a -> a.val));
}
class Pair {
int val;
int index;
public Pair(int val, int index) {
this.val = val;
this.index = index;
}
}
}
```

## 186. Reverse Words in a String II

### Description

```
Given an input string , reverse the string word by word.
Example:
Input: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
Note:
A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces.
The words are always separated by a single space.
```

### Solution

```
class Solution {
public void reverseWords(char[] s) {
int len = s.length;
swapAll(s, 0, len - 1);
int i = 0, j = 0;
while (i < len && j < len) {
while(j<len && s[j]!=' '){
j++;
}
swapAll(s,i,j-1);
i = j+1;
j = j+1;
}
}
private void swapAll(char[] arr, int i, int j) {
int len = j - i + 1;
for (int offset = 0; offset < len / 2; offset++) {
char temp = arr[i + offset];
arr[i + offset] = arr[j - offset];
arr[j - offset] = temp;
}
}
}
```

## 381. Insert Delete GetRandom O(1) - Duplicates allowed

### Description

```
Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
Example:
// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();
// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);
// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);
// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);
// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();
// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);
// getRandom should return 1 and 2 both equally likely.
collection.getRandom();
```

### Solution

```
import java.util.*;
class RandomizedCollection {
List<Integer> arr;
HashMap<Integer, HashSet<Integer>> map;
Random rand;
/**
* Initialize your data structure here.
*/
public RandomizedCollection() {
arr = new ArrayList<>();
map = new HashMap<>();
rand = new Random();
}
/**
* Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
*/
public boolean insert(int val) {
boolean contains = map.containsKey(val);
if (!contains) {
map.put(val, new HashSet<>());
}
arr.add(val);
map.get(val).add(arr.size()-1);
return !contains;
}
/**
* Removes a value from the collection. Returns true if the collection contained the specified element.
*/
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
int targetIndex = map.get(val).iterator().next();
int last = arr.size() - 1;
//swap last number with the deleted one.
if (val != arr.get(last)) {
int lastOneVal = arr.get(last);
map.get(lastOneVal).remove(last);
map.get(lastOneVal).add(targetIndex);
arr.set(targetIndex,lastOneVal);
}else{
//in case the removed one is also exist at tail, then simply remove tail would be good.
targetIndex = last;
}
arr.remove(last);
map.get(val).remove(targetIndex);
if (map.get(val).size() == 0) {
map.remove(val);
}
return true;
}
/**
* Get a random element from the collection.
*/
public int getRandom() {
return arr.get(rand.nextInt(arr.size()));
}
```

## 356. Line Reflection

### Description

```
Given n points on a 2D plane, find if there is such a line parallel to y-axis that reflect the given points symmetrically, in other words, answer whether or not if there exists a line that after reflecting all points over the given line the set of the original points is the same that the reflected ones.
Note that there can be repeated points.
Follow up:
Could you do better than O(n2) ?
```

```
Example 1:
Input: points = [[1,1],[-1,1]]
Output: true
Explanation: We can choose the line x = 0.
Example 2:
Input: points = [[1,1],[-1,-1]]
Output: false
Explanation: We can't choose a line.
Constraints:
n == points.length
1 <= n <= 10^4
-10^8 <= points[i][j] <= 10^8
```

### Solution

```
class Solution {
public boolean isReflected(int[][] points) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
HashSet<String> set = new HashSet<>();
for (int[] point : points) {
min = Math.min(min, point[0]);
max = Math.max(max, point[0]);
set.add(point[0] + " " + point[1]);
}
int sum = min + max;
for (int[] point : points) {
String ref = (sum - point[0]) + " " + point[1];
if (!set.contains(ref)) {
return false;
}
}
return true;
}
}
```

# 2020-07-27

## 1383. Maximum Performance of a Team

### Description

```
There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.
The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
Example 1:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation:
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.
Example 2:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.
Example 3:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72
Constraints:
1 <= n <= 10^5
speed.length == n
efficiency.length == n
1 <= speed[i] <= 10^5
1 <= efficiency[i] <= 10^8
1 <= k <= n
```

### Solution

```
/**
Sorted by effeciency, so while looping, we get the current eff as the global eff as it's the min.
then use priorityQueue to store previous speed and pop the min spped and keep the max speed sum.
so the current max workload is their multiple.
*/
class Solution {
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
int mod = (int) 1e9 + 7;
Pair[] arr = new Pair[n];
for (int i = 0; i < n; i++) {
arr[i] = new Pair(speed[i], efficiency[i]);
}
Arrays.sort(arr, (a, b) -> Integer.compare(b.eff, a.eff));
PriorityQueue<Pair> pq = new PriorityQueue<>(k + 1, (a, b) -> Integer.compare(a.speed, b.speed));
long speedSum = 0;
long max_res = 0;
for (int i = 0; i < n; i++) {
pq.add(arr[i]);
speedSum += arr[i].speed;
if (i >= k) {
Pair pre = pq.poll();
speedSum -= pre.speed;
}
max_res = Math.max(max_res, arr[i].eff * speedSum );
}
return (int) (max_res % (long)(1e9 + 7));
}
class Pair {
int speed;
int eff;
public Pair(int speed, int eff) {
this.speed = speed;
this.eff = eff;
}
}
}
```

## 921. Minimum Add to Make Parentheses Valid

### Description

```
Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.
Formally, a parentheses string is valid if and only if:
It is the empty string, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.
Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.
Example 1:
Input: "())"
Output: 1
Example 2:
Input: "((("
Output: 3
Example 3:
Input: "()"
Output: 0
Example 4:
Input: "()))(("
Output: 4
Note:
S.length <= 1000
S only consists of '(' and ')' characters.
```

### Solution

```
class Solution {
public int minAddToMakeValid(String S) {
int sum = 0;
int cur = 0;
for (char c : S.toCharArray()) {
cur += c == '(' ? 1 : -1;
//if cur is less than 0, means right p is more than left, it cannot be valid
//so it has to add a left p until cur is 0.
if(cur<0){
sum -= cur;
cur = 0;
}
}
sum += Math.abs(cur);
return sum;
}
}
```

## 845. Longest Mountain in Array

### Description

```
Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:
B.length >= 3
There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
(Note that B could be any subarray of A, including the entire array A.)
Given an array A of integers, return the length of the longest mountain.
Return 0 if there is no mountain.
Example 1:
Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.
Example 2:
Input: [2,2,2]
Output: 0
Explanation: There is no mountain.
Note:
0 <= A.length <= 10000
0 <= A[i] <= 10000
Follow up:
Can you solve it using only one pass?
Can you solve it in O(1) space?
```

### Solution

```
class Solution {
public int longestMountain(int[] A) {
int len = A.length;
int[] left = new int[len];
int[] right = new int[len];
for (int i = 1; i < len; i++) {
if (A[i - 1] < A[i]) {
left[i] = left[i - 1] + 1;
} else {
left[i] = 0;
}
}
for (int i = len - 2; i >= 0; i--) {
if (A[i + 1] < A[i]) {
right[i] = right[i + 1] + 1;
} else {
right[i] = 0;
}
}
int max = 0;
for (int i = 1; i <= len - 1; i++) {
if(left[i]!=0 && right[i]!=0){
max = Math.max(left[i]+right[i]+1,max);
}
}
return max;
}
}
```

one-pass solution

```
/**
Key point is that the mountain will not overlap, so just travers and find up count and down count,
no need to store previous solution.
*/
class Solution {
public int longestMountain(int[] A) {
int i = 1, up = 0, down = 0;
int res = 0;
while (i < A.length) {
while (i < A.length && A[i] == A[i - 1]) {
i++;
}
up = 0;
while (i < A.length && A[i - 1] < A[i]) {
up++;
i++;
}
down = 0;
while (i < A.length && A[i - 1] > A[i]) {
down++;
i++;
}
if (up != 0 && down != 0) {
res = Math.max(res, up + down + 1);
}
}
return res;
}
}
```

## 605. Can Place Flowers

### Description

```
Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.
Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.
Example 1:
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True
Example 2:
Input: flowerbed = [1,0,0,0,1], n = 2
Output: False
Note:
The input array won't violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won't exceed the input array size.
```

### Solution

```
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count = 0;
for (int i = 0; i < flowerbed.length; i++) {
if (flowerbed[i] == 1) {
continue;
}
if ((i == 0 || flowerbed[i-1]==0) && (i==flowerbed.length-1 || flowerbed[i+1]==0)){
count++;
flowerbed[i] = 1;
}
}
//System.out.println(count);
return n <= count;
}
}
```

## 37. House Robber III

### Description

```
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
Input: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
```

### Solution

```
class Solution {
public int rob(TreeNode root) {
int[] res = helper(root);
return Math.max(res[0],res[1]);
}
public int[] helper(TreeNode root){
int[] res = new int[2];
if(root==null){
return res;
}
int[] left = helper(root.left);
int[] right = helper(root.right);
//not take cur node
//can take its two children, get their max.
res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
//take the cur node;
//will be the current value plue the max
res[1] = root.val + left[0] + right[0];
return res;
}
}
```

## 333. Largest BST Subtree

### Description

```
Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.
Note:
A subtree must include all of its descendants.
Example:
Input: [10,5,15,1,8,null,7]
10
/ \
5 15
/ \ \
1 8 7
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree's size, which is 3.
Follow up:
Can you figure out ways to solve it with O(n) time complexity?
```

### Solution

```
/**
use arr to return result as [size(-1 if invalid), min_value, max_value]
*/
class Solution {
int max_node;
public int largestBSTSubtree(TreeNode root) {
helper(root);
return max_node;
}
public int[] helper(TreeNode root) {
int curSize = 1;
int min = root.val, max = root.val;
//must use a flag instead of simply return because you need to travers both left and right.
//cannot return early.
boolean isValid = true;
if (root.left != null) {
int[] left = helper(root.left);
//if subtree is not a BST or the current node is not valid.
if (left[0] == -1 || left[2] >= root.val) {
isValid = false;
}
curSize += left[0];
//record the min value, since it's valid, min value will always be the min of left subtree.
min = left[1];
}
if (root.right != null) {
int[] right = helper(root.right);
if (right[0] == -1 || right[1] <= root.val) {
isValid = false;
}
//get the total size of the tree.
curSize += right[0];
max = right[2];
}
//if any condition, the subtree is invalid, no need to return value but a -1.
if (!isValid) {
return new int[]{-1, 0, 0};
}
//valid, record the max size of a subtree.
max_node = Math.max(max_node, curSize);
return new int[]{curSize, min, max};
}
}
```

## 792. Number of Matching Subsequences

### Description

```
Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.
Example :
Input:
S = "abcde"
words = ["a", "bb", "acd", "ace"]
Output: 3
Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".
Note:
All words in words and S will only consists of lowercase letters.
The length of S will be in the range of [1, 50000].
The length of words will be in the range of [1, 5000].
The length of words[i] will be in the range of [1, 50].
```

### Solution

```
/**
store each word as a queue, group them by the first letter.
iterate the whole string and poll the current char for all string starting cur char.
when and only when the word is empty means all char has been polled, so it's valid.
*/
class Solution {
public int numMatchingSubseq(String S, String[] words) {
Queue<Queue<Character>>[] map = new Queue[26];
for (int i = 0; i < 26; i++) {
map[i] = new ArrayDeque<>();
}
for (String word : words) {
//store word as a queue so we can poll its head.
Queue<Character> queue = new ArrayDeque<>(word.length());
for (char c : word.toCharArray()) {
queue.add(c);
}
//store and group them by their head.
map[word.charAt(0) - 'a'].add(queue);
}
int count = 0;
for (char c : S.toCharArray()) {
//go through all words starting with c.
Queue<Queue<Character>> temp = map[c-'a'];
int size = temp.size();
for(int i = 0;i<size;i++){
//get one word.
Queue<Character> cur = temp.poll();
//if size is one, means after poll, it will be empty, so it's valid.
//also no need to put into another bin.
if(cur.size()==1){
count++;
}else{
//remove head.
cur.poll();
//add to its new bin based on the head.
map[cur.peek()-'a'].add(cur);
}
}
}
return count;
}
}
```

# 2020-07-28

## 456. 132 Pattern

### Description

```
Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.
Example 1:
Input: [1, 2, 3, 4]
Output: False
Explanation: There is no 132 pattern in the sequence.
Example 2:
Input: [3, 1, 4, 2]
Output: True
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
Input: [-1, 3, 2, 0]
Output: True
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
```

### Solution

```
class Solution {
public boolean find132pattern(int[] nums) {
if (nums.length < 3) {
return false;
}
int[] min = new int[nums.length];
min[0] = nums[0];
//min will keep decending.
for (int i = 1; i < nums.length; i++) {
min[i] = Math.min(min[i-1], nums[i]);
}
//stack will keep the valid number that lasger than smallest but smaller than the middle one.
ArrayDeque<Integer> stack = new ArrayDeque<>();
for (int j = nums.length - 1; j >= 0; j--) {
//if current number has a smaller number to its left.
if(nums[j] > min[j]){
//remove all numbers that is smaller than min until a valid number\6
//find the first number that's larger than the min.
while(!stack.isEmpty() && stack.peek() <= min[j]){
stack.pop();
}
//if valid, then return true.
//only need to check once.
if(!stack.isEmpty() && stack.peek() < nums[j]){
return true;
}
stack.push(nums[j]);
}
}
return false;
}
}
```

## 250. Count Univalue Subtrees

### Description

```
Given a binary tree, count the number of uni-value subtrees.
A Uni-value subtree means all nodes of the subtree have the same value.
Example :
Input: root = [5,1,5,5,5,null,5]
5
/ \
1 5
/ \ \
5 5 5
Output: 4
```

### Solution

```
class Solution {
int count;
public int countUnivalSubtrees(TreeNode root) {
count = 0;
if(root==null){
return 0;
}
helper(root);
return count;
}
//return if it's a uni, if either of the children is not uni, then the root is not uni.
private boolean helper(TreeNode root) {
boolean isUni = true;
if (root.left != null) {
boolean isUniLeft = helper(root.left);
if(isUniLeft){
//only when left child is uni need to check value
//if left is uni, means every node has value equals to root.left.
isUni &= (root.val==root.left.val);
}else{
isUni = false;
}
}
if (root.right != null) {
boolean isUniRight = helper(root.right);
if(isUniRight){
isUni &= (root.val==root.right.val);
}else{
isUni = false;
}
}
if(isUni){
count++;
}
return isUni;
}
}
```

## 918. Maximum Sum Circular Subarray

### Description

```
Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.
Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)
Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)
Example 1:
Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3
Example 2:
Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10
Example 3:
Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4
Example 4:
Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3
Example 5:
Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1
Note:
-30000 <= A[i] <= 30000
1 <= A.length <= 30000
```

### Solution

```
/**
Corner case
Just one to pay attention:
If all numbers are negative, maxSum = max(A) and minSum = sum(A).
In this case, max(maxSum, total - minSum) = 0, which means the sum of an empty subarray.
According to the deacription, We need to return the max(A), instead of sum of am empty subarray.
So we return the maxSum to handle this corner case.
*/
class Solution {
public int maxSubarraySumCircular(int[] A) {
int total = 0, maxSum = A[0], curMax = 0, minSum = A[0], curMin = 0;
for (int a : A) {
curMax = Math.max(curMax + a, a);
maxSum = Math.max(maxSum, curMax);
curMin = Math.min(curMin + a, a);
minSum = Math.min(minSum, curMin);
total += a;
}
return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
}
}
```

# 2020-07-29

## 1026. Maximum Difference Between Node and Ancestor

### Description

```
Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.
(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)
```

```
Example 1:
Input: [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation:
We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
Note:
The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.
```

### Solution

```
/**
simply return the max and min value accorsing the whole subtree, then compare.
*/
class Solution {
int global_max;
public int maxAncestorDiff(TreeNode root) {
this.global_max = 0;
helper(root);
return global_max;
}
public int[] helper(TreeNode root) {
if (root == null) {
return new int[]{Integer.MAX_VALUE/2, Integer.MIN_VALUE/2};
}
int min = root.val, max = root.val;
if (root.left != null) {
int[] leftRes = helper(root.left);
min = Math.min(min, leftRes[0]);
max = Math.max(max, leftRes[1]);
}
if (root.right != null) {
int[] rightRes = helper(root.right);
min = Math.min(min, rightRes[0]);
max = Math.max(max, rightRes[1]);
}
int local_max = Math.max(Math.abs(root.val - min), Math.abs(root.val - max));
this.global_max = Math.max(this.global_max, local_max);
min = Math.min(min, root.val);
max = Math.max(max, root.val);
return new int[]{min, max};
}
}
```

```
/**
Follow up 1:
What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
For the follow-up 1, we are only able to load one row at one time, so we have to use a buffer (1D data structure) to store the row info. When next row comes as a streaming flow, we can compare each value (say, matrix[i][j], i>=1, j>=1) to the "upper-left" value in the buffer (buffer[j - 1]); meanwhile, we update the buffer by inserting the 1st element of the current row (matrix[i][0]) to buffer at position 0 (buffer[0]), and removing the last element in the buffer.
*/
class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return true;
int row = matrix.length;
int col = matrix[0].length;
List<Integer> buffer = new LinkedList<>();
for(int j = 0; j < col; j++) buffer.add(matrix[0][j]);
for(int i = 1; i < row; i++){
for(int j = 1; j < col; j++){
if(buffer.get(j - 1) != matrix[i][j]) return false;
}
buffer.remove(buffer.size() - 1);
buffer.add(0, matrix[i][0]);
}
return true;
}
}
```

```
Follow up 2:
What if the matrix is so large that you can only load up a partial row into the memory at once?
For the follow-up 2, we can only load a partial row at one time. We could split the whole matrix vertically into several sub-matrices, while each sub-matrix should have one column overlapped. We repeat the same method in follow-up 1 for each sub-matrix.
For example:
[1 2 3 4 5 6 7 8 9 0] [1 2 3 4] [4 5 6 7] [7 8 9 0]
[0 1 2 3 4 5 6 7 8 9] [0 1 2 3] [3 4 5 6] [6 7 8 9]
[1 0 1 2 3 4 5 6 7 8] --> [1 0 1 2] + [2 3 4 5] + [5 6 7 8]
[2 1 0 1 2 3 4 5 6 7] [2 1 0 1] [1 2 3 4] [4 5 6 7]
[3 2 1 0 1 2 3 4 5 6] [3 2 1 0] [0 1 2 3] [3 4 5 6]
```

## 805. Split Array With Same Average

### Description

```
In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)
Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.
Example :
Input:
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.
Note:
The length of A will be in the range [1, 30].
A[i] will be in the range of [0, 10000].
```

### Solution

```
class Solution {
public boolean splitArraySameAverage(int[] A) {
int n = A.length, s = Arrays.stream(A).sum();
//sort can help skip same number.
Arrays.sort(A);
//only need to find the smaller one.
for (int i = 1; i <= n / 2; ++i) if (s * i % n == 0 && find(A, s * i / n, i, 0)) return true;
return false;
}
public boolean find(int[] A, int target, int k, int i) {
if (k == 0) return target == 0;
for (int j = i; j < A.length; j++) {
//why can skip the same number?
//consider the case [60, 30, 30, 30, 40,... ]
//if we pick the first 30, then you still have chance to add the other two 30.
//if you pick second 30 then you can have 1 or 2 30 which has already been included in the previous case.
//so only need to pick the first number and skip all the same.
if (j != i && A[j] == A[j - 1]) continue;
if (find(A, target - A[j], k - 1, j + 1)) return true;
}
return false;
}
}
```

## 864. Shortest Path to Get All Keys

### Description

```
We are given a 2-dimensional grid. "." is an empty cell, "#" is a wall, "@" is the starting point, ("a", "b", ...) are keys, and ("A", "B", ...) are locks.
We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions. We cannot walk outside the grid, or walk into a wall. If we walk over a key, we pick it up. We can't walk over a lock unless we have the corresponding key.
For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first K letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.
Return the lowest number of moves to acquire all keys. If it's impossible, return -1.
Example 1:
Input: ["@.a.#","###.#","b.A.B"]
Output: 8
Example 2:
Input: ["@..aA","..B#.","....b"]
Output: 6
Note:
1 <= grid.length <= 30
1 <= grid[0].length <= 30
grid[i][j] contains only '.', '#', '@', 'a'-'f' and 'A'-'F'
The number of keys is in [1, 6]. Each key has a different letter and opens exactly one lock.
```

### Solution

```
/**
* BFS with status, traverse based on keys, x, y and use binary to store key information.
*/
class Solution {
public int shortestPathAllKeys(String[] grid) {
int x = -1, y = -1, max = -1, m = grid.length, n = grid[0].length();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
char c = grid[i].charAt(j);
//find the starting point.
if (c == '@') {
x = i;
y = j;
}
//find total count of key/lock pairs.
if (c >= 'a' && c <= 'f') {
max = Math.max(c - 'a' + 1, max);
}
}
}
int[] start = new int[]{0, x, y};
Queue<int[]> queue = new LinkedList<>();
//still check visited, but this time with keys status
Set<String> visited = new HashSet<>();
visited.add(0 + " " + x + " " + y);
queue.add(start);
int[][] dirs = new int[][][[0, 1], [1, 0], [0, -1], [-1, 0]];
int steps = 0;
while (!queue.isEmpty()) {
//traverse by levels.
int size = queue.size();
while (size-- > 0) {
int[] cur = queue.poll();
//a,b,c, max = 3, then keys = 111, which equals to 1<<3 - 1.
//means all keys have been acquired.
if (cur[0] == (1 << max) - 1) {
return steps;
}
for (int[] dir : dirs) {
int n_x = cur[1] + dir[0];
int n_y = cur[2] + dir[1];
//if still in the range of the boarder.
if (n_x >= 0 && n_x < m && n_y >= 0 && n_y < n) {
int keys = cur[0];
char c = grid[n_x].charAt(n_y);
if (c == '#') {
continue;
}
if (c >= 'a' && c <= 'f') {
keys |= (1 << (c - 'a'));
}
//it's a lock that we don't possess its key.
if (c >= 'A' && c <= 'F' && ((keys >> (c - 'A')) & 1) == 0) {
continue;
}
//the new state.
String state = keys + " " + n_x + " " + n_y;
if (!visited.contains(state)) {
queue.add(new int[]{keys, n_x, n_y});
visited.add(state);
}
}
}
}
//after looping all nodes in this level, go next.
steps++;
}
return -1;
}
}
```

## 895. Maximum Frequency Stack

### Description

```
Implement FreqStack, a class which simulates the operation of a stack-like data structure.
FreqStack has two functions:
push(int x), which pushes an integer x onto the stack.
pop(), which removes and returns the most frequent element in the stack.
If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.
Example 1:
Input:
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top. Then:
pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].
pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].
pop() -> returns 5.
The stack becomes [5,7,4].
pop() -> returns 4.
The stack becomes [5,7].
Note:
Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
It is guaranteed that FreqStack.pop() won't be called if the stack has zero elements.
The total number of FreqStack.push calls will not exceed 10000 in a single test case.
The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.
```

### Solution

```
class FreqStack {
HashMap<Integer, Integer> freq;
HashMap<Integer, ArrayDeque<Integer>> stackMap;
int maxFreq;
public FreqStack() {
freq = new HashMap<Integer, Integer>();
stackMap = new HashMap<>();
maxFreq = 0;
}
public void push(int x) {
int f = freq.getOrDefault(x, 0) + 1;
freq.put(x, f);
maxFreq = Math.max(f, maxFreq);
stackMap.putIfAbsent(f, new ArrayDeque<>());
stackMap.get(f).push(x);
}
public int pop() {
int x = stackMap.get(maxFreq).pop();
freq.put(x, maxFreq - 1);
if (stackMap.get(maxFreq).size() == 0) {
stackMap.remove(maxFreq);
maxFreq--;
}
return x;
}
}
```

## 997. Find the Town Judge

### Description

```
In a town, there are N people labelled from 1 to N. There is a rumor that one of these people is secretly the town judge.
If the town judge exists, then:
The town judge trusts nobody.
Everybody (except for the town judge) trusts the town judge.
There is exactly one person that satisfies properties 1 and 2.
You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.
If the town judge exists and can be identified, return the label of the town judge. Otherwise, return -1.
Example 1:
Input: N = 2, trust = [[1,2]]
Output: 2
Example 2:
Input: N = 3, trust = [[1,3],[2,3]]
Output: 3
Example 3:
Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
Example 4:
Input: N = 3, trust = [[1,2],[2,3]]
Output: -1
Example 5:
Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3
Constraints:
1 <= N <= 1000
0 <= trust.length <= 10^4
trust[i].length == 2
trust[i] are all different
trust[i][0] != trust[i][1]
1 <= trust[i][0], trust[i][1] <= N
```

### Solution

```
class Solution {
public int findJudge(int N, int[][] trust) {
int[] degree = new int[N+1];
for(int[] t:trust){
degree[t[0]]--;
degree[t[1]]++;
}
for(int i = 1;i<=N;i++){
if(degree[i]==N-1){
return i;
}
}
return -1;
}
}
```

# 2020-07-30

## 165. Compare Version Numbers

### Description

```
Compare two version numbers version1 and version2.
If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.
You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.
Example 1:
Input: version1 = "0.1", version2 = "1.1"
Output: -1
Example 2:
Input: version1 = "1.0.1", version2 = "1"
Output: 1
Example 3:
Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1
Example 4:
Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both “01” and “001" represent the same number “1”
Example 5:
Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: The first version number does not have a third level revision number, which means its third level revision number is default to "0"
Note:
Version strings are composed of numeric strings separated by dots . and this numeric strings may have leading zeroes.
Version strings do not start or end with dots, and they will not be two consecutive dots.
```

### Solution

```
class Solution {
public int compareVersion(String version1, String version2) {
String[] v1 = version1.split("\\.");
String[] v2 = version2.split("\\.");
int len1 = v1.length;
int len2 = v2.length;
int len = Math.max(len1, len2);
for (int i = 0; i < len; i++) {
int i1 = i<len1 ?Integer.parseInt(v1[i]):0;
int i2 = i<len2 ?Integer.parseInt(v2[i]):0;
int compare = Integer.compare(i1,i2);
if(compare!=0){
return compare;
}
}
return 0;
}
}
```

## 581. Shortest Unsorted Continuous Subarray

### Description

```
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.
```

### Solution

```
class Solution {
public int findUnsortedSubarray(int[] nums) {
int[] sorted = Arrays.copyOf(nums,nums.length);
Arrays.sort(sorted);
int i =0,j=nums.length-1;
while(i<j && nums[i]==sorted[i]){
i++;
}
while(i<j && nums[j]==sorted[j]){
j--;
}
return j==i?0:j-i+1;
}
}
```

## 1058. Minimize Rounding Error to Meet Target

### Description

```
Given an array of prices [p1,p2...,pn] and a target, round each price pi to Roundi(pi) so that the rounded array [Round1(p1),Round2(p2)...,Roundn(pn)] sums to the given target. Each operation Roundi(pi) could be either Floor(pi) or Ceil(pi).
Return the string "-1" if the rounded array is impossible to sum to target. Otherwise, return the smallest rounding error, which is defined as Σ |Roundi(pi) - (pi)| for i from 1 to n, as a string with three places after the decimal.
Example 1:
Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"
Explanation:
Use Floor, Ceil and Ceil operations to get (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0 .
Example 2:
Input: prices = ["1.500","2.500","3.500"], target = 10
Output: "-1"
Explanation:
It is impossible to meet the target.
Note:
1 <= prices.length <= 500.
Each string of prices prices[i] represents a real number which is between 0 and 1000 and has exactly 3 decimal places.
target is between 0 and 1000000.
```

### Solution

```
/**
Main idea is to first floor all numbers, and then count the min value of all cost to switch from floor to ceil.
*/
class Solution {
public String minimizeError(String[] prices, int target) {
PriorityQueue<Double> pq = new PriorityQueue<>();
double floorSum = 0;
double ceilSum = 0;
double cost = 0;
for (String price : prices) {
double num = Double.parseDouble(price);
double high = Math.ceil(num);
double low = Math.floor(num);
//the additional cost to switch from floor to ceil, could be negative.
//edge case: 2.000 which should be ignored.
if (low != high) {
pq.offer((high - num) - (num - low));
}
//cost to switch to floor.
cost += num - low;
ceilSum += high;
floorSum += low;
}
//impossible to reach the target.
if (target < floorSum || target > ceilSum) {
return "-1";
}
double res = cost;
//switch the number to ceiling with min additional cost.
while (target != floorSum) {
res += pq.poll();
target--;
}
//leave three point.
return String.format("%.3f", res);
}
}
```

## 1008. Construct Binary Search Tree from Preorder Traversal

### Description

```
Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.
Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Constraints:
1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
The values of preorder are distinct.
```

### Solution

```
class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
return build(preorder,0,preorder.length-1);
}
public TreeNode build(int[] preorder, int start, int end) {
//when the boarder is invalid
if (start > end || start >= preorder.length) {
return null;
}
int val = preorder[start];
int rightFirst = start + 1;
//find the min value in the right subtree, which is the first element that is larger than val.
while (rightFirst < preorder.length && preorder[rightFirst] < val) {
rightFirst++;
}
TreeNode root = new TreeNode(val);
root.left = build(preorder, start + 1, rightFirst - 1);
root.right = build(preorder, rightFirst, end);
return root;
}
}
```

## 1047. Remove All Adjacent Duplicates In String

### Description

```
Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.
We repeatedly make duplicate removals on S until we no longer can.
Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.
Example 1:
Input: "abbaca"
Output: "ca"
Explanation:
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".
Note:
1 <= S.length <= 20000
S consists only of English lowercase letters.
```

### Solution

```
class Solution {
public String removeDuplicates(String S) {
ArrayDeque<Character> stack = new ArrayDeque<>();
for(char c: S.toCharArray()){
int size = stack.size();
if(size!=0 && stack.peek()==c){
stack.pop();
}else{
stack.push(c);
}
}
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pollLast());
}
return sb.toString();
}
}
```

# 2020-07-31

## 33. Search in Rotated Sorted Array

### Description

```
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
```

### Solution

```
public int search(int[] nums, int target) {
if(nums==null||nums.length==0) return -1;
int lo = 0;
int hi = nums.length - 1;
while(lo<hi)
{
int mid = lo + (hi-lo)/2;
//target and mid are on the same side
if(!(nums[mid]-nums[nums.length-1]>0)^(target-nums[nums.length-1]>0))
{
if(nums[mid]<target)
lo = mid + 1;
else
hi = mid;
}else if(target>nums[nums.length-1])
hi = mid; // target on the left side
else
lo = mid + 1; // target on the right side
}
// now hi == lo
if(nums[lo]==target)
return lo;
else
return -1;
}
```

## 81. Search in Rotated Sorted Array II

### Description

```
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:
This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?
```

### Solution

```
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 (nums[mid] == target) {
return true;
}
//the situation where need special handle.
if ((nums[lo] == nums[mid]) && (nums[hi] == nums[mid])) {
++lo;
--hi;
} else if (nums[lo] <= nums[mid]) {
//mid is on the left part
if ((nums[lo] <= target) && (nums[mid] > target)) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
//mid is on the right part.
if ((nums[mid] < target) && (nums[hi] >= target)) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return false;
}
}
```

## 1365. How Many Numbers Are Smaller Than the Current Number

### Description

```
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].
Return the answer in an array.
Example 1:
Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).
Example 2:
Input: nums = [6,5,4,8]
Output: [2,1,0,3]
Example 3:
Input: nums = [7,7,7,7]
Output: [0,0,0,0]
Constraints:
2 <= nums.length <= 500
0 <= nums[i] <= 100
```

### Solution

```
/**
key idea is to sort the array, and the index (i) of the first apperance of a number has i smaller number
ex. 8,1,2,2,3 -> 1,2,2,3,8
index for 3 is 3, and 3 has 3 number that are smaller than itself.
*/
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int[] res = Arrays.copyOf(nums,nums.length);
HashMap<Integer, Integer> count = new HashMap<>();
Arrays.sort(res);
for(int i = 0;i<res.length;i++){
count.putIfAbsent(res[i],i);
}
for(int i = 0;i<nums.length;i++){
res[i] = count.get(nums[i]);
}
return res;
}
}
```

## 896. Monotonic Array

### Description

```
An array is monotonic if it is either monotone increasing or monotone decreasing.
An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is monotone decreasing if for all i <= j, A[i] >= A[j].
Return true if and only if the given array A is monotonic.
Example 1:
Input: [1,2,2,3]
Output: true
Example 2:
Input: [6,5,4,4]
Output: true
Example 3:
Input: [1,3,2]
Output: false
Example 4:
Input: [1,2,4,5]
Output: true
Example 5:
Input: [1,1,1]
Output: true
Note:
1 <= A.length <= 50000
-100000 <= A[i] <= 100000
```

### Solution

```
class Solution {
public boolean isMonotonic(int[] A) {
int acceding = 0;
for (int i = 1; i < A.length; i++) {
//if equal just skip.
if (A[i] == A[i - 1]) {
continue;
}
if (A[i] > A[i - 1]) {
//if the arr is decending but this pair is accending, return false;
if (acceding == -1) {
return false;
}
//in case the flag is 0 (init status).
acceding = 1;
} else if (A[i] < A[i - 1]) {
if (acceding == 1) {
return false;
}
acceding = -1;
}
}
return true;
}
}
```

## 821. Shortest Distance to a Character

### Description

```
Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.
Example 1:
Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
Note:
S string length is in [1, 10000].
C is a single character, and guaranteed to be in string S.
All letters in S and C are lowercase.
```

### Solution

```
class Solution {
public int[] shortestToChar(String S, char C) {
int len = S.length();
int[] res = new int[len];
Arrays.fill(res,Integer.MAX_VALUE);
int idx =Integer.MAX_VALUE/2;
for(int i = 0;i<len;i++){
if(S.charAt(i)==C){
idx = 0;
}
res[i] = Math.min(res[i],idx);
idx++;
}
for(int i = len-1;i>=0;i--){
if(S.charAt(i)==C){
idx = 0;
}
res[i] = Math.min(res[i],idx);
idx++;
}
return res;
}
}
```

## 113. Path Sum II

### Description

```
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
Return:
[
[5,4,11,2],
[5,8,4,5]
]
```

### Solution

```
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
helper(root, new ArrayList<>(), 0, sum, res);
return res;
}
private void helper(TreeNode root, List<Integer> temp, int runningSum, int target, List<List<Integer>> res) {
temp.add(root.val);
runningSum += root.val;
if (root.left == null && root.right == null) {
if (runningSum == target) {
res.add(new ArrayList<>(temp));
}
temp.remove(temp.size() - 1);
return;
}
if (root.left != null) {
helper(root.left, temp, runningSum, target, res);
}
if (root.right != null) {
helper(root.right, temp, runningSum, target, res);
}
temp.remove(temp.size() - 1);
}
}
```

## 129. Sum Root to Leaf Numbers

### Description

```
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
Note: A leaf is a node with no children.
Example:
Input: [1,2,3]
1
/ \
2 3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Example 2:
Input: [4,9,0,5,1]
4
/ \
9 0
/ \
5 1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
```

### Solution

```
class Solution {
int global_sum;
public int sumNumbers(TreeNode root) {
if(root==null){
return 0;
}
global_sum = 0;
helper(root, 0);
return global_sum;
}
public void helper(TreeNode root, int runningSum) {
runningSum *= 10;
runningSum += root.val;
if (root.left == null && root.right == null) {
global_sum += runningSum;
return;
}
if (root.left != null) {
helper(root.left, runningSum);
}
if (root.right != null) {
helper(root.right, runningSum);
}
}
}
```

## 1233. Remove Sub-Folders from the Filesystem

### Description

```
Given a list of folders, remove all sub-folders in those folders and return in any order the folders after removing.
If a folder[i] is located within another folder[j], it is called a sub-folder of it.
The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.
Example 1:
Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b/" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.
Example 2:
Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d/" will be removed because they are subfolders of "/a".
Example 3:
Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]
Constraints:
1 <= folder.length <= 4 * 10^4
2 <= folder[i].length <= 100
folder[i] contains only lowercase letters and '/'
folder[i] always starts with character '/'
Each folder name is unique.
```

### Solution

```
class Solution {
public List<String> removeSubfolders(String[] folder) {
Arrays.sort(folder);
List<String> result = new ArrayList<>();
for (int i = 0; i < folder.length; i++) {
String str = folder[i];
result.add(str);
String base = str + "/";
while (i + 1 < folder.length && folder[i + 1].startsWith(base)) {
i++;
}
}
return result;
}
}
```