2025-05-10
2918. Minimum Equal Sum of Two Arrays After Replacing Zeros

Topic: Array, Greedy
Difficulty: Medium

Problem:
You are given two arrays nums1 and nums2 consisting of positive integers.

You have to replace all the 0's in both arrays with strictly positive integers such that the sum of elements of both arrays becomes equal.

Return the minimum equal sum you can obtain, or -1 if it is impossible.

Example 1:

Input: nums1 = [3,2,0,1,0], nums2 = [6,5,0]
Output: 12
Explanation: We can replace 0's in the following way:
- Replace the two 0's in nums1 with the values 2 and 4. The resulting array is nums1 = [3,2,2,1,4].
- Replace the 0 in nums2 with the value 1. The resulting array is nums2 = [6,5,1].
Both arrays have an equal sum of 12. It can be shown that it is the minimum sum we can obtain.

Example 2:

Input: nums1 = [2,0,2,0], nums2 = [1,4]
Output: -1
Explanation: It is impossible to make the sum of both arrays equal.

Constraints:

• 1 <= nums1.length, nums2.length <= 10^5
• 0 <= nums1[i], nums2[i] <= 10^6

2025-05-11
1550. Three Consecutive Odds

Topic: Array
Difficulty: Easy

Problem:
Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.

Example 1:

Input: arr = [2,6,4,1]
Output: false
Explanation: There are no three consecutive odds.

Example 2:

Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] are three consecutive odds.

Constraints:

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000

2025-05-12
2094. Finding 3-Digit Even Numbers

Topic: Array, Hash Table, Sorting, Enumeration
Difficulty: Easy

Problem:
You are given an integer array digits, where each element is a digit. The array may contain duplicates.

You need to find all the unique integers that follow the given requirements:

• The integer consists of the concatenation of three elements from digits in any arbitrary order.
• The integer does not have leading zeros.
• The integer is even.

For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.

Return a sorted array of the unique integers.

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: All the possible integers that follow the requirements are in the output array. 
Notice that there are no odd integers or integers with leading zeros.

Example 2:

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: The same digit can be used as many times as it appears in digits. 
In this example, the digit 8 is used twice each time in 288, 828, and 882.

Example 3:

Input: digits = [3,7,5]
Output: []
Explanation: No even integers can be formed using the given digits.

Constraints:

• 3 <= digits.length <= 100
• 0 <= digits[i] <= 9

2025-05-13
3335. Total Characters in String After Transformations I

Topic: Hash Table, Math, String, Dynamic Programming, Counting
Difficulty: Medium

Problem:
You are given a string s and an integer t, representing the number of transformations to perform. In one transformation, every character in s is replaced according to the following rules:

• If the character is 'z', replace it with the string "ab".
• Otherwise, replace it with the next character in the alphabet. For example, 'a' is replaced with 'b', 'b' is replaced with 'c', and so on.

Return the length of the resulting string after exactly t transformations.

Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: s = "abcyy", t = 2

Output: 7

Explanation:

• First Transformation (t = 1):
• 'a' becomes 'b'
• 'b' becomes 'c'
• 'c' becomes 'd'
• 'y' becomes 'z'
• 'y' becomes 'z'
• String after the first transformation: "bcdzz"
• Second Transformation (t = 2):
• 'b' becomes 'c'
• 'c' becomes 'd'
• 'd' becomes 'e'
• 'z' becomes "ab"
• 'z' becomes "ab"
• String after the second transformation: "cdeabab"
• Final Length of the string: The string is "cdeabab", which has 7 characters.

Example 2:

Input: s = "azbk", t = 1

Output: 5

Explanation:

• First Transformation (t = 1):
• 'a' becomes 'b'
• 'z' becomes "ab"
• 'b' becomes 'c'
• 'k' becomes 'l'
• String after the first transformation: "babcl"
• Final Length of the string: The string is "babcl", which has 5 characters.

Constraints:

• 1 <= s.length <= 10^5
• s consists only of lowercase English letters.
• 1 <= t <= 10^5

2025-05-14
3337. Total Characters in String After Transformations II

Topic: Hash Table, Math, String, Dynamic Programming, Counting
Difficulty: Hard

Problem:
You are given a string s consisting of lowercase English letters, an integer t representing the number of transformations to perform, and an array nums of size 26. In one transformation, every character in s is replaced according to the following rules:

