bowang0911/leetcode huggingface dataset:
Divide Players Into Teams of Equal Skill

You are given a positive integer array `skill` of **even** length `n` where `skill[i]` denotes the skill of the `ith` player. Divide the players into `n / 2` teams of size `2` such that the total skill of each team is **equal**.

The **chemistry** of a team is equal to the **product** of the skills of the players on that team.

Return _the sum of the **chemistry** of all the teams, or return_ `-1` _if there is no way to divide the players into teams such that the total skill of each team is equal._

**Example 1:**

**Input:** skill = \[3,2,5,1,3,4\]
**Output:** 22
**Explanation:** 
Divide the players into the following teams: (1, 5), (2, 4), (3, 3), where each team has a total skill of 6.
The sum of the chemistry of all the teams is: 1 \* 5 + 2 \* 4 + 3 \* 3 = 5 + 8 + 9 = 22.

**Example 2:**

**Input:** skill = \[3,4\]
**Output:** 12
**Explanation:** 
The two players form a team with a total skill of 7.
The chemistry of the team is 3 \* 4 = 12.

**Example 3:**

**Input:** skill = \[1,1,2,3\]
**Output:** -1
**Explanation:** 
There is no way to divide the players into teams such that the total skill of each team is equal.

**Constraints:**

*   `2 <= skill.length <= 105`
*   `skill.length` is even.
*   `1 <= skill[i] <= 1000`
Minimum Score of a Path Between Two Cities

You are given a positive integer `n` representing `n` cities numbered from `1` to `n`. You are also given a **2D** array `roads` where `roads[i] = [ai, bi, distancei]` indicates that there is a **bidirectional** road between cities `ai` and `bi` with a distance equal to `distancei`. The cities graph is not necessarily connected.

The **score** of a path between two cities is defined as the **minimum** distance of a road in this path.

Return _the **minimum** possible score of a path between cities_ `1` _and_ `n`.

**Note**:

*   A path is a sequence of roads between two cities.
*   It is allowed for a path to contain the same road **multiple** times, and you can visit cities `1` and `n` multiple times along the path.
*   The test cases are generated such that there is **at least** one path between `1` and `n`.

**Example 1:**

**Input:** n = 4, roads = \[\[1,2,9\],\[2,3,6\],\[2,4,5\],\[1,4,7\]\]
**Output:** 5
**Explanation:** The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 4. The score of this path is min(9,5) = 5.
It can be shown that no other path has less score.

**Example 2:**

**Input:** n = 4, roads = \[\[1,2,2\],\[1,3,4\],\[3,4,7\]\]
**Output:** 2
**Explanation:** The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 1 -> 3 -> 4. The score of this path is min(2,2,4,7) = 2.

**Constraints:**

*   `2 <= n <= 105`
*   `1 <= roads.length <= 105`
*   `roads[i].length == 3`
*   `1 <= ai, bi <= n`
*   `ai != bi`
*   `1 <= distancei <= 104`
*   There are no repeated edges.
*   There is at least one path between `1` and `n`.
Divide Nodes Into the Maximum Number of Groups

You are given a positive integer `n` representing the number of nodes in an **undirected** graph. The nodes are labeled from `1` to `n`.

You are also given a 2D integer array `edges`, where `edges[i] = [ai, bi]` indicates that there is a **bidirectional** edge between nodes `ai` and `bi`. **Notice** that the given graph may be disconnected.

Divide the nodes of the graph into `m` groups (**1-indexed**) such that:

*   Each node in the graph belongs to exactly one group.
*   For every pair of nodes in the graph that are connected by an edge `[ai, bi]`, if `ai` belongs to the group with index `x`, and `bi` belongs to the group with index `y`, then `|y - x| = 1`.

Return _the maximum number of groups (i.e., maximum_ `m`_) into which you can divide the nodes_. Return `-1` _if it is impossible to group the nodes with the given conditions_.

**Example 1:**

