## 1020. Partition Array Into Three Parts With Equal Sum

Given an array `A` of integers, return `true` if and only if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes `i+1 < j` with `(A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])`

Example 1:

Input:

```[0,2,1,-6,6,-7,9,1,2,0,1]
```

Output:

```true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
```

Example 2:

Input:

```[0,2,1,-6,6,7,9,-1,2,0,1]
```

Output:

```false
```

Example 3:

Input:

```[3,3,6,5,-2,2,5,1,-9,4]
```

Output:

```true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
```

Note:

1. `3 <= A.length <= 50000`
2. `-10000 <= A[i] <= 10000`
```class Solution {

/**
* @param Integer[] \$A
* @return Boolean
*/
function canThreePartsEqualSum(\$A) {
\$mean = array_sum(\$A) / 3;
if (floor(\$mean) != \$mean){
return false;
}

\$count  = 0;
\$sum = 0;
\$i = 0;
while (\$i < count(\$A)){
\$sum += \$A[\$i];
\$i ++;
if(\$sum == \$mean){
\$count ++;
\$sum = 0;
}
}
return \$count == 3;
}
}```

## 1022. Smallest Integer Divisible by K

Given a positive integer `K`, you need find the smallest positive integer `N` such that `N` is divisible by `K`, and `N` only contains the digit 1.

Return the length of `N`.  If there is no such `N`, return -1.

Example 1:

Input:

``` 1
```

Output:

``` 1
```

Explanation:

` The smallest answer is N = 1, which has length 1.`

Example 2:

Input:

``` 2
```

Output:

``` -1
```

Explanation:

` There is no such positive integer N divisible by 2.`

Example 3:

Input:

``` 3
```

Output:

``` 3
```

Explanation:

` The smallest answer is N = 111, which has length 3.`

Note:

• `1 <= K <= 10^5`

#### Thoughts:

Two tricky parts.

