2025-03-04
1780. Check if Number is a Sum of Powers of Three
Topic: Math
Difficulty: Medium
Problem:
Given an integer
An integer
Example 1:
Example 2:
Example 3:
Constraints:
•
1780. Check if Number is a Sum of Powers of Three
Topic: Math
Difficulty: Medium
Problem:
Given an integer
n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.An integer
y is a power of three if there exists an integer x such that y == 3^x.Example 1:
Input: n = 12
Output: true
Explanation: 12 = 3^1 + 3^2
Example 2:
Input: n = 91
Output: true
Explanation: 91 = 3^0 + 3^2 + 3^4
Example 3:
Input: n = 21
Output: false
Constraints:
•
1 <= n <= 10^72025-03-05
2579. Count Total Number of Colored Cells
Topic: Math
Difficulty: Medium
Problem:
There exists an infinitely large two-dimensional grid of uncolored unit cells. You are given a positive integer
• At the first minute, color any arbitrary unit cell blue.
• Every minute thereafter, color blue every uncolored cell that touches a blue cell.
Below is a pictorial representation of the state of the grid after minutes 1, 2, and 3.
Image: https://assets.leetcode.com/uploads/2023/01/10/example-copy-2.png
Return the number of colored cells at the end of
Example 1:
Example 2:
Constraints:
•
2579. Count Total Number of Colored Cells
Topic: Math
Difficulty: Medium
Problem:
There exists an infinitely large two-dimensional grid of uncolored unit cells. You are given a positive integer
n, indicating that you must do the following routine for n minutes:• At the first minute, color any arbitrary unit cell blue.
• Every minute thereafter, color blue every uncolored cell that touches a blue cell.
Below is a pictorial representation of the state of the grid after minutes 1, 2, and 3.
Image: https://assets.leetcode.com/uploads/2023/01/10/example-copy-2.png
Return the number of colored cells at the end of
n minutes.Example 1:
Input: n = 1
Output: 1
Explanation: After 1 minute, there is only 1 blue cell, so we return 1.
Example 2:
Input: n = 2
Output: 5
Explanation: After 2 minutes, there are 4 colored cells on the boundary and 1 in the center, so we return 5.
Constraints:
•
1 <= n <= 10^52025-03-06
2965. Find Missing and Repeated Values
Topic: Array, Hash Table, Math, Matrix
Difficulty: Easy
Problem:
You are given a 0-indexed 2D integer matrix
Return a 0-indexed integer array
Example 1:
Example 2:
Constraints:
•
•
• For all
• For all
• For all
2965. Find Missing and Repeated Values
Topic: Array, Hash Table, Math, Matrix
Difficulty: Easy
Problem:
You are given a 0-indexed 2D integer matrix
grid of size n * n with values in the range [1, n^2]. Each integer appears exactly once except a which appears twice and b which is missing. The task is to find the repeating and missing numbers a and b.Return a 0-indexed integer array
ans of size 2 where ans[0] equals to a and ans[1] equals to b.Example 1:
Input: grid = [[1,3],[2,2]]
Output: [2,4]
Explanation: Number 2 is repeated and number 4 is missing so the answer is [2,4].
Example 2:
Input: grid = [[9,1,7],[8,9,2],[3,4,6]]
Output: [9,5]
Explanation: Number 9 is repeated and number 5 is missing so the answer is [9,5].
Constraints:
•
2 <= n == grid.length == grid[i].length <= 50•
1 <= grid[i][j] <= n * n• For all
x that 1 <= x <= n * n there is exactly one x that is not equal to any of the grid members.• For all
x that 1 <= x <= n * n there is exactly one x that is equal to exactly two of the grid members.• For all
x that 1 <= x <= n * n except two of them there is exatly one pair of i, j that 0 <= i, j <= n - 1 and grid[i][j] == x.2025-03-07
2523. Closest Prime Numbers in Range
Topic: Math, Number Theory
Difficulty: Medium
Problem:
Given two positive integers
•
• Both
•
Return the positive integer array
Example 1:
Example 2:
Constraints:
•
2523. Closest Prime Numbers in Range
Topic: Math, Number Theory
Difficulty: Medium
Problem:
Given two positive integers
left and right, find the two integers num1 and num2 such that:•
left <= num1 < num2 <= right .• Both
num1 and num2 are prime numbers.•
num2 - num1 is the minimum amongst all other pairs satisfying the above conditions.Return the positive integer array
ans = [num1, num2]. If there are multiple pairs satisfying these conditions, return the one with the smallest num1 value. If no such numbers exist, return [-1, -1].Example 1:
Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.
Example 2:
Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.
Constraints:
•
1 <= left <= right <= 10^62025-03-08
2379. Minimum Recolors to Get K Consecutive Black Blocks
Topic: String, Sliding Window
Difficulty: Easy
Problem:
You are given a 0-indexed string
You are also given an integer
In one operation, you can recolor a white block such that it becomes a black block.
Return the minimum number of operations needed such that there is at least one occurrence of
Example 1:
Example 2:
Constraints:
•
•
•
•
2379. Minimum Recolors to Get K Consecutive Black Blocks
Topic: String, Sliding Window
Difficulty: Easy
Problem:
You are given a 0-indexed string
blocks of length n, where blocks[i] is either 'W' or 'B', representing the color of the i^th block. The characters 'W' and 'B' denote the colors white and black, respectively.You are also given an integer
k, which is the desired number of consecutive black blocks.In one operation, you can recolor a white block such that it becomes a black block.
Return the minimum number of operations needed such that there is at least one occurrence of
k consecutive black blocks.Example 1:
Input: blocks = "WBBWWBBWBW", k = 7
Output: 3
Explanation:
One way to achieve 7 consecutive black blocks is to recolor the 0th, 3rd, and 4th blocks
so that blocks = "BBBBBBBWBW".
It can be shown that there is no way to achieve 7 consecutive black blocks in less than 3 operations.
Therefore, we return 3.
Example 2:
Input: blocks = "WBWBBBW", k = 2
Output: 0
Explanation:
No changes need to be made, since 2 consecutive black blocks already exist.
Therefore, we return 0.
Constraints:
•
n == blocks.length•
1 <= n <= 100•
blocks[i] is either 'W' or 'B'.•
1 <= k <= n2025-03-09
3208. Alternating Groups II
Topic: Array, Sliding Window
Difficulty: Medium
Problem:
There is a circle of red and blue tiles. You are given an array of integers
•
•
An alternating group is every
Return the number of alternating groups.
Note that since
Example 1:
Input: colors = 0,1,0,1,0, k = 3
Output: 3
Explanation:
Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-183519.png
Alternating groups:
Image: https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-182448.png
Image: https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-182844.png
Image: https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-183057.png
Example 2:
Input: colors = 0,1,0,0,1,0,1, k = 6
Output: 2
Explanation:
Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-183907.png
Alternating groups:
Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184128.png
Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184240.png
Example 3:
Input: colors = 1,1,0,1, k = 4
Output: 0
Explanation:
Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184516.png
Constraints:
•
•
•
3208. Alternating Groups II
Topic: Array, Sliding Window
Difficulty: Medium
Problem:
There is a circle of red and blue tiles. You are given an array of integers
colors and an integer k. The color of tile i is represented by colors[i]:•
colors[i] == 0 means that tile i is red.•
colors[i] == 1 means that tile i is blue.An alternating group is every
k contiguous tiles in the circle with alternating colors (each tile in the group except the first and last one has a different color from its left and right tiles).Return the number of alternating groups.
Note that since
colors represents a circle, the first and the last tiles are considered to be next to each other.Example 1:
Input: colors = 0,1,0,1,0, k = 3
Output: 3
Explanation:
Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-183519.png
Alternating groups:
Image: https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-182448.png
Image: https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-182844.png
Image: https://assets.leetcode.com/uploads/2024/05/28/screenshot-2024-05-28-183057.png
Example 2:
Input: colors = 0,1,0,0,1,0,1, k = 6
Output: 2
Explanation:
Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-183907.png
Alternating groups:
Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184128.png
Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184240.png
Example 3:
Input: colors = 1,1,0,1, k = 4
Output: 0
Explanation:
Image: https://assets.leetcode.com/uploads/2024/06/19/screenshot-2024-05-28-184516.png
Constraints:
•
3 <= colors.length <= 10^5•
0 <= colors[i] <= 1•
3 <= k <= colors.length2025-03-10
3306. Count of Substrings Containing Every Vowel and K Consonants II
Topic: Hash Table, String, Sliding Window
Difficulty: Medium
Problem:
You are given a string
Return the total number of substrings of
Example 1:
Input: word = "aeioqq", k = 1
Output: 0
Explanation:
There is no substring with every vowel.
Example 2:
Input: word = "aeiou", k = 0
Output: 1
Explanation:
The only substring with every vowel and zero consonants is
Example 3:
Input: word = "ieaouqqieaouqq", k = 1
Output: 3
Explanation:
The substrings with every vowel and one consonant are:
•
•
•
Constraints:
•
•
•
3306. Count of Substrings Containing Every Vowel and K Consonants II
Topic: Hash Table, String, Sliding Window
Difficulty: Medium
Problem:
You are given a string
word and a non-negative integer k.Return the total number of substrings of
word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.Example 1:
Input: word = "aeioqq", k = 1
Output: 0
Explanation:
There is no substring with every vowel.
Example 2:
Input: word = "aeiou", k = 0
Output: 1
Explanation:
The only substring with every vowel and zero consonants is
word[0..4], which is "aeiou".Example 3:
Input: word = "ieaouqqieaouqq", k = 1
Output: 3
Explanation:
The substrings with every vowel and one consonant are:
•
word[0..5], which is "ieaouq".•
word[6..11], which is "qieaou".•
word[7..12], which is "ieaouq".Constraints:
•
5 <= word.length <= 2 * 10^5•
word consists only of lowercase English letters.•
0 <= k <= word.length - 52025-03-11
1358. Number of Substrings Containing All Three Characters
Topic: Hash Table, String, Sliding Window
Difficulty: Medium
Problem:
Given a string
Return the number of substrings containing at least one occurrence of all these characters a, b and c.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1358. Number of Substrings Containing All Three Characters
Topic: Hash Table, String, Sliding Window
Difficulty: Medium
Problem:
Given a string
s consisting only of characters a, b and c.Return the number of substrings containing at least one occurrence of all these characters a, b and c.
Example 1:
Input: s = "abcabc"
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" and "abc" (again).
Example 2:
Input: s = "aaacb"
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are "aaacb", "aacb" and "acb".
Example 3:
Input: s = "abc"
Output: 1
Constraints:
•
3 <= s.length <= 5 x 10^4•
s only consists of a, b or c characters.2025-03-12
2529. Maximum Count of Positive Integer and Negative Integer
Topic: Array, Binary Search, Counting
Difficulty: Easy
Problem:
Given an array
• In other words, if the number of positive integers in
Note that
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
Follow up: Can you solve the problem in
2529. Maximum Count of Positive Integer and Negative Integer
Topic: Array, Binary Search, Counting
Difficulty: Easy
Problem:
Given an array
nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.• In other words, if the number of positive integers in
nums is pos and the number of negative integers is neg, then return the maximum of pos and neg.Note that
0 is neither positive nor negative.Example 1:
Input: nums = [-2,-1,-1,1,2,3]
Output: 3
Explanation: There are 3 positive integers and 3 negative integers. The maximum count among them is 3.
Example 2:
Input: nums = [-3,-2,-1,0,0,1,2]
Output: 3
Explanation: There are 2 positive integers and 3 negative integers. The maximum count among them is 3.
Example 3:
Input: nums = [5,20,66,1314]
Output: 4
Explanation: There are 4 positive integers and 0 negative integers. The maximum count among them is 4.
Constraints:
•
1 <= nums.length <= 2000•
-2000 <= nums[i] <= 2000•
nums is sorted in a non-decreasing order.Follow up: Can you solve the problem in
O(log(n)) time complexity?2025-03-13
3356. Zero Array Transformation II
Topic: Array, Binary Search, Prefix Sum
Difficulty: Medium
Problem:
You are given an integer array
Each
• Decrement the value at each index in the range
• The amount by which each value is decremented can be chosen independently for each index.
A Zero Array is an array with all its elements equal to 0.
Return the minimum possible non-negative value of
Example 1:
Input: nums = 2,0,2, queries = [0,2,1,0,2,1,1,1,3]
Output: 2
Explanation:
• For i = 0 (l = 0, r = 2, val = 1):
• Decrement values at indices
• The array will become
• For i = 1 (l = 0, r = 2, val = 1):
• Decrement values at indices
• The array will become
Example 2:
Input: nums = 4,3,2,1, queries = [1,3,2,0,2,1]
Output: -1
Explanation:
• For i = 0 (l = 1, r = 3, val = 2):
• Decrement values at indices
• The array will become
• For i = 1 (l = 0, r = 2, val = 1):
• Decrement values at indices
• The array will become
Constraints:
•
•
•
•
•
•
3356. Zero Array Transformation II
Topic: Array, Binary Search, Prefix Sum
Difficulty: Medium
Problem:
You are given an integer array
nums of length n and a 2D array queries where queries[i] = [l_i, r_i, val_i].Each
queries[i] represents the following action on nums:• Decrement the value at each index in the range
[l_i, r_i] in nums by at most val_i.• The amount by which each value is decremented can be chosen independently for each index.
A Zero Array is an array with all its elements equal to 0.
Return the minimum possible non-negative value of
k, such that after processing the first k queries in sequence, nums becomes a Zero Array. If no such k exists, return -1.Example 1:
Input: nums = 2,0,2, queries = [0,2,1,0,2,1,1,1,3]
Output: 2
Explanation:
• For i = 0 (l = 0, r = 2, val = 1):
• Decrement values at indices
[0, 1, 2] by [1, 0, 1] respectively.• The array will become
[1, 0, 1].• For i = 1 (l = 0, r = 2, val = 1):
• Decrement values at indices
[0, 1, 2] by [1, 0, 1] respectively.• The array will become
[0, 0, 0], which is a Zero Array. Therefore, the minimum value of k is 2.Example 2:
Input: nums = 4,3,2,1, queries = [1,3,2,0,2,1]
Output: -1
Explanation:
• For i = 0 (l = 1, r = 3, val = 2):
• Decrement values at indices
[1, 2, 3] by [2, 2, 1] respectively.• The array will become
[4, 1, 0, 0].• For i = 1 (l = 0, r = 2, val = 1):
• Decrement values at indices
[0, 1, 2] by [1, 1, 0] respectively.• The array will become
[3, 0, 0, 0], which is not a Zero Array.Constraints:
•
1 <= nums.length <= 10^5•
0 <= nums[i] <= 5 * 10^5•
1 <= queries.length <= 10^5•
queries[i].length == 3•
0 <= l_i <= r_i < nums.length•
1 <= val_i <= 52025-03-14
2226. Maximum Candies Allocated to K Children
Topic: Array, Binary Search
Difficulty: Medium
Problem:
You are given a 0-indexed integer array
You are also given an integer
Return the maximum number of candies each child can get.
Example 1:
Example 2:
Constraints:
•
•
•
2226. Maximum Candies Allocated to K Children
Topic: Array, Binary Search
Difficulty: Medium
Problem:
You are given a 0-indexed integer array
candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.You are also given an integer
k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can be allocated candies from only one pile of candies and some piles of candies may go unused.Return the maximum number of candies each child can get.
Example 1:
Input: candies = [5,8,6], k = 3
Output: 5
Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.
Example 2:
Input: candies = [2,5], k = 11
Output: 0
Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.
Constraints:
•
1 <= candies.length <= 10^5•
1 <= candies[i] <= 10^7•
1 <= k <= 10^122025-03-15
2560. House Robber IV
Topic: Array, Binary Search
Difficulty: Medium
Problem:
There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes.
The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed.
You are given an integer array
You are also given an integer
Return the minimum capability of the robber out of all the possible ways to steal at least
Example 1:
Example 2:
Constraints:
•
•
•
2560. House Robber IV
Topic: Array, Binary Search
Difficulty: Medium
Problem:
There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes.
The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed.
You are given an integer array
nums representing how much money is stashed in each house. More formally, the i^th house from the left has nums[i] dollars.You are also given an integer
k, representing the minimum number of houses the robber will steal from. It is always possible to steal at least k houses.Return the minimum capability of the robber out of all the possible ways to steal at least
k houses.Example 1:
Input: nums = [2,3,5,9], k = 2
Output: 5
Explanation:
There are three ways to rob at least 2 houses:
- Rob the houses at indices 0 and 2. Capability is max(nums[0], nums[2]) = 5.
- Rob the houses at indices 0 and 3. Capability is max(nums[0], nums[3]) = 9.
- Rob the houses at indices 1 and 3. Capability is max(nums[1], nums[3]) = 9.
Therefore, we return min(5, 9, 9) = 5.
Example 2:
Input: nums = [2,7,9,3,1], k = 2
Output: 2
Explanation: There are 7 ways to rob the houses. The way which leads to minimum capability is to rob the house at index 0 and 4. Return max(nums[0], nums[4]) = 2.
Constraints:
•
1 <= nums.length <= 10^5•
1 <= nums[i] <= 10^9•
1 <= k <= (nums.length + 1)/22025-03-17
2206. Divide Array Into Equal Pairs
Topic: Array, Hash Table, Bit Manipulation, Counting
Difficulty: Easy
Problem:
You are given an integer array
You need to divide
• Each element belongs to exactly one pair.
• The elements present in a pair are equal.
Return
Example 1:
Example 2:
Constraints:
•
•
•
2206. Divide Array Into Equal Pairs
Topic: Array, Hash Table, Bit Manipulation, Counting
Difficulty: Easy
Problem:
You are given an integer array
nums consisting of 2 * n integers.You need to divide
nums into n pairs such that:• Each element belongs to exactly one pair.
• The elements present in a pair are equal.
Return
true if nums can be divided into n pairs, otherwise return false.Example 1:
Input: nums = [3,2,3,2,2,2]
Output: true
Explanation:
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.
Example 2:
Input: nums = [1,2,3,4]
Output: false
Explanation:
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.
Constraints:
•
nums.length == 2 * n•
1 <= n <= 500•
1 <= nums[i] <= 5002025-03-18
2401. Longest Nice Subarray
Topic: Array, Bit Manipulation, Sliding Window
Difficulty: Medium
Problem:
You are given an array
We call a subarray of
Return the length of the longest nice subarray.
A subarray is a contiguous part of an array.
Note that subarrays of length
Example 1:
Example 2:
Constraints:
•
•
2401. Longest Nice Subarray
Topic: Array, Bit Manipulation, Sliding Window
Difficulty: Medium
Problem:
You are given an array
nums consisting of positive integers.We call a subarray of
nums nice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to 0.Return the length of the longest nice subarray.
A subarray is a contiguous part of an array.
Note that subarrays of length
1 are always considered nice.Example 1:
Input: nums = [1,3,8,48,10]
Output: 3
Explanation: The longest nice subarray is [3,8,48]. This subarray satisfies the conditions:
- 3 AND 8 = 0.
- 3 AND 48 = 0.
- 8 AND 48 = 0.
It can be proven that no longer nice subarray can be obtained, so we return 3.
Example 2:
Input: nums = [3,1,5,11,13]
Output: 1
Explanation: The length of the longest nice subarray is 1. Any subarray of length 1 can be chosen.
Constraints:
•
1 <= nums.length <= 10^5•
1 <= nums[i] <= 10^92025-03-19
3191. Minimum Operations to Make Binary Array Elements Equal to One I
Topic: Array, Bit Manipulation, Queue, Sliding Window, Prefix Sum
Difficulty: Medium
Problem:
You are given a binary array
You can do the following operation on the array any number of times (possibly zero):
• Choose any 3 consecutive elements from the array and flip all of them.
Flipping an element means changing its value from 0 to 1, and from 1 to 0.
Return the minimum number of operations required to make all elements in
Example 1:
Input: nums = 0,1,1,1,0,0
Output: 3
Explanation:
We can do the following operations:
• Choose the elements at indices 0, 1 and 2. The resulting array is
• Choose the elements at indices 1, 2 and 3. The resulting array is
• Choose the elements at indices 3, 4 and 5. The resulting array is
Example 2:
Input: nums = 0,1,1,1
Output: -1
Explanation:
It is impossible to make all elements equal to 1.
Constraints:
•
•
3191. Minimum Operations to Make Binary Array Elements Equal to One I
Topic: Array, Bit Manipulation, Queue, Sliding Window, Prefix Sum
Difficulty: Medium
Problem:
You are given a binary array
nums.You can do the following operation on the array any number of times (possibly zero):
• Choose any 3 consecutive elements from the array and flip all of them.
Flipping an element means changing its value from 0 to 1, and from 1 to 0.
Return the minimum number of operations required to make all elements in
nums equal to 1. If it is impossible, return -1.Example 1:
Input: nums = 0,1,1,1,0,0
Output: 3
Explanation:
We can do the following operations:
• Choose the elements at indices 0, 1 and 2. The resulting array is
nums = [1,0,0,1,0,0].• Choose the elements at indices 1, 2 and 3. The resulting array is
nums = [1,1,1,0,0,0].• Choose the elements at indices 3, 4 and 5. The resulting array is
nums = [1,1,1,1,1,1].Example 2:
Input: nums = 0,1,1,1
Output: -1
Explanation:
It is impossible to make all elements equal to 1.
Constraints:
•
3 <= nums.length <= 10^5•
0 <= nums[i] <= 12025-03-20
3108. Minimum Cost Walk in Weighted Graph
Topic: Array, Bit Manipulation, Union Find, Graph
Difficulty: Hard
Problem:
There is an undirected weighted graph with
You are given the integer
A walk on a graph is a sequence of vertices and edges. The walk starts and ends with a vertex, and each edge connects the vertex that comes before it and the vertex that comes after it. It's important to note that a walk may visit the same edge or vertex more than once.
The cost of a walk starting at node
You are also given a 2D array
Return the array
Example 1:
Input: n = 5, edges = [0,1,7,1,3,7,1,2,1], query = [0,3,3,4]
Output: 1,-1
Explanation:
Image: https://assets.leetcode.com/uploads/2024/01/31/q4_example1-1.png
To achieve the cost of 1 in the first query, we need to move on the following edges:
In the second query, there is no walk between nodes 3 and 4, so the answer is -1.
Example 2:
Input: n = 3, edges = [0,2,7,0,1,15,1,2,6,1,2,1], query = [1,2]
Output: 0
Explanation:
Image: https://assets.leetcode.com/uploads/2024/01/31/q4_example2e.png
To achieve the cost of 0 in the first query, we need to move on the following edges:
Constraints:
•
•
•
•
•
•
•
•
•
•
3108. Minimum Cost Walk in Weighted Graph
Topic: Array, Bit Manipulation, Union Find, Graph
Difficulty: Hard
Problem:
There is an undirected weighted graph with
n vertices labeled from 0 to n - 1.You are given the integer
n and an array edges, where edges[i] = [u_i, v_i, w_i] indicates that there is an edge between vertices u_i and v_i with a weight of w_i.A walk on a graph is a sequence of vertices and edges. The walk starts and ends with a vertex, and each edge connects the vertex that comes before it and the vertex that comes after it. It's important to note that a walk may visit the same edge or vertex more than once.
The cost of a walk starting at node
u and ending at node v is defined as the bitwise AND of the weights of the edges traversed during the walk. In other words, if the sequence of edge weights encountered during the walk is w_0, w_1, w_2, ..., w_k, then the cost is calculated as w_0 & w_1 & w_2 & ... & w_k, where & denotes the bitwise AND operator.You are also given a 2D array
query, where query[i] = [s_i, t_i]. For each query, you need to find the minimum cost of the walk starting at vertex s_i and ending at vertex t_i. If there exists no such walk, the answer is -1.Return the array
answer, where answer[i] denotes the minimum cost of a walk for query i.Example 1:
Input: n = 5, edges = [0,1,7,1,3,7,1,2,1], query = [0,3,3,4]
Output: 1,-1
Explanation:
Image: https://assets.leetcode.com/uploads/2024/01/31/q4_example1-1.png
To achieve the cost of 1 in the first query, we need to move on the following edges:
0->1 (weight 7), 1->2 (weight 1), 2->1 (weight 1), 1->3 (weight 7).In the second query, there is no walk between nodes 3 and 4, so the answer is -1.
Example 2:
Input: n = 3, edges = [0,2,7,0,1,15,1,2,6,1,2,1], query = [1,2]
Output: 0
Explanation:
Image: https://assets.leetcode.com/uploads/2024/01/31/q4_example2e.png
To achieve the cost of 0 in the first query, we need to move on the following edges:
1->2 (weight 1), 2->1 (weight 6), 1->2 (weight 1).Constraints:
•
2 <= n <= 10^5•
0 <= edges.length <= 10^5•
edges[i].length == 3•
0 <= u_i, v_i <= n - 1•
u_i != v_i•
0 <= w_i <= 10^5•
1 <= query.length <= 10^5•
query[i].length == 2•
0 <= s_i, t_i <= n - 1•
s_i != t_i2025-03-21
2115. Find All Possible Recipes from Given Supplies
Topic: Array, Hash Table, String, Graph, Topological Sort
Difficulty: Medium
Problem:
You have information about
You are also given a string array
Return a list of all the recipes that you can create. You may return the answer in any order.
Note that two recipes may contain each other in their ingredients.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
•
•
• All the values of
• Each
2115. Find All Possible Recipes from Given Supplies
Topic: Array, Hash Table, String, Graph, Topological Sort
Difficulty: Medium
Problem:
You have information about
n different recipes. You are given a string array recipes and a 2D string array ingredients. The i^th recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. A recipe can also be an ingredient for other recipes, i.e., ingredients[i] may contain a string that is in recipes.You are also given a string array
supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.Return a list of all the recipes that you can create. You may return the answer in any order.
Note that two recipes may contain each other in their ingredients.
Example 1:
Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output: ["bread"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
Example 2:
Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
Example 3:
Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich","burger"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".
Constraints:
•
n == recipes.length == ingredients.length•
1 <= n <= 100•
1 <= ingredients[i].length, supplies.length <= 100•
1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10•
recipes[i], ingredients[i][j], and supplies[k] consist only of lowercase English letters.• All the values of
recipes and supplies combined are unique.• Each
ingredients[i] does not contain any duplicate values.2025-03-22
2685. Count the Number of Complete Components
Topic: Depth-First Search, Breadth-First Search, Union Find, Graph
Difficulty: Medium
Problem:
You are given an integer
Return the number of complete connected components of the graph.
A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.
A connected component is said to be complete if there exists an edge between every pair of its vertices.
Example 1:
Image: https://assets.leetcode.com/uploads/2023/04/11/screenshot-from-2023-04-11-23-31-23.png
Example 2:
Image: https://assets.leetcode.com/uploads/2023/04/11/screenshot-from-2023-04-11-23-32-00.png
Constraints:
•
•
•
•
•
• There are no repeated edges.
2685. Count the Number of Complete Components
Topic: Depth-First Search, Breadth-First Search, Union Find, Graph
Difficulty: Medium
Problem:
You are given an integer
n. There is an undirected graph with n vertices, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [a_i, b_i] denotes that there exists an undirected edge connecting vertices a_i and b_i.Return the number of complete connected components of the graph.
A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.
A connected component is said to be complete if there exists an edge between every pair of its vertices.
Example 1:
Image: https://assets.leetcode.com/uploads/2023/04/11/screenshot-from-2023-04-11-23-31-23.png
Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
Output: 3
Explanation: From the picture above, one can see that all of the components of this graph are complete.
Example 2:
Image: https://assets.leetcode.com/uploads/2023/04/11/screenshot-from-2023-04-11-23-32-00.png
Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
Output: 1
Explanation: The component containing vertices 0, 1, and 2 is complete since there is an edge between every pair of two vertices. On the other hand, the component containing vertices 3, 4, and 5 is not complete since there is no edge between vertices 4 and 5. Thus, the number of complete components in this graph is 1.
Constraints:
•
1 <= n <= 50•
0 <= edges.length <= n * (n - 1) / 2•
edges[i].length == 2•
0 <= a_i, b_i <= n - 1•
a_i != b_i• There are no repeated edges.
2025-03-23
1976. Number of Ways to Arrive at Destination
Topic: Dynamic Programming, Graph, Topological Sort, Shortest Path
Difficulty: Medium
Problem:
You are in a city that consists of
You are given an integer
Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo
Example 1:
Image: https://assets.leetcode.com/uploads/2025/02/14/1976_corrected.png
Example 2:
Constraints:
•
•
•
•
•
•
• There is at most one road connecting any two intersections.
• You can reach any intersection from any other intersection.
1976. Number of Ways to Arrive at Destination
Topic: Dynamic Programming, Graph, Topological Sort, Shortest Path
Difficulty: Medium
Problem:
You are in a city that consists of
n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.You are given an integer
n and a 2D integer array roads where roads[i] = [u_i, v_i, time_i] means that there is a road between intersections u_i and v_i that takes time_i minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n - 1 in the shortest amount of time.Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo
10^9 + 7.Example 1:
Image: https://assets.leetcode.com/uploads/2025/02/14/1976_corrected.png
Input: n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output: 4
Explanation: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
Example 2:
Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.
Constraints:
•
1 <= n <= 200•
n - 1 <= roads.length <= n * (n - 1) / 2•
roads[i].length == 3•
0 <= u_i, v_i <= n - 1•
1 <= time_i <= 10^9•
u_i != v_i• There is at most one road connecting any two intersections.
• You can reach any intersection from any other intersection.
2025-03-24
3169. Count Days Without Meetings
Topic: Array, Sorting
Difficulty: Medium
Problem:
You are given a positive integer
Return the count of days when the employee is available for work but no meetings are scheduled.
Note: The meetings may overlap.
Example 1:
Input: days = 10, meetings = [5,7,1,3,9,10]
Output: 2
Explanation:
There is no meeting scheduled on the 4^th and 8^th days.
Example 2:
Input: days = 5, meetings = [2,4,1,3]
Output: 1
Explanation:
There is no meeting scheduled on the 5^th day.
Example 3:
Input: days = 6, meetings = [1,6]
Output: 0
Explanation:
Meetings are scheduled for all working days.
Constraints:
•
•
•
•
3169. Count Days Without Meetings
Topic: Array, Sorting
Difficulty: Medium
Problem:
You are given a positive integer
days representing the total number of days an employee is available for work (starting from day 1). You are also given a 2D array meetings of size n where, meetings[i] = [start_i, end_i] represents the starting and ending days of meeting i (inclusive).Return the count of days when the employee is available for work but no meetings are scheduled.
Note: The meetings may overlap.
Example 1:
Input: days = 10, meetings = [5,7,1,3,9,10]
Output: 2
Explanation:
There is no meeting scheduled on the 4^th and 8^th days.
Example 2:
Input: days = 5, meetings = [2,4,1,3]
Output: 1
Explanation:
There is no meeting scheduled on the 5^th day.
Example 3:
Input: days = 6, meetings = [1,6]
Output: 0
Explanation:
Meetings are scheduled for all working days.
Constraints:
•
1 <= days <= 10^9•
1 <= meetings.length <= 10^5•
meetings[i].length == 2•
1 <= meetings[i][0] <= meetings[i][1] <= days