**Input:** n = 6, edges = \[\[1,2\],\[1,4\],\[1,5\],\[2,6\],\[2,3\],\[4,6\]\]
**Output:** 4
**Explanation:** As shown in the image we:
- Add node 5 to the first group.
- Add node 1 to the second group.
- Add nodes 2 and 4 to the third group.
- Add nodes 3 and 6 to the fourth group.
We can see that every edge is satisfied.
It can be shown that that if we create a fifth group and move any node from the third or fourth group to it, at least on of the edges will not be satisfied.

**Example 2:**

**Input:** n = 3, edges = \[\[1,2\],\[2,3\],\[3,1\]\]
**Output:** -1
**Explanation:** If we add node 1 to the first group, node 2 to the second group, and node 3 to the third group to satisfy the first two edges, we can see that the third edge will not be satisfied.
It can be shown that no grouping is possible.

**Constraints:**

*   `1 <= n <= 500`
*   `1 <= edges.length <= 104`
*   `edges[i].length == 2`
*   `1 <= ai, bi <= n`
*   `ai != bi`
*   There is at most one edge between any pair of vertices.
Number of Subarrays Having Even Product

Given a **0-indexed** integer array `nums`, return _the number of subarrays of_ `nums` _having an even product_.

**Example 1:**

**Input:** nums = \[9,6,7,13\]
**Output:** 6
**Explanation:** There are 6 subarrays with an even product:
- nums\[0..1\] = 9 \* 6 = 54.
- nums\[0..2\] = 9 \* 6 \* 7 = 378.
- nums\[0..3\] = 9 \* 6 \* 7 \* 13 = 4914.
- nums\[1..1\] = 6.
- nums\[1..2\] = 6 \* 7 = 42.
- nums\[1..3\] = 6 \* 7 \* 13 = 546.

**Example 2:**

