## LeetCode 226. Invert Binary Tree

Problem:

Invert a binary tree.

```     4
/   \
2     7
/ \   / \
1   3 6   9```

to

```     4
/   \
7     2
/ \   / \
9   6 3   1```

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

Solution:

The famous Google interview question for Max Howell ROFL.

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
```

## LeetCode 213. House Robber II

Problem:

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Solution:

```public class Solution {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
}

private int rob(int[] nums, int low, int high) {
int include = 0, exclude = 0;
for (int i = low; i <= high; i++) {
int tmp = include;
include = exclude + nums[i];
exclude = Math.max(exclude, tmp);
}
return Math.max(include, exclude);
}
}
```

## LeetCode 337. House Robber III

Problem:

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:

```     3
/ \
2   3
\   \
3   1
```

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

```     3
/ \
4   5
/ \   \
1   3   1
```

Maximum amount of money the thief can rob = 4 + 5 = 9.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution:

DP, at first I just did it recursively and it was AWFUL.

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
HashMap<TreeNode, Integer> map = new HashMap<>();

public int rob(TreeNode root) {
if (root == null) return 0;
if (map.containsKey(root)) return map.get(root);
int rob0 = robNot(root);
int rob1 = robYes(root);
int max = Math.max(rob0, rob1);
map.put(root, max);
return max;
}

private int robYes(TreeNode root) {
if (root == null) return 0;
return root.val + robNot(root.left) + robNot(root.right);
}

private int robNot(TreeNode root) {
if (root == null) return 0;
return rob(root.left) + rob(root.right);
}
}
```

## LeetCode 238. Product of Array Except Self

Problem:

Given an array of n integers where n > 1, `nums`, return an array `output` such that `output[i]` is equal to the product of all the elements of`nums` except `nums[i]`.

Solve it without division and in O(n).

For example, given `[1,2,3,4]`, return `[24,12,8,6]`.

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Solution:

```public class Solution {
public int[] productExceptSelf(int[] nums) {
int[] output = new int[nums.length];
output[0] = 1;
for (int i = 1; i < nums.length; i++) {
output[i] = output[i-1] * nums[i-1];
}
int right = 1;
for (int i = nums.length - 1; i >= 0; i--) {
output[i] *= right;
right *= nums[i];
}
return output;
}
}
```

## LeetCode 279. Perfect Squares

Problem:

Given a positive integer n, find the least number of perfect square numbers (for example, `1, 4, 9, 16, ...`) which sum to n.

For example, given n = `12`, return `3` because `12 = 4 + 4 + 4`; given n = `13`, return `2` because `13 = 4 + 9`.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Solution:

DP

```public class Solution {

public int numSquares(int n) {
int[] least = new int[n+1];
int root = 0;
for (int i = 0; i <= n; i++) {
if (i == root * root) {
least[i] = 1;
root++;
continue;
}
int min = Integer.MAX_VALUE;
for (int j = 1; j * j < i; j++)
min = Math.min(least[j*j] + least[i-j*j], min);
least[i] = min;
}
return least[n];
}
}
```

## LeetCode 382. Linked List Random Node

Problem:

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

```// Init a singly linked list [1,2,3].

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();```

Solution:

Not using Reservoir Sampling, but I found this post that describes the process.

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {

int count;

Note that the head is guaranteed to be not null, so it contains at least one node. */
count = 0;
while (current != null) {
current = current.next;
count++;
}
}

/** Returns a random node's value. */
public int getRandom() {
Random random = new Random();
int rnd = random.nextInt(count);
for (int i = 0; i < rnd; i++)
current = current.next;
return current.val;
}
}

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/
```

## LeetCode 59. Spiral Matrix II

Problem:

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = `3`,

You should return the following matrix:

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

Solution:

Just like Spiral Matrix problem.

```public class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
if (n == 0) return result;
int x = n, y = n;
int row = 0, col = -1;
int num = 0;
while (true) {
for (int i = 0; i < x; i++)
result[row][++col] = ++num;
if (--y == 0) break;
for (int i = 0; i < y; i++)
result[++row][col] = ++num;
if (--x == 0) break;
for (int i = 0; i < x; i++)
result[row][--col] = ++num;
if (--y == 0) break;
for (int i = 0; i < y; i++)
result[--row][col] = ++num;
if (--x == 0) break;
}
return result;
}
}
```

## LeetCode 172. Factorial Trailing Zeroes

Problem:

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution:

```public class Solution {
public int trailingZeroes(int n) {
int deg = 5;
int div = n/deg;
int result = div;
while(div > 1) {
deg *= 5;
div  = n/deg;
result += div;
}
return result;
}
}
```

## LeetCode 39. Combination Sum

Problem:

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set `[2, 3, 6, 7]` and target `7`,
A solution set is:

```[
[7],
[2, 2, 3]
]```

Solution:

Should’ve used DP but whatever I passed.

```public class Solution {
List<List<Integer>> result;
int[] candidates;
int target;

public List<List<Integer>> combinationSum(int[] candidates, int target) {
result = new ArrayList<List<Integer>>();
this.candidates = candidates;
this.target = target;
List<Integer> option = new ArrayList<Integer>();
tryOption(option, 0);
return result;
}

private void tryOption(List<Integer> option, int sum) {
if (sum > target) return;
if (sum == target) {
List<Integer> copy = new ArrayList<Integer>(option);