• Replace s[i] with the next nums[s[i] - 'a'] consecutive characters in the alphabet. For example, if s[i] = 'a' and nums[0] = 3, the character 'a' transforms into the next 3 consecutive characters ahead of it, which results in "bcd".
• The transformation wraps around the alphabet if it exceeds 'z'. For example, if s[i] = 'y' and nums[24] = 3, the character 'y' transforms into the next 3 consecutive characters ahead of it, which results in "zab".

Return the length of the resulting string after exactly t transformations.

Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: s = "abcyy", t = 2, nums = 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2

Output: 7

Explanation:

• First Transformation (t = 1):

• 'a' becomes 'b' as nums[0] == 1
• 'b' becomes 'c' as nums[1] == 1
• 'c' becomes 'd' as nums[2] == 1
• 'y' becomes 'z' as nums[24] == 1
• 'y' becomes 'z' as nums[24] == 1
• String after the first transformation: "bcdzz"
• Second Transformation (t = 2):

• 'b' becomes 'c' as nums[1] == 1
• 'c' becomes 'd' as nums[2] == 1
• 'd' becomes 'e' as nums[3] == 1
• 'z' becomes 'ab' as nums[25] == 2
• 'z' becomes 'ab' as nums[25] == 2
• String after the second transformation: "cdeabab"
• Final Length of the string: The string is "cdeabab", which has 7 characters.

Example 2:

Input: s = "azbk", t = 1, nums = 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2

Output: 8

Explanation:

• First Transformation (t = 1):

• 'a' becomes 'bc' as nums[0] == 2
• 'z' becomes 'ab' as nums[25] == 2
• 'b' becomes 'cd' as nums[1] == 2
• 'k' becomes 'lm' as nums[10] == 2
• String after the first transformation: "bcabcdlm"
• Final Length of the string: The string is "bcabcdlm", which has 8 characters.

Constraints:

• 1 <= s.length <= 10^5
• s consists only of lowercase English letters.
• 1 <= t <= 10^9
• nums.length == 26
• 1 <= nums[i] <= 25

2025-05-15
2900. Longest Unequal Adjacent Groups Subsequence I

Topic: Array, String, Dynamic Programming, Greedy
Difficulty: Easy

Problem:
You are given a string array words and a binary array groups both of length n, where words[i] is associated with groups[i].

Your task is to select the longest alternating subsequence from words. A subsequence of words is alternating if for any two consecutive strings in the sequence, their corresponding elements in the binary array groups differ. Essentially, you are to choose strings such that adjacent elements have non-matching corresponding bits in the groups array.

Formally, you need to find the longest subsequence of an array of indices [0, 1, ..., n - 1] denoted as [i_0, i_1, ..., i_k-1], such that groups[i_j] != groups[i_j+1] for each 0 <= j < k - 1 and then find the words corresponding to these indices.

Return the selected subsequence. If there are multiple answers, return any of them.

Note: The elements in words are distinct.

Example 1:

Input: words = "e","a","b", groups = 0,0,1

Output: "e","b"

Explanation: A subsequence that can be selected is ["e","b"] because groups[0] != groups[2]. Another subsequence that can be selected is ["a","b"] because groups[1] != groups[2]. It can be demonstrated that the length of the longest subsequence of indices that satisfies the condition is 2.

Example 2:

Input: words = "a","b","c","d", groups = 1,0,1,1

Output: "a","b","c"

Explanation: A subsequence that can be selected is ["a","b","c"] because groups[0] != groups[1] and groups[1] != groups[2]. Another subsequence that can be selected is ["a","b","d"] because groups[0] != groups[1] and groups[1] != groups[3]. It can be shown that the length of the longest subsequence of indices that satisfies the condition is 3.

Constraints:

• 1 <= n == words.length == groups.length <= 100
• 1 <= words[i].length <= 10
• groups[i] is either 0 or 1.
• words consists of distinct strings.
• words[i] consists of lowercase English letters.

2025-05-16
2901. Longest Unequal Adjacent Groups Subsequence II

Topic: Array, String, Dynamic Programming
Difficulty: Medium

Problem:
You are given a string array words, and an array groups, both arrays having length n.

The hamming distance between two strings of equal length is the number of positions at which the corresponding characters are different.

You need to select the longest subsequence from an array of indices [0, 1, ..., n - 1], such that for the subsequence denoted as [i_0, i_1, ..., i_k-1] having length k, the following holds:

