2025-11-09
2169. Count Operations to Obtain Zero

Topic: Math, Simulation
Difficulty: Easy

Problem:
You are given two non-negative integers num1 and num2.

In one operation, if num1 >= num2, you must subtract num2 from num1, otherwise subtract num1 from num2.

• For example, if num1 = 5 and num2 = 4, subtract num2 from num1, thus obtaining num1 = 1 and num2 = 4. However, if num1 = 4 and num2 = 5, after one operation, num1 = 4 and num2 = 1.

Return the number of operations required to make either num1 = 0 or num2 = 0.

Example 1:

Input: num1 = 2, num2 = 3
Output: 3
Explanation: 
- Operation 1: num1 = 2, num2 = 3. Since num1 < num2, we subtract num1 from num2 and get num1 = 2, num2 = 3 - 2 = 1.
- Operation 2: num1 = 2, num2 = 1. Since num1 > num2, we subtract num2 from num1.
- Operation 3: num1 = 1, num2 = 1. Since num1 == num2, we subtract num2 from num1.
Now num1 = 0 and num2 = 1. Since num1 == 0, we do not need to perform any further operations.
So the total number of operations required is 3.

Example 2:

Input: num1 = 10, num2 = 10
Output: 1
Explanation: 
- Operation 1: num1 = 10, num2 = 10. Since num1 == num2, we subtract num2 from num1 and get num1 = 10 - 10 = 0.
Now num1 = 0 and num2 = 10. Since num1 == 0, we are done.
So the total number of operations required is 1.

Constraints:

• 0 <= num1, num2 <= 10^5

2025-11-10
3542. Minimum Operations to Convert All Elements to Zero

Topic: Array, Hash Table, Stack, Greedy, Monotonic Stack
Difficulty: Medium

Problem:
You are given an array nums of size n, consisting of non-negative integers. Your task is to apply some (possibly zero) operations on the array so that all elements become 0.

In one operation, you can select a subarray [i, j] (where 0 <= i <= j < n) and set all occurrences of the minimum non-negative integer in that subarray to 0.

Return the minimum number of operations required to make all elements in the array 0.

Example 1:

Input: nums = 0,2

Output: 1

Explanation:

• Select the subarray [1,1] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0].
• Thus, the minimum number of operations required is 1.

Example 2:

Input: nums = 3,1,2,1

Output: 3

Explanation:

• Select subarray [1,3] (which is [1,2,1]), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in [3,0,2,0].
• Select subarray [2,2] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [3,0,0,0].
• Select subarray [0,0] (which is [3]), where the minimum non-negative integer is 3. Setting all occurrences of 3 to 0 results in [0,0,0,0].
• Thus, the minimum number of operations required is 3.

Example 3:

Input: nums = 1,2,1,2,1,2

Output: 4

Explanation:

• Select subarray [0,5] (which is [1,2,1,2,1,2]), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in [0,2,0,2,0,2].
• Select subarray [1,1] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,2,0,2].
• Select subarray [3,3] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,0,0,2].
• Select subarray [5,5] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,0,0,0].
• Thus, the minimum number of operations required is 4.

Constraints:

• 1 <= n == nums.length <= 10^5
• 0 <= nums[i] <= 10^5

2025-11-11
474. Ones and Zeroes

Topic: Array, String, Dynamic Programming
Difficulty: Medium

Problem:
You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Example 1:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

Example 2:

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

Constraints:

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] consists only of digits '0' and '1'.
• 1 <= m, n <= 100

2025-11-12
2654. Minimum Number of Operations to Make All Array Elements Equal to 1

Topic: Array, Math, Number Theory
Difficulty: Medium

Problem:
You are given a 0-indexed array nums consisiting of positive integers. You can do the following operation on the array any number of times:

• Select an index i such that 0 <= i < n - 1 and replace either of nums[i] or nums[i+1] with their gcd value.

Return the minimum number of operations to make all elements of nums equal to 1. If it is impossible, return -1.

The gcd of two integers is the greatest common divisor of the two integers.

Example 1:

Input: nums = [2,6,3,4]
Output: 4
Explanation: We can do the following operations:
- Choose index i = 2 and replace nums[2] with gcd(3,4) = 1. Now we have nums = [2,6,1,4].
- Choose index i = 1 and replace nums[1] with gcd(6,1) = 1. Now we have nums = [2,1,1,4].
- Choose index i = 0 and replace nums[0] with gcd(2,1) = 1. Now we have nums = [1,1,1,4].
- Choose index i = 2 and replace nums[3] with gcd(1,4) = 1. Now we have nums = [1,1,1,1].

Example 2:

Input: nums = [2,10,6,14]
Output: -1
Explanation: It can be shown that it is impossible to make all the elements equal to 1.

Constraints:

• 2 <= nums.length <= 50
• 1 <= nums[i] <= 10^6

