/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let l = 0;
let r = numbers.length - 1;
while (l < r) {
let sum = numbers[l] + numbers[r];
if (sum === target) break;
else if (sum > target) r--;
else l++;
}
// this question use 1-indexed
return [l + 1, r + 1];
};
Solution 2: (Hash table)
var twoSum = function(numbers, target) {
let map = new Map;
for (var i = 0; i < numbers.length; i++) {
var diff = target - numbers[i];
if(map.has(diff)) {
return [map.get(diff), i + 1];
}
map.set(numbers[i], i + 1);
}
};
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
return dfs(matrix, target, 0, 0);
};
function dfs(matrix, target, x, y) {
let rows = matrix.length;
let cols = matrix[0].length;
// exit recursion condition, reach to the end;
if (y === rows) return false;
// traverse from left to right, then next row
let nextX = (x + 1) % cols;
let nextY = nextX === 0 ? y + 1 : y;
// found return true or not found, DFS next element
if (matrix[y][x] === target)
return true;
else
return dfs(matrix, target, nextX, nextY);
return false;
}
Solution 2: (Binary Search) Better and Faster!
Time complexity: O(log(mn))
Space complexity: O(1)
var searchMatrix = function(matrix, target) {
let cols = matrix[0].length;
// treat 2D as 1D, use binary search
let l = 0;
let r = matrix.length * cols;
while (l < r) {
let mid = l + Math.floor((r - l) / 2);
let row = Math.floor(mid / cols);
let col = mid % cols;
if (matrix[row][col] === target) {
return true;
} else if (matrix[row][col] > target) {
r = mid;
} else {
l = mid + 1;
}
}
return false;
};
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 an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Traverse connected components: Use DFS to traverse 4 directions and mark them “0” if found “1”
Solution:
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
let row = grid.length;
if (row === 0) return 0;
let col = grid[0].length;
let res = 0;
for (let x = 0; x < col ; x++) {
for (let y = 0; y < row; y++) {
if (grid[y][x] === "1") {
res++;
dfs(grid, x, y, col, row);
}
}
}
return res;
};
var dfs = function(grid, x, y, n, m) {
// over boundry cases and not "1" => return
if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] === "0") return;
// already visited mark it "0"
grid[y][x] = "0";
// traverse 4 directions if any "1" => mark them "0"
dfs(grid, x + 1, y, n, m);
dfs(grid, x - 1, y, n, m);
dfs(grid, x, y + 1, n, m);
dfs(grid, x, y - 1, n, m);
}
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Constraints:
The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000
Idea: 背口诀
reverse LinkedList 口诀: create newHead and next
next -> head.next -> newHead.next -> head -> next
Solution:
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
// empty or only one node
if (head === null || head.next === null) return head;
let newHead = new ListNode();
let next = new ListNode();
while (head !== null) {
// next helper create
next = head.next;
// disconnect, and point to newHead.next
head.next = newHead.next;
// move newHead.next to head
newHead.next = head;
// move head to next location
head = next;
}
return newHead.next;
};
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,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 of unique elements, return the minimum element of this array.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
Constraints:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.
Idea:
Use Binary Search Template
Time Complexity: O(logN)
Space Complexity: O(1)
Solution:
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
// if only have one number
if (nums.length === 1) return nums[0];
let l = 0;
let r = nums.length;
// if this array is sorted
if (nums[0] < nums[r - 1]) return nums[0];
while (l < r) {
let mid = l + Math.floor((r - l) / 2);
// if previous element is greater than next element,
// next element is the smallest
if (nums[mid] > nums[mid + 1])
return nums[mid + 1];
if (nums[mid - 1] > nums[mid])
return nums[mid];
// first half is sorted: min is on right side
if (nums[mid] > nums[0])
l = mid;
else
r = mid + 1;
}
return -1;
};
Solution 2:
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));
}
The idea of CQRS is to enable an application (in the large sense) to work with different models:
One internal model it writes with: the write model, altered by Commands (more on this later)
One or several read models it and other applications read from (we can’t let others read the write model)
This pattern trade control over scalability and flexibility.
Advantages:
We can scale the read and write databases independently of each other
The write database can be normalized to 3rd Normal Form to make writes efficient
The read databases can be denormalized the data to suit specific queries and no need to perform complex operations like JOIN tables to return the required data.
Managing security and permissions is easy
It makes queries simple
It forces us to change the way we think, UI sends a command to the write model and not a data model object
We can use a relational database for the write side and use NoSQL database for the read side. Scaling a NoSQL database is relatively easy.
Disadvantages:
It makes the whole system complex
Data can be stale
Handling eventually consistent data is a monster of its own.
Points to consider before implementation
This is not a system-wide or high-level pattern. It should be applied only in a bounded context where it makes sense.
The data will be eventually consistent
It works well with event sourcing pattern
It is useful in systems where multiple systems/actors perform parallel actions on the same data.
It shouldn’t be used for applications which are simple CRUD based.
The write model is always the source of truth. So we could query the write model and return data as the result of command execution.
It is not simple to handle eventual-consistent data.
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
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;
};
