2025-11-18
717. 1-bit and 2-bit Characters
Topic: Array
Difficulty: Easy
Problem:
We have two special characters:
• The first character can be represented by one bit
• The second character can be represented by two bits (
Given a binary array
Example 1:
Example 2:
Constraints:
•
•
717. 1-bit and 2-bit Characters
Topic: Array
Difficulty: Easy
Problem:
We have two special characters:
• The first character can be represented by one bit
0.• The second character can be represented by two bits (
10 or 11).Given a binary array
bits that ends with 0, return true if the last character must be a one-bit character.Example 1:
Input: bits = [1,0,0]
Output: true
Explanation: The only way to decode it is two-bit character and one-bit character.
So the last character is one-bit character.
Example 2:
Input: bits = [1,1,1,0]
Output: false
Explanation: The only way to decode it is two-bit character and two-bit character.
So the last character is not one-bit character.
Constraints:
•
1 <= bits.length <= 1000•
bits[i] is either 0 or 1.2025-11-19
2154. Keep Multiplying Found Values by Two
Topic: Array, Hash Table, Sorting, Simulation
Difficulty: Easy
Problem:
You are given an array of integers
You then do the following steps:
1. If
2. Otherwise, stop the process.
3. Repeat this process with the new number as long as you keep finding the number.
Return the final value of
Example 1:
Example 2:
Constraints:
•
•
2154. Keep Multiplying Found Values by Two
Topic: Array, Hash Table, Sorting, Simulation
Difficulty: Easy
Problem:
You are given an array of integers
nums. You are also given an integer original which is the first number that needs to be searched for in nums.You then do the following steps:
1. If
original is found in nums, multiply it by two (i.e., set original = 2 * original).2. Otherwise, stop the process.
3. Repeat this process with the new number as long as you keep finding the number.
Return the final value of
original.Example 1:
Input: nums = [5,3,6,1,12], original = 3
Output: 24
Explanation:
- 3 is found in nums. 3 is multiplied by 2 to obtain 6.
- 6 is found in nums. 6 is multiplied by 2 to obtain 12.
- 12 is found in nums. 12 is multiplied by 2 to obtain 24.
- 24 is not found in nums. Thus, 24 is returned.
Example 2:
Input: nums = [2,7,9], original = 4
Output: 4
Explanation:
- 4 is not found in nums. Thus, 4 is returned.
Constraints:
•
1 <= nums.length <= 1000•
1 <= nums[i], original <= 10002025-11-20
757. Set Intersection Size At Least Two
Topic: Array, Greedy, Sorting
Difficulty: Hard
Problem:
You are given a 2D integer array
A containing set is an array
• For example, if
Return the minimum possible size of a containing set.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
757. Set Intersection Size At Least Two
Topic: Array, Greedy, Sorting
Difficulty: Hard
Problem:
You are given a 2D integer array
intervals where intervals[i] = [start_i, end_i] represents all the integers from start_i to end_i inclusively.A containing set is an array
nums where each interval from intervals has at least two integers in nums.• For example, if
intervals = [[1,3], [3,7], [8,9]], then [1,2,4,7,8,9] and [2,3,4,8,9] are containing sets.Return the minimum possible size of a containing set.
Example 1:
Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5
Explanation: let nums = [2, 3, 4, 8, 9].
It can be shown that there cannot be any containing array of size 4.
Example 2:
Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: let nums = [2, 3, 4].
It can be shown that there cannot be any containing array of size 2.
Example 3:
Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Explanation: let nums = [1, 2, 3, 4, 5].
It can be shown that there cannot be any containing array of size 4.
Constraints:
•
1 <= intervals.length <= 3000•
intervals[i].length == 2•
0 <= start_i < end_i <= 10^82025-11-21
1930. Unique Length-3 Palindromic Subsequences
Topic: Hash Table, String, Bit Manipulation, Prefix Sum
Difficulty: Medium
Problem:
Given a string
Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.
A palindrome is a string that reads the same forwards and backwards.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
• For example,
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1930. Unique Length-3 Palindromic Subsequences
Topic: Hash Table, String, Bit Manipulation, Prefix Sum
Difficulty: Medium
Problem:
Given a string
s, return the number of unique palindromes of length three that are a subsequence of s.Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.
A palindrome is a string that reads the same forwards and backwards.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
• For example,
"ace" is a subsequence of "abcde".Example 1:
Input: s = "aabca"
Output: 3
Explanation: The 3 palindromic subsequences of length 3 are:
- "aba" (subsequence of "aabca")
- "aaa" (subsequence of "aabca")
- "aca" (subsequence of "aabca")
Example 2:
Input: s = "adc"
Output: 0
Explanation: There are no palindromic subsequences of length 3 in "adc".
Example 3:
Input: s = "bbcbaba"
Output: 4
Explanation: The 4 palindromic subsequences of length 3 are:
- "bbb" (subsequence of "bbcbaba")
- "bcb" (subsequence of "bbcbaba")
- "bab" (subsequence of "bbcbaba")
- "aba" (subsequence of "bbcbaba")
Constraints:
•
3 <= s.length <= 10^5•
s consists of only lowercase English letters.2025-11-22
3190. Find Minimum Operations to Make All Elements Divisible by Three
Topic: Array, Math
Difficulty: Easy
Problem:
You are given an integer array
Return the minimum number of operations to make all elements of
Example 1:
Input: nums = 1,2,3,4
Output: 3
Explanation:
All array elements can be made divisible by 3 using 3 operations:
• Subtract 1 from 1.
• Add 1 to 2.
• Subtract 1 from 4.
Example 2:
Input: nums = 3,6,9
Output: 0
Constraints:
•
•
3190. Find Minimum Operations to Make All Elements Divisible by Three
Topic: Array, Math
Difficulty: Easy
Problem:
You are given an integer array
nums. In one operation, you can add or subtract 1 from any element of nums.Return the minimum number of operations to make all elements of
nums divisible by 3.Example 1:
Input: nums = 1,2,3,4
Output: 3
Explanation:
All array elements can be made divisible by 3 using 3 operations:
• Subtract 1 from 1.
• Add 1 to 2.
• Subtract 1 from 4.
Example 2:
Input: nums = 3,6,9
Output: 0
Constraints:
•
1 <= nums.length <= 50•
1 <= nums[i] <= 502025-11-23
1262. Greatest Sum Divisible by Three
Topic: Array, Dynamic Programming, Greedy, Sorting
Difficulty: Medium
Problem:
Given an integer array
Example 1:
Example 2:
Example 3:
Constraints:
•
•
1262. Greatest Sum Divisible by Three
Topic: Array, Dynamic Programming, Greedy, Sorting
Difficulty: Medium
Problem:
Given an integer array
nums, return the maximum possible sum of elements of the array such that it is divisible by three.Example 1:
Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).
Example 2:
Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.
Example 3:
Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).
Constraints:
•
1 <= nums.length <= 4 * 10^4•
1 <= nums[i] <= 10^42025-11-24
1018. Binary Prefix Divisible By 5
Topic: Array, Bit Manipulation
Difficulty: Easy
Problem:
You are given a binary array
We define
• For example, if
Return an array of booleans
Example 1:
Example 2:
Constraints:
•
•
1018. Binary Prefix Divisible By 5
Topic: Array, Bit Manipulation
Difficulty: Easy
Problem:
You are given a binary array
nums (0-indexed).We define
x_i as the number whose binary representation is the subarray nums[0..i] (from most-significant-bit to least-significant-bit).• For example, if
nums = [1,0,1], then x_0 = 1, x_1 = 2, and x_2 = 5.Return an array of booleans
answer where answer[i] is true if x_i is divisible by 5.Example 1:
Input: nums = [0,1,1]
Output: [true,false,false]
Explanation: The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10.
Only the first number is divisible by 5, so answer[0] is true.
Example 2:
Input: nums = [1,1,1]
Output: [false,false,false]
Constraints:
•
1 <= nums.length <= 10^5•
nums[i] is either 0 or 1.2025-11-25
1015. Smallest Integer Divisible by K
Topic: Hash Table, Math
Difficulty: Medium
Problem:
Given a positive integer
Return the length of
Note:
Example 1:
Example 2:
Example 3:
Constraints:
•
1015. Smallest Integer Divisible by K
Topic: Hash Table, Math
Difficulty: Medium
Problem:
Given a positive integer
k, you need to find the length of the smallest positive integer n such that n is divisible by k, and n only contains the digit 1.Return the length of
n. If there is no such n, return -1.Note:
n may not fit in a 64-bit signed integer.Example 1:
Input: k = 1
Output: 1
Explanation: The smallest answer is n = 1, which has length 1.
Example 2:
Input: k = 2
Output: -1
Explanation: There is no such positive integer n divisible by 2.
Example 3:
Input: k = 3
Output: 3
Explanation: The smallest answer is n = 111, which has length 3.
Constraints:
•
1 <= k <= 10^52025-11-26
2435. Paths in Matrix Whose Sum Is Divisible by K
Topic: Array, Dynamic Programming, Matrix
Difficulty: Hard
Problem:
You are given a 0-indexed
Return the number of paths where the sum of the elements on the path is divisible by
Example 1:
Image: https://assets.leetcode.com/uploads/2022/08/13/image-20220813183124-1.png
Example 2:
Image: https://assets.leetcode.com/uploads/2022/08/17/image-20220817112930-3.png
Example 3:
Image: https://assets.leetcode.com/uploads/2022/08/12/image-20220812224605-3.png
Constraints:
•
•
•
•
•
•
2435. Paths in Matrix Whose Sum Is Divisible by K
Topic: Array, Dynamic Programming, Matrix
Difficulty: Hard
Problem:
You are given a 0-indexed
m x n integer matrix grid and an integer k. You are currently at position (0, 0) and you want to reach position (m - 1, n - 1) moving only down or right.Return the number of paths where the sum of the elements on the path is divisible by
k. Since the answer may be very large, return it modulo 10^9 + 7.Example 1:
Image: https://assets.leetcode.com/uploads/2022/08/13/image-20220813183124-1.png
Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
Output: 2
Explanation: There are two paths where the sum of the elements on the path is divisible by k.
The first path highlighted in red has a sum of 5 + 2 + 4 + 5 + 2 = 18 which is divisible by 3.
The second path highlighted in blue has a sum of 5 + 3 + 0 + 5 + 2 = 15 which is divisible by 3.
Example 2:
Image: https://assets.leetcode.com/uploads/2022/08/17/image-20220817112930-3.png
Input: grid = [[0,0]], k = 5
Output: 1
Explanation: The path highlighted in red has a sum of 0 + 0 = 0 which is divisible by 5.
Example 3:
Image: https://assets.leetcode.com/uploads/2022/08/12/image-20220812224605-3.png
Input: grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
Output: 10
Explanation: Every integer is divisible by 1 so the sum of the elements on every possible path is divisible by k.
Constraints:
•
m == grid.length•
n == grid[i].length•
1 <= m, n <= 5 * 10^4•
1 <= m * n <= 5 * 10^4•
0 <= grid[i][j] <= 100•
1 <= k <= 502025-11-27
3381. Maximum Subarray Sum With Length Divisible by K
Topic: Array, Hash Table, Prefix Sum
Difficulty: Medium
Problem:
You are given an array of integers
Return the maximum sum of a subarray of
Example 1:
Input: nums = 1,2, k = 1
Output: 3
Explanation:
The subarray
Example 2:
Input: nums = -1,-2,-3,-4,-5, k = 4
Output: -10
Explanation:
The maximum sum subarray is
Example 3:
Input: nums = -5,1,2,-3,4, k = 2
Output: 4
Explanation:
The maximum sum subarray is
Constraints:
•
•
3381. Maximum Subarray Sum With Length Divisible by K
Topic: Array, Hash Table, Prefix Sum
Difficulty: Medium
Problem:
You are given an array of integers
nums and an integer k.Return the maximum sum of a subarray of
nums, such that the size of the subarray is divisible by k.Example 1:
Input: nums = 1,2, k = 1
Output: 3
Explanation:
The subarray
[1, 2] with sum 3 has length equal to 2 which is divisible by 1.Example 2:
Input: nums = -1,-2,-3,-4,-5, k = 4
Output: -10
Explanation:
The maximum sum subarray is
[-1, -2, -3, -4] which has length equal to 4 which is divisible by 4.Example 3:
Input: nums = -5,1,2,-3,4, k = 2
Output: 4
Explanation:
The maximum sum subarray is
[1, 2, -3, 4] which has length equal to 4 which is divisible by 2.Constraints:
•
1 <= k <= nums.length <= 2 * 10^5•
-10^9 <= nums[i] <= 10^92025-11-28
2872. Maximum Number of K-Divisible Components
Topic: Tree, Depth-First Search
Difficulty: Hard
Problem:
There is an undirected tree with
You are also given a 0-indexed integer array
A valid split of the tree is obtained by removing any set of edges, possibly empty, from the tree such that the resulting components all have values that are divisible by
Return the maximum number of components in any valid split.
Example 1:
Image: https://assets.leetcode.com/uploads/2023/08/07/example12-cropped2svg.jpg
Example 2:
Image: https://assets.leetcode.com/uploads/2023/08/07/example21svg-1.jpg
Constraints:
•
•
•
•
•
•
•
• Sum of
• The input is generated such that
2872. Maximum Number of K-Divisible Components
Topic: Tree, Depth-First Search
Difficulty: Hard
Problem:
There is an undirected tree with
n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the tree.You are also given a 0-indexed integer array
values of length n, where values[i] is the value associated with the i^th node, and an integer k.A valid split of the tree is obtained by removing any set of edges, possibly empty, from the tree such that the resulting components all have values that are divisible by
k, where the value of a connected component is the sum of the values of its nodes.Return the maximum number of components in any valid split.
Example 1:
Image: https://assets.leetcode.com/uploads/2023/08/07/example12-cropped2svg.jpg
Input: n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6
Output: 2
Explanation: We remove the edge connecting node 1 with 2. The resulting split is valid because:
- The value of the component containing nodes 1 and 3 is values[1] + values[3] = 12.
- The value of the component containing nodes 0, 2, and 4 is values[0] + values[2] + values[4] = 6.
It can be shown that no other valid split has more than 2 connected components.
Example 2:
Image: https://assets.leetcode.com/uploads/2023/08/07/example21svg-1.jpg
Input: n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [3,0,6,1,5,2,1], k = 3
Output: 3
Explanation: We remove the edge connecting node 0 with 2, and the edge connecting node 0 with 1. The resulting split is valid because:
- The value of the component containing node 0 is values[0] = 3.
- The value of the component containing nodes 2, 5, and 6 is values[2] + values[5] + values[6] = 9.
- The value of the component containing nodes 1, 3, and 4 is values[1] + values[3] + values[4] = 6.
It can be shown that no other valid split has more than 3 connected components.
Constraints:
•
1 <= n <= 3 * 10^4•
edges.length == n - 1•
edges[i].length == 2•
0 <= a_i, b_i < n•
values.length == n•
0 <= values[i] <= 10^9•
1 <= k <= 10^9• Sum of
values is divisible by k.• The input is generated such that
edges represents a valid tree.2025-11-29
3512. Minimum Operations to Make Array Sum Divisible by K
Topic: Array, Math
Difficulty: Easy
Problem:
You are given an integer array
• Select an index
Return the minimum number of operations required to make the sum of the array divisible by
Example 1:
Input: nums = 3,9,7, k = 5
Output: 4
Explanation:
• Perform 4 operations on
• The sum is 15, which is divisible by 5.
Example 2:
Input: nums = 4,1,3, k = 4
Output: 0
Explanation:
• The sum is 8, which is already divisible by 4. Hence, no operations are needed.
Example 3:
Input: nums = 3,2, k = 6
Output: 5
Explanation:
• Perform 3 operations on
• The sum is 0, which is divisible by 6.
Constraints:
•
•
•
3512. Minimum Operations to Make Array Sum Divisible by K
Topic: Array, Math
Difficulty: Easy
Problem:
You are given an integer array
nums and an integer k. You can perform the following operation any number of times:• Select an index
i and replace nums[i] with nums[i] - 1.Return the minimum number of operations required to make the sum of the array divisible by
k.Example 1:
Input: nums = 3,9,7, k = 5
Output: 4
Explanation:
• Perform 4 operations on
nums[1] = 9. Now, nums = [3, 5, 7].• The sum is 15, which is divisible by 5.
Example 2:
Input: nums = 4,1,3, k = 4
Output: 0
Explanation:
• The sum is 8, which is already divisible by 4. Hence, no operations are needed.
Example 3:
Input: nums = 3,2, k = 6
Output: 5
Explanation:
• Perform 3 operations on
nums[0] = 3 and 2 operations on nums[1] = 2. Now, nums = [0, 0].• The sum is 0, which is divisible by 6.
Constraints:
•
1 <= nums.length <= 1000•
1 <= nums[i] <= 1000•
1 <= k <= 1002025-11-30
1590. Make Sum Divisible by P
Topic: Array, Hash Table, Prefix Sum
Difficulty: Medium
Problem:
Given an array of positive integers
Return the length of the smallest subarray that you need to remove, or
A subarray is defined as a contiguous block of elements in the array.
Example 1:
Example 2:
Example 3:
Constraints:
•
•
•
1590. Make Sum Divisible by P
Topic: Array, Hash Table, Prefix Sum
Difficulty: Medium
Problem:
Given an array of positive integers
nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.Return the length of the smallest subarray that you need to remove, or
-1 if it's impossible.A subarray is defined as a contiguous block of elements in the array.
Example 1:
Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.
Example 2:
Input: nums = [6,3,5,2], p = 9
Output: 2
Explanation: We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.
Example 3:
Input: nums = [1,2,3], p = 3
Output: 0
Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.
Constraints:
•
1 <= nums.length <= 10^5•
1 <= nums[i] <= 10^9•
1 <= p <= 10^92025-12-01
2141. Maximum Running Time of N Computers
Topic: Array, Binary Search, Greedy, Sorting
Difficulty: Hard
Problem:
You have
Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.
Note that the batteries cannot be recharged.
Return the maximum number of minutes you can run all the
Example 1:
Image: https://assets.leetcode.com/uploads/2022/01/06/example1-fit.png
Example 2:
Image: https://assets.leetcode.com/uploads/2022/01/06/example2.png
Constraints:
•
•
2141. Maximum Running Time of N Computers
Topic: Array, Binary Search, Greedy, Sorting
Difficulty: Hard
Problem:
You have
n computers. You are given the integer n and a 0-indexed integer array batteries where the i^th battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries.Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.
Note that the batteries cannot be recharged.
Return the maximum number of minutes you can run all the
n computers simultaneously.Example 1:
Image: https://assets.leetcode.com/uploads/2022/01/06/example1-fit.png
Input: n = 2, batteries = [3,3,3]
Output: 4
Explanation:
Initially, insert battery 0 into the first computer and battery 1 into the second computer.
After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute.
At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead.
By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running.
We can run the two computers simultaneously for at most 4 minutes, so we return 4.
Example 2:
Image: https://assets.leetcode.com/uploads/2022/01/06/example2.png
Input: n = 2, batteries = [1,1,1,1]
Output: 2
Explanation:
Initially, insert battery 0 into the first computer and battery 2 into the second computer.
After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer.
After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running.
We can run the two computers simultaneously for at most 2 minutes, so we return 2.
Constraints:
•
1 <= n <= batteries.length <= 10^5•
1 <= batteries[i] <= 10^92025-12-02
3623. Count Number of Trapezoids I
Topic: Array, Hash Table, Math, Geometry
Difficulty: Medium
Problem:
You are given a 2D integer array
A horizontal trapezoid is a convex quadrilateral with at least one pair of horizontal sides (i.e. parallel to the x-axis). Two lines are parallel if and only if they have the same slope.
Return the number of unique horizontal trapezoids that can be formed by choosing any four distinct points from
Since the answer may be very large, return it modulo
Example 1:
Input: points = [1,0,2,0,3,0,2,2,3,2]
Output: 3
Explanation:
Image: https://assets.leetcode.com/uploads/2025/05/01/desmos-graph-6.png
Image: https://assets.leetcode.com/uploads/2025/05/01/desmos-graph-7.png
Image: https://assets.leetcode.com/uploads/2025/05/01/desmos-graph-8.png
There are three distinct ways to pick four points that form a horizontal trapezoid:
• Using points
• Using points
• Using points
Example 2:
Input: points = [0,0,1,0,0,1,2,1]
Output: 1
Explanation:
Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-5.png
There is only one horizontal trapezoid that can be formed.
Constraints:
•
•
• All points are pairwise distinct.
3623. Count Number of Trapezoids I
Topic: Array, Hash Table, Math, Geometry
Difficulty: Medium
Problem:
You are given a 2D integer array
points, where points[i] = [x_i, y_i] represents the coordinates of the i^th point on the Cartesian plane.A horizontal trapezoid is a convex quadrilateral with at least one pair of horizontal sides (i.e. parallel to the x-axis). Two lines are parallel if and only if they have the same slope.
Return the number of unique horizontal trapezoids that can be formed by choosing any four distinct points from
points.Since the answer may be very large, return it modulo
10^9 + 7.Example 1:
Input: points = [1,0,2,0,3,0,2,2,3,2]
Output: 3
Explanation:
Image: https://assets.leetcode.com/uploads/2025/05/01/desmos-graph-6.png
Image: https://assets.leetcode.com/uploads/2025/05/01/desmos-graph-7.png
Image: https://assets.leetcode.com/uploads/2025/05/01/desmos-graph-8.png
There are three distinct ways to pick four points that form a horizontal trapezoid:
• Using points
[1,0], [2,0], [3,2], and [2,2].• Using points
[2,0], [3,0], [3,2], and [2,2].• Using points
[1,0], [3,0], [3,2], and [2,2].Example 2:
Input: points = [0,0,1,0,0,1,2,1]
Output: 1
Explanation:
Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-5.png
There is only one horizontal trapezoid that can be formed.
Constraints:
•
4 <= points.length <= 10^5•
–10^8 <= x_i, y_i <= 10^8• All points are pairwise distinct.
2025-12-03
3625. Count Number of Trapezoids II
Topic: Array, Hash Table, Math, Geometry
Difficulty: Hard
Problem:
You are given a 2D integer array
Return the number of unique trapezoids that can be formed by choosing any four distinct points from
A trapezoid is a convex quadrilateral with at least one pair of parallel sides. Two lines are parallel if and only if they have the same slope.
Example 1:
Input: points = [-3,2,3,0,2,3,3,2,2,-3]
Output: 2
Explanation:
Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-4.png
Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-3.png
There are two distinct ways to pick four points that form a trapezoid:
• The points
• The points
Example 2:
Input: points = [0,0,1,0,0,1,2,1]
Output: 1
Explanation:
Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-5.png
There is only one trapezoid which can be formed.
Constraints:
•
•
• All points are pairwise distinct.
3625. Count Number of Trapezoids II
Topic: Array, Hash Table, Math, Geometry
Difficulty: Hard
Problem:
You are given a 2D integer array
points where points[i] = [x_i, y_i] represents the coordinates of the i^th point on the Cartesian plane.Return the number of unique trapezoids that can be formed by choosing any four distinct points from
points.A trapezoid is a convex quadrilateral with at least one pair of parallel sides. Two lines are parallel if and only if they have the same slope.
Example 1:
Input: points = [-3,2,3,0,2,3,3,2,2,-3]
Output: 2
Explanation:
Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-4.png
Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-3.png
There are two distinct ways to pick four points that form a trapezoid:
• The points
[-3,2], [2,3], [3,2], [2,-3] form one trapezoid.• The points
[2,3], [3,2], [3,0], [2,-3] form another trapezoid.Example 2:
Input: points = [0,0,1,0,0,1,2,1]
Output: 1
Explanation:
Image: https://assets.leetcode.com/uploads/2025/04/29/desmos-graph-5.png
There is only one trapezoid which can be formed.
Constraints:
•
4 <= points.length <= 500•
–1000 <= x_i, y_i <= 1000• All points are pairwise distinct.
2025-12-04
2211. Count Collisions on a Road
Topic: String, Stack, Simulation
Difficulty: Medium
Problem:
There are
You are given a 0-indexed string
The number of collisions can be calculated as follows:
• When two cars moving in opposite directions collide with each other, the number of collisions increases by
• When a moving car collides with a stationary car, the number of collisions increases by
After a collision, the cars involved can no longer move and will stay at the point where they collided. Other than that, cars cannot change their state or direction of motion.
Return the total number of collisions that will happen on the road.
Example 1:
Example 2:
Constraints:
•
•
2211. Count Collisions on a Road
Topic: String, Stack, Simulation
Difficulty: Medium
Problem:
There are
n cars on an infinitely long road. The cars are numbered from 0 to n - 1 from left to right and each car is present at a unique point.You are given a 0-indexed string
directions of length n. directions[i] can be either 'L', 'R', or 'S' denoting whether the i^th car is moving towards the left, towards the right, or staying at its current point respectively. Each moving car has the same speed.The number of collisions can be calculated as follows:
• When two cars moving in opposite directions collide with each other, the number of collisions increases by
2.• When a moving car collides with a stationary car, the number of collisions increases by
1.After a collision, the cars involved can no longer move and will stay at the point where they collided. Other than that, cars cannot change their state or direction of motion.
Return the total number of collisions that will happen on the road.
Example 1:
Input: directions = "RLRSLL"
Output: 5
Explanation:
The collisions that will happen on the road are:
- Cars 0 and 1 will collide with each other. Since they are moving in opposite directions, the number of collisions becomes 0 + 2 = 2.
- Cars 2 and 3 will collide with each other. Since car 3 is stationary, the number of collisions becomes 2 + 1 = 3.
- Cars 3 and 4 will collide with each other. Since car 3 is stationary, the number of collisions becomes 3 + 1 = 4.
- Cars 4 and 5 will collide with each other. After car 4 collides with car 3, it will stay at the point of collision and get hit by car 5. The number of collisions becomes 4 + 1 = 5.
Thus, the total number of collisions that will happen on the road is 5.
Example 2:
Input: directions = "LLRR"
Output: 0
Explanation:
No cars will collide with each other. Thus, the total number of collisions that will happen on the road is 0.
Constraints:
•
1 <= directions.length <= 10^5•
directions[i] is either 'L', 'R', or 'S'.2025-12-05
3432. Count Partitions with Even Sum Difference
Topic: Array, Math, Prefix Sum
Difficulty: Easy
Problem:
You are given an integer array
A partition is defined as an index
• Left subarray contains indices
• Right subarray contains indices
Return the number of partitions where the difference between the sum of the left and right subarrays is even.
Example 1:
Input: nums = 10,10,3,7,6
Output: 4
Explanation:
The 4 partitions are:
•
•
•
•
Example 2:
Input: nums = 1,2,2
Output: 0
Explanation:
No partition results in an even sum difference.
Example 3:
Input: nums = 2,4,6,8
Output: 3
Explanation:
All partitions result in an even sum difference.
Constraints:
•
•
3432. Count Partitions with Even Sum Difference
Topic: Array, Math, Prefix Sum
Difficulty: Easy
Problem:
You are given an integer array
nums of length n.A partition is defined as an index
i where 0 <= i < n - 1, splitting the array into two non-empty subarrays such that:• Left subarray contains indices
[0, i].• Right subarray contains indices
[i + 1, n - 1].Return the number of partitions where the difference between the sum of the left and right subarrays is even.
Example 1:
Input: nums = 10,10,3,7,6
Output: 4
Explanation:
The 4 partitions are:
•
[10], [10, 3, 7, 6] with a sum difference of 10 - 26 = -16, which is even.•
[10, 10], [3, 7, 6] with a sum difference of 20 - 16 = 4, which is even.•
[10, 10, 3], [7, 6] with a sum difference of 23 - 13 = 10, which is even.•
[10, 10, 3, 7], [6] with a sum difference of 30 - 6 = 24, which is even.Example 2:
Input: nums = 1,2,2
Output: 0
Explanation:
No partition results in an even sum difference.
Example 3:
Input: nums = 2,4,6,8
Output: 3
Explanation:
All partitions result in an even sum difference.
Constraints:
•
2 <= n == nums.length <= 100•
1 <= nums[i] <= 1002025-12-06
3578. Count Partitions With Max-Min Difference at Most K
Topic: Array, Dynamic Programming, Queue, Sliding Window, Prefix Sum, Monotonic Queue
Difficulty: Medium
Problem:
You are given an integer array
Return the total number of ways to partition
Since the answer may be too large, return it modulo
Example 1:
Input: nums = 9,4,1,3,7, k = 4
Output: 6
Explanation:
There are 6 valid partitions where the difference between the maximum and minimum elements in each segment is at most
•
•
•
•
•
•
Example 2:
Input: nums = 3,3,4, k = 0
Output: 2
Explanation:
There are 2 valid partitions that satisfy the given conditions:
•
•
Constraints:
•
•
•
3578. Count Partitions With Max-Min Difference at Most K
Topic: Array, Dynamic Programming, Queue, Sliding Window, Prefix Sum, Monotonic Queue
Difficulty: Medium
Problem:
You are given an integer array
nums and an integer k. Your task is to partition nums into one or more non-empty contiguous segments such that in each segment, the difference between its maximum and minimum elements is at most k.Return the total number of ways to partition
nums under this condition.Since the answer may be too large, return it modulo
10^9 + 7.Example 1:
Input: nums = 9,4,1,3,7, k = 4
Output: 6
Explanation:
There are 6 valid partitions where the difference between the maximum and minimum elements in each segment is at most
k = 4:•
[[9], [4], [1], [3], [7]]•
[[9], [4], [1], [3, 7]]•
[[9], [4], [1, 3], [7]]•
[[9], [4, 1], [3], [7]]•
[[9], [4, 1], [3, 7]]•
[[9], [4, 1, 3], [7]]Example 2:
Input: nums = 3,3,4, k = 0
Output: 2
Explanation:
There are 2 valid partitions that satisfy the given conditions:
•
[[3], [3], [4]]•
[[3, 3], [4]]Constraints:
•
2 <= nums.length <= 5 * 10^4•
1 <= nums[i] <= 10^9•
0 <= k <= 10^92025-12-07
1523. Count Odd Numbers in an Interval Range
Topic: Math
Difficulty: Easy
Problem:
Given two non-negative integers
Example 1:
Example 2:
Constraints:
•
1523. Count Odd Numbers in an Interval Range
Topic: Math
Difficulty: Easy
Problem:
Given two non-negative integers
low and high. Return the count of odd numbers between low and high (inclusive).Example 1:
Input: low = 3, high = 7
Output: 3
Explanation: The odd numbers between 3 and 7 are [3,5,7].
Example 2:
Input: low = 8, high = 10
Output: 1
Explanation: The odd numbers between 8 and 10 are [9].
Constraints:
•
0 <= low <= high <= 10^9