# Posts published in “Difficulty”

Suppose an array of length `n` sorted in ascending order is rotated between `1` and `n` times. For example, the array `nums = [0,1,4,4,5,6,7]` might become:

• `[4,5,6,7,0,1,4]` if it was rotated `4` times.
• `[0,1,4,4,5,6,7]` if it was rotated `7` times.

Notice that rotating an array `[a[0], a[1], a[2], ..., a[n-1]]` 1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`.

Given the sorted rotated array `nums` that may contain duplicates, return the minimum element of this array.

Example 1:

```Input: nums = [1,3,5]
Output: 1
```

Example 2:

```Input: nums = [2,2,2,0,1]
Output: 0
```

Constraints:

• `n == nums.length`
• `1 <= n <= 5000`
• `-5000 <= nums[i] <= 5000`
• `nums` is sorted and rotated between `1` and `n` times.

Idea:

Divide and Conquer

Solution:

``````/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
return searchMin(nums, 0, nums.length - 1);
};

function searchMin(nums, l, r) {
// exit recursion:
// only one or two elements in the array
if (l + 1 >= r)
return Math.min(nums[l], nums[r]);
// this array is sorted
if (nums[l] < nums[r])
return nums[l];

let mid = l + Math.floor((r - l) / 2);
return Math.min(searchMin(nums, l , mid), searchMin(nums, mid + 1, r));
}``````

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

```Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
```

Example 2:

```Input: root = []
Output: []
```

Example 3:

```Input: root = [1]
Output: [1]
```

Example 4:

```Input: root = [1,2]
Output: [1,2]
```

Constraints:

• The number of nodes in the tree is in the range `[0, 104]`.
• `-1000 <= Node.val <= 1000`

Idea: (Recursion)

```We can encodes the tree to a single string.
// # indicates reach to the leave
Convert above tree to 12##34##56## ```

Time Complexity O(n)

Solution:

``````/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/

/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function(root) {
let res = [];
serializer(root, res);
return res.join(",");
};

var serializer = function(root, output) {
if (root === null) {
output.push("#");
return;
}
output.push(root.val);
serializer(root.left, output);
serializer(root.right, output);
}

// Decodes your encoded data to tree.
var deserialize = function(data) {
data = data.split(",");
let index = 0;

function deserializer(data) {
if(index > data.length || data[index] === "#") {
return null;
}
let root = new TreeNode(parseInt(data[index]));
index++;
root.left = deserializer(data);
index++;
root.right = deserializer(data);
return root;
}
return deserializer(data);
};``````

Given an integer `n`, return the least number of perfect square numbers that sum to `n`.

perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, `1``4``9`, and `16` are perfect squares while `3` and `11` are not.

Example 1:

```Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
```

Example 2:

```Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
```

Constraints:

• `1 <= n <= 104`

Idea: (Dynamic Programing)

• Time complexity: O(n * sqrt(n))
• Space complexity: O(n)
```dp[i] := return the least number of perfect square numbers that sum to i.
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} and 1 <= j * j <= i ex:[1, 4, 6, 9…]
// For example:
dp[5] = min{
dp[5 – 2*2] + 1 = dp[1] + 1 = (dp[1 – 1*1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1*1] + 1 = dp[4] + 1 = (dp[4 – 1*1] + 1) + 1 = dp[3] + 2 =
dp[3 – 1*1] + 1 + 2 = dp[2 - 1*1] + 1 + 3 = dp[1 - 1*1] + 1 + 4 =
dp[0] + 5 = 5
};
so dp[5] = 2```

Solution:

``````/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
// Important: n + 1 length because we use dp[0]
let dp = new Array(n + 1).fill(Number.MAX_VALUE);
dp[0] = 0;
for (let i = 1; i <= n; i++)
for(let j = 1; j * j <= i; j++)
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);

return dp[n];
};``````

Given an integer array `nums` sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

```Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
```

Example 2:

```Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
```

Constraints:

• `1 <= nums.length <= 104`
• `-104 <= nums[i] <= 104`
• `nums` is sorted in non-decreasing order.

Solution 1: (Quick Sort)

``````/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function(nums) {
nums = nums.map(num => num * num);
quickSort(nums, 0, nums.length - 1);
return nums;
};