• For adjacent indices in the subsequence, their corresponding groups are unequal, i.e., groups[i_j] != groups[i_j+1], for each j where 0 < j + 1 < k.
• words[i_j] and words[i_j+1] are equal in length, and the hamming distance between them is 1, where 0 < j + 1 < k, for all indices in the subsequence.

Return a string array containing the words corresponding to the indices (in order) in the selected subsequence. If there are multiple answers, return any of them.

Note: strings in words may be unequal in length.

Example 1:

Input: words = "bab","dab","cab", groups = 1,2,2

Output: "bab","cab"

Explanation: A subsequence that can be selected is [0,2].

• groups[0] != groups[2]
• words[0].length == words[2].length, and the hamming distance between them is 1.

So, a valid answer is [words[0],words[2]] = ["bab","cab"].

Another subsequence that can be selected is [0,1].

• groups[0] != groups[1]
• words[0].length == words[1].length, and the hamming distance between them is 1.

So, another valid answer is [words[0],words[1]] = ["bab","dab"].

It can be shown that the length of the longest subsequence of indices that satisfies the conditions is 2.

Example 2:

Input: words = "a","b","c","d", groups = 1,2,3,4

Output: "a","b","c","d"

Explanation: We can select the subsequence [0,1,2,3].

It satisfies both conditions.

Hence, the answer is [words[0],words[1],words[2],words[3]] = ["a","b","c","d"].

It has the longest length among all subsequences of indices that satisfy the conditions.

Hence, it is the only answer.

Constraints:

• 1 <= n == words.length == groups.length <= 1000
• 1 <= words[i].length <= 10
• 1 <= groups[i] <= n
• words consists of distinct strings.
• words[i] consists of lowercase English letters.

2025-05-17
75. Sort Colors

Topic: Array, Two Pointers, Sorting
Difficulty: Medium

Problem:
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Constraints:

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

2025-05-18
1931. Painting a Grid With Three Different Colors

Topic: Dynamic Programming
Difficulty: Hard

Problem:
You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.

Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 10^9 + 7.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/06/22/colorthegrid.png

Input: m = 1, n = 1
Output: 3
Explanation: The three possible colorings are shown in the image above.

Example 2:

Image: https://assets.leetcode.com/uploads/2021/06/22/copy-of-colorthegrid.png

Input: m = 1, n = 2
Output: 6
Explanation: The six possible colorings are shown in the image above.

Example 3:

Input: m = 5, n = 5
Output: 580986

Constraints:

• 1 <= m <= 5
• 1 <= n <= 1000

2025-05-19
3024. Type of Triangle

Topic: Array, Math, Sorting
Difficulty: Easy

Problem:
You are given a 0-indexed integer array nums of size 3 which can form the sides of a triangle.

• A triangle is called equilateral if it has all sides of equal length.
• A triangle is called isosceles if it has exactly two sides of equal length.
• A triangle is called scalene if all its sides are of different lengths.

Return a string representing the type of triangle that can be formed or "none" if it cannot form a triangle.

Example 1:

Input: nums = [3,3,3]
Output: "equilateral"
Explanation: Since all the sides are of equal length, therefore, it will form an equilateral triangle.

Example 2:

Input: nums = [3,4,5]
Output: "scalene"
Explanation: 
nums[0] + nums[1] = 3 + 4 = 7, which is greater than nums[2] = 5.
nums[0] + nums[2] = 3 + 5 = 8, which is greater than nums[1] = 4.
nums[1] + nums[2] = 4 + 5 = 9, which is greater than nums[0] = 3. 
Since the sum of the two sides is greater than the third side for all three cases, therefore, it can form a triangle.
As all the sides are of different lengths, it will form a scalene triangle.

Constraints:

• nums.length == 3
• 1 <= nums[i] <= 100

2025-05-20
3355. Zero Array Transformation I

Topic: Array, 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].

For each queries[i]:

• Select a subset of indices within the range [l_i, r_i] in nums.
• Decrement the values at the selected indices by 1.

A Zero Array is an array where all elements are equal to 0.

Return true if it is possible to transform nums into a Zero Array after processing all the queries sequentially, otherwise return false.

Example 1:

Input: nums = 1,0,1, queries = [0,2]

Output: true

Explanation:

• For i = 0:
• Select the subset of indices as [0, 2] and decrement the values at these indices by 1.
• The array will become [0, 0, 0], which is a Zero Array.

