2023-08-14
215. Kth Largest Element in an Array
Topic: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect
Difficulty: Medium
Problem:
Given an integer array
Note that it is the
Can you solve it without sorting?
Example 1:
Example 2:
Constraints:
•
•
215. Kth Largest Element in an Array
Topic: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Quickselect
Difficulty: Medium
Problem:
Given an integer array
nums and an integer k, return the k^th largest element in the array.Note that it is the
k^th largest element in the sorted order, not the k^th distinct element.Can you solve it without sorting?
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
Constraints:
•
1 <= k <= nums.length <= 10^5•
-10^4 <= nums[i] <= 10^42023-08-15
86. Partition List
Topic: Linked List, Two Pointers
Difficulty: Medium
Problem:
Given the
You should preserve the original relative order of the nodes in each of the two partitions.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/04/partition.jpg
Example 2:
Constraints:
• The number of nodes in the list is in the range
•
•
86. Partition List
Topic: Linked List, Two Pointers
Difficulty: Medium
Problem:
Given the
head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.You should preserve the original relative order of the nodes in each of the two partitions.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/01/04/partition.jpg
Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Example 2:
Input: head = [2,1], x = 2
Output: [1,2]
Constraints:
• The number of nodes in the list is in the range
[0, 200].•
-100 <= Node.val <= 100•
-200 <= x <= 2002023-08-16
239. Sliding Window Maximum
Topic: Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue
Difficulty: Hard
Problem:
You are given an array of integers
Return the max sliding window.
Example 1:
Example 2:
Constraints:
•
•
•
239. Sliding Window Maximum
Topic: Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue
Difficulty: Hard
Problem:
You are given an array of integers
nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
•
1 <= nums.length <= 10^5•
-10^4 <= nums[i] <= 10^4•
1 <= k <= nums.length2023-08-17
542. 01 Matrix
Topic: Array, Dynamic Programming, Breadth-First Search, Matrix
Difficulty: Medium
Problem:
Given an
The distance between two adjacent cells is
Example 1:
Image: https://assets.leetcode.com/uploads/2021/04/24/01-1-grid.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/04/24/01-2-grid.jpg
Constraints:
•
•
•
•
•
• There is at least one
542. 01 Matrix
Topic: Array, Dynamic Programming, Breadth-First Search, Matrix
Difficulty: Medium
Problem:
Given an
m x n binary matrix mat, return the distance of the nearest 0 for each cell.The distance between two adjacent cells is
1.Example 1:
Image: https://assets.leetcode.com/uploads/2021/04/24/01-1-grid.jpg
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
Example 2:
Image: https://assets.leetcode.com/uploads/2021/04/24/01-2-grid.jpg
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
Constraints:
•
m == mat.length•
n == mat[i].length•
1 <= m, n <= 10^4•
1 <= m * n <= 10^4•
mat[i][j] is either 0 or 1.• There is at least one
0 in mat.2023-08-18
1615. Maximal Network Rank
Topic: Graph
Difficulty: Medium
Problem:
There is an infrastructure of
The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.
The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.
Given the integer
Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/21/ex1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/09/21/ex2.png
Example 3:
Constraints:
•
•
•
•
•
• Each pair of cities has at most one road connecting them.
1615. Maximal Network Rank
Topic: Graph
Difficulty: Medium
Problem:
There is an infrastructure of
n cities with some number of roads connecting these cities. Each roads[i] = [a_i, b_i] indicates that there is a bidirectional road between cities a_i and b_i.The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.
The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.
Given the integer
n and the array roads, return the maximal network rank of the entire infrastructure.Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/21/ex1.png
Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.
Example 2:
Image: https://assets.leetcode.com/uploads/2020/09/21/ex2.png
Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.
Example 3:
Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.
Constraints:
•
2 <= n <= 100•
0 <= roads.length <= n * (n - 1) / 2•
roads[i].length == 2•
0 <= a_i, b_i <= n-1•
a_i != b_i• Each pair of cities has at most one road connecting them.
2023-08-19
1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Topic: Union Find, Graph, Sorting, Minimum Spanning Tree, Strongly Connected Component
Difficulty: Hard
Problem:
Given a weighted undirected connected graph with
Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.
Note that you can return the indices of the edges in any order.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/06/04/ex1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2020/06/04/ex2.png
Constraints:
•
•
•
•
•
• All pairs
1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Topic: Union Find, Graph, Sorting, Minimum Spanning Tree, Strongly Connected Component
Difficulty: Hard
Problem:
Given a weighted undirected connected graph with
n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [a_i, b_i, weight_i] represents a bidirectional and weighted edge between nodes a_i and b_i. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight.Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.
Note that you can return the indices of the edges in any order.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/06/04/ex1.png
Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output: [[0,1],[2,3,4,5]]
Explanation: The figure above describes the graph.
The following figure shows all the possible MSTs:
Image: [https://assets.leetcode.com/uploads/2020/06/04/msts.png](https://assets.leetcode.com/uploads/2020/06/04/msts.png)
Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output.
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.
Example 2:
Image: https://assets.leetcode.com/uploads/2020/06/04/ex2.png
Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: [[],[0,1,2,3]]
Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.
Constraints:
•
2 <= n <= 100•
1 <= edges.length <= min(200, n * (n - 1) / 2)•
edges[i].length == 3•
0 <= a_i < b_i < n•
1 <= weight_i <= 1000• All pairs
(a_i, b_i) are distinct.2023-08-20
1203. Sort Items by Groups Respecting Dependencies
Topic: Depth-First Search, Breadth-First Search, Graph, Topological Sort
Difficulty: Hard
Problem:
There are
Return a sorted list of the items such that:
• The items that belong to the same group are next to each other in the sorted list.
• There are some relations between these items where
Return any solution if there is more than one solution and return an empty list if there is no solution.
Example 1:
Image: https://assets.leetcode.com/uploads/2019/09/11/1359_ex1.png
Example 2:
Constraints:
•
•
•
•
•
•
•
1203. Sort Items by Groups Respecting Dependencies
Topic: Depth-First Search, Breadth-First Search, Graph, Topological Sort
Difficulty: Hard
Problem:
There are
n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it's equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.Return a sorted list of the items such that:
• The items that belong to the same group are next to each other in the sorted list.
• There are some relations between these items where
beforeItems[i] is a list containing all the items that should come before the i-th item in the sorted array (to the left of the i-th item).Return any solution if there is more than one solution and return an empty list if there is no solution.
Example 1:
Image: https://assets.leetcode.com/uploads/2019/09/11/1359_ex1.png
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]
Example 2:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
Output: []
Explanation: This is the same as example 1 except that 4 needs to be before 6 in the sorted list.
Constraints:
•
1 <= m <= n <= 3 * 10^4•
group.length == beforeItems.length == n•
-1 <= group[i] <= m - 1•
0 <= beforeItems[i].length <= n - 1•
0 <= beforeItems[i][j] <= n - 1•
i != beforeItems[i][j]•
beforeItems[i]does not contain duplicates elements.2023-08-21
459. Repeated Substring Pattern
Topic: String, String Matching
Difficulty: Easy
Problem:
Given a string
Example 1:
Example 2:
Example 3:
Constraints:
•
•
459. Repeated Substring Pattern
Topic: String, String Matching
Difficulty: Easy
Problem:
Given a string
s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.Example 1:
Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.
Example 2:
Input: s = "aba"
Output: false
Example 3:
Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.
Constraints:
•
1 <= s.length <= 10^4•
s consists of lowercase English letters.2023-08-22
168. Excel Sheet Column Title
Topic: Math, String
Difficulty: Easy
Problem:
Given an integer
For example:
Example 1:
Example 2:
Example 3:
Constraints:
•
168. Excel Sheet Column Title
Topic: Math, String
Difficulty: Easy
Problem:
Given an integer
columnNumber, return its corresponding column title as it appears in an Excel sheet.For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
Example 1:
Input: columnNumber = 1
Output: "A"
Example 2:
Input: columnNumber = 28
Output: "AB"
Example 3:
Input: columnNumber = 701
Output: "ZY"
Constraints:
•
1 <= columnNumber <= 2^31 - 12023-08-23
767. Reorganize String
Topic: Hash Table, String, Greedy, Sorting, Heap (Priority Queue), Counting
Difficulty: Medium
Problem:
Given a string
Return any possible rearrangement of
Example 1:
Example 2:
Constraints:
•
•
767. Reorganize String
Topic: Hash Table, String, Greedy, Sorting, Heap (Priority Queue), Counting
Difficulty: Medium
Problem:
Given a string
s, rearrange the characters of s so that any two adjacent characters are not the same.Return any possible rearrangement of
s or return "" if not possible.Example 1:
Input: s = "aab"
Output: "aba"
Example 2:
Input: s = "aaab"
Output: ""
Constraints:
•
1 <= s.length <= 500•
s consists of lowercase English letters.2023-08-24
68. Text Justification
Topic: Array, String, Simulation
Difficulty: Hard
Problem:
Given an array of strings
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left-justified, and no extra space is inserted between words.
Note:
• A word is defined as a character sequence consisting of non-space characters only.
• Each word's length is guaranteed to be greater than
• The input array
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
•
68. Text Justification
Topic: Array, String, Simulation
Difficulty: Hard
Problem:
Given an array of strings
words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces
' ' when necessary so that each line has exactly maxWidth characters.Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left-justified, and no extra space is inserted between words.
Note:
• A word is defined as a character sequence consisting of non-space characters only.
• Each word's length is guaranteed to be greater than
0 and not exceed maxWidth.• The input array
words contains at least one word.Example 1:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
Example 2:
Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified because it contains only one word.
Example 3:
Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
Constraints:
•
1 <= words.length <= 300•
1 <= words[i].length <= 20•
words[i] consists of only English letters and symbols.•
1 <= maxWidth <= 100•
words[i].length <= maxWidth2023-08-25
97. Interleaving String
Topic: String, Dynamic Programming
Difficulty: Medium
Problem:
Given strings
An interleaving of two strings
•
•
•
• The interleaving is
Note:
Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/02/interleave.jpg
Example 2:
Example 3:
Constraints:
•
•
•
Follow up: Could you solve it using only
97. Interleaving String
Topic: String, Dynamic Programming
Difficulty: Medium
Problem:
Given strings
s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.An interleaving of two strings
s and t is a configuration where s and t are divided into n and m substrings respectively, such that:•
s = s_1 + s_2 + ... + s_n•
t = t_1 + t_2 + ... + t_m•
|n - m| <= 1• The interleaving is
s_1 + t_1 + s_2 + t_2 + s_3 + t_3 + ... or t_1 + s_1 + t_2 + s_2 + t_3 + s_3 + ...Note:
a + b is the concatenation of strings a and b.Example 1:
Image: https://assets.leetcode.com/uploads/2020/09/02/interleave.jpg
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.
Example 3:
Input: s1 = "", s2 = "", s3 = ""
Output: true
Constraints:
•
0 <= s1.length, s2.length <= 100•
0 <= s3.length <= 200•
s1, s2, and s3 consist of lowercase English letters.Follow up: Could you solve it using only
O(s2.length) additional memory space?2023-08-26
646. Maximum Length of Pair Chain
Topic: Array, Dynamic Programming, Greedy, Sorting
Difficulty: Medium
Problem:
You are given an array of
A pair
Return the length longest chain which can be formed.
You do not need to use up all the given intervals. You can select pairs in any order.
Example 1:
Example 2:
Constraints:
•
•
•
646. Maximum Length of Pair Chain
Topic: Array, Dynamic Programming, Greedy, Sorting
Difficulty: Medium
Problem:
You are given an array of
n pairs pairs where pairs[i] = [left_i, right_i] and left_i < right_i.A pair
p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.Return the length longest chain which can be formed.
You do not need to use up all the given intervals. You can select pairs in any order.
Example 1:
Input: pairs = [[1,2],[2,3],[3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4].
Example 2:
Input: pairs = [[1,2],[7,8],[4,5]]
Output: 3
Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].
Constraints:
•
n == pairs.length•
1 <= n <= 1000•
-1000 <= left_i < right_i <= 10002023-08-27
403. Frog Jump
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of
If the frog's last jump was
Example 1:
Example 2:
Constraints:
•
•
•
•
403. Frog Jump
Topic: Array, Dynamic Programming
Difficulty: Hard
Problem:
A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.
Given a list of
stones' positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.If the frog's last jump was
k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.Example 1:
Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.
Example 2:
Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.
Constraints:
•
2 <= stones.length <= 2000•
0 <= stones[i] <= 2^31 - 1•
stones[0] == 0•
stones is sorted in a strictly increasing order.2023-08-28
225. Implement Stack using Queues
Topic: Stack, Design, Queue
Difficulty: Easy
Problem:
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (
Implement the
•
•
•
•
Notes:
• You must use only standard operations of a queue, which means that only
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.
Example 1:
Constraints:
•
• At most
• All the calls to
Follow-up: Can you implement the stack using only one queue?
225. Implement Stack using Queues
Topic: Stack, Design, Queue
Difficulty: Easy
Problem:
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (
push, top, pop, and empty).Implement the
MyStack class:•
void push(int x) Pushes element x to the top of the stack.•
int pop() Removes the element on the top of the stack and returns it.•
int top() Returns the element on the top of the stack.•
boolean empty() Returns true if the stack is empty, false otherwise.Notes:
• You must use only standard operations of a queue, which means that only
push to back, peek/pop from front, size and is empty operations are valid.• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.
Example 1:
Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
Constraints:
•
1 <= x <= 9• At most
100 calls will be made to push, pop, top, and empty.• All the calls to
pop and top are valid.Follow-up: Can you implement the stack using only one queue?
2023-08-29
2483. Minimum Penalty for a Shop
Topic: String, Prefix Sum
Difficulty: Medium
Problem:
You are given the customer visit log of a shop represented by a 0-indexed string
• if the
• whereas
If the shop closes at the
• For every hour when the shop is open and no customers come, the penalty increases by
• For every hour when the shop is closed and customers come, the penalty increases by
Return the earliest hour at which the shop must be closed to incur a minimum penalty.
Note that if a shop closes at the
Example 1:
Example 2:
Example 3:
Constraints:
•
•
2483. Minimum Penalty for a Shop
Topic: String, Prefix Sum
Difficulty: Medium
Problem:
You are given the customer visit log of a shop represented by a 0-indexed string
customers consisting only of characters 'N' and 'Y':• if the
i^th character is 'Y', it means that customers come at the i^th hour• whereas
'N' indicates that no customers come at the i^th hour.If the shop closes at the
j^th hour (0 <= j <= n), the penalty is calculated as follows:• For every hour when the shop is open and no customers come, the penalty increases by
1.• For every hour when the shop is closed and customers come, the penalty increases by
1.Return the earliest hour at which the shop must be closed to incur a minimum penalty.
Note that if a shop closes at the
j^th hour, it means the shop is closed at the hour j.Example 1:
Input: customers = "YYNY"
Output: 2
Explanation:
- Closing the shop at the 0^th hour incurs in 1+1+0+1 = 3 penalty.
- Closing the shop at the 1^st hour incurs in 0+1+0+1 = 2 penalty.
- Closing the shop at the 2^nd hour incurs in 0+0+0+1 = 1 penalty.
- Closing the shop at the 3^rd hour incurs in 0+0+1+1 = 2 penalty.
- Closing the shop at the 4^th hour incurs in 0+0+1+0 = 1 penalty.
Closing the shop at 2^nd or 4^th hour gives a minimum penalty. Since 2 is earlier, the optimal closing time is 2.
Example 2:
Input: customers = "NNNNN"
Output: 0
Explanation: It is best to close the shop at the 0^th hour as no customers arrive.
Example 3:
Input: customers = "YYYY"
Output: 4
Explanation: It is best to close the shop at the 4^th hour as customers arrive at each hour.
Constraints:
•
1 <= customers.length <= 10^5•
customers consists only of characters 'Y' and 'N'.2023-08-30
2366. Minimum Replacements to Sort the Array
Topic: Array, Math, Greedy
Difficulty: Hard
Problem:
You are given a 0-indexed integer array
• For example, consider
Return the minimum number of operations to make an array that is sorted in non-decreasing order.
Example 1:
Example 2:
Constraints:
•
•
2366. Minimum Replacements to Sort the Array
Topic: Array, Math, Greedy
Difficulty: Hard
Problem:
You are given a 0-indexed integer array
nums. In one operation you can replace any element of the array with any two elements that sum to it.• For example, consider
nums = [5,6,7]. In one operation, we can replace nums[1] with 2 and 4 and convert nums to [5,2,4,7].Return the minimum number of operations to make an array that is sorted in non-decreasing order.
Example 1:
Input: nums = [3,9,3]
Output: 2
Explanation: Here are the steps to sort the array in non-decreasing order:
- From [3,9,3], replace the 9 with 3 and 6 so the array becomes [3,3,6,3]
- From [3,3,6,3], replace the 6 with 3 and 3 so the array becomes [3,3,3,3,3]
There are 2 steps to sort the array in non-decreasing order. Therefore, we return 2.
Example 2:
Input: nums = [1,2,3,4,5]
Output: 0
Explanation: The array is already in non-decreasing order. Therefore, we return 0.
Constraints:
•
1 <= nums.length <= 10^5•
1 <= nums[i] <= 10^92023-08-31
1326. Minimum Number of Taps to Open to Water a Garden
Topic: Array, Dynamic Programming, Greedy
Difficulty: Hard
Problem:
There is a one-dimensional garden on the x-axis. The garden starts at the point
There are
Given an integer
Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/16/1685_example_1.png
Example 2:
Constraints:
•
•
•
1326. Minimum Number of Taps to Open to Water a Garden
Topic: Array, Dynamic Programming, Greedy
Difficulty: Hard
Problem:
There is a one-dimensional garden on the x-axis. The garden starts at the point
0 and ends at the point n. (i.e The length of the garden is n).There are
n + 1 taps located at points [0, 1, ..., n] in the garden.Given an integer
n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.
Example 1:
Image: https://assets.leetcode.com/uploads/2020/01/16/1685_example_1.png
Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]
Example 2:
Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.
Constraints:
•
1 <= n <= 10^4•
ranges.length == n + 1•
0 <= ranges[i] <= 1002023-09-01
338. Counting Bits
Topic: Dynamic Programming, Bit Manipulation
Difficulty: Easy
Problem:
Given an integer
Example 1:
Example 2:
Constraints:
•
Follow up:
• It is very easy to come up with a solution with a runtime of
• Can you do it without using any built-in function (i.e., like
338. Counting Bits
Topic: Dynamic Programming, Bit Manipulation
Difficulty: Easy
Problem:
Given an integer
n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Constraints:
•
0 <= n <= 10^5Follow up:
• It is very easy to come up with a solution with a runtime of
O(n log n). Can you do it in linear time O(n) and possibly in a single pass?• Can you do it without using any built-in function (i.e., like
__builtin_popcount in C++)?2023-09-02
2707. Extra Characters in a String
Topic: Array, Hash Table, String, Dynamic Programming, Trie
Difficulty: Medium
Problem:
You are given a 0-indexed string
Return the minimum number of extra characters left over if you break up
Example 1:
Example 2:
Constraints:
•
•
•
•
•
2707. Extra Characters in a String
Topic: Array, Hash Table, String, Dynamic Programming, Trie
Difficulty: Medium
Problem:
You are given a 0-indexed string
s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings.Return the minimum number of extra characters left over if you break up
s optimally.Example 1:
Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
Explanation: We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.
Example 2:
Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
Explanation: We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.
Constraints:
•
1 <= s.length <= 50•
1 <= dictionary.length <= 50•
1 <= dictionary[i].length <= 50•
dictionary[i] and s consists of only lowercase English letters•
dictionary contains distinct words