1. `\$n = (\$n * 10 +1) % \$K;`Suppose r = (aK + b) when r > K, next r supposed to be 10r+1 = 10aK + 10b + 1. Since 10aK is divisible by K, we just need to consider 10b + 1. b is r % K, so we can update r = r % K. [By https://leetcode.com/wangqiuc/]
2. The exit condition for loop, \$n <= \$K, actually, there always exist an answer, we can use while true instead.

Proof  [By https://leetcode.com/starsthu2016/]

It is obvious that if K is the multiple of 2 or multiple of 5, N is definitely not multiple of K because the ones digit of N is 1. Thus, return -1 for this case.

If K is neither multiple of 2 nor multiple of 5, we have this theorem.

Theorem: there must be one number from the K-long candidates list [1, 11, 111, …, 111..111(with K ones)], which is the multiple of K.

Why? Let’s think in the opposite way. Is it possible that none of the K candidates is the multiple of K?

If true, then the module of these K candidate numbers (mod K) must be in [1, .., K-1] (K-1 possible module values). Thus, there must be 2 candidate numbers with the same module. Let’s denote these two numbers as N_i with i ones, and N_j with j ones and i<j.

Thus N_j-N_i = 1111…1000…0 with (j-i) ones and i zeros. N_j-N_i = 111..11 (j-i ones) * 100000..000 (i zeros). We know that N_i and N_j have the same module of K. Then N_j-N_i is the multiple of K. However, 100000..000 (i zeros) does not contain any factors of K (K is neither multiple of 2 nor multiple of 5). Thus, 111..11 (j-i ones) is the multiple of K. This is contradictory to our assumption that all K candidates including 111..11 (j-i ones) are not multiple of K.

Finally, we know that there is at least one number, from the first K candidates, which is the multiple of K.

```class Solution {

/**
* @param Integer \$K
* @return Integer
*/
function smallestRepunitDivByK(\$K) {
if(\$K % 2 == 0 || \$K % 5 == 0){
return -1;
}
\$n = 1;
\$r = 1;
while(\$n <= \$K ){
if(\$n % \$K == 0){
return  \$r;
}
\$n = (\$n * 10 +1) % \$K;
\$r ++;
}
return -1;
}
}```

## 1006. Clumsy Factorial

Normally, the factorial of a positive integer `n` is the product of all positive integers less than or equal to `n`.  For example, `factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1`.

We instead make a clumsy factorial: using the integers in decreasing order, we swap out the multiply operations for a fixed rotation of operations: multiply (*), divide (/), add (+) and subtract (-) in this order.

For example, `clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1`.  However, these operations are still applied using the usual order of operations of arithmetic: we do all multiplication and division steps before any addition or subtraction steps, and multiplication and division steps are processed left to right.

Additionally, the division that we use is floor division such that `10 * 9 / 8` equals `11`.  This guarantees the result is an integer.

`Implement the clumsy` function as defined above: given an integer `N`, it returns the clumsy factorial of `N`.

Example 1:

Input:

```4
```

Output:

``` 7
```

Explanation:

``` 7 = 4 * 3 / 2 + 1
```

Example 2:

Input:

```10
```

Output:

```12
```

Explanation:

```12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1
```

Note:

1. `1 <= N <= 10000`
2. `-2^31 <= answer <= 2^31 - 1`  (The answer is guaranteed to fit within a 32-bit integer.)

#### Thoughts:

• Split into chunks of size 4, then deal with case 3 or 2 or 1
• The first chunk has a positive sign, then negative starting from the second trunk, including the remaining (3, 2, or 1) part
• if n < 4, the sign is positive

```class Solution {

/**
* @param Integer \$N
* @return Integer
*/
function clumsy(\$n) {
\$r = 0;
\$f = 0;
\$first_positive_chunk_set = false;

if(\$n >= 4){
\$r = floor(\$n*(\$n-1)/(\$n-2)) + \$n-3;
\$n -= 4;
\$first_positive_chunk_set = true;
}

while(floor(\$n / 4) >= 1){
\$r -= floor(\$n*(\$n-1)/(\$n-2)) - \$n+3;
\$n -= 4;
}
if(\$n >= 3){
\$r -= floor(\$n*(\$n-1)/(\$n-2)) ;
\$n -= 3;
}
if(\$n >= 2){
\$r -= \$n*(\$n-1) ;
\$n -= 2;
}
if(\$n >= 1){
\$r -= \$n ;
\$n -= 1;
}
return \$first_positive_chunk_set?\$r:-\$r;
}
}```

#### Another Solution Inspired by Other

• Base on math
• Other than that(short), this solution is hard to read and understand.
```class Solution {

/**
* @param Integer \$N
* @return Integer
*/
function clumsy(\$n) {
if (\$n<5){
return  \$n+3*(\$n>2);
}
return \$n+2-3*(\$n%4==3)-(\$n%4==0);
}
}```

## 1007. Minimum Domino Rotations For Equal Row

In a row of dominoes, `A[i]` and `B[i]` represent the top and bottom halves of the `i`-th domino.  (A domino is a tile with two numbers from 1 to 6 – one on each half of the tile.)

We may rotate the `i`-th domino, so that `A[i]` and `B[i]` swap values.

Return the minimum number of rotations so that all the values in `A` are the same, or all the values in `B` are the same.

If it cannot be done, return `-1`.

Example 1:

Input:

```A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]
```

Output:

```2
```

Explanation:

```The first figure represents the dominoes as given by A and B: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.
```

Example 2:

Input:

```A = [3,5,1,2,3], B = [3,6,3,3,4]
```

Output:

```-1
```

Explanation:

```In this case, it is not possible to rotate the dominoes to make one row of values equal.
```

Note:

1. `1 <= A[i], B[i] <= 6`
2. `2 <= A.length == B.length <= 20000`

#### Thoughts:

• Two possible values, A[0] and B[0]
• For each possible value, and foreach index, if one doesn’t have while the other does add 1 to counter
• There are two counters for each possible values, {B->A, A->B}
• Return the best result

The speaking of domino’s top and bottom is misleading, no domino has the same value for top and bottom. Why not just say a single digit number?

```class Solution {

/**
* @param Integer[] \$A
* @param Integer[] \$B
* @return Integer
*/
function minDominoRotations(\$A, \$B) {

\$p = [];      // Possible Values
\$p[] = \$A[0]; // Either First elem if A
\$p[] = \$B[0]; // Either First elem of B
\$r = [];      // List of mins

// Foreach Possible Values
foreach(\$p as \$s){
\$x = 0;   // Counter, swap B to match A's Value
\$y = 0;   // Counter, swap A to match B's Value
\$nf = false;    // For a possible value, not found both Swap A to B and B to A
for(\$i = 0;\$i < count(\$A); \$i ++){
if(\$s == \$A[\$i] && \$s !== \$B[\$i]){
\$y ++;
} elseif (\$s == \$B[\$i] && \$s !== \$A[\$i]){
\$x ++;
} else if(\$s !== \$A[\$i] && \$s !== \$B[\$i]) {
// If possible value not found in either array, move to next possible value.
\$nf = true;
break;
}

}

if(!\$nf){
// If found
if(\$x == 0 || \$y ==0){
// O is the best, no need to continue
return 0;
}
// Otherwise push the best counter result to array
\$r[] = min(\$x, \$y);
}

}
// When all possible values are no longer possible :(
if(empty(\$r)){
return -1;
}
// Otherwise return the best result
return min(\$r);
}
}```

## 154. Find Minimum in Rotated Sorted Array II

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]`).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input:

``` [1,3,5]
```

Output:

` 1`

Example 2:

Input:

``` [2,2,2,0,1]
```

Output:

` 0`

Note:

#### Thoughts:

• try binary search first, then go through the  ambiguous sections one by one.
My First Draft:
```class Solution {

/**
* @param Integer[] \$nums
* @return Integer
*/
function findMin(\$nums) {
\$last = count(\$nums)-1;
\$first = 0;
\$mid = floor((\$last + \$first) /2);
\$min = null;
while(\$nums[\$first] > \$nums[\$mid] xor \$nums[\$mid] > \$nums[\$last]){
if(\$nums[\$first] > \$nums[\$mid]){
\$last = \$mid;
\$mid = floor((\$last + \$first) /2);
} else {
\$first = \$mid +1;
\$mid = floor((\$last + \$first) /2);
}
}
if(\$first == \$last){
return \$nums[\$last];
} else {
for(\$min = \$nums[\$first];\$first <= \$last;\$first++){
if(\$nums[\$first] < \$min){
\$min = \$nums[\$first];
}
}

}
return \$min;
}

}```

sheehan‘s pretty solution:
```class Solution {
public:
int findMin(vector<int> &num) {
int lo = 0;
int hi = num.size() - 1;
int mid = 0;

while(lo < hi) {
mid = lo + (hi - lo) / 2;

if (num[mid] > num[hi]) {
lo = mid + 1;
}
else if (num[mid] < num[hi]) {
hi = mid;
}
else { // when num[mid] and num[hi] are same
hi--;
}
}
return num[lo];
}
};```

## 181. Employees Earning More Than Their Managers

The `Employee` table holds all employees including their managers. Every employee has an Id, and there is also a column for the manager Id.
```+----+-------+--------+-----------+
| Id | Name  | Salary | ManagerId |
+----+-------+--------+-----------+
| 1  | Joe   | 70000  | 3         |
| 2  | Henry | 80000  | 4         |
| 3  | Sam   | 60000  | NULL      |
| 4  | Max   | 90000  | NULL      |
+----+-------+--------+-----------+
```

Given the `Employee` table, write a SQL query that finds out employees who earn more than their managers. For the above table, Joe is the only employee who earns more than his manager.

```+----------+
| Employee |
+----------+
| Joe      |
+----------+
```

#### Thoughts:

Self  Join, nothing special

```# Write your MySQL query statement below
SELECT e1.Name as Employee FROM Employee e1  LEFT JOIN Employee e2 on e2.id =  e1.ManagerId WHERE e2.Salary < e1.Salary;```

## 104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree `[3,9,20,null,null,15,7]`,

```    3
/ \
9  20
/  \
15   7```

return its depth = 3.

#### Thought:

Nothing special but..

I’m using Java this time..

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
return maxDepthHelper(root, 0);
}
public int maxDepthHelper(TreeNode node, int depth) {
if(node != null){
return Math.max(maxDepthHelper(node.left, depth+1)
, maxDepthHelper(node.right, depth+1));
}
return depth;
}
}```

## 807. Max Increase to Keep City Skyline

In a 2 dimensional array `grid`, each value `grid[i][j]` represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.

At the end, the “skyline” when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city’s skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.

What is the maximum total sum that the height of the buildings can be increased?

Example:

Input:

``` grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
```

Output:

``` 35
```

Explanation:

```
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]

The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]

```

Notes:

• `1 < grid.length = grid[0].length <= 50`.
• All heights `grid[i][j]` are in the range `[0, 100]`.
• All buildings in `grid[i][j]` occupy the entire grid cell: that is, they are a `1 x 1 x grid[i][j]` rectangular prism.

#### Thoughts;

1. Vertical & Horizontal  scan, generate skyline view array
2. Max increment = min(vertical, horizontal).
3. Result = Sum (each max increment)

```class Solution {

/**
* @param Integer[][] \$grid
* @return Integer
*/
function maxIncreaseKeepingSkyline(\$grid) {
if(empty(\$grid)){
return 0;
}
\$result = 0;
\$h = array_fill(0,count(\$grid), 0);
\$v = array_fill(0,count(\$grid[0]), 0);

for(\$i = 0; \$i < count(\$grid); \$i ++){
\$h[\$i] = max(\$grid[\$i]);
for(\$j = 0; \$j < count(\$grid[0]); \$j ++){
if(\$grid[\$i][\$j] > \$v[\$j]){
\$v[\$j] = \$grid[\$i][\$j];
}
}
}

for(\$i = 0; \$i < count(\$grid); \$i ++){
for(\$j = 0; \$j < count(\$grid[0]); \$j ++){
\$max = min(\$h[\$i], \$v[\$j]);
\$result += \$max - \$grid[\$i][\$j];
}
}
return \$result;
}
}```