Example 2:

Input: nums = 4,3,2,1, queries = [1,3,0,2]

Output: false

Explanation:

• For i = 0:
• Select the subset of indices as [1, 2, 3] and decrement the values at these indices by 1.
• The array will become [4, 2, 1, 0].
• For i = 1:
• Select the subset of indices as [0, 1, 2] and decrement the values at these indices by 1.
• The array will become [3, 1, 0, 0], which is not a Zero Array.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= l_i <= r_i < nums.length

2025-05-21
73. Set Matrix Zeroes

Topic: Array, Hash Table, Matrix
Difficulty: Medium

Problem:
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

Example 1:

Image: https://assets.leetcode.com/uploads/2020/08/17/mat1.jpg

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Image: https://assets.leetcode.com/uploads/2020/08/17/mat2.jpg

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^31 <= matrix[i][j] <= 2^31 - 1

Follow up:

• A straightforward solution using O(mn) space is probably a bad idea.
• A simple improvement uses O(m + n) space, but still not the best solution.
• Could you devise a constant space solution?

2025-05-22
3362. Zero Array Transformation III

Topic: Array, Greedy, Sorting, Heap (Priority Queue), 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].

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 1.
• The amount by which the 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 maximum number of elements that can be removed from queries, such that nums can still be converted to a zero array using the remaining queries. If it is not possible to convert nums to a zero array, return -1.

Example 1:

Input: nums = 2,0,2, queries = [0,2,0,2,1,1]

Output: 1

Explanation:

After removing queries[2], nums can still be converted to a zero array.

• Using queries[0], decrement nums[0] and nums[2] by 1 and nums[1] by 0.
• Using queries[1], decrement nums[0] and nums[2] by 1 and nums[1] by 0.

Example 2:

Input: nums = 1,1,1,1, queries = [1,3,0,2,1,3,1,2]

Output: 2

Explanation:

We can remove queries[2] and queries[3].

Example 3:

Input: nums = 1,2,3,4, queries = [0,3]

Output: -1

Explanation:

nums cannot be converted to a zero array even after using all the queries.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= l_i <= r_i < nums.length

2025-05-23
3068. Find the Maximum Sum of Node Values

Topic: Array, Dynamic Programming, Greedy, Bit Manipulation, Tree, Sorting
Difficulty: Hard

Problem:
There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 0-indexed 2D integer array edges of length n - 1, where edges[i] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i in the tree. You are also given a positive integer k, and a 0-indexed array of non-negative integers nums of length n, where nums[i] represents the value of the node numbered i.

Alice wants the sum of values of tree nodes to be maximum, for which Alice can perform the following operation any number of times (including zero) on the tree:

• Choose any edge [u, v] connecting the nodes u and v, and update their values as follows:
• nums[u] = nums[u] XOR k
• nums[v] = nums[v] XOR k

Return the maximum possible sum of the values Alice can achieve by performing the operation any number of times.

Example 1:

Image: https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012513.png

Input: nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
Output: 6
Explanation: Alice can achieve the maximum sum of 6 using a single operation:
- Choose the edge [0,2]. nums[0] and nums[2] become: 1 XOR 3 = 2, and the array nums becomes: [1,2,1] -> [2,2,2].
The total sum of values is 2 + 2 + 2 = 6.
It can be shown that 6 is the maximum achievable sum of values.

Example 2:

Image: https://assets.leetcode.com/uploads/2024/01/09/screenshot-2024-01-09-220017.png

Input: nums = [2,3], k = 7, edges = [[0,1]]
Output: 9
Explanation: Alice can achieve the maximum sum of 9 using a single operation:
- Choose the edge [0,1]. nums[0] becomes: 2 XOR 7 = 5 and nums[1] become: 3 XOR 7 = 4, and the array nums becomes: [2,3] -> [5,4].
The total sum of values is 5 + 4 = 9.
It can be shown that 9 is the maximum achievable sum of values.

Example 3:

Image: https://assets.leetcode.com/uploads/2023/11/09/screenshot-2023-11-10-012641.png

Input: nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
Output: 42
Explanation: The maximum achievable sum is 42 which can be achieved by Alice performing no operations.

Constraints:

• 2 <= n == nums.length <= 2 * 10^4
• 1 <= k <= 10^9
• 0 <= nums[i] <= 10^9
• edges.length == n - 1
• edges[i].length == 2
• 0 <= edges[i][0], edges[i][1] <= n - 1
• The input is generated such that edges represent a valid tree.