**Input:** nums = \[7,3,5\]
**Output:** 0
**Explanation:** There are no subarrays with an even product.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 105`
Maximum Value of a String in an Array

The **value** of an alphanumeric string can be defined as:

*   The **numeric** representation of the string in base `10`, if it comprises of digits **only**.
*   The **length** of the string, otherwise.

Given an array `strs` of alphanumeric strings, return _the **maximum value** of any string in_ `strs`.

**Example 1:**

**Input:** strs = \[ "alic3 ", "bob ", "3 ", "4 ", "00000 "\]
**Output:** 5
**Explanation:** 
-  "alic3 " consists of both letters and digits, so its value is its length, i.e. 5.
-  "bob " consists only of letters, so its value is also its length, i.e. 3.
-  "3 " consists only of digits, so its value is its numeric equivalent, i.e. 3.
-  "4 " also consists only of digits, so its value is 4.
-  "00000 " consists only of digits, so its value is 0.
Hence, the maximum value is 5, of  "alic3 ".

**Example 2:**

**Input:** strs = \[ "1 ", "01 ", "001 ", "0001 "\]
**Output:** 1
**Explanation:** 
Each string in the array has value 1. Hence, we return 1.

**Constraints:**

*   `1 <= strs.length <= 100`
*   `1 <= strs[i].length <= 9`
*   `strs[i]` consists of only lowercase English letters and digits.
Maximum Star Sum of a Graph

There is an undirected graph consisting of `n` nodes numbered from `0` to `n - 1`. You are given a **0-indexed** integer array `vals` of length `n` where `vals[i]` denotes the value of the `ith` node.

You are also given a 2D integer array `edges` where `edges[i] = [ai, bi]` denotes that there exists an **undirected** edge connecting nodes `ai` and `bi.`

A **star graph** is a subgraph of the given graph having a center node containing `0` or more neighbors. In other words, it is a subset of edges of the given graph such that there exists a common node for all edges.

The image below shows star graphs with `3` and `4` neighbors respectively, centered at the blue node.

The **star sum** is the sum of the values of all the nodes present in the star graph.

Given an integer `k`, return _the **maximum star sum** of a star graph containing **at most**_ `k` _edges._

**Example 1:**

**Input:** vals = \[1,2,3,4,10,-10,-20\], edges = \[\[0,1\],\[1,2\],\[1,3\],\[3,4\],\[3,5\],\[3,6\]\], k = 2
**Output:** 16
**Explanation:** The above diagram represents the input graph.
The star graph with the maximum star sum is denoted by blue. It is centered at 3 and includes its neighbors 1 and 4.
It can be shown it is not possible to get a star graph with a sum greater than 16.

**Example 2:**

**Input:** vals = \[-5\], edges = \[\], k = 0
**Output:** -5
**Explanation:** There is only one possible star graph, which is node 0 itself.
Hence, we return -5.

**Constraints:**

*   `n == vals.length`
*   `1 <= n <= 105`
*   `-104 <= vals[i] <= 104`
*   `0 <= edges.length <= min(n * (n - 1) / 2``, 105)`
*   `edges[i].length == 2`
*   `0 <= ai, bi <= n - 1`
*   `ai != bi`
*   `0 <= k <= n - 1`
Frog Jump II

You are given a **0-indexed** integer array `stones` sorted in **strictly increasing order** representing the positions of stones in a river.

A frog, initially on the first stone, wants to travel to the last stone and then return to the first stone. However, it can jump to any stone **at most once**.

The **length** of a jump is the absolute difference between the position of the stone the frog is currently on and the position of the stone to which the frog jumps.

*   More formally, if the frog is at `stones[i]` and is jumping to `stones[j]`, the length of the jump is `|stones[i] - stones[j]|`.

The **cost** of a path is the **maximum length of a jump** among all jumps in the path.

Return _the **minimum** cost of a path for the frog_.

**Example 1:**

**Input:** stones = \[0,2,5,6,7\]
**Output:** 5
**Explanation:** The above figure represents one of the optimal paths the frog can take.
The cost of this path is 5, which is the maximum length of a jump.
Since it is not possible to achieve a cost of less than 5, we return it.

**Example 2:**

**Input:** stones = \[0,3,9\]
**Output:** 9
**Explanation:** 
The frog can jump directly to the last stone and come back to the first stone. 
In this case, the length of each jump will be 9. The cost for the path will be max(9, 9) = 9.
It can be shown that this is the minimum achievable cost.

**Constraints:**

*   `2 <= stones.length <= 105`
*   `0 <= stones[i] <= 109`
*   `stones[0] == 0`
*   `stones` is sorted in a strictly increasing order.
Minimum Total Cost to Make Arrays Unequal

You are given two **0-indexed** integer arrays `nums1` and `nums2`, of equal length `n`.

In one operation, you can swap the values of any two indices of `nums1`. The **cost** of this operation is the **sum** of the indices.

Find the **minimum** total cost of performing the given operation **any** number of times such that `nums1[i] != nums2[i]` for all `0 <= i <= n - 1` after performing all the operations.

Return _the **minimum total cost** such that_ `nums1` and `nums2` _satisfy the above condition_. In case it is not possible, return `-1`.

**Example 1:**

**Input:** nums1 = \[1,2,3,4,5\], nums2 = \[1,2,3,4,5\]
**Output:** 10
**Explanation:** 
One of the ways we can perform the operations is:
- Swap values at indices 0 and 3, incurring cost = 0 + 3 = 3. Now, nums1 = \[4,2,3,1,5\]
- Swap values at indices 1 and 2, incurring cost = 1 + 2 = 3. Now, nums1 = \[4,3,2,1,5\].
- Swap values at indices 0 and 4, incurring cost = 0 + 4 = 4. Now, nums1 =\[5,3,2,1,4\].
We can see that for each index i, nums1\[i\] != nums2\[i\]. The cost required here is 10.
Note that there are other ways to swap values, but it can be proven that it is not possible to obtain a cost less than 10.

**Example 2:**

**Input:** nums1 = \[2,2,2,1,3\], nums2 = \[1,2,2,3,3\]
**Output:** 10
**Explanation:** 
One of the ways we can perform the operations is:
- Swap values at indices 2 and 3, incurring cost = 2 + 3 = 5. Now, nums1 = \[2,2,1,2,3\].
- Swap values at indices 1 and 4, incurring cost = 1 + 4 = 5. Now, nums1 = \[2,3,1,2,2\].
The total cost needed here is 10, which is the minimum possible.

**Example 3:**

**Input:** nums1 = \[1,2,2\], nums2 = \[1,2,2\]
**Output:** -1
**Explanation:** 
It can be shown that it is not possible to satisfy the given conditions irrespective of the number of operations we perform.
Hence, we return -1.

**Constraints:**

*   `n == nums1.length == nums2.length`
*   `1 <= n <= 105`
*   `1 <= nums1[i], nums2[i] <= n`
Delete Greatest Value in Each Row

You are given an `m x n` matrix `grid` consisting of positive integers.

Perform the following operation until `grid` becomes empty:

*   Delete the element with the greatest value from each row. If multiple such elements exist, delete any of them.
*   Add the maximum of deleted elements to the answer.

**Note** that the number of columns decreases by one after each operation.

Return _the answer after performing the operations described above_.

**Example 1:**

**Input:** grid = \[\[1,2,4\],\[3,3,1\]\]
**Output:** 8
**Explanation:** The diagram above shows the removed values in each step.
- In the first operation, we remove 4 from the first row and 3 from the second row (notice that, there are two cells with value 3 and we can remove any of them). We add 4 to the answer.
- In the second operation, we remove 2 from the first row and 3 from the second row. We add 3 to the answer.
- In the third operation, we remove 1 from the first row and 1 from the second row. We add 1 to the answer.
The final answer = 4 + 3 + 1 = 8.

**Example 2:**

**Input:** grid = \[\[10\]\]
**Output:** 10
**Explanation:** The diagram above shows the removed values in each step.
- In the first operation, we remove 10 from the first row. We add 10 to the answer.
The final answer = 10.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 50`
*   `1 <= grid[i][j] <= 100`
Longest Square Streak in an Array

