2024-11-15
1574. Shortest Subarray to be Removed to Make Array Sorted
Topic: Array, Two Pointers, Binary Search, Stack, Monotonic Stack
Difficulty: Medium
Problem:
Given an integer array
Return the length of the shortest subarray to remove.
A subarray is a contiguous subsequence of the array.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1574. Shortest Subarray to be Removed to Make Array Sorted
Topic: Array, Two Pointers, Binary Search, Stack, Monotonic Stack
Difficulty: Medium
Problem:
Given an integer array
arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.Return the length of the shortest subarray to remove.
A subarray is a contiguous subsequence of the array.
Example 1:
Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].
Example 2:
Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].
Example 3:
Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.
Constraints:
•
1 <= arr.length <= 10^5•
0 <= arr[i] <= 10^92024-11-16
3254. Find the Power of K-Size Subarrays I
Topic: Array, Sliding Window
Difficulty: Medium
Problem:
You are given an array of integers
The power of an array is defined as:
• Its maximum element if all of its elements are consecutive and sorted in ascending order.
• -1 otherwise.
You need to find the power of all subarrays of
Return an integer array
Example 1:
Input: nums = 1,2,3,4,3,2,5, k = 3
Output: 3,4,-1,-1,-1
Explanation:
There are 5 subarrays of
•
•
•
•
•
Example 2:
Input: nums = 2,2,2,2,2, k = 4
Output: -1,-1
Example 3:
Input: nums = 3,2,3,2,3,2, k = 2
Output: -1,3,-1,3,-1
Constraints:
•
•
•
3254. Find the Power of K-Size Subarrays I
Topic: Array, Sliding Window
Difficulty: Medium
Problem:
You are given an array of integers
nums of length n and a positive integer k.The power of an array is defined as:
• Its maximum element if all of its elements are consecutive and sorted in ascending order.
• -1 otherwise.
You need to find the power of all subarrays of
nums of size k.Return an integer array
results of size n - k + 1, where results[i] is the power of nums[i..(i + k - 1)].Example 1:
Input: nums = 1,2,3,4,3,2,5, k = 3
Output: 3,4,-1,-1,-1
Explanation:
There are 5 subarrays of
nums of size 3:•
[1, 2, 3] with the maximum element 3.•
[2, 3, 4] with the maximum element 4.•
[3, 4, 3] whose elements are not consecutive.•
[4, 3, 2] whose elements are not sorted.•
[3, 2, 5] whose elements are not consecutive.Example 2:
Input: nums = 2,2,2,2,2, k = 4
Output: -1,-1
Example 3:
Input: nums = 3,2,3,2,3,2, k = 2
Output: -1,3,-1,3,-1
Constraints:
•
1 <= n == nums.length <= 500•
1 <= nums[i] <= 10^5•
1 <= k <= n2024-11-17
862. Shortest Subarray with Sum at Least K
Topic: Array, Binary Search, Queue, Sliding Window, Heap (Priority Queue), Prefix Sum, Monotonic Queue
Difficulty: Hard
Problem:
Given an integer array
A subarray is a contiguous part of an array.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
862. Shortest Subarray with Sum at Least K
Topic: Array, Binary Search, Queue, Sliding Window, Heap (Priority Queue), Prefix Sum, Monotonic Queue
Difficulty: Hard
Problem:
Given an integer array
nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1], k = 1
Output: 1
Example 2:
Input: nums = [1,2], k = 4
Output: -1
Example 3:
Input: nums = [2,-1,2], k = 3
Output: 3
Constraints:
•
1 <= nums.length <= 10^5•
-10^5 <= nums[i] <= 10^5•
1 <= k <= 10^92024-11-18
1652. Defuse the Bomb
Topic: Array, Sliding Window
Difficulty: Easy
Problem:
You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array
To decrypt the code, you must replace every number. All the numbers are replaced simultaneously.
• If
• If
• If
As
Given the circular array
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
1652. Defuse the Bomb
Topic: Array, Sliding Window
Difficulty: Easy
Problem:
You have a bomb to defuse, and your time is running out! Your informer will provide you with a circular array
code of length of n and a key k.To decrypt the code, you must replace every number. All the numbers are replaced simultaneously.
• If
k > 0, replace the i^th number with the sum of the next k numbers.• If
k < 0, replace the i^th number with the sum of the previous k numbers.• If
k == 0, replace the i^th number with 0.As
code is circular, the next element of code[n-1] is code[0], and the previous element of code[0] is code[n-1].Given the circular array
code and an integer key k, return the decrypted code to defuse the bomb!Example 1:
Input: code = [5,7,1,4], k = 3
Output: [12,10,16,13]
Explanation: Each number is replaced by the sum of the next 3 numbers. The decrypted code is [7+1+4, 1+4+5, 4+5+7, 5+7+1]. Notice that the numbers wrap around.
Example 2:
Input: code = [1,2,3,4], k = 0
Output: [0,0,0,0]
Explanation: When k is zero, the numbers are replaced by 0.
Example 3:
Input: code = [2,4,9,3], k = -2
Output: [12,5,6,13]
Explanation: The decrypted code is [3+9, 2+3, 4+2, 9+4]. Notice that the numbers wrap around again. If k is negative, the sum is of the previous numbers.
Constraints:
•
n == code.length•
1 <= n <= 100•
1 <= code[i] <= 100•
-(n - 1) <= k <= n - 12024-11-19
2461. Maximum Sum of Distinct Subarrays With Length K
Topic: Array, Hash Table, Sliding Window
Difficulty: Medium
Problem:
You are given an integer array
• The length of the subarray is
• All the elements of the subarray are distinct.
Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Example 2:
Constraints:
•
•
2461. Maximum Sum of Distinct Subarrays With Length K
Topic: Array, Hash Table, Sliding Window
Difficulty: Medium
Problem:
You are given an integer array
nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:• The length of the subarray is
k, and• All the elements of the subarray are distinct.
Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return
0.A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions
Example 2:
Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.
Constraints:
•
1 <= k <= nums.length <= 10^5•
1 <= nums[i] <= 10^52024-11-20
2516. Take K of Each Character From Left and Right
Topic: Hash Table, String, Sliding Window
Difficulty: Medium
Problem:
You are given a string
Return the minimum number of minutes needed for you to take at least
Example 1:
Example 2:
Constraints:
•
•
•
2516. Take K of Each Character From Left and Right
Topic: Hash Table, String, Sliding Window
Difficulty: Medium
Problem:
You are given a string
s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k. Each minute, you may take either the leftmost character of s, or the rightmost character of s.Return the minimum number of minutes needed for you to take at least
k of each character, or return -1 if it is not possible to take k of each character.Example 1:
Input: s = "aabaaaacaabc", k = 2
Output: 8
Explanation:
Take three characters from the left of s. You now have two 'a' characters, and one 'b' character.
Take five characters from the right of s. You now have four 'a' characters, two 'b' characters, and two 'c' characters.
A total of 3 + 5 = 8 minutes is needed.
It can be proven that 8 is the minimum number of minutes needed.
Example 2:
Input: s = "a", k = 1
Output: -1
Explanation: It is not possible to take one 'b' or 'c' so return -1.
Constraints:
•
1 <= s.length <= 10^5•
s consists of only the letters 'a', 'b', and 'c'.•
0 <= k <= s.length2024-11-21
2257. Count Unguarded Cells in the Grid
Topic: Array, Matrix, Simulation
Difficulty: Medium
Problem:
You are given two integers
A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it.
Return the number of unoccupied cells that are not guarded.
Example 1:
Image: https://assets.leetcode.com/uploads/2022/03/10/example1drawio2.png
Example 2:
Image: https://assets.leetcode.com/uploads/2022/03/10/example2drawio.png
Constraints:
•
•
•
•
•
•
•
• All the positions in
2257. Count Unguarded Cells in the Grid
Topic: Array, Matrix, Simulation
Difficulty: Medium
Problem:
You are given two integers
m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays guards and walls where guards[i] = [row_i, col_i] and walls[j] = [row_j, col_j] represent the positions of the i^th guard and j^th wall respectively.A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it.
Return the number of unoccupied cells that are not guarded.
Example 1:
Image: https://assets.leetcode.com/uploads/2022/03/10/example1drawio2.png
Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
Output: 7
Explanation: The guarded and unguarded cells are shown in red and green respectively in the above diagram.
There are a total of 7 unguarded cells, so we return 7.
Example 2:
Image: https://assets.leetcode.com/uploads/2022/03/10/example2drawio.png
Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
Output: 4
Explanation: The unguarded cells are shown in green in the above diagram.
There are a total of 4 unguarded cells, so we return 4.
Constraints:
•
1 <= m, n <= 10^5•
2 <= m * n <= 10^5•
1 <= guards.length, walls.length <= 5 * 10^4•
2 <= guards.length + walls.length <= m * n•
guards[i].length == walls[j].length == 2•
0 <= row_i, row_j < m•
0 <= col_i, col_j < n• All the positions in
guards and walls are unique.2024-11-22
1072. Flip Columns For Maximum Number of Equal Rows
Topic: Array, Hash Table, Matrix
Difficulty: Medium
Problem:
You are given an
You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from
Return the maximum number of rows that have all values equal after some number of flips.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
1072. Flip Columns For Maximum Number of Equal Rows
Topic: Array, Hash Table, Matrix
Difficulty: Medium
Problem:
You are given an
m x n binary matrix matrix.You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from
0 to 1 or vice versa).Return the maximum number of rows that have all values equal after some number of flips.
Example 1:
Input: matrix = [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.
Example 2:
Input: matrix = [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.
Example 3:
Input: matrix = [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.
Constraints:
•
m == matrix.length•
n == matrix[i].length•
1 <= m, n <= 300•
matrix[i][j] is either 0 or 1.2024-11-23
1861. Rotating the Box
Topic: Array, Two Pointers, Matrix
Difficulty: Medium
Problem:
You are given an
• A stone
• A stationary obstacle
• Empty
The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity does not affect the obstacles' positions, and the inertia from the box's rotation does not affect the stones' horizontal positions.
It is guaranteed that each stone in
Return an
Example 1:
Image: https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcodewithstones.png
Example 2:
Image: https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcode2withstones.png
Example 3:
Image: https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcode3withstone.png
Constraints:
•
•
•
•
1861. Rotating the Box
Topic: Array, Two Pointers, Matrix
Difficulty: Medium
Problem:
You are given an
m x n matrix of characters box representing a side-view of a box. Each cell of the box is one of the following:• A stone
'#'• A stationary obstacle
'*'• Empty
'.'The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity does not affect the obstacles' positions, and the inertia from the box's rotation does not affect the stones' horizontal positions.
It is guaranteed that each stone in
box rests on an obstacle, another stone, or the bottom of the box.Return an
n x m matrix representing the box after the rotation described above.Example 1:
Image: https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcodewithstones.png
Input: box = [["#",".","#"]]
Output: [["."],
["#"],
["#"]]
Example 2:
Image: https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcode2withstones.png
Input: box = [["#",".","*","."],
["#","#","*","."]]
Output: [["#","."],
["#","#"],
["*","*"],
[".","."]]
Example 3:
Image: https://assets.leetcode.com/uploads/2021/04/08/rotatingtheboxleetcode3withstone.png
Input: box = [["#","#","*",".","*","."],
["#","#","#","*",".","."],
["#","#","#",".","#","."]]
Output: [[".","#","#"],
[".","#","#"],
["#","#","*"],
["#","*","."],
["#",".","*"],
["#",".","."]]
Constraints:
•
m == box.length•
n == box[i].length•
1 <= m, n <= 500•
box[i][j] is either '#', '*', or '.'.2024-11-24
1975. Maximum Matrix Sum
Topic: Array, Greedy, Matrix
Difficulty: Medium
Problem:
You are given an
• Choose any two adjacent elements of
Two elements are considered adjacent if and only if they share a border.
Your goal is to maximize the summation of the matrix's elements. Return the maximum sum of the matrix's elements using the operation mentioned above.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex2.png
Constraints:
•
•
•
1975. Maximum Matrix Sum
Topic: Array, Greedy, Matrix
Difficulty: Medium
Problem:
You are given an
n x n integer matrix. You can do the following operation any number of times:• Choose any two adjacent elements of
matrix and multiply each of them by -1.Two elements are considered adjacent if and only if they share a border.
Your goal is to maximize the summation of the matrix's elements. Return the maximum sum of the matrix's elements using the operation mentioned above.
Example 1:
Image: https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex1.png
Input: matrix = [[1,-1],[-1,1]]
Output: 4
Explanation: We can follow the following steps to reach sum equals 4:
- Multiply the 2 elements in the first row by -1.
- Multiply the 2 elements in the first column by -1.
Example 2:
Image: https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex2.png
Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
Output: 16
Explanation: We can follow the following step to reach sum equals 16:
- Multiply the 2 last elements in the second row by -1.
Constraints:
•
n == matrix.length == matrix[i].length•
2 <= n <= 250•
-10^5 <= matrix[i][j] <= 10^52024-11-25
773. Sliding Puzzle
Topic: Array, Breadth-First Search, Matrix
Difficulty: Hard
Problem:
On an
The state of the board is solved if and only if the board is
Given the puzzle board
Example 1:
Image: https://assets.leetcode.com/uploads/2021/06/29/slide1-grid.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2021/06/29/slide2-grid.jpg
Example 3:
Image: https://assets.leetcode.com/uploads/2021/06/29/slide3-grid.jpg
Constraints:
•
•
•
• Each value
773. Sliding Puzzle
Topic: Array, Breadth-First Search, Matrix
Difficulty: Hard
Problem:
On an
2 x 3 board, there are five tiles labeled from 1 to 5, and an empty square represented by 0. A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.The state of the board is solved if and only if the board is
[[1,2,3],[4,5,0]].Given the puzzle board
board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.Example 1:
Image: https://assets.leetcode.com/uploads/2021/06/29/slide1-grid.jpg
Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.
Example 2:
Image: https://assets.leetcode.com/uploads/2021/06/29/slide2-grid.jpg
Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.
Example 3:
Image: https://assets.leetcode.com/uploads/2021/06/29/slide3-grid.jpg
Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]
Constraints:
•
board.length == 2•
board[i].length == 3•
0 <= board[i][j] <= 5• Each value
board[i][j] is unique.2024-11-26
2924. Find Champion II
Topic: Graph
Difficulty: Medium
Problem:
There are
You are given the integer
A directed edge from
Team
Return the team that will be the champion of the tournament if there is a unique champion, otherwise, return
Notes
• A cycle is a series of nodes
• A DAG is a directed graph that does not have any cycle.
Example 1:
Image: https://assets.leetcode.com/uploads/2023/10/19/graph-3.png
Example 2:
Image: https://assets.leetcode.com/uploads/2023/10/19/graph-4.png
Constraints:
•
•
•
•
•
•
• The input is generated such that if team
• The input is generated such that if team
2924. Find Champion II
Topic: Graph
Difficulty: Medium
Problem:
There are
n teams numbered from 0 to n - 1 in a tournament; each team is also a node in a DAG.You are given the integer
n and a 0-indexed 2D integer array edges of length m representing the DAG, where edges[i] = [u_i, v_i] indicates that there is a directed edge from team u_i to team v_i in the graph.A directed edge from
a to b in the graph means that team a is stronger than team b and team b is weaker than team a.Team
a will be the champion of the tournament if there is no team b that is stronger than team a.Return the team that will be the champion of the tournament if there is a unique champion, otherwise, return
-1.Notes
• A cycle is a series of nodes
a_1, a_2, ..., a_n, a_n+1 such that node a_1 is the same node as node a_n+1, the nodes a_1, a_2, ..., a_n are distinct, and there is a directed edge from the node a_i to node a_i+1 for every i in the range [1, n].• A DAG is a directed graph that does not have any cycle.
Example 1:
Image: https://assets.leetcode.com/uploads/2023/10/19/graph-3.png
Input: n = 3, edges = [[0,1],[1,2]]
Output: 0
Explanation: Team 1 is weaker than team 0. Team 2 is weaker than team 1. So the champion is team 0.
Example 2:
Image: https://assets.leetcode.com/uploads/2023/10/19/graph-4.png
Input: n = 4, edges = [[0,2],[1,3],[1,2]]
Output: -1
Explanation: Team 2 is weaker than team 0 and team 1. Team 3 is weaker than team 1. But team 1 and team 0 are not weaker than any other teams. So the answer is -1.
Constraints:
•
1 <= n <= 100•
m == edges.length•
0 <= m <= n * (n - 1) / 2•
edges[i].length == 2•
0 <= edge[i][j] <= n - 1•
edges[i][0] != edges[i][1]• The input is generated such that if team
a is stronger than team b, team b is not stronger than team a.• The input is generated such that if team
a is stronger than team b and team b is stronger than team c, then team a is stronger than team c.2024-11-27
3243. Shortest Distance After Road Addition Queries I
Topic: Array, Breadth-First Search, Graph
Difficulty: Medium
Problem:
You are given an integer
There are
Return an array
Example 1:
Input: n = 5, queries = [2,4,0,2,0,4]
Output: 3,2,1
Explanation:
Image: https://assets.leetcode.com/uploads/2024/06/28/image8.jpg
After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.
Image: https://assets.leetcode.com/uploads/2024/06/28/image9.jpg
After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.
Image: https://assets.leetcode.com/uploads/2024/06/28/image10.jpg
After the addition of the road from 0 to 4, the length of the shortest path from 0 to 4 is 1.
Example 2:
Input: n = 4, queries = [0,3,0,2]
Output: 1,1
Explanation:
Image: https://assets.leetcode.com/uploads/2024/06/28/image11.jpg
After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.
Image: https://assets.leetcode.com/uploads/2024/06/28/image12.jpg
After the addition of the road from 0 to 2, the length of the shortest path remains 1.
Constraints:
•
•
•
•
•
• There are no repeated roads among the queries.
3243. Shortest Distance After Road Addition Queries I
Topic: Array, Breadth-First Search, Graph
Difficulty: Medium
Problem:
You are given an integer
n and a 2D integer array queries.There are
n cities numbered from 0 to n - 1. Initially, there is a unidirectional road from city i to city i + 1 for all 0 <= i < n - 1.queries[i] = [u_i, v_i] represents the addition of a new unidirectional road from city u_i to city v_i. After each query, you need to find the length of the shortest path from city 0 to city n - 1.Return an array
answer where for each i in the range [0, queries.length - 1], answer[i] is the length of the shortest path from city 0 to city n - 1 after processing the first i + 1 queries.Example 1:
Input: n = 5, queries = [2,4,0,2,0,4]
Output: 3,2,1
Explanation:
Image: https://assets.leetcode.com/uploads/2024/06/28/image8.jpg
After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.
Image: https://assets.leetcode.com/uploads/2024/06/28/image9.jpg
After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.
Image: https://assets.leetcode.com/uploads/2024/06/28/image10.jpg
After the addition of the road from 0 to 4, the length of the shortest path from 0 to 4 is 1.
Example 2:
Input: n = 4, queries = [0,3,0,2]
Output: 1,1
Explanation:
Image: https://assets.leetcode.com/uploads/2024/06/28/image11.jpg
After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.
Image: https://assets.leetcode.com/uploads/2024/06/28/image12.jpg
After the addition of the road from 0 to 2, the length of the shortest path remains 1.
Constraints:
•
3 <= n <= 500•
1 <= queries.length <= 500•
queries[i].length == 2•
0 <= queries[i][0] < queries[i][1] < n•
1 < queries[i][1] - queries[i][0]• There are no repeated roads among the queries.
2024-11-28
2290. Minimum Obstacle Removal to Reach Corner
Topic: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path
Difficulty: Hard
Problem:
You are given a 0-indexed 2D integer array
•
•
You can move up, down, left, or right from and to an empty cell.
Return the minimum number of obstacles to remove so you can move from the upper left corner
Example 1:
Image: https://assets.leetcode.com/uploads/2022/04/06/example1drawio-1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2022/04/06/example1drawio.png
Constraints:
•
•
•
•
•
•
2290. Minimum Obstacle Removal to Reach Corner
Topic: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path
Difficulty: Hard
Problem:
You are given a 0-indexed 2D integer array
grid of size m x n. Each cell has one of two values:•
0 represents an empty cell,•
1 represents an obstacle that may be removed.You can move up, down, left, or right from and to an empty cell.
Return the minimum number of obstacles to remove so you can move from the upper left corner
(0, 0) to the lower right corner (m - 1, n - 1).Example 1:
Image: https://assets.leetcode.com/uploads/2022/04/06/example1drawio-1.png
Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
Output: 2
Explanation: We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2).
It can be shown that we need to remove at least 2 obstacles, so we return 2.
Note that there may be other ways to remove 2 obstacles to create a path.
Example 2:
Image: https://assets.leetcode.com/uploads/2022/04/06/example1drawio.png
Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
Output: 0
Explanation: We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.
Constraints:
•
m == grid.length•
n == grid[i].length•
1 <= m, n <= 10^5•
2 <= m * n <= 10^5•
grid[i][j] is either 0 or 1.•
grid[0][0] == grid[m - 1][n - 1] == 02024-11-29
2577. Minimum Time to Visit a Cell In a Grid
Topic: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path
Difficulty: Hard
Problem:
You are given a
You are standing in the top-left cell of the matrix in the
Return the minimum time required in which you can visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, then return
Example 1:
Image: https://assets.leetcode.com/uploads/2023/02/14/yetgriddrawio-8.png
Example 2:
Image: https://assets.leetcode.com/uploads/2023/02/14/yetgriddrawio-9.png
Constraints:
•
•
•
•
•
•
.spoilerbutton {display:block; border:dashed; padding: 0px 0px; margin:10px 0px; font-size:150%; font-weight: bold; color:#000000; background-color:cyan; outline:0;
}
.spoiler {overflow:hidden;}
.spoiler > div {-webkit-transition: all 0s ease;-moz-transition: margin 0s ease;-o-transition: all 0s ease;transition: margin 0s ease;}
.spoilerbuttonvalue="Show Message" + .spoiler > div {margin-top:-500%;}
.spoilerbuttonvalue="Hide Message" + .spoiler {padding:5px;}
2577. Minimum Time to Visit a Cell In a Grid
Topic: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path
Difficulty: Hard
Problem:
You are given a
m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which means you can visit the cell (row, col) only when the time you visit it is greater than or equal to grid[row][col].You are standing in the top-left cell of the matrix in the
0^th second, and you must move to any adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second.Return the minimum time required in which you can visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, then return
-1.Example 1:
Image: https://assets.leetcode.com/uploads/2023/02/14/yetgriddrawio-8.png
Input: grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
Output: 7
Explanation: One of the paths that we can take is the following:
- at t = 0, we are on the cell (0,0).
- at t = 1, we move to the cell (0,1). It is possible because grid[0][1] <= 1.
- at t = 2, we move to the cell (1,1). It is possible because grid[1][1] <= 2.
- at t = 3, we move to the cell (1,2). It is possible because grid[1][2] <= 3.
- at t = 4, we move to the cell (1,1). It is possible because grid[1][1] <= 4.
- at t = 5, we move to the cell (1,2). It is possible because grid[1][2] <= 5.
- at t = 6, we move to the cell (1,3). It is possible because grid[1][3] <= 6.
- at t = 7, we move to the cell (2,3). It is possible because grid[2][3] <= 7.
The final time is 7. It can be shown that it is the minimum time possible.
Example 2:
Image: https://assets.leetcode.com/uploads/2023/02/14/yetgriddrawio-9.png
Input: grid = [[0,2,4],[3,2,1],[1,0,4]]
Output: -1
Explanation: There is no path from the top left to the bottom-right cell.
Constraints:
•
m == grid.length•
n == grid[i].length•
2 <= m, n <= 1000•
4 <= m * n <= 10^5•
0 <= grid[i][j] <= 10^5•
grid[0][0] == 0.spoilerbutton {display:block; border:dashed; padding: 0px 0px; margin:10px 0px; font-size:150%; font-weight: bold; color:#000000; background-color:cyan; outline:0;
}
.spoiler {overflow:hidden;}
.spoiler > div {-webkit-transition: all 0s ease;-moz-transition: margin 0s ease;-o-transition: all 0s ease;transition: margin 0s ease;}
.spoilerbuttonvalue="Show Message" + .spoiler > div {margin-top:-500%;}
.spoilerbuttonvalue="Hide Message" + .spoiler {padding:5px;}
2024-11-30
2097. Valid Arrangement of Pairs
Topic: Depth-First Search, Graph, Eulerian Circuit
Difficulty: Hard
Problem:
You are given a 0-indexed 2D integer array
Return any valid arrangement of
Note: The inputs will be generated such that there exists a valid arrangement of
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
• No two pairs are exactly the same.
• There exists a valid arrangement of
2097. Valid Arrangement of Pairs
Topic: Depth-First Search, Graph, Eulerian Circuit
Difficulty: Hard
Problem:
You are given a 0-indexed 2D integer array
pairs where pairs[i] = [start_i, end_i]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have end_i-1 == start_i.Return any valid arrangement of
pairs.Note: The inputs will be generated such that there exists a valid arrangement of
pairs.Example 1:
Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
Output: [[11,9],[9,4],[4,5],[5,1]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end_0 = 9 == 9 = start_1
end_1 = 4 == 4 = start_2
end_2 = 5 == 5 = start_3
Example 2:
Input: pairs = [[1,3],[3,2],[2,1]]
Output: [[1,3],[3,2],[2,1]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end_0 = 3 == 3 = start_1
end_1 = 2 == 2 = start_2
The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.
Example 3:
Input: pairs = [[1,2],[1,3],[2,1]]
Output: [[1,2],[2,1],[1,3]]
Explanation:
This is a valid arrangement since end_i-1 always equals start_i.
end_0 = 2 == 2 = start_1
end_1 = 1 == 1 = start_2
Constraints:
•
1 <= pairs.length <= 10^5•
pairs[i].length == 2•
0 <= start_i, end_i <= 10^9•
start_i != end_i• No two pairs are exactly the same.
• There exists a valid arrangement of
pairs.2024-12-01
1346. Check If N and Its Double Exist
Topic: Array, Hash Table, Two Pointers, Binary Search, Sorting
Difficulty: Easy
Problem:
Given an array
•
•
•
Example 1:
Example 2:
Constraints:
•
•
1346. Check If N and Its Double Exist
Topic: Array, Hash Table, Two Pointers, Binary Search, Sorting
Difficulty: Easy
Problem:
Given an array
arr of integers, check if there exist two indices i and j such that :•
i != j•
0 <= i, j < arr.length•
arr[i] == 2 * arr[j]Example 1:
Input: arr = [10,2,5,3]
Output: true
Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]
Example 2:
Input: arr = [3,1,7,11]
Output: false
Explanation: There is no i and j that satisfy the conditions.
Constraints:
•
2 <= arr.length <= 500•
-10^3 <= arr[i] <= 10^32024-12-02
1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence
Topic: Two Pointers, String, String Matching
Difficulty: Easy
Problem:
Given a
Return the index of the word in
A prefix of a string
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence
Topic: Two Pointers, String, String Matching
Difficulty: Easy
Problem:
Given a
sentence that consists of some words separated by a single space, and a searchWord, check if searchWord is a prefix of any word in sentence.Return the index of the word in
sentence (1-indexed) where searchWord is a prefix of this word. If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.A prefix of a string
s is any leading contiguous substring of s.Example 1:
Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.
Example 2:
Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.
Example 3:
Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.
Constraints:
•
1 <= sentence.length <= 100•
1 <= searchWord.length <= 10•
sentence consists of lowercase English letters and spaces.•
searchWord consists of lowercase English letters.2024-12-03
2109. Adding Spaces to a String
Topic: Array, Two Pointers, String, Simulation
Difficulty: Medium
Problem:
You are given a 0-indexed string
• For example, given
Return the modified string after the spaces have been added.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
• All the values of
2109. Adding Spaces to a String
Topic: Array, Two Pointers, String, Simulation
Difficulty: Medium
Problem:
You are given a 0-indexed string
s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index.• For example, given
s = "EnjoyYourCoffee" and spaces = [5, 9], we place spaces before 'Y' and 'C', which are at indices 5 and 9 respectively. Thus, we obtain "Enjoy Your Coffee".Return the modified string after the spaces have been added.
Example 1:
Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
Output: "Leetcode Helps Me Learn"
Explanation:
The indices 8, 13, and 15 correspond to the underlined characters in "LeetcodeHelpsMeLearn".
We then place spaces before those characters.
Example 2:
Input: s = "icodeinpython", spaces = [1,5,7,9]
Output: "i code in py thon"
Explanation:
The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython".
We then place spaces before those characters.
Example 3:
Input: s = "spacing", spaces = [0,1,2,3,4,5,6]
Output: " s p a c i n g"
Explanation:
We are also able to place spaces before the first character of the string.
Constraints:
•
1 <= s.length <= 3 * 10^5•
s consists only of lowercase and uppercase English letters.•
1 <= spaces.length <= 3 * 10^5•
0 <= spaces[i] <= s.length - 1• All the values of
spaces are strictly increasing.2024-12-04
2825. Make String a Subsequence Using Cyclic Increments
Topic: Two Pointers, String
Difficulty: Medium
Problem:
You are given two 0-indexed strings
In an operation, you select a set of indices in
Return
Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
2825. Make String a Subsequence Using Cyclic Increments
Topic: Two Pointers, String
Difficulty: Medium
Problem:
You are given two 0-indexed strings
str1 and str2.In an operation, you select a set of indices in
str1, and for each index i in the set, increment str1[i] to the next character cyclically. That is 'a' becomes 'b', 'b' becomes 'c', and so on, and 'z' becomes 'a'.Return
true if it is possible to make str2 a subsequence of str1 by performing the operation at most once, and false otherwise.Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.
Example 1:
Input: str1 = "abc", str2 = "ad"
Output: true
Explanation: Select index 2 in str1.
Increment str1[2] to become 'd'.
Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.
Example 2:
Input: str1 = "zc", str2 = "ad"
Output: true
Explanation: Select indices 0 and 1 in str1.
Increment str1[0] to become 'a'.
Increment str1[1] to become 'd'.
Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.
Example 3:
Input: str1 = "ab", str2 = "d"
Output: false
Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once.
Therefore, false is returned.
Constraints:
•
1 <= str1.length <= 10^5•
1 <= str2.length <= 10^5•
str1 and str2 consist of only lowercase English letters.