2025-05-24
2942. Find Words Containing Character

Topic: Array, String
Difficulty: Easy

Problem:
You are given a 0-indexed array of strings words and a character x.

Return an array of indices representing the words that contain the character x.

Note that the returned array may be in any order.

Example 1:

Input: words = ["leet","code"], x = "e"
Output: [0,1]
Explanation: "e" occurs in both words: "leet", and "code". Hence, we return indices 0 and 1.

Example 2:

Input: words = ["abc","bcd","aaaa","cbc"], x = "a"
Output: [0,2]
Explanation: "a" occurs in "abc", and "aaaa". Hence, we return indices 0 and 2.

Example 3:

Input: words = ["abc","bcd","aaaa","cbc"], x = "z"
Output: []
Explanation: "z" does not occur in any of the words. Hence, we return an empty array.

Constraints:

• 1 <= words.length <= 50
• 1 <= words[i].length <= 50
• x is a lowercase English letter.
• words[i] consists only of lowercase English letters.

2025-05-25
2131. Longest Palindrome by Concatenating Two Letter Words

Topic: Array, Hash Table, String, Greedy, Counting
Difficulty: Medium

Problem:
You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

Example 1:

Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.

Example 2:

Input: words = ["ab","ty","yt","lc","cl","ab"]
Output: 8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.

Example 3:

Input: words = ["cc","ll","xx"]
Output: 2
Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".

Constraints:

• 1 <= words.length <= 10^5
• words[i].length == 2
• words[i] consists of lowercase English letters.

2025-05-26
1857. Largest Color Value in a Directed Graph

Topic: Hash Table, Dynamic Programming, Graph, Topological Sort, Memoization, Counting
Difficulty: Hard

Problem:
There is a directed graph of n colored nodes and m edges. The nodes are numbered from 0 to n - 1.

You are given a string colors where colors[i] is a lowercase English letter representing the color of the i^th node in this graph (0-indexed). You are also given a 2D array edges where edges[j] = [a_j, b_j] indicates that there is a directed edge from node a_j to node b_j.

A valid path in the graph is a sequence of nodes x_1 -> x_2 -> x_3 -> ... -> x_k such that there is a directed edge from x_i to x_i+1 for every 1 <= i < k. The color value of the path is the number of nodes that are colored the most frequently occurring color along that path.

Return the largest color value of any valid path in the given graph, or -1 if the graph contains a cycle.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/04/21/leet1.png

Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).

Example 2:

Image: https://assets.leetcode.com/uploads/2021/04/21/leet2.png

Input: colors = "a", edges = [[0,0]]
Output: -1
Explanation: There is a cycle from 0 to 0.

Constraints:

• n == colors.length
• m == edges.length
• 1 <= n <= 10^5
• 0 <= m <= 10^5
• colors consists of lowercase English letters.
• 0 <= a_j, b_j < n

2025-05-27
2894. Divisible and Non-divisible Sums Difference

Topic: Math
Difficulty: Easy

Problem:
You are given positive integers n and m.

Define two integers as follows:

• num1: The sum of all integers in the range [1, n] (both inclusive) that are not divisible by m.
• num2: The sum of all integers in the range [1, n] (both inclusive) that are divisible by m.

Return the integer num1 - num2.

Example 1:

Input: n = 10, m = 3
Output: 19
Explanation: In the given example:
- Integers in the range [1, 10] that are not divisible by 3 are [1,2,4,5,7,8,10], num1 is the sum of those integers = 37.
- Integers in the range [1, 10] that are divisible by 3 are [3,6,9], num2 is the sum of those integers = 18.
We return 37 - 18 = 19 as the answer.

Example 2:

Input: n = 5, m = 6
Output: 15
Explanation: In the given example:
- Integers in the range [1, 5] that are not divisible by 6 are [1,2,3,4,5], num1 is the sum of those integers = 15.
- Integers in the range [1, 5] that are divisible by 6 are [], num2 is the sum of those integers = 0.
We return 15 - 0 = 15 as the answer.

Example 3:

Input: n = 5, m = 1
Output: -15
Explanation: In the given example:
- Integers in the range [1, 5] that are not divisible by 1 are [], num1 is the sum of those integers = 0.
- Integers in the range [1, 5] that are divisible by 1 are [1,2,3,4,5], num2 is the sum of those integers = 15.
We return 0 - 15 = -15 as the answer.

