2022-08-22
342. Power of Four
Topic: Math, Bit Manipulation, Recursion
Difficulty: Easy
Problem:
Given an integer
An integer
Example 1:
Example 2:
Example 3:
Constraints:
•
Follow up: Could you solve it without loops/recursion?
342. Power of Four
Topic: Math, Bit Manipulation, Recursion
Difficulty: Easy
Problem:
Given an integer
n, return true if it is a power of four. Otherwise, return false.An integer
n is a power of four, if there exists an integer x such that n == 4^x.Example 1:
Input: n = 16
Output: true
Example 2:
Input: n = 5
Output: false
Example 3:
Input: n = 1
Output: true
Constraints:
•
-2^31 <= n <= 2^31 - 1Follow up: Could you solve it without loops/recursion?
2022-08-23
234. Palindrome Linked List
Topic: Linked List, Two Pointers, Stack, Recursion
Difficulty: Easy
Problem:
Given the
Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg
Constraints:
• The number of nodes in the list is in the range
•
Follow up: Could you do it in
234. Palindrome Linked List
Topic: Linked List, Two Pointers, Stack, Recursion
Difficulty: Easy
Problem:
Given the
head of a singly linked list, return true if it is a palindrome.Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg
Input: head = [1,2,2,1]
Output: true
Example 2:
Image: https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg
Input: head = [1,2]
Output: false
Constraints:
• The number of nodes in the list is in the range
[1, 10^5].•
0 <= Node.val <= 9Follow up: Could you do it in
O(n) time and O(1) space?2022-08-24
326. Power of Three
Topic: Math, Recursion
Difficulty: Easy
Problem:
Given an integer
An integer
Example 1:
Example 2:
Example 3:
Constraints:
•
Follow up: Could you solve it without loops/recursion?
326. Power of Three
Topic: Math, Recursion
Difficulty: Easy
Problem:
Given an integer
n, return true if it is a power of three. Otherwise, return false.An integer
n is a power of three, if there exists an integer x such that n == 3^x.Example 1:
Input: n = 27
Output: true
Example 2:
Input: n = 0
Output: false
Example 3:
Input: n = 9
Output: true
Constraints:
•
-2^31 <= n <= 2^31 - 1Follow up: Could you solve it without loops/recursion?
2022-08-25
383. Ransom Note
Topic: Hash Table, String, Counting
Difficulty: Easy
Problem:
Given two strings
Each letter in
Example 1:
Example 2:
Example 3:
Constraints:
•
•
383. Ransom Note
Topic: Hash Table, String, Counting
Difficulty: Easy
Problem:
Given two strings
ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.Each letter in
magazine can only be used once in ransomNote.Example 1:
Input: ransomNote = "a", magazine = "b"
Output: false
Example 2:
Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3:
Input: ransomNote = "aa", magazine = "aab"
Output: true
Constraints:
•
1 <= ransomNote.length, magazine.length <= 10^5•
ransomNote and magazine consist of lowercase English letters.2022-08-26
869. Reordered Power of 2
Topic: Math, Sorting, Counting, Enumeration
Difficulty: Medium
Problem:
You are given an integer
Return
Example 1:
Example 2:
Constraints:
•
869. Reordered Power of 2
Topic: Math, Sorting, Counting, Enumeration
Difficulty: Medium
Problem:
You are given an integer
n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.Return
true if and only if we can do this so that the resulting number is a power of two.Example 1:
Input: n = 1
Output: true
Example 2:
Input: n = 10
Output: false
Constraints:
•
1 <= n <= 10^92022-08-27
363. Max Sum of Rectangle No Larger Than K
Topic: Array, Binary Search, Matrix, Prefix Sum, Ordered Set
Difficulty: Hard
Problem:
Given an
It is guaranteed that there will be a rectangle with a sum no larger than
Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/18/sum-grid.jpg
Example 2:
Constraints:
•
•
•
•
•
Follow up: What if the number of rows is much larger than the number of columns?
363. Max Sum of Rectangle No Larger Than K
Topic: Array, Binary Search, Matrix, Prefix Sum, Ordered Set
Difficulty: Hard
Problem:
Given an
m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.It is guaranteed that there will be a rectangle with a sum no larger than
k.Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/18/sum-grid.jpg
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).
Example 2:
Input: matrix = [[2,2,-1]], k = 3
Output: 3
Constraints:
•
m == matrix.length•
n == matrix[i].length•
1 <= m, n <= 100•
-100 <= matrix[i][j] <= 100•
-10^5 <= k <= 10^5Follow up: What if the number of rows is much larger than the number of columns?
2022-08-28
1329. Sort the Matrix Diagonally
Topic: Array, Sorting, Matrix
Difficulty: Medium
Problem:
A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end. For example, the matrix diagonal starting from
Given an
Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/21/1482_example_1_2.png
Example 2:
Constraints:
•
•
•
•
1329. Sort the Matrix Diagonally
Topic: Array, Sorting, Matrix
Difficulty: Medium
Problem:
A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end. For example, the matrix diagonal starting from
mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].Given an
m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/21/1482_example_1_2.png
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]
Example 2:
Input: mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
Output: [[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]
Constraints:
•
m == mat.length•
n == mat[i].length•
1 <= m, n <= 100•
1 <= mat[i][j] <= 1002022-08-29
200. Number of Islands
Topic: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix
Difficulty: Medium
Problem:
Given an
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.
Example 1:
Example 2:
Constraints:
•
•
•
•
200. Number of Islands
Topic: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix
Difficulty: Medium
Problem:
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.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Constraints:
•
m == grid.length•
n == grid[i].length•
1 <= m, n <= 300•
grid[i][j] is '0' or '1'.2022-08-30
48. Rotate Image
Topic: Array, Math, Matrix
Difficulty: Medium
Problem:
You are given an
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/08/28/mat1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2020/08/28/mat2.jpg
Constraints:
•
•
•
48. Rotate Image
Topic: Array, Math, Matrix
Difficulty: Medium
Problem:
You are given an
n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/08/28/mat1.jpg
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Image: https://assets.leetcode.com/uploads/2020/08/28/mat2.jpg
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Constraints:
•
n == matrix.length == matrix[i].length•
1 <= n <= 20•
-1000 <= matrix[i][j] <= 10002022-08-31
417. Pacific Atlantic Water Flow
Topic: Array, Depth-First Search, Breadth-First Search, Matrix
Difficulty: Medium
Problem:
There is an
The island is partitioned into a grid of square cells. You are given an
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates
Example 1:
Image: https://assets.leetcode.com/uploads/2021/06/08/waterflow-grid.jpg
Example 2:
Constraints:
•
•
•
•
417. Pacific Atlantic Water Flow
Topic: Array, Depth-First Search, Breadth-First Search, Matrix
Difficulty: Medium
Problem:
There is an
m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.The island is partitioned into a grid of square cells. You are given an
m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates
result where result[i] = [r_i, c_i] denotes that rain water can flow from cell (r_i, c_i) to both the Pacific and Atlantic oceans.Example 1:
Image: https://assets.leetcode.com/uploads/2021/06/08/waterflow-grid.jpg
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean
[0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean
[1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean
[1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean
[2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean
[3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean
[3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean
[4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.
Example 2:
Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.
Constraints:
•
m == heights.length•
n == heights[r].length•
1 <= m, n <= 200•
0 <= heights[r][c] <= 10^52022-09-01
1448. Count Good Nodes in Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given a binary tree
Return the number of good nodes in the binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/04/02/test_sample_1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/04/02/test_sample_2.png
Example 3:
Constraints:
• The number of nodes in the binary tree is in the range
• Each node's value is between
1448. Count Good Nodes in Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given a binary tree
root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.Return the number of good nodes in the binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/04/02/test_sample_1.png
Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.
Example 2:
Image: https://assets.leetcode.com/uploads/2020/04/02/test_sample_2.png
Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.
Example 3:
Input: root = [1]
Output: 1
Explanation: Root is considered as good.
Constraints:
• The number of nodes in the binary tree is in the range
[1, 10^5].• Each node's value is between
[-10^4, 10^4].2022-09-02
637. Average of Levels in Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/09/avg1-tree.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/03/09/avg2-tree.jpg
Constraints:
• The number of nodes in the tree is in the range
•
637. Average of Levels in Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10^-5 of the actual answer will be accepted.Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/09/avg1-tree.jpg
Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11.
Hence return [3, 14.5, 11].
Example 2:
Image: https://assets.leetcode.com/uploads/2021/03/09/avg2-tree.jpg
Input: root = [3,9,20,15,7]
Output: [3.00000,14.50000,11.00000]
Constraints:
• The number of nodes in the tree is in the range
[1, 10^4].•
-2^31 <= Node.val <= 2^31 - 12022-09-03
967. Numbers With Same Consecutive Differences
Topic: Backtracking, Breadth-First Search
Difficulty: Medium
Problem:
Return all non-negative integers of length
Note that every number in the answer must not have leading zeros. For example,
You may return the answer in any order.
Example 1:
Example 2:
Constraints:
•
•
967. Numbers With Same Consecutive Differences
Topic: Backtracking, Breadth-First Search
Difficulty: Medium
Problem:
Return all non-negative integers of length
n such that the absolute difference between every two consecutive digits is k.Note that every number in the answer must not have leading zeros. For example,
01 has one leading zero and is invalid.You may return the answer in any order.
Example 1:
Input: n = 3, k = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.
Example 2:
Input: n = 2, k = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]
Constraints:
•
2 <= n <= 9•
0 <= k <= 92022-09-04
987. Vertical Order Traversal of a Binary Tree
Topic: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Hard
Problem:
Given the
For each node at position
The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.
Return the vertical order traversal of the binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree2.jpg
Example 3:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree3.jpg
Constraints:
• The number of nodes in the tree is in the range
•
987. Vertical Order Traversal of a Binary Tree
Topic: Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Hard
Problem:
Given the
root of a binary tree, calculate the vertical order traversal of the binary tree.For each node at position
(row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.
Return the vertical order traversal of the binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree1.jpg
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.
Example 2:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree2.jpg
Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
1 is at the top, so it comes first.
5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.
Example 3:
Image: https://assets.leetcode.com/uploads/2021/01/29/vtree3.jpg
Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.
Constraints:
• The number of nodes in the tree is in the range
[1, 1000].•
0 <= Node.val <= 10002022-09-05
429. N-ary Tree Level Order Traversal
Topic: Tree, Breadth-First Search
Difficulty: Medium
Problem:
Given an n-ary tree, return the level order traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Example 1:
Image: https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png
Example 2:
Image: https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png
Constraints:
• The height of the n-ary tree is less than or equal to
• The total number of nodes is between
429. N-ary Tree Level Order Traversal
Topic: Tree, Breadth-First Search
Difficulty: Medium
Problem:
Given an n-ary tree, return the level order traversal of its nodes' values.
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).
Example 1:
Image: https://assets.leetcode.com/uploads/2018/10/12/narytreeexample.png
Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]
Example 2:
Image: https://assets.leetcode.com/uploads/2019/11/08/sample_4_964.png
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
Constraints:
• The height of the n-ary tree is less than or equal to
1000• The total number of nodes is between
[0, 10^4]2022-09-06
814. Binary Tree Pruning
Topic: Tree, Depth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
A subtree of a node
Example 1:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png
Example 2:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png
Example 3:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png
Constraints:
• The number of nodes in the tree is in the range
•
814. Binary Tree Pruning
Topic: Tree, Depth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.A subtree of a node
node is node plus every node that is a descendant of node.Example 1:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png
Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation:
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.
Example 2:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png
Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]
Example 3:
Image: https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png
Input: root = [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]
Constraints:
• The number of nodes in the tree is in the range
[1, 200].•
Node.val is either 0 or 1.2022-09-07
606. Construct String from Binary Tree
Topic: String, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons1-tree.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons2-tree.jpg
Constraints:
• The number of nodes in the tree is in the range
•
606. Construct String from Binary Tree
Topic: String, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons1-tree.jpg
Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)"
Example 2:
Image: https://assets.leetcode.com/uploads/2021/05/03/cons2-tree.jpg
Input: root = [1,2,3,null,4]
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, except we cannot omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
Constraints:
• The number of nodes in the tree is in the range
[1, 10^4].•
-1000 <= Node.val <= 10002022-09-08
94. Binary Tree Inorder Traversal
Topic: Stack, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg
Example 2:
Example 3:
Constraints:
• The number of nodes in the tree is in the range
•
Follow up: Recursive solution is trivial, could you do it iteratively?
94. Binary Tree Inorder Traversal
Topic: Stack, Tree, Depth-First Search, Binary Tree
Difficulty: Easy
Problem:
Given the
root of a binary tree, return the inorder traversal of its nodes' values.Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg
Input: root = [1,null,2,3]
Output: [1,3,2]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Constraints:
• The number of nodes in the tree is in the range
[0, 100].•
-100 <= Node.val <= 100Follow up: Recursive solution is trivial, could you do it iteratively?
2022-09-09
1996. The Number of Weak Characters in the Game
Topic: Array, Stack, Greedy, Sorting, Monotonic Stack
Difficulty: Medium
Problem:
You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array
A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character
Return the number of weak characters.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
1996. The Number of Weak Characters in the Game
Topic: Array, Stack, Greedy, Sorting, Monotonic Stack
Difficulty: Medium
Problem:
You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array
properties where properties[i] = [attack_i, defense_i] represents the properties of the i^th character in the game.A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character
i is said to be weak if there exists another character j where attack_j > attack_i and defense_j > defense_i.Return the number of weak characters.
Example 1:
Input: properties = [[5,5],[6,3],[3,6]]
Output: 0
Explanation: No character has strictly greater attack and defense than the other.
Example 2:
Input: properties = [[2,2],[3,3]]
Output: 1
Explanation: The first character is weak because the second character has a strictly greater attack and defense.
Example 3:
Input: properties = [[1,5],[10,4],[4,3]]
Output: 1
Explanation: The third character is weak because the second character has a strictly greater attack and defense.
Constraints:
•
2 <= properties.length <= 10^5•
properties[i].length == 2•
1 <= attack_i, defense_i <= 10^52022-09-10
188. Best Time to Buy and Sell Stock IV
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
You are given an integer array
Find the maximum profit you can achieve. You may complete at most
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Example 2:
Constraints:
•
•
•
188. Best Time to Buy and Sell Stock IV
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
You are given an integer array
prices where prices[i] is the price of a given stock on the i^th day, and an integer k.Find the maximum profit you can achieve. You may complete at most
k transactions.Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Constraints:
•
0 <= k <= 100•
0 <= prices.length <= 1000•
0 <= prices[i] <= 10002022-09-11
1383. Maximum Performance of a Team
Topic: Array, Greedy, Sorting, Heap (Priority Queue)
Difficulty: Hard
Problem:
You are given two integers
Choose at most
The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
Return the maximum performance of this team. Since the answer can be a huge number, return it modulo
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
•
1383. Maximum Performance of a Team
Topic: Array, Greedy, Sorting, Heap (Priority Queue)
Difficulty: Hard
Problem:
You are given two integers
n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the i^th engineer respectively.Choose at most
k different engineers out of the n engineers to form a team with the maximum performance.The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
Return the maximum performance of this team. Since the answer can be a huge number, return it modulo
10^9 + 7.Example 1:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation:
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.
Example 2:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.
Example 3:
Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72
Constraints:
•
1 <= k <= n <= 10^5•
speed.length == n•
efficiency.length == n•
1 <= speed[i] <= 10^5•
1 <= efficiency[i] <= 10^8