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.
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);
}
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
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[0].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 === p 2. 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[0] === s[0] || p[0] === '.'));
// If a star is present in the pattern, it will be in the
// second position p[1]. 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[1] === '*') {
// 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));
}
};
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;
};