2025-11-13
3228. Maximum Number of Operations to Move Ones to the End

Topic: String, Greedy, Counting
Difficulty: Medium

Problem:
You are given a binary string s.

You can perform the following operation on the string any number of times:

• Choose any index i from the string where i + 1 < s.length such that s[i] == '1' and s[i + 1] == '0'.
• Move the character s[i] to the right until it reaches the end of the string or another '1'. For example, for s = "010010", if we choose i = 1, the resulting string will be s = "000110".

Return the maximum number of operations that you can perform.

Example 1:

Input: s = "1001101"

Output: 4

Explanation:

We can perform the following operations:

• Choose index i = 0. The resulting string is s = "0011101".
• Choose index i = 4. The resulting string is s = "0011011".
• Choose index i = 3. The resulting string is s = "0010111".
• Choose index i = 2. The resulting string is s = "0001111".

Example 2:

Input: s = "00111"

Output: 0

Constraints:

• 1 <= s.length <= 10^5
• s[i] is either '0' or '1'.

2025-11-14
2536. Increment Submatrices by One

Topic: Array, Matrix, Prefix Sum
Difficulty: Medium

Problem:
You are given a positive integer n, indicating that we initially have an n x n 0-indexed integer matrix mat filled with zeroes.

You are also given a 2D integer array query. For each query[i] = [row1_i, col1_i, row2_i, col2_i], you should do the following operation:

• Add 1 to every element in the submatrix with the top left corner (row1_i, col1_i) and the bottom right corner (row2_i, col2_i). That is, add 1 to mat[x][y] for all row1_i <= x <= row2_i and col1_i <= y <= col2_i.

Return the matrix mat after performing every query.

Example 1:

Image: https://assets.leetcode.com/uploads/2022/11/24/p2example11.png

Input: n = 3, queries = [[1,1,2,2],[0,0,1,1]]
Output: [[1,1,0],[1,2,1],[0,1,1]]
Explanation: The diagram above shows the initial matrix, the matrix after the first query, and the matrix after the second query.
- In the first query, we add 1 to every element in the submatrix with the top left corner (1, 1) and bottom right corner (2, 2).
- In the second query, we add 1 to every element in the submatrix with the top left corner (0, 0) and bottom right corner (1, 1).

Example 2:

Image: https://assets.leetcode.com/uploads/2022/11/24/p2example22.png

Input: n = 2, queries = [[0,0,1,1]]
Output: [[1,1],[1,1]]
Explanation: The diagram above shows the initial matrix and the matrix after the first query.
- In the first query we add 1 to every element in the matrix.

Constraints:

• 1 <= n <= 500
• 1 <= queries.length <= 10^4
• 0 <= row1_i <= row2_i < n
• 0 <= col1_i <= col2_i < n

2025-11-15
3234. Count the Number of Substrings With Dominant Ones

Topic: String, Sliding Window, Enumeration
Difficulty: Medium

Problem:
You are given a binary string s.

Return the number of substrings with dominant ones.

A string has dominant ones if the number of ones in the string is greater than or equal to the square of the number of zeros in the string.

Example 1:

Input: s = "00011"

Output: 5

Explanation:

The substrings with dominant ones are shown in the table below.

ijsi..jNumber of ZerosNumber of Ones33101441012301113411022401112
Example 2:

Input: s = "101101"

Output: 16

Explanation:

The substrings with non-dominant ones are shown in the table below.

Since there are 21 substrings total and 5 of them have non-dominant ones, it follows that there are 16 substrings with dominant ones.

ijsi..jNumber of ZerosNumber of Ones110104401014011022041011023150110123

Constraints:

• 1 <= s.length <= 4 * 10^4
• s consists only of characters '0' and '1'.

2025-11-16
1513. Number of Substrings With Only 1s

Topic: Math, String
Difficulty: Medium

Problem:
Given a binary string s, return the number of substrings with all characters 1's. Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

Constraints:

• 1 <= s.length <= 10^5
• s[i] is either '0' or '1'.

2025-11-17
1437. Check If All 1's Are at Least Length K Places Away

Topic: Array
Difficulty: Easy

Problem:
Given an binary array nums and an integer k, return true if all 1's are at least k places away from each other, otherwise return false.

Example 1:

Image: https://assets.leetcode.com/uploads/2020/04/15/sample_1_1791.png

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

Example 2:

Image: https://assets.leetcode.com/uploads/2020/04/15/sample_2_1791.png

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The second 1 and third 1 are only one apart from each other.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= k <= nums.length
• nums[i] is 0 or 1

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 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 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 <= 1000

2025-11-20
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^8

2025-11-21
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 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] <= 50

2025-11-23
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^4

2025-11-24
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 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^5

2025-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 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 <= 50

2025-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 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^9

2025-11-28
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.