You are given an integer array `nums`. A subsequence of `nums` is called a **square streak** if:

*   The length of the subsequence is at least `2`, and
*   **after** sorting the subsequence, each element (except the first element) is the **square** of the previous number.

Return _the length of the **longest square streak** in_ `nums`_, or return_ `-1` _if there is no **square streak**._

A **subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

**Example 1:**

**Input:** nums = \[4,3,6,16,8,2\]
**Output:** 3
**Explanation:** Choose the subsequence \[4,16,2\]. After sorting it, it becomes \[2,4,16\].
- 4 = 2 \* 2.
- 16 = 4 \* 4.
Therefore, \[4,16,2\] is a square streak.
It can be shown that every subsequence of length 4 is not a square streak.

**Example 2:**

**Input:** nums = \[2,3,5,6,7\]
**Output:** -1
**Explanation:** There is no square streak in nums so return -1.

**Constraints:**

*   `2 <= nums.length <= 105`
*   `2 <= nums[i] <= 105`
Design Memory Allocator

You are given an integer `n` representing the size of a **0-indexed** memory array. All memory units are initially free.

You have a memory allocator with the following functionalities:

1.  **Allocate** a block of `size` consecutive free memory units and assign it the id `mID`.
2.  **Free** all memory units with the given id `mID`.

**Note** that:

*   Multiple blocks can be allocated to the same `mID`.
*   You should free all the memory units with `mID`, even if they were allocated in different blocks.

Implement the `Allocator` class:

*   `Allocator(int n)` Initializes an `Allocator` object with a memory array of size `n`.
*   `int allocate(int size, int mID)` Find the **leftmost** block of `size` **consecutive** free memory units and allocate it with the id `mID`. Return the block's first index. If such a block does not exist, return `-1`.
*   `int free(int mID)` Free all memory units with the id `mID`. Return the number of memory units you have freed.

**Example 1:**

**Input**
\[ "Allocator ",  "allocate ",  "allocate ",  "allocate ",  "free ",  "allocate ",  "allocate ",  "allocate ",  "free ",  "allocate ",  "free "\]
\[\[10\], \[1, 1\], \[1, 2\], \[1, 3\], \[2\], \[3, 4\], \[1, 1\], \[1, 1\], \[1\], \[10, 2\], \[7\]\]
**Output**
\[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0\]