function quickSort(nums, left, right) {
let index;
if (nums.length > 1) {
// index returned from partition
index = partition(nums, left, right);
// more elements on the left side of the pivot
if (left < index - 1)
quickSort(nums, left, index - 1);
// more elements on the right side of the pivot
if (index < right)
quickSort(nums, index, right);
}
// you can return or not return,
// since we change nums, no need to return
// return nums;
}

function partition(nums, start, end) {
let l = start, r = end;
let mid = Math.floor((start + end) / 2);
let pivot = nums[mid];
// Important: l <= r not l < r
while (l <= r) {
while(nums[l] < pivot)
l++;
while(nums[r] > pivot)
r--;
if (l <= r) {
// swap
[nums[l], nums[r]] = [nums[r], nums[l]];
l++;
r--;
}
}
return l;
}``````

Solution 2: (Merge Sort)

``````/**
* @param {number[]} nums
* @return {number[]}
*/
var sortedSquares = function(nums) {
nums = nums.map(num => num * num);
let temp = [];
mergeSort(nums, 0, nums.length - 1, temp);
return nums;
};

function mergeSort(nums, start, end, temp) {
if (start >= end) return;
let mid =  Math.floor((start + end) / 2);
mergeSort(nums, start, mid, temp);
mergeSort(nums, mid + 1, end, temp);
merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
let mid =  Math.floor((start + end) / 2);
let l_index = start;
let r_index = mid + 1;
let index = start;
while (l_index <= mid && r_index <= end) {
if (nums[l_index] < nums[r_index]) {
temp[index++] = nums[l_index++];
} else {
temp[index++] = nums[r_index++];
}
}
while (l_index <= mid) {
temp[index++] = nums[l_index++];
}
while (r_index <= end) {
temp[index++] = nums[r_index++];
}
for (let i = 0; i <= end; i++)
nums[i] = temp[i];
}``````

Given an `m x n` grid of characters `board` and a string `word`, return `true` if `word` exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
```

Example 2:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
```

Example 3:

```Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
```

Constraints:

• `m == board.length`
• `n = board[i].length`
• `1 <= m, n <= 6`
• `1 <= word.length <= 15`
• `board` and `word` consists of only lowercase and uppercase English letters.

Idea:

DFS

Solution:

``````/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
for (let x = 0; x < board[0].length; x++)
for (let y = 0; y < board.length; y++)
if (dfs(board, word, 0, x, y)) return true;
return false;
};

function dfs(board, word, i, x, y) {
// exit recursion:
if (x < 0 || y < 0 || x >= board[0].length || y >= board.length || word[i] !== board[y][x])
return false;
// found the last letter
if (i === word.length - 1)
return true;

let cur = board[y][x];
// mark it 0 means already visit
board[y][x] = 0;
let found = dfs(board, word, i + 1, x + 1, y) ||
dfs(board, word, i + 1, x - 1, y) ||
dfs(board, word, i + 1, x, y + 1) ||
dfs(board, word, i + 1, x, y - 1);
// recover
board[y][x] = cur;
return found;
}``````

There are `N` rooms and you start in room `0`.  Each room has a distinct number in `0, 1, 2, ..., N-1`, and each room may have some keys to access the next room.

Formally, each room `i` has a list of keys `rooms[i]`, and each key `rooms[i][j]` is an integer in `[0, 1, ..., N-1]` where `N = rooms.length`.  A key `rooms[i][j] = v` opens the room with number `v`.

Initially, all the rooms start locked (except for room `0`).

You can walk back and forth between rooms freely.

Return `true` if and only if you can enter every room.

Example 1:

```Input: [[1],[2],[3],[]]
Output: true
Explanation:
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.
```

Example 2:

```Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.
```

Note:

1. `1 <= rooms.length <= 1000`
2. `0 <= rooms[i].length <= 1000`
3. The number of keys in all rooms combined is at most `3000`.

Idea:

DFS

Solution:

``````/**
* @param {number[][]} rooms
* @return {boolean}
*/
var canVisitAllRooms = function(rooms) {
let visited = [];
dfs(rooms, visited, 0);
return visited.length === rooms.length;
};

