# Posts tagged as “Hard”

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, a, a, ..., a[n-1]]` 1 time results in the array `[a[n-1], a, a, a, ..., 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 = 
Output: 
```

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);
};``````

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.val, second.val] = [second.val, first.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 && prev.val > root.val) {
if (first === null) first = prev;
second = root;
}
prev = root;
inorder(root.right, first, second, prev);
}``````

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits `1-9` must occur exactly once in each row.
2. Each of the digits `1-9` must occur exactly once in each column.
3. Each of the digits `1-9` must occur exactly once in each of the 9 `3x3` sub-boxes of the grid.

The `'.'` character indicates empty cells.

Example 1:

```Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below: ```

Constraints:

• `board.length == 9`
• `board[i].length == 9`
• `board[i][j]` is a digit or `'.'`.
• It is guaranteed that the input board has only one solution.

Idea:

```Create 3 tracking arrays:
`1 - 9 occur once in whole row, whole col, whole box.`
`[ith row][number] [ith col][number] [ith box][number]`
`ex: [ith row][N] = 1 means ith row already use number N`
DFS/Backtracking
Travese the board from left to right, row by row
Try to fill 1-9, success return,
if not success, recover data and try next element```

Solution:

``````/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function(board) {
// 1 - 9 occur once in whole row, whole col, whole box
// [ith row][number] [ith col][number] [ith box][number]
// ex: [ith row][N] = 1 means ith row already use number N
let rows = Array.from(new Array(9), () => new Array(10).fill(0));
let cols = Array.from(new Array(9), () => new Array(10).fill(0));
let boxes = Array.from(new Array(9), () => new Array(10).fill(0));

for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const c = board[i][j];
if (c !== '.') {
let num = parseInt(c);
let bx = Math.floor(j / 3);
let by = Math.floor(i / 3);
rows[i][num] = 1;
cols[j][num] = 1;
boxes[by * 3 + bx][num] = 1;
}
}
}
dfs(board, 0, 0, rows, cols, boxes);
};

function dfs(board, x, y, rows, cols, boxes) {
// exit recursion condition, reach to the end;
if (y === 9) return true;

// traverse from left to right, then next row
let nextX = (x + 1) % 9;
let nextY = nextX === 0 ? y + 1 : y;

// already has number, DFS next element
if (board[y][x] !== '.') return dfs(board, nextX, nextY, rows, cols, boxes);

// fill number from 1 - 9
for (let i = 1; i <= 9; i++) {
let bx = Math.floor(x / 3);
let by = Math.floor(y / 3);
let box_index = by * 3 + bx;
// if not breaking the following 3 rules
if (!rows[y][i] && !cols[x][i] && !boxes[box_index][i]) {
// modify, fill the number
rows[y][i] = 1;
cols[x][i] = 1;
boxes[box_index][i] = 1;
board[y][x] = i.toString();
// Try to fill next element, if success return true, or recover
if (dfs(board, nextX, nextY, rows, cols, boxes)) return true;
// recover data
board[y][x] = '.';
boxes[box_index][i] = 0;
cols[x][i] = 0;
rows[y][i] = 0;
}
}
return false;
}``````

Given a `rows x cols` binary `matrix` filled with `0`‘s and `1`‘s, find the largest rectangle containing only `1`‘s and return its area.

Example 1:

```Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.
```

Example 2:

```Input: matrix = []
Output: 0
```

Example 3:

```Input: matrix = [["0"]]
Output: 0
```

Example 4:

```Input: matrix = [["1"]]
Output: 1
```

Example 5:

```Input: matrix = [["0","0"]]
Output: 0
```

Constraints:

• `rows == matrix.length`
• `cols == matrix[i].length`
• `0 <= row, cols <= 200`
• `matrix[i][j]` is `'0'` or `'1'`.

Idea:

Dynamic Programing

• Time complexity: O(mn)
• Space complexity: O(mn)
``````dp[i][j] := max length of all 1s ends with col j at row i.
dp[i][j] = 0 if matrix[i][j] == "0"
dp[i][j] = dp[i][j-1] + 1 if matrix[i][j] == "1"

Then loop through matrix
Min Width(has "1"):= Math.min(width, dp[curRow][j]);
Min Height(has "1"):= curRow - i + 1;
MaxArea = Min Width * Min Height``````

Solution:

``````/**
* @param {character[][]} matrix
* @return {number}
*/
var maximalRectangle = function(matrix) {
let row = matrix.length;
if (row === 0) return 0;
let col = matrix.length;

// dp[i][j] := max length of all 1s ends with col j at row i.
// dp[i][j] = 0 if matrix[i][j] == "0"
// dp[i][j] = dp[i][j-1] + 1 if matrix[i][j] == "1"
let dp = Array.from(new Array(row), () => new Array(col));
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
if (matrix[i][j] === "1") {
dp[i][j] = j === 0 ? 1 : dp[i][j - 1] + 1;
} else {
dp[i][j] = 0;
}
}
}

let maxArea = 0;
for (let i = 0; i < row; i++) {
for (let j = 0; j < col; j++) {
let width = Infinity;
for (let curRow = i; curRow < row; curRow++) {
width = Math.min(width, dp[curRow][j]);
if (width === 0) break;
let height = curRow - i + 1;
maxArea = Math.max(maxArea, width * height);
}
}
}
return maxArea;
};``````

Given an input string (`s`) and a pattern (`p`), implement regular expression matching with support for `'.'` and `'*'` where:

• `'.'` Matches any single character.​​​​
• `'*'` Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Example 1:

```Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
```

Example 2:

```Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
```

Example 3:

```Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
```

Example 4:

```Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
```

Example 5:

```Input: s = "mississippi", p = "mis*is*p*."
Output: false
```

Constraints:

• `0 <= s.length <= 20`
• `0 <= p.length <= 30`
• `s` contains only lowercase English letters.
• `p` contains only lowercase English letters, `'.'`, and `'*'`.
• It is guaranteed for each appearance of the character `'*'`, there will be a previous valid character to match.

Idea:

Backtracking / Depth-first search (DFS)

There are two normal cases without consideration of `*`:

`1. s === p2. s !== p, but p === '.' and s is any character`

And then let’s consider how to handle the pattern `*`:

If we have a `x*` in the pattern(x stands for any character), we may ignore this part of
the pattern, or delete a matching character in the text

```// no match: aa , c*                || match: aaa , a*
(isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p)));```

According to these analyses, we can construct a depth-first search algorithm, it’s a recursive algorithm.

Solution:

``````/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
let sLen = s.length;
let pLen = p.length;
if (pLen === 0) return sLen === 0;
let first_match = (sLen !== 0 && (p === s || p === '.'));

// If a star is present in the pattern, it will be in the
// second position p. Then, we may ignore this part of
// the pattern, or delete a matching character in the text.
// If we have a match on the remaining strings after any of
// these operations, then the initial inputs matched.
if (pLen >= 2 && p === '*') {
// no match:  aa , c*       ||      match:       aaa , a*
return (isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p)));
} else {
return first_match && isMatch(s.substring(1), p.substring(1));
}
};
``````

You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.

Example 1:

```Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
```

Example 2:

```Input: lists = []
Output: []
```

Example 3:

```Input: lists = [[]]
Output: []
```

Constraints:

• `k == lists.length`
• `0 <= k <= 10^4`
• `0 <= lists[i].length <= 500`
• `-10^4 <= lists[i][j] <= 10^4`
• `lists[i]` is sorted in ascending order.
• The sum of `lists[i].length` won’t exceed `10^4`.

Idea:

Divide and Conquer

Solution:

``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
return merge(lists, 0, lists.length - 1);
};

function merge(lists, l , r) {
if (lists.length === 0) return null;
if (l === r) return lists[l];
let mid = Math.floor((l + r) / 2);
let l1 = merge(lists, l, mid);
let l2 = merge(lists, mid + 1, r);
return mergeTwoLists(l1, l2);
}

var mergeTwoLists = function(l1, l2) {
// If one of the list is empty, return the other one.
if (l1 === null) {
return l2;
}
if (l2 === null) {
return l1;
}

// The smaller one becomes the head.
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};``````

Given a string `s` representing an expression, implement a basic calculator to evaluate it.

Example 1:

```Input: s = "1 + 1"
Output: 2
```

Example 2:

```Input: s = " 2-1 + 2 "
Output: 3
```

Example 3:

```Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
```

Constraints:

• `1 <= s.length <= 3 * 105`
• `s` consists of digits, `'+'``'-'``'('``')'`, and `' '`.
• `s` represents a valid expression.

Solution:

``````/**
* @param {string} s
* @return {number}
*/
var calculate = function(s) {
let len = s.length;
if (len === 0) return 0;
let stack = [];
let res = 0;
let sign = 1;

// remove space
s.replace(" ", "");
for (let i = 0; i < len; i++) {
let n = s.charAt(i);
if (!isNaN(parseInt(n))) {
let cur = parseInt(n);
while (i + 1 < len && !isNaN(parseInt(s.charAt(i + 1)))) {
cur = cur * 10 + parseInt(s.charAt(i + 1));
i++;
}
res += cur * sign;
} else if (n === '-') {
sign = -1;
} else if (n === '+') {
sign = 1;
} else if (n === '(') {
stack.push(res);
res = 0;
stack.push(sign);
sign = 1;
} else if (n === ')') {
res = res * stack.pop() + stack.pop();
}
}

return res;
};``````

Given a string containing just the characters `'('` and `')'`, find the length of the longest valid (well-formed) parentheses substring.

Example 1:

```Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
```

Example 2:

```Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
```

Example 3:

```Input: s = ""
Output: 0
```

Constraints:

• `0 <= s.length <= 3 * 104`
• `s[i]` is `'('`, or `')'`.

Solution:

``````/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
let stack = [];
// track the start position
let start = 0;
let ans = 0;

for (let i = 0; i < s.length; i++) {
// open parenthese '(' push that index of '('
if (s[i] === '(') {
stack.push(i);
} else {
// if stack empty => invalid, start from i + 1
if (stack.length === 0) {
start = i + 1;
} else {
stack.pop();
// empty stack: calculate [start...i]
// or Not empty stack calculate [index of '('...i]
// store the max length
ans = Math.max(ans, stack.length === 0 ? i - start + 1 : i - stack[stack.length - 1]);
}
}
}
return ans;
};``````

Given `n` non-negative integers representing an elevation map where the width of each bar is `1`, compute how much water it can trap after raining.

Example 1:

```Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
```

Example 2:

```Input: height = [4,2,0,3,2,5]
Output: 9
```

Constraints:

• `n == height.length`
• `0 <= n <= 3 * 104`
• `0 <= height[i] <= 105`

Idea:

Two pointers traversal

Solution:

``````/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
let res = 0;
const n = height.length;
let l = 0;
let r = n - 1;

while (l < r) {
let min = Math.min(height[l], height[r]);

// if left side is smaller
if (min === height[l]) {
l++;
while (l < r && height[l] < min) {
res += min - height[l++];
}
} else { // right side is smaller
r--;
while (l < r && height[r] < min) {
res += min - height[r--];
}
}
}
return res;
};``````