**Explanation**
Allocator loc = new Allocator(10); // Initialize a memory array of size 10. All memory units are initially free.
loc.allocate(1, 1); // The leftmost block's first index is 0. The memory array becomes \[**1**,\_,\_,\_,\_,\_,\_,\_,\_,\_\]. We return 0.
loc.allocate(1, 2); // The leftmost block's first index is 1. The memory array becomes \[1,**2**,\_,\_,\_,\_,\_,\_,\_,\_\]. We return 1.
loc.allocate(1, 3); // The leftmost block's first index is 2. The memory array becomes \[1,2,**3**,\_,\_,\_,\_,\_,\_,\_\]. We return 2.
loc.free(2); // Free all memory units with mID 2. The memory array becomes \[1,\_, 3,\_,\_,\_,\_,\_,\_,\_\]. We return 1 since there is only 1 unit with mID 2.
loc.allocate(3, 4); // The leftmost block's first index is 3. The memory array becomes \[1,\_,3,**4**,**4**,**4**,\_,\_,\_,\_\]. We return 3.
loc.allocate(1, 1); // The leftmost block's first index is 1. The memory array becomes \[1,**1**,3,4,4,4,\_,\_,\_,\_\]. We return 1.
loc.allocate(1, 1); // The leftmost block's first index is 6. The memory array becomes \[1,1,3,4,4,4,**1**,\_,\_,\_\]. We return 6.
loc.free(1); // Free all memory units with mID 1. The memory array becomes \[\_,\_,3,4,4,4,\_,\_,\_,\_\]. We return 3 since there are 3 units with mID 1.
loc.allocate(10, 2); // We can not find any free block with 10 consecutive free memory units, so we return -1.
loc.free(7); // Free all memory units with mID 7. The memory array remains the same since there is no memory unit with mID 7. We return 0.

**Constraints:**

*   `1 <= n, size, mID <= 1000`
*   At most `1000` calls will be made to `allocate` and `free`.
Maximum Number of Points From Grid Queries

You are given an `m x n` integer matrix `grid` and an array `queries` of size `k`.

Find an array `answer` of size `k` such that for each integer `queries[i]` you start in the **top left** cell of the matrix and repeat the following process:

*   If `queries[i]` is **strictly** greater than the value of the current cell that you are in, then you get one point if it is your first time visiting this cell, and you can move to any **adjacent** cell in all `4` directions: up, down, left, and right.
*   Otherwise, you do not get any points, and you end this process.

After the process, `answer[i]` is the **maximum** number of points you can get. **Note** that for each query you are allowed to visit the same cell **multiple** times.

Return _the resulting array_ `answer`.

**Example 1:**

**Input:** grid = \[\[1,2,3\],\[2,5,7\],\[3,5,1\]\], queries = \[5,6,2\]
**Output:** \[5,8,1\]
**Explanation:** The diagrams above show which cells we visit to get points for each query.

**Example 2:**

**Input:** grid = \[\[5,2,1\],\[1,1,2\]\], queries = \[3\]
**Output:** \[0\]
**Explanation:** We can not get any points because the value of the top left cell is already greater than or equal to 3.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `2 <= m, n <= 1000`
*   `4 <= m * n <= 105`
*   `k == queries.length`
*   `1 <= k <= 104`
*   `1 <= grid[i][j], queries[i] <= 106`
Bitwise OR of All Subsequence Sums

Given an integer array `nums`, return _the value of the bitwise_ **OR** _of the sum of all possible **subsequences** in the array_.

A **subsequence** is a sequence that can be derived from another sequence by removing zero or more elements without changing the order of the remaining elements.

**Example 1:**

**Input:** nums = \[2,1,0,3\]
**Output:** 7
**Explanation:** All possible subsequence sums that we can have are: 0, 1, 2, 3, 4, 5, 6.
And we have 0 OR 1 OR 2 OR 3 OR 4 OR 5 OR 6 = 7, so we return 7.

**Example 2:**

**Input:** nums = \[0,0,0\]
**Output:** 0
**Explanation:** 0 is the only possible subsequence sum we can have, so we return 0.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `0 <= nums[i] <= 109`
Count Pairs Of Similar Strings