Constraints:

• 1 <= n, m <= 1000

2025-05-28
3372. Maximize the Number of Target Nodes After Connecting Trees I

Topic: Tree, Depth-First Search, Breadth-First Search
Difficulty: Medium

Problem:
There exist two undirected trees with n and m nodes, with distinct labels in ranges [0, n - 1] and [0, m - 1], respectively.

You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the first tree and edges2[i] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i in the second tree. You are also given an integer k.

Node u is target to node v if the number of edges on the path from u to v is less than or equal to k. Note that a node is always target to itself.

Return an array of n integers answer, where answer[i] is the maximum possible number of nodes target to node i of the first tree if you have to connect one node from the first tree to another node in the second tree.

Note that queries are independent from each other. That is, for every query you will remove the added edge before proceeding to the next query.

Example 1:

Input: edges1 = [0,1,0,2,2,3,2,4], edges2 = [0,1,0,2,0,3,2,7,1,4,4,5,4,6], k = 2

Output: 9,7,9,8,8

Explanation:

• For i = 0, connect node 0 from the first tree to node 0 from the second tree.
• For i = 1, connect node 1 from the first tree to node 0 from the second tree.
• For i = 2, connect node 2 from the first tree to node 4 from the second tree.
• For i = 3, connect node 3 from the first tree to node 4 from the second tree.
• For i = 4, connect node 4 from the first tree to node 4 from the second tree.

Image: https://assets.leetcode.com/uploads/2024/09/24/3982-1.png

Example 2:

Input: edges1 = [0,1,0,2,0,3,0,4], edges2 = [0,1,1,2,2,3], k = 1

Output: 6,3,3,3,3

Explanation:

For every i, connect node i of the first tree with any node of the second tree.

Image: https://assets.leetcode.com/uploads/2024/09/24/3928-2.png

Constraints:

• 2 <= n, m <= 1000
• edges1.length == n - 1
• edges2.length == m - 1
• edges1[i].length == edges2[i].length == 2
• edges1[i] = [a_i, b_i]
• 0 <= a_i, b_i < n
• edges2[i] = [u_i, v_i]
• 0 <= u_i, v_i < m
• The input is generated such that edges1 and edges2 represent valid trees.
• 0 <= k <= 1000

2025-05-29
3373. Maximize the Number of Target Nodes After Connecting Trees II

Topic: Tree, Depth-First Search, Breadth-First Search
Difficulty: Hard

Problem:
There exist two undirected trees with n and m nodes, labeled from [0, n - 1] and [0, m - 1], respectively.

You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the first tree and edges2[i] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i in the second tree.

Node u is target to node v if the number of edges on the path from u to v is even. Note that a node is always target to itself.

Return an array of n integers answer, where answer[i] is the maximum possible number of nodes that are target to node i of the first tree if you had to connect one node from the first tree to another node in the second tree.

Note that queries are independent from each other. That is, for every query you will remove the added edge before proceeding to the next query.

Example 1:

Input: edges1 = [0,1,0,2,2,3,2,4], edges2 = [0,1,0,2,0,3,2,7,1,4,4,5,4,6]

Output: 8,7,7,8,8

Explanation:

• For i = 0, connect node 0 from the first tree to node 0 from the second tree.
• For i = 1, connect node 1 from the first tree to node 4 from the second tree.
• For i = 2, connect node 2 from the first tree to node 7 from the second tree.
• For i = 3, connect node 3 from the first tree to node 0 from the second tree.
• For i = 4, connect node 4 from the first tree to node 4 from the second tree.

Image: https://assets.leetcode.com/uploads/2024/09/24/3982-1.png

Example 2:

Input: edges1 = [0,1,0,2,0,3,0,4], edges2 = [0,1,1,2,2,3]

Output: 3,6,6,6,6

Explanation:

For every i, connect node i of the first tree with any node of the second tree.

Image: https://assets.leetcode.com/uploads/2024/09/24/3928-2.png

Constraints:

• 2 <= n, m <= 10^5
• edges1.length == n - 1
• edges2.length == m - 1
• edges1[i].length == edges2[i].length == 2
• edges1[i] = [a_i, b_i]
• 0 <= a_i, b_i < n
• edges2[i] = [u_i, v_i]
• 0 <= u_i, v_i < m
• The input is generated such that edges1 and edges2 represent valid trees.