function dfs(rooms, visited, roomNum){
// exit recursion:
if (visited.includes(roomNum)) return;

visited.push(roomNum);
// possible solution
for (let key of rooms[roomNum])
dfs(rooms, visited, key);
}``````

Given an integer array `nums` where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

```Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

```

Example 2:

```Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.
```

Constraints:

• `1 <= nums.length <= 104`
• `-104 <= nums[i] <= 104`
• `nums` is sorted in a strictly increasing order.

Idea:

Recursion + Divide and Conquer

Time complexity: O(n)
Space complexity: O(logn)

Solution:

``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
return createBST(nums, 0, nums.length - 1);
};

function createBST(nums, l, r) {
// exit recursion condition
if (l > r) return null;

let mid = l + Math.floor((r - l) / 2);
let root = new TreeNode(nums[mid]);
root.left = createBST(nums, l, mid - 1);
root.right = createBST(nums, mid + 1, r);
return root;
}``````

You are given the `root` of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Follow up: A solution using `O(n)` space is pretty straight forward. Could you devise a constant space solution?

Example 1:

```Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
```

Example 2:

```Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
```

Constraints:

• The number of nodes in the tree is in the range `[2, 1000]`.
• `-231 <= Node.val <= 231 - 1`

Idea:

Because inorder traverse BST, all values are sorted. We can use inorder traversal to find two nodes that have prev.val > root. val and swap them

Time complexity: O(n)
Space complexity: O(height)

Solution:

``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {void} Do not return anything, modify root in-place instead.
*/
var recoverTree = function(root) {
// javascript can't pass value by reference
// so pass array object by reference
let first = [null];
let second = [null];
let prev = [null];
inorder(root, first, second, prev);
[first[0].val, second[0].val] = [second[0].val, first[0].val];
};

function inorder(root, first, second, prev) {
// Because inorder traverse BST, all values are sorted.
// Using inorder traversal to find two nodes that have prev.val > root.val
if (root === null) return;
inorder(root.left, first, second, prev);
if (prev[0] && prev[0].val > root.val) {
if (first[0] === null) first[0] = prev[0];
second[0] = root;
}
prev[0] = root;
inorder(root.right, first, second, prev);
}``````

Given the `head` of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in `O(n logn)` time and `O(1)` memory (i.e. constant space)?

Example 1:

```Input: head = [4,2,1,3]
Output: [1,2,3,4]
```

Example 2:

```Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
```

Example 3:

```Input: head = []
Output: []
```

Constraints:

• The number of nodes in the list is in the range `[0, 5 * 104]`.
• `-105 <= Node.val <= 105`

Idea:

Merge Sort (use slow and fast pointer to find the middle of the linked list and split them)

Time Complexity: O(nlogn)

Solution:

``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/
// empty or one node
let right = sortList(mid);
return merge(left, right);
};

function merge(list1, list2) {
let tail = new ListNode();
while (list1 !== null && list2 !== null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
tail = tail.next;
} else {
tail.next = list2;
list2 = list2.next;
tail = tail.next;
}
}
tail.next = (list1 !== null) ? list1 : list2;
};

while (fast !== null && fast.next !== null) {
slow = slow.next
fast = fast.next.next;
}
// !!!Important here:
// disconnect, split them into two lists
return secondHalf;
}``````

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`

Idea:

Use Merge Sort Template

Solution:

``````/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArray = function(nums) {
if (nums === null || nums.length === 0) return;
let temp = [];
mergeSort(nums, 0, nums.length - 1, temp);
return nums;
};

function mergeSort(nums, start, end, temp) {
if (start >= end) return;
// deal with first half
mergeSort(nums, start, Math.floor((start + end) / 2), temp);
// deal with second half
mergeSort(nums, Math.floor((start +end) / 2) + 1, end, temp);
// merge
merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
let mid = Math.floor((start + end) / 2);
let l_index = start;
let r_index = mid + 1;
let index = start;
while (l_index <= mid && r_index <= end) {
if (nums[l_index] < nums[r_index]) {
temp[index++] = nums[l_index++];
} else {
temp[index++] = nums[r_index++];
}
}
while (l_index <= mid) {
temp[index++] = nums[l_index++];
}
while (r_index <= end) {
temp[index++] = nums[r_index++];
}
for (let i = start; i <= end; i++) {
nums[i] = temp[i];
}
}``````