You are given a **0-indexed** string array `words`.

Two strings are **similar** if they consist of the same characters.

*   For example, `"abca "` and `"cba "` are similar since both consist of characters `'a'`, `'b'`, and `'c'`.
*   However, `"abacba "` and `"bcfd "` are not similar since they do not consist of the same characters.

Return _the number of pairs_ `(i, j)` _such that_ `0 <= i < j <= word.length - 1` _and the two strings_ `words[i]` _and_ `words[j]` _are similar_.

**Example 1:**

**Input:** words = \[ "aba ", "aabb ", "abcd ", "bac ", "aabc "\]
**Output:** 2
**Explanation:** There are 2 pairs that satisfy the conditions:
- i = 0 and j = 1 : both words\[0\] and words\[1\] only consist of characters 'a' and 'b'. 
- i = 3 and j = 4 : both words\[3\] and words\[4\] only consist of characters 'a', 'b', and 'c'. 

**Example 2:**

**Input:** words = \[ "aabb ", "ab ", "ba "\]
**Output:** 3
**Explanation:** There are 3 pairs that satisfy the conditions:
- i = 0 and j = 1 : both words\[0\] and words\[1\] only consist of characters 'a' and 'b'. 
- i = 0 and j = 2 : both words\[0\] and words\[2\] only consist of characters 'a' and 'b'.
- i = 1 and j = 2 : both words\[1\] and words\[2\] only consist of characters 'a' and 'b'.

**Example 3:**

**Input:** words = \[ "nba ", "cba ", "dba "\]
**Output:** 0
**Explanation:** Since there does not exist any pair that satisfies the conditions, we return 0.

**Constraints:**

*   `1 <= words.length <= 100`
*   `1 <= words[i].length <= 100`
*   `words[i]` consist of only lowercase English letters.
Smallest Value After Replacing With Sum of Prime Factors

You are given a positive integer `n`.

Continuously replace `n` with the sum of its **prime factors**.

*   Note that if a prime factor divides `n` multiple times, it should be included in the sum as many times as it divides `n`.

Return _the smallest value_ `n` _will take on._

**Example 1:**

**Input:** n = 15
**Output:** 5
**Explanation:** Initially, n = 15.
15 = 3 \* 5, so replace n with 3 + 5 = 8.
8 = 2 \* 2 \* 2, so replace n with 2 + 2 + 2 = 6.
6 = 2 \* 3, so replace n with 2 + 3 = 5.
5 is the smallest value n will take on.

**Example 2:**

**Input:** n = 3
**Output:** 3
**Explanation:** Initially, n = 3.
3 is the smallest value n will take on.

**Constraints:**

*   `2 <= n <= 105`
Add Edges to Make Degrees of All Nodes Even

There is an **undirected** graph consisting of `n` nodes numbered from `1` to `n`. You are given the integer `n` and a **2D** array `edges` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi`. The graph can be disconnected.

You can add **at most** two additional edges (possibly none) to this graph so that there are no repeated edges and no self-loops.

Return `true` _if it is possible to make the degree of each node in the graph even, otherwise return_ `false`_._

The degree of a node is the number of edges connected to it.

**Example 1:**

**Input:** n = 5, edges = \[\[1,2\],\[2,3\],\[3,4\],\[4,2\],\[1,4\],\[2,5\]\]
**Output:** true
**Explanation:** The above diagram shows a valid way of adding an edge.
Every node in the resulting graph is connected to an even number of edges.

**Example 2:**

**Input:** n = 4, edges = \[\[1,2\],\[3,4\]\]
**Output:** true
**Explanation:** The above diagram shows a valid way of adding two edges.

**Example 3:**

**Input:** n = 4, edges = \[\[1,2\],\[1,3\],\[1,4\]\]
**Output:** false
**Explanation:** It is not possible to obtain a valid graph with adding at most 2 edges.

**Constraints:**

*   `3 <= n <= 105`
*   `2 <= edges.length <= 105`
*   `edges[i].length == 2`
*   `1 <= ai, bi <= n`
*   `ai != bi`
*   There are no repeated edges.