2021-12-11
878. Nth Magical Number
Topic: Math, Binary Search
Difficulty: Hard
Problem:
A positive integer is magical if it is divisible by either
Given the three integers
Example 1:
Example 2:
Example 3:
Example 4:
Constraints:
878. Nth Magical Number
Topic: Math, Binary Search
Difficulty: Hard
Problem:
A positive integer is magical if it is divisible by either
a or b.Given the three integers
n, a, and b, return the n^th magical number. Since the answer may be very large, return it modulo 10^9 + 7.Example 1:
Input: n = 1, a = 2, b = 3
Output: 2
Example 2:
Input: n = 4, a = 2, b = 3
Output: 6
Example 3:
Input: n = 5, a = 2, b = 4
Output: 10
Example 4:
Input: n = 3, a = 6, b = 4
Output: 8
Constraints:
1 <= n <= 10^92 <= a, b <= 4 * 10^42021-12-12
416. Partition Equal Subset Sum
Topic: Array, Dynamic Programming
Difficulty: Medium
Problem:
Given a non-empty array
Example 1:
Example 2:
Constraints:
•
•
416. Partition Equal Subset Sum
Topic: Array, Dynamic Programming
Difficulty: Medium
Problem:
Given a non-empty array
nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
•
1 <= nums.length <= 200•
1 <= nums[i] <= 1002021-12-13
1446. Consecutive Characters
Topic: String
Difficulty: Easy
Problem:
The power of the string is the maximum length of a non-empty substring that contains only one unique character.
Given a string
Example 1:
Example 2:
Example 3:
Example 4:
Example 5:
Constraints:
•
•
1446. Consecutive Characters
Topic: String
Difficulty: Easy
Problem:
The power of the string is the maximum length of a non-empty substring that contains only one unique character.
Given a string
s, return the power of s.Example 1:
Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.
Example 2:
Input: s = "abbcccddddeeeeedcba"
Output: 5
Explanation: The substring "eeeee" is of length 5 with the character 'e' only.
Example 3:
Input: s = "triplepillooooow"
Output: 5
Example 4:
Input: s = "hooraaaaaaaaaaay"
Output: 11
Example 5:
Input: s = "tourist"
Output: 1
Constraints:
•
1 <= s.length <= 500•
s consists of only lowercase English letters.2021-12-14
938. Range Sum of BST
Topic: Tree, Depth-First Search, Binary Search Tree, Binary Tree
Difficulty: Easy
Problem:
Given the
Example 1:
Image: https://assets.leetcode.com/uploads/2020/11/05/bst1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2020/11/05/bst2.jpg
Constraints:
• The number of nodes in the tree is in the range
•
•
• All
938. Range Sum of BST
Topic: Tree, Depth-First Search, Binary Search Tree, Binary Tree
Difficulty: Easy
Problem:
Given the
root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].Example 1:
Image: https://assets.leetcode.com/uploads/2020/11/05/bst1.jpg
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.
Example 2:
Image: https://assets.leetcode.com/uploads/2020/11/05/bst2.jpg
Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.
Constraints:
• The number of nodes in the tree is in the range
[1, 2 * 10^4].•
1 <= Node.val <= 10^5•
1 <= low <= high <= 10^5• All
Node.val are unique.2021-12-15
147. Insertion Sort List
Topic: Linked List, Sorting
Difficulty: Medium
Problem:
Given the
The steps of the insertion sort algorithm:
1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
3. It repeats until no input elements remain.
The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.
Image: https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif
Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/04/sort1linked-list.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/03/04/sort2linked-list.jpg
Constraints:
• The number of nodes in the list is in the range
•
147. Insertion Sort List
Topic: Linked List, Sorting
Difficulty: Medium
Problem:
Given the
head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.The steps of the insertion sort algorithm:
1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
3. It repeats until no input elements remain.
The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.
Image: https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif
Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/04/sort1linked-list.jpg
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Example 2:
Image: https://assets.leetcode.com/uploads/2021/03/04/sort2linked-list.jpg
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Constraints:
• The number of nodes in the list is in the range
[1, 5000].•
-5000 <= Node.val <= 50002021-12-16
310. Minimum Height Trees
Topic: Depth-First Search, Breadth-First Search, Graph, Topological Sort
Difficulty: Medium
Problem:
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
Given a tree of
Return a list of all MHTs' root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/01/e1.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2020/09/01/e2.jpg
Example 3:
Example 4:
Constraints:
•
•
•
•
• All the pairs
• The given input is guaranteed to be a tree and there will be no repeated edges.
310. Minimum Height Trees
Topic: Depth-First Search, Breadth-First Search, Graph, Topological Sort
Difficulty: Medium
Problem:
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
Given a tree of
n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [a_i, b_i] indicates that there is an undirected edge between the two nodes a_i and b_i in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).Return a list of all MHTs' root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/01/e1.jpg
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.
Example 2:
Image: https://assets.leetcode.com/uploads/2020/09/01/e2.jpg
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]
Example 3:
Input: n = 1, edges = []
Output: [0]
Example 4:
Input: n = 2, edges = [[0,1]]
Output: [0,1]
Constraints:
•
1 <= n <= 2 * 10^4•
edges.length == n - 1•
0 <= a_i, b_i < n•
a_i != b_i• All the pairs
(a_i, b_i) are distinct.• The given input is guaranteed to be a tree and there will be no repeated edges.
2021-12-17
221. Maximal Square
Topic: Array, Dynamic Programming, Matrix
Difficulty: Medium
Problem:
Given an
Example 1:
Image: https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2020/11/26/max2grid.jpg
Example 3:
Constraints:
•
•
•
•
221. Maximal Square
Topic: Array, Dynamic Programming, Matrix
Difficulty: Medium
Problem:
Given an
m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.Example 1:
Image: https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
Example 2:
Image: https://assets.leetcode.com/uploads/2020/11/26/max2grid.jpg
Input: matrix = [["0","1"],["1","0"]]
Output: 1
Example 3:
Input: matrix = [["0"]]
Output: 0
Constraints:
•
m == matrix.length•
n == matrix[i].length•
1 <= m, n <= 300•
matrix[i][j] is '0' or '1'.2021-12-18
902. Numbers At Most N Given Digit Set
Topic: Array, Math, Binary Search, Dynamic Programming
Difficulty: Hard
Problem:
Given an array of
Return the number of positive integers that can be generated that are less than or equal to a given integer
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
• All the values in
•
•
902. Numbers At Most N Given Digit Set
Topic: Array, Math, Binary Search, Dynamic Programming
Difficulty: Hard
Problem:
Given an array of
digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.Return the number of positive integers that can be generated that are less than or equal to a given integer
n.Example 1:
Input: digits = ["1","3","5","7"], n = 100
Output: 20
Explanation:
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
Example 2:
Input: digits = ["1","4","9"], n = 1000000000
Output: 29523
Explanation:
We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,
81 four digit numbers, 243 five digit numbers, 729 six digit numbers,
2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.
In total, this is 29523 integers that can be written using the digits array.
Example 3:
Input: digits = ["7"], n = 8
Output: 1
Constraints:
•
1 <= digits.length <= 9•
digits[i].length == 1•
digits[i] is a digit from '1' to '9'.• All the values in
digits are unique.•
digits is sorted in non-decreasing order.•
1 <= n <= 10^92021-12-19
394. Decode String
Topic: String, Stack, Recursion
Difficulty: Medium
Problem:
Given an encoded string, return its decoded string.
The encoding rule is:
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,
Example 1:
Example 2:
Example 3:
Example 4:
Constraints:
•
•
•
• All the integers in
394. Decode String
Topic: String, Stack, Recursion
Difficulty: Medium
Problem:
Given an encoded string, return its decoded string.
The encoding rule is:
k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,
k. For example, there won't be input like 3a or 2[4].Example 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Example 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Example 4:
Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"
Constraints:
•
1 <= s.length <= 30•
s consists of lowercase English letters, digits, and square brackets '[]'.•
s is guaranteed to be a valid input.• All the integers in
s are in the range [1, 300].2021-12-20
1200. Minimum Absolute Difference
Topic: Array, Sorting
Difficulty: Easy
Problem:
Given an array of distinct integers
Return a list of pairs in ascending order(with respect to pairs), each pair
•
•
•
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1200. Minimum Absolute Difference
Topic: Array, Sorting
Difficulty: Easy
Problem:
Given an array of distinct integers
arr, find all pairs of elements with the minimum absolute difference of any two elements. Return a list of pairs in ascending order(with respect to pairs), each pair
[a, b] follows•
a, b are from arr•
a < b•
b - a equals to the minimum absolute difference of any two elements in arrExample 1:
Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.
Example 2:
Input: arr = [1,3,6,10,15]
Output: [[1,3]]
Example 3:
Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]
Constraints:
•
2 <= arr.length <= 10^5•
-10^6 <= arr[i] <= 10^62021-12-21
231. Power of Two
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?
231. Power of Two
Topic: Math, Bit Manipulation, Recursion
Difficulty: Easy
Problem:
Given an integer
n, return true if it is a power of two. Otherwise, return false.An integer
n is a power of two, if there exists an integer x such that n == 2^x.Example 1:
Input: n = 1
Output: true
Explanation: 2^0 = 1
Example 2:
Input: n = 16
Output: true
Explanation: 2^4 = 16
Example 3:
Input: n = 3
Output: false
Constraints:
•
-2^31 <= n <= 2^31 - 1Follow up: Could you solve it without loops/recursion?
2021-12-22
143. Reorder List
Topic: Linked List, Two Pointers, Stack, Recursion
Difficulty: Medium
Problem:
You are given the head of a singly linked-list. The list can be represented as:
Reorder the list to be on the following form:
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/04/reorder1linked-list.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/03/09/reorder2-linked-list.jpg
Constraints:
• The number of nodes in the list is in the range
•
143. Reorder List
Topic: Linked List, Two Pointers, Stack, Recursion
Difficulty: Medium
Problem:
You are given the head of a singly linked-list. The list can be represented as:
L_0 → L_1 → … → L_n - 1 → L_n
Reorder the list to be on the following form:
L_0 → L_n → L_1 → L_n - 1 → L_2 → L_n - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/03/04/reorder1linked-list.jpg
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Image: https://assets.leetcode.com/uploads/2021/03/09/reorder2-linked-list.jpg
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Constraints:
• The number of nodes in the list is in the range
[1, 5 * 10^4].•
1 <= Node.val <= 10002021-12-23
210. Course Schedule II
Topic: Depth-First Search, Breadth-First Search, Graph, Topological Sort
Difficulty: Medium
Problem:
There are a total of
• For example, the pair
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
•
• All the pairs
210. Course Schedule II
Topic: Depth-First Search, Breadth-First Search, Graph, Topological Sort
Difficulty: Medium
Problem:
There are a total of
numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.• For example, the pair
[0, 1], indicates that to take course 0 you have to first take course 1.Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
Example 2:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
Example 3:
Input: numCourses = 1, prerequisites = []
Output: [0]
Constraints:
•
1 <= numCourses <= 2000•
0 <= prerequisites.length <= numCourses * (numCourses - 1)•
prerequisites[i].length == 2•
0 <= a_i, b_i < numCourses•
a_i != b_i• All the pairs
[a_i, b_i] are distinct.2021-12-24
56. Merge Intervals
Topic: Array, Sorting
Difficulty: Medium
Problem:
Given an array of
Example 1:
Example 2:
Constraints:
•
•
•
56. Merge Intervals
Topic: Array, Sorting
Difficulty: Medium
Problem:
Given an array of
intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
•
1 <= intervals.length <= 10^4•
intervals[i].length == 2•
0 <= start_i <= end_i <= 10^42021-12-25
227. Basic Calculator II
Topic: Math, String, Stack
Difficulty: Medium
Problem:
Given a string
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
• All the integers in the expression are non-negative integers in the range
• The answer is guaranteed to fit in a 32-bit integer.
227. Basic Calculator II
Topic: Math, String, Stack
Difficulty: Medium
Problem:
Given a string
s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of
[-2^31, 2^31 - 1].Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as
eval().Example 1:
Input: s = "3+2*2"
Output: 7
Example 2:
Input: s = " 3/2 "
Output: 1
Example 3:
Input: s = " 3+5 / 2 "
Output: 5
Constraints:
•
1 <= s.length <= 3 * 10^5•
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.•
s represents a valid expression.• All the integers in the expression are non-negative integers in the range
[0, 2^31 - 1].• The answer is guaranteed to fit in a 32-bit integer.