2023-04-08
133. Clone Graph
Topic: Hash Table, Depth-First Search, Breadth-First Search, Graph
Difficulty: Medium
Problem:
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (
Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with
Example 1:
Image: https://assets.leetcode.com/uploads/2019/11/04/133_clone_graph_question.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/01/07/graph.png
Example 3:
Constraints:
• The number of nodes in the graph is in the range
•
•
• There are no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.
133. Clone Graph
Topic: Hash Table, Depth-First Search, Breadth-First Search, Graph
Difficulty: Medium
Problem:
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (
int) and a list (List[Node]) of its neighbors.class Node {
public int val;
public List<Node> neighbors;
}
Test case format:
For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with
val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with
val = 1. You must return the copy of the given node as a reference to the cloned graph.Example 1:
Image: https://assets.leetcode.com/uploads/2019/11/04/133_clone_graph_question.png
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
Example 2:
Image: https://assets.leetcode.com/uploads/2020/01/07/graph.png
Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:
Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
Constraints:
• The number of nodes in the graph is in the range
[0, 100].•
1 <= Node.val <= 100•
Node.val is unique for each node.• There are no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.
2023-04-09
1857. Largest Color Value in a Directed Graph
Topic: Hash Table, Dynamic Programming, Graph, Topological Sort, Memoization, Counting
Difficulty: Hard
Problem:
There is a directed graph of
You are given a string
A valid path in the graph is a sequence of nodes
Return the largest color value of any valid path in the given graph, or
Example 1:
Image: https://assets.leetcode.com/uploads/2021/04/21/leet1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2021/04/21/leet2.png
Constraints:
•
•
•
•
•
•
1857. Largest Color Value in a Directed Graph
Topic: Hash Table, Dynamic Programming, Graph, Topological Sort, Memoization, Counting
Difficulty: Hard
Problem:
There is a directed graph of
n colored nodes and m edges. The nodes are numbered from 0 to n - 1.You are given a string
colors where colors[i] is a lowercase English letter representing the color of the i^th node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [a_j, b_j] indicates that there is a directed edge from node a_j to node b_j.A valid path in the graph is a sequence of nodes
x_1 -> x_2 -> x_3 -> ... -> x_k such that there is a directed edge from x_i to x_i+1 for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.Return the largest color value of any valid path in the given graph, or
-1 if the graph contains a cycle.Example 1:
Image: https://assets.leetcode.com/uploads/2021/04/21/leet1.png
Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).
Example 2:
Image: https://assets.leetcode.com/uploads/2021/04/21/leet2.png
Input: colors = "a", edges = [[0,0]]
Output: -1
Explanation: There is a cycle from 0 to 0.
Constraints:
•
n == colors.length•
m == edges.length•
1 <= n <= 10^5•
0 <= m <= 10^5•
colors consists of lowercase English letters.•
0 <= a_j, b_j < n2023-04-10
20. Valid Parentheses
Topic: String, Stack
Difficulty: Easy
Problem:
Given a string
An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
20. Valid Parentheses
Topic: String, Stack
Difficulty: Easy
Problem:
Given a string
s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
•
1 <= s.length <= 10^4•
s consists of parentheses only '()[]{}'.2023-04-11
2390. Removing Stars From a String
Topic: String, Stack, Simulation
Difficulty: Medium
Problem:
You are given a string
In one operation, you can:
• Choose a star in
• Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.
Note:
• The input will be generated such that the operation is always possible.
• It can be shown that the resulting string will always be unique.
Example 1:
Example 2:
Constraints:
•
•
• The operation above can be performed on
2390. Removing Stars From a String
Topic: String, Stack, Simulation
Difficulty: Medium
Problem:
You are given a string
s, which contains stars *.In one operation, you can:
• Choose a star in
s.• Remove the closest non-star character to its left, as well as remove the star itself.
Return the string after all stars have been removed.
Note:
• The input will be generated such that the operation is always possible.
• It can be shown that the resulting string will always be unique.
Example 1:
Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1^st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2^nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3^rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".
Example 2:
Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.
Constraints:
•
1 <= s.length <= 10^5•
s consists of lowercase English letters and stars *.• The operation above can be performed on
s.2023-04-12
71. Simplify Path
Topic: String, Stack
Difficulty: Medium
Problem:
Given a string
In a Unix-style file system, a period
The canonical path should have the following format:
• The path starts with a single slash
• Any two directories are separated by a single slash
• The path does not end with a trailing
• The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period
Return the simplified canonical path.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
71. Simplify Path
Topic: String, Stack
Difficulty: Medium
Problem:
Given a string
path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.In a Unix-style file system, a period
'.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.The canonical path should have the following format:
• The path starts with a single slash
'/'.• Any two directories are separated by a single slash
'/'.• The path does not end with a trailing
'/'.• The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period
'.' or double period '..')Return the simplified canonical path.
Example 1:
Input: path = "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.
Example 2:
Input: path = "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
Example 3:
Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
Constraints:
•
1 <= path.length <= 3000•
path consists of English letters, digits, period '.', slash '/' or '_'.•
path is a valid absolute Unix path.2023-04-13
946. Validate Stack Sequences
Topic: Array, Stack, Simulation
Difficulty: Medium
Problem:
Given two integer arrays
Example 1:
Example 2:
Constraints:
•
•
• All the elements of
•
•
946. Validate Stack Sequences
Topic: Array, Stack, Simulation
Difficulty: Medium
Problem:
Given two integer arrays
pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.Example 1:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
Example 2:
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.
Constraints:
•
1 <= pushed.length <= 1000•
0 <= pushed[i] <= 1000• All the elements of
pushed are unique.•
popped.length == pushed.length•
popped is a permutation of pushed.2023-04-14
516. Longest Palindromic Subsequence
Topic: String, Dynamic Programming
Difficulty: Medium
Problem:
Given a string
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Example 2:
Constraints:
•
•
516. Longest Palindromic Subsequence
Topic: String, Dynamic Programming
Difficulty: Medium
Problem:
Given a string
s, find the longest palindromic subsequence's length in s.A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: s = "bbbab"
Output: 4
Explanation: One possible longest palindromic subsequence is "bbbb".
Example 2:
Input: s = "cbbd"
Output: 2
Explanation: One possible longest palindromic subsequence is "bb".
Constraints:
•
1 <= s.length <= 1000•
s consists only of lowercase English letters.2023-04-15
2218. Maximum Value of K Coins From Piles
Topic: Array, Dynamic Programming, Prefix Sum
Difficulty: Hard
Problem:
There are
In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.
Given a list
Example 1:
Image: https://assets.leetcode.com/uploads/2019/11/09/e1.png
Example 2:
Constraints:
•
•
•
•
2218. Maximum Value of K Coins From Piles
Topic: Array, Dynamic Programming, Prefix Sum
Difficulty: Hard
Problem:
There are
n piles of coins on a table. Each pile consists of a positive number of coins of assorted denominations.In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.
Given a list
piles, where piles[i] is a list of integers denoting the composition of the i^th pile from top to bottom, and a positive integer k, return the maximum total value of coins you can have in your wallet if you choose exactly k coins optimally.Example 1:
Image: https://assets.leetcode.com/uploads/2019/11/09/e1.png
Input: piles = [[1,100,3],[7,8,9]], k = 2
Output: 101
Explanation:
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.
Example 2:
Input: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
Output: 706
Explanation:
The maximum total can be obtained if we choose all coins from the last pile.
Constraints:
•
n == piles.length•
1 <= n <= 1000•
1 <= piles[i][j] <= 10^5•
1 <= k <= sum(piles[i].length) <= 20002023-04-16
1639. Number of Ways to Form a Target String Given a Dictionary
Topic: Array, String, Dynamic Programming
Difficulty: Hard
Problem:
You are given a list of strings of the same length
Your task is to form
•
• To form the
• Once you use the
• Repeat the process until you form the string
Notice that you can use multiple characters from the same string in
Return the number of ways to form
Example 1:
Example 2:
Constraints:
•
•
• All strings in
•
•
1639. Number of Ways to Form a Target String Given a Dictionary
Topic: Array, String, Dynamic Programming
Difficulty: Hard
Problem:
You are given a list of strings of the same length
words and a string target.Your task is to form
target using the given words under the following rules:•
target should be formed from left to right.• To form the
i^th character (0-indexed) of target, you can choose the k^th character of the j^th string in words if target[i] = words[j][k].• Once you use the
k^th character of the j^th string of words, you can no longer use the x^th character of any string in words where x <= k. In other words, all characters to the left of or at index k become unusuable for every string.• Repeat the process until you form the string
target.Notice that you can use multiple characters from the same string in
words provided the conditions above are met.Return the number of ways to form
target from words. Since the answer may be too large, return it modulo 10^9 + 7.Example 1:
Input: words = ["acca","bbbb","caca"], target = "aba"
Output: 6
Explanation: There are 6 ways to form target.
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("caca")
"aba" -> index 0 ("acca"), index 1 ("bbbb"), index 3 ("acca")
"aba" -> index 0 ("acca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("acca")
"aba" -> index 1 ("caca"), index 2 ("bbbb"), index 3 ("caca")
Example 2:
Input: words = ["abba","baab"], target = "bab"
Output: 4
Explanation: There are 4 ways to form target.
"bab" -> index 0 ("baab"), index 1 ("baab"), index 2 ("abba")
"bab" -> index 0 ("baab"), index 1 ("baab"), index 3 ("baab")
"bab" -> index 0 ("baab"), index 2 ("baab"), index 3 ("baab")
"bab" -> index 1 ("abba"), index 2 ("baab"), index 3 ("baab")
Constraints:
•
1 <= words.length <= 1000•
1 <= words[i].length <= 1000• All strings in
words have the same length.•
1 <= target.length <= 1000•
words[i] and target contain only lowercase English letters.2023-04-17
1431. Kids With the Greatest Number of Candies
Topic: Array
Difficulty: Easy
Problem:
There are
Return a boolean array
Note that multiple kids can have the greatest number of candies.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
1431. Kids With the Greatest Number of Candies
Topic: Array
Difficulty: Easy
Problem:
There are
n kids with candies. You are given an integer array candies, where each candies[i] represents the number of candies the i^th kid has, and an integer extraCandies, denoting the number of extra candies that you have.Return a boolean array
result of length n, where result[i] is true if, after giving the i^th kid all the extraCandies, they will have the greatest number of candies among all the kids, or false otherwise.Note that multiple kids can have the greatest number of candies.
Example 1:
Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true]
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
Example 2:
Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false]
Explanation: There is only 1 extra candy.
Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.
Example 3:
Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]
Constraints:
•
n == candies.length•
2 <= n <= 100•
1 <= candies[i] <= 100•
1 <= extraCandies <= 502023-04-18
1768. Merge Strings Alternately
Topic: Two Pointers, String
Difficulty: Easy
Problem:
You are given two strings
Return the merged string.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1768. Merge Strings Alternately
Topic: Two Pointers, String
Difficulty: Easy
Problem:
You are given two strings
word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.Return the merged string.
Example 1:
Input: word1 = "abc", word2 = "pqr"
Output: "apbqcr"
Explanation: The merged string will be merged as so:
word1: a b c
word2: p q r
merged: a p b q c r
Example 2:
Input: word1 = "ab", word2 = "pqrs"
Output: "apbqrs"
Explanation: Notice that as word2 is longer, "rs" is appended to the end.
word1: a b
word2: p q r s
merged: a p b q r s
Example 3:
Input: word1 = "abcd", word2 = "pq"
Output: "apbqcd"
Explanation: Notice that as word1 is longer, "cd" is appended to the end.
word1: a b c d
word2: p q
merged: a p b q c d
Constraints:
•
1 <= word1.length, word2.length <= 100•
word1 and word2 consist of lowercase English letters.2023-04-19
1372. Longest ZigZag Path in a Binary Tree
Topic: Dynamic Programming, Tree, Depth-First Search, Binary Tree
Difficulty: Medium
Problem:
You are given the
A ZigZag path for a binary tree is defined as follow:
• Choose any node in the binary tree and a direction (right or left).
• If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
• Change the direction from right to left or from left to right.
• Repeat the second and third steps until you can't move in the tree.
Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).
Return the longest ZigZag path contained in that tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/22/sample_1_1702.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/01/22/sample_2_1702.png
Example 3:
Constraints:
• The number of nodes in the tree is in the range
•
1372. Longest ZigZag Path in a Binary Tree
Topic: Dynamic Programming, Tree, Depth-First Search, Binary Tree
Difficulty: Medium
Problem:
You are given the
root of a binary tree.A ZigZag path for a binary tree is defined as follow:
• Choose any node in the binary tree and a direction (right or left).
• If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
• Change the direction from right to left or from left to right.
• Repeat the second and third steps until you can't move in the tree.
Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).
Return the longest ZigZag path contained in that tree.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/22/sample_1_1702.png
Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).
Example 2:
Image: https://assets.leetcode.com/uploads/2020/01/22/sample_2_1702.png
Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).
Example 3:
Input: root = [1]
Output: 0
Constraints:
• The number of nodes in the tree is in the range
[1, 5 * 10^4].•
1 <= Node.val <= 1002023-04-20
662. Maximum Width of Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.
It is guaranteed that the answer will in the range of a 32-bit signed integer.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/05/03/width1-tree.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2022/03/14/maximum-width-of-binary-tree-v3.jpg
Example 3:
Image: https://assets.leetcode.com/uploads/2021/05/03/width3-tree.jpg
Constraints:
• The number of nodes in the tree is in the range
•
662. Maximum Width of Binary Tree
Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium
Problem:
Given the
root of a binary tree, return the maximum width of the given tree.The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.
It is guaranteed that the answer will in the range of a 32-bit signed integer.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/05/03/width1-tree.jpg
Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).
Example 2:
Image: https://assets.leetcode.com/uploads/2022/03/14/maximum-width-of-binary-tree-v3.jpg
Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).
Example 3:
Image: https://assets.leetcode.com/uploads/2021/05/03/width3-tree.jpg
Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width exists in the second level with length 2 (3,2).
Constraints:
• The number of nodes in the tree is in the range
[1, 3000].•
-100 <= Node.val <= 1002023-04-21
879. Profitable Schemes
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
There is a group of
Let's call a profitable scheme any subset of these crimes that generates at least
Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo
Example 1:
Example 2:
Constraints:
•
•
•
•
•
•
879. Profitable Schemes
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
There is a group of
n members, and a list of various crimes they could commit. The i^th crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can't participate in another crime.Let's call a profitable scheme any subset of these crimes that generates at least
minProfit profit, and the total number of members participating in that subset of crimes is at most n.Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo
10^9 + 7.Example 1:
Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.
Example 2:
Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: To make a profit of at least 5, the group could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).
Constraints:
•
1 <= n <= 100•
0 <= minProfit <= 100•
1 <= group.length <= 100•
1 <= group[i] <= 100•
profit.length == group.length•
0 <= profit[i] <= 1002023-04-22
1312. Minimum Insertion Steps to Make a String Palindrome
Topic: String, Dynamic Programming
Difficulty: Hard
Problem:
Given a string
Return the minimum number of steps to make
A Palindrome String is one that reads the same backward as well as forward.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1312. Minimum Insertion Steps to Make a String Palindrome
Topic: String, Dynamic Programming
Difficulty: Hard
Problem:
Given a string
s. In one step you can insert any character at any index of the string.Return the minimum number of steps to make
s palindrome.A Palindrome String is one that reads the same backward as well as forward.
Example 1:
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.
Example 2:
Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".
Example 3:
Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".
Constraints:
•
1 <= s.length <= 500•
s consists of lowercase English letters.2023-04-23
1416. Restore The Array
Topic: String, Dynamic Programming
Difficulty: Hard
Problem:
A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits
Given the string
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
1416. Restore The Array
Topic: String, Dynamic Programming
Difficulty: Hard
Problem:
A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits
s and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.Given the string
s and the integer k, return the number of the possible arrays that can be printed as s using the mentioned program. Since the answer may be very large, return it modulo 10^9 + 7.Example 1:
Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]
Example 2:
Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.
Example 3:
Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]
Constraints:
•
1 <= s.length <= 10^5•
s consists of only digits and does not contain leading zeros.•
1 <= k <= 10^92023-04-24
1046. Last Stone Weight
Topic: Array, Heap (Priority Queue)
Difficulty: Easy
Problem:
You are given an array of integers
We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights
• If
• If
At the end of the game, there is at most one stone left.
Return the weight of the last remaining stone. If there are no stones left, return
Example 1:
Example 2:
Constraints:
•
•
1046. Last Stone Weight
Topic: Array, Heap (Priority Queue)
Difficulty: Easy
Problem:
You are given an array of integers
stones where stones[i] is the weight of the i^th stone.We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights
x and y with x <= y. The result of this smash is:• If
x == y, both stones are destroyed, and• If
x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.At the end of the game, there is at most one stone left.
Return the weight of the last remaining stone. If there are no stones left, return
0.Example 1:
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.
Example 2:
Input: stones = [1]
Output: 1
Constraints:
•
1 <= stones.length <= 30•
1 <= stones[i] <= 10002023-04-25
2336. Smallest Number in Infinite Set
Topic: Hash Table, Design, Heap (Priority Queue)
Difficulty: Medium
Problem:
You have a set which contains all positive integers
Implement the
•
•
•
Example 1:
Constraints:
•
• At most
2336. Smallest Number in Infinite Set
Topic: Hash Table, Design, Heap (Priority Queue)
Difficulty: Medium
Problem:
You have a set which contains all positive integers
[1, 2, 3, 4, 5, ...].Implement the
SmallestInfiniteSet class:•
SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.•
int popSmallest() Removes and returns the smallest integer contained in the infinite set.•
void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.Example 1:
Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]
Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2); // 2 is already in the set, so no change is made.
smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.
smallestInfiniteSet.addBack(1); // 1 is added back to the set.
smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and
// is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.
Constraints:
•
1 <= num <= 1000• At most
1000 calls will be made in total to popSmallest and addBack.2023-04-26
258. Add Digits
Topic: Math, Simulation, Number Theory
Difficulty: Easy
Problem:
Given an integer
Example 1:
Example 2:
Constraints:
•
Follow up: Could you do it without any loop/recursion in
258. Add Digits
Topic: Math, Simulation, Number Theory
Difficulty: Easy
Problem:
Given an integer
num, repeatedly add all its digits until the result has only one digit, and return it.Example 1:
Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
Since 2 has only one digit, return it.
Example 2:
Input: num = 0
Output: 0
Constraints:
•
0 <= num <= 2^31 - 1Follow up: Could you do it without any loop/recursion in
O(1) runtime?2023-04-27
319. Bulb Switcher
Topic: Math, Brainteaser
Difficulty: Medium
Problem:
There are
On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the
Return the number of bulbs that are on after
Example 1:
Image: https://assets.leetcode.com/uploads/2020/11/05/bulb.jpg
Example 2:
Example 3:
Constraints:
•
319. Bulb Switcher
Topic: Math, Brainteaser
Difficulty: Medium
Problem:
There are
n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the
i^th round, you toggle every i bulb. For the n^th round, you only toggle the last bulb.Return the number of bulbs that are on after
n rounds.Example 1:
Image: https://assets.leetcode.com/uploads/2020/11/05/bulb.jpg
Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off].
So you should return 1 because there is only one bulb is on.
Example 2:
Input: n = 0
Output: 0
Example 3:
Input: n = 1
Output: 1
Constraints:
•
0 <= n <= 10^9