bowang0911/leetcode huggingface dataset:
Sort Array by Moving Items to Empty Space

You are given an integer array `nums` of size `n` containing **each** element from `0` to `n - 1` (**inclusive**). Each of the elements from `1` to `n - 1` represents an item, and the element `0` represents an empty space.

In one operation, you can move **any** item to the empty space. `nums` is considered to be sorted if the numbers of all the items are in **ascending** order and the empty space is either at the beginning or at the end of the array.

For example, if `n = 4`, `nums` is sorted if:

*   `nums = [0,1,2,3]` or
*   `nums = [1,2,3,0]`

...and considered to be unsorted otherwise.

Return _the **minimum** number of operations needed to sort_ `nums`.

**Example 1:**

**Input:** nums = \[4,2,0,3,1\]
**Output:** 3
**Explanation:**
- Move item 2 to the empty space. Now, nums = \[4,0,2,3,1\].
- Move item 1 to the empty space. Now, nums = \[4,1,2,3,0\].
- Move item 4 to the empty space. Now, nums = \[0,1,2,3,4\].
It can be proven that 3 is the minimum number of operations needed.

**Example 2:**

**Input:** nums = \[1,2,3,4,0\]
**Output:** 0
**Explanation:** nums is already sorted so return 0.

**Example 3:**

**Input:** nums = \[1,0,2,4,3\]
**Output:** 2
**Explanation:**
- Move item 2 to the empty space. Now, nums = \[1,2,0,4,3\].
- Move item 3 to the empty space. Now, nums = \[1,2,3,4,0\].
It can be proven that 2 is the minimum number of operations needed.

**Constraints:**

*   `n == nums.length`
*   `2 <= n <= 105`
*   `0 <= nums[i] < n`
*   All the values of `nums` are **unique**.
Apply Operations to an Array

You are given a **0-indexed** array `nums` of size `n` consisting of **non-negative** integers.

You need to apply `n - 1` operations to this array where, in the `ith` operation (**0-indexed**), you will apply the following on the `ith` element of `nums`:

*   If `nums[i] == nums[i + 1]`, then multiply `nums[i]` by `2` and set `nums[i + 1]` to `0`. Otherwise, you skip this operation.

After performing **all** the operations, **shift** all the `0`'s to the **end** of the array.

*   For example, the array `[1,0,2,0,0,1]` after shifting all its `0`'s to the end, is `[1,2,1,0,0,0]`.

Return _the resulting array_.

**Note** that the operations are applied **sequentially**, not all at once.

**Example 1:**

**Input:** nums = \[1,2,2,1,1,0\]
**Output:** \[1,4,2,0,0,0\]
**Explanation:** We do the following operations:
- i = 0: nums\[0\] and nums\[1\] are not equal, so we skip this operation.
- i = 1: nums\[1\] and nums\[2\] are equal, we multiply nums\[1\] by 2 and change nums\[2\] to 0. The array becomes \[1,**4**,**0**,1,1,0\].
- i = 2: nums\[2\] and nums\[3\] are not equal, so we skip this operation.
- i = 3: nums\[3\] and nums\[4\] are equal, we multiply nums\[3\] by 2 and change nums\[4\] to 0. The array becomes \[1,4,0,**2**,**0**,0\].
- i = 4: nums\[4\] and nums\[5\] are equal, we multiply nums\[4\] by 2 and change nums\[5\] to 0. The array becomes \[1,4,0,2,**0**,**0**\].
After that, we shift the 0's to the end, which gives the array \[1,4,2,0,0,0\].

**Example 2:**

**Input:** nums = \[0,1\]
**Output:** \[1,0\]
**Explanation:** No operation can be applied, we just shift the 0 to the end.

**Constraints:**

*   `2 <= nums.length <= 2000`
*   `0 <= nums[i] <= 1000`
Maximum Sum of Distinct Subarrays With Length K

You are given an integer array `nums` and an integer `k`. Find the maximum subarray sum of all the subarrays of `nums` that meet the following conditions:

*   The length of the subarray is `k`, and
*   All the elements of the subarray are **distinct**.

Return _the maximum subarray sum of all the subarrays that meet the conditions__._ If no subarray meets the conditions, return `0`.

_A **subarray** is a contiguous non-empty sequence of elements within an array._

**Example 1:**

**Input:** nums = \[1,5,4,2,9,9,9\], k = 3
**Output:** 15
**Explanation:** The subarrays of nums with length 3 are:
- \[1,5,4\] which meets the requirements and has a sum of 10.
- \[5,4,2\] which meets the requirements and has a sum of 11.
- \[4,2,9\] which meets the requirements and has a sum of 15.
- \[2,9,9\] which does not meet the requirements because the element 9 is repeated.
- \[9,9,9\] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

**Example 2:**

**Input:** nums = \[4,4,4\], k = 3
**Output:** 0
**Explanation:** The subarrays of nums with length 3 are:
- \[4,4,4\] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.

**Constraints:**

*   `1 <= k <= nums.length <= 105`
*   `1 <= nums[i] <= 105`
Total Cost to Hire K Workers

You are given a **0-indexed** integer array `costs` where `costs[i]` is the cost of hiring the `ith` worker.

You are also given two integers `k` and `candidates`. We want to hire exactly `k` workers according to the following rules:

*   You will run `k` sessions and hire exactly one worker in each session.
*   In each hiring session, choose the worker with the lowest cost from either the first `candidates` workers or the last `candidates` workers. Break the tie by the smallest index.
    *   For example, if `costs = [3,2,7,7,1,2]` and `candidates = 2`, then in the first hiring session, we will choose the `4th` worker because they have the lowest cost `[3,2,7,7,**1**,2]`.
    *   In the second hiring session, we will choose `1st` worker because they have the same lowest cost as `4th` worker but they have the smallest index `[3,**2**,7,7,2]`. Please note that the indexing may be changed in the process.
*   If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
*   A worker can only be chosen once.

Return _the total cost to hire exactly_ `k` _workers._

**Example 1:**

**Input:** costs = \[17,12,10,2,7,2,11,20,8\], k = 3, candidates = 4
**Output:** 11
**Explanation:** We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from \[17,12,10,2,7,2,11,20,8\]. The lowest cost is 2, and we break the tie by the smallest index, which is 3. The total cost = 0 + 2 = 2.
- In the second hiring round we choose the worker from \[17,12,10,7,2,11,20,8\]. The lowest cost is 2 (index 4). The total cost = 2 + 2 = 4.
- In the third hiring round we choose the worker from \[17,12,10,7,11,20,8\]. The lowest cost is 7 (index 3). The total cost = 4 + 7 = 11. Notice that the worker with index 3 was common in the first and last four workers.
The total hiring cost is 11.

**Example 2:**

**Input:** costs = \[1,2,4,1\], k = 3, candidates = 3
**Output:** 4
**Explanation:** We hire 3 workers in total. The total cost is initially 0.
- In the first hiring round we choose the worker from \[1,2,4,1\]. The lowest cost is 1, and we break the tie by the smallest index, which is 0. The total cost = 0 + 1 = 1. Notice that workers with index 1 and 2 are common in the first and last 3 workers.
- In the second hiring round we choose the worker from \[2,4,1\]. The lowest cost is 1 (index 2). The total cost = 1 + 1 = 2.
- In the third hiring round there are less than three candidates. We choose the worker from the remaining workers \[2,4\]. The lowest cost is 2 (index 0). The total cost = 2 + 2 = 4.
The total hiring cost is 4.

**Constraints:**

*   `1 <= costs.length <= 105`
*   `1 <= costs[i] <= 105`
*   `1 <= k, candidates <= costs.length`
Minimum Total Distance Traveled

There are some robots and factories on the X-axis. You are given an integer array `robot` where `robot[i]` is the position of the `ith` robot. You are also given a 2D integer array `factory` where `factory[j] = [positionj, limitj]` indicates that `positionj` is the position of the `jth` factory and that the `jth` factory can repair at most `limitj` robots.

The positions of each robot are **unique**. The positions of each factory are also **unique**. Note that a robot can be **in the same position** as a factory initially.

All the robots are initially broken; they keep moving in one direction. The direction could be the negative or the positive direction of the X-axis. When a robot reaches a factory that did not reach its limit, the factory repairs the robot, and it stops moving.

**At any moment**, you can set the initial direction of moving for **some** robot. Your target is to minimize the total distance traveled by all the robots.

Return _the minimum total distance traveled by all the robots_. The test cases are generated such that all the robots can be repaired.

**Note that**

*   All robots move at the same speed.
*   If two robots move in the same direction, they will never collide.
*   If two robots move in opposite directions and they meet at some point, they do not collide. They cross each other.
*   If a robot passes by a factory that reached its limits, it crosses it as if it does not exist.
*   If the robot moved from a position `x` to a position `y`, the distance it moved is `|y - x|`.

**Example 1:**

**Input:** robot = \[0,4,6\], factory = \[\[2,2\],\[6,2\]\]
**Output:** 4
**Explanation:** As shown in the figure:
- The first robot at position 0 moves in the positive direction. It will be repaired at the first factory.
- The second robot at position 4 moves in the negative direction. It will be repaired at the first factory.
- The third robot at position 6 will be repaired at the second factory. It does not need to move.
The limit of the first factory is 2, and it fixed 2 robots.
The limit of the second factory is 2, and it fixed 1 robot.
The total distance is |2 - 0| + |2 - 4| + |6 - 6| = 4. It can be shown that we cannot achieve a better total distance than 4.

**Example 2:**

**Input:** robot = \[1,-1\], factory = \[\[-2,1\],\[2,1\]\]
**Output:** 2
**Explanation:** As shown in the figure:
- The first robot at position 1 moves in the positive direction. It will be repaired at the second factory.
- The second robot at position -1 moves in the negative direction. It will be repaired at the first factory.
The limit of the first factory is 1, and it fixed 1 robot.
The limit of the second factory is 1, and it fixed 1 robot.
The total distance is |2 - 1| + |(-2) - (-1)| = 2. It can be shown that we cannot achieve a better total distance than 2.

**Constraints:**

*   `1 <= robot.length, factory.length <= 100`
*   `factory[j].length == 2`
*   `-109 <= robot[i], positionj <= 109`
*   `0 <= limitj <= robot.length`
*   The input will be generated such that it is always possible to repair every robot.
Minimum Subarrays in a Valid Split

You are given an integer array `nums`.

Splitting of an integer array `nums` into **subarrays** is **valid** if:

*   the _greatest common divisor_ of the first and last elements of each subarray is **greater** than `1`, and
*   each element of `nums` belongs to exactly one subarray.

Return _the **minimum** number of subarrays in a **valid** subarray splitting of_ `nums`. If a valid subarray splitting is not possible, return `-1`.

**Note** that:

*   The **greatest common divisor** of two numbers is the largest positive integer that evenly divides both numbers.
*   A **subarray** is a contiguous non-empty part of an array.

**Example 1:**

**Input:** nums = \[2,6,3,4,3\]
**Output:** 2
**Explanation:** We can create a valid split in the following way: \[2,6\] | \[3,4,3\].
- The starting element of the 1st subarray is 2 and the ending is 6. Their greatest common divisor is 2, which is greater than 1.
- The starting element of the 2nd subarray is 3 and the ending is 3. Their greatest common divisor is 3, which is greater than 1.
It can be proved that 2 is the minimum number of subarrays that we can obtain in a valid split.

**Example 2:**

**Input:** nums = \[3,5\]
**Output:** 2
**Explanation:** We can create a valid split in the following way: \[3\] | \[5\].
- The starting element of the 1st subarray is 3 and the ending is 3. Their greatest common divisor is 3, which is greater than 1.
- The starting element of the 2nd subarray is 5 and the ending is 5. Their greatest common divisor is 5, which is greater than 1.
It can be proved that 2 is the minimum number of subarrays that we can obtain in a valid split.

**Example 3:**

**Input:** nums = \[1,2,1\]
**Output:** -1
**Explanation:** It is impossible to create valid split.

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= 105`
Number of Distinct Averages

You are given a **0-indexed** integer array `nums` of **even** length.

As long as `nums` is **not** empty, you must repetitively:

*   Find the minimum number in `nums` and remove it.
*   Find the maximum number in `nums` and remove it.
*   Calculate the average of the two removed numbers.

The **average** of two numbers `a` and `b` is `(a + b) / 2`.

*   For example, the average of `2` and `3` is `(2 + 3) / 2 = 2.5`.

Return _the number of **distinct** averages calculated using the above process_.

**Note** that when there is a tie for a minimum or maximum number, any can be removed.

**Example 1:**

**Input:** nums = \[4,1,4,0,3,5\]
**Output:** 2
**Explanation:**
1. Remove 0 and 5, and the average is (0 + 5) / 2 = 2.5. Now, nums = \[4,1,4,3\].
2. Remove 1 and 4. The average is (1 + 4) / 2 = 2.5, and nums = \[4,3\].
3. Remove 3 and 4, and the average is (3 + 4) / 2 = 3.5.
Since there are 2 distinct numbers among 2.5, 2.5, and 3.5, we return 2.

**Example 2:**

**Input:** nums = \[1,100\]
**Output:** 1
**Explanation:**
There is only one average to be calculated after removing 1 and 100, so we return 1.

**Constraints:**

*   `2 <= nums.length <= 100`
*   `nums.length` is even.
*   `0 <= nums[i] <= 100`
Count Ways To Build Good Strings

Given the integers `zero`, `one`, `low`, and `high`, we can construct a string by starting with an empty string, and then at each step perform either of the following:

*   Append the character `'0'` `zero` times.
*   Append the character `'1'` `one` times.

This can be performed any number of times.

A **good** string is a string constructed by the above process having a **length** between `low` and `high` (**inclusive**).

Return _the number of **different** good strings that can be constructed satisfying these properties._ Since the answer can be large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** low = 3, high = 3, zero = 1, one = 1
**Output:** 8
**Explanation:** 
One possible valid good string is  "011 ". 
It can be constructed as follows:  " " ->  "0 " ->  "01 " ->  "011 ". 
All binary strings from  "000 " to  "111 " are good strings in this example.

**Example 2:**

**Input:** low = 2, high = 3, zero = 1, one = 2
**Output:** 5
**Explanation:** The good strings are  "00 ",  "11 ",  "000 ",  "110 ", and  "011 ".

**Constraints:**

*   `1 <= low <= high <= 105`
*   `1 <= zero, one <= low`
Most Profitable Path in a Tree

There is an undirected tree with `n` nodes labeled from `0` to `n - 1`, rooted at node `0`. You are given a 2D integer array `edges` of length `n - 1` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the tree.

At every node `i`, there is a gate. You are also given an array of even integers `amount`, where `amount[i]` represents:

*   the price needed to open the gate at node `i`, if `amount[i]` is negative, or,
*   the cash reward obtained on opening the gate at node `i`, otherwise.

The game goes on as follows:

*   Initially, Alice is at node `0` and Bob is at node `bob`.
*   At every second, Alice and Bob **each** move to an adjacent node. Alice moves towards some **leaf node**, while Bob moves towards node `0`.
*   For **every** node along their path, Alice and Bob either spend money to open the gate at that node, or accept the reward. Note that:
    *   If the gate is **already open**, no price will be required, nor will there be any cash reward.
    *   If Alice and Bob reach the node **simultaneously**, they share the price/reward for opening the gate there. In other words, if the price to open the gate is `c`, then both Alice and Bob pay `c / 2` each. Similarly, if the reward at the gate is `c`, both of them receive `c / 2` each.
*   If Alice reaches a leaf node, she stops moving. Similarly, if Bob reaches node `0`, he stops moving. Note that these events are **independent** of each other.

Return _the **maximum** net income Alice can have if she travels towards the optimal leaf node._

**Example 1:**

**Input:** edges = \[\[0,1\],\[1,2\],\[1,3\],\[3,4\]\], bob = 3, amount = \[-2,4,2,-4,6\]
**Output:** 6
**Explanation:** 
The above diagram represents the given tree. The game goes as follows:
- Alice is initially on node 0, Bob on node 3. They open the gates of their respective nodes.
  Alice's net income is now -2.
- Both Alice and Bob move to node 1. 
  Since they reach here simultaneously, they open the gate together and share the reward.
  Alice's net income becomes -2 + (4 / 2) = 0.
- Alice moves on to node 3. Since Bob already opened its gate, Alice's income remains unchanged.
  Bob moves on to node 0, and stops moving.
- Alice moves on to node 4 and opens the gate there. Her net income becomes 0 + 6 = 6.
Now, neither Alice nor Bob can make any further moves, and the game ends.
It is not possible for Alice to get a higher net income.

**Example 2:**

**Input:** edges = \[\[0,1\]\], bob = 1, amount = \[-7280,2350\]
**Output:** -7280
**Explanation:** 
Alice follows the path 0->1 whereas Bob follows the path 1->0.
Thus, Alice opens the gate at node 0 only. Hence, her net income is -7280. 

**Constraints:**

*   `2 <= n <= 105`
*   `edges.length == n - 1`
*   `edges[i].length == 2`
*   `0 <= ai, bi < n`
*   `ai != bi`
*   `edges` represents a valid tree.
*   `1 <= bob < n`
*   `amount.length == n`
*   `amount[i]` is an **even** integer in the range `[-104, 104]`.
Split Message Based on Limit

You are given a string, `message`, and a positive integer, `limit`.

You must **split** `message` into one or more **parts** based on `limit`. Each resulting part should have the suffix `" "`, where `"b "` is to be **replaced** with the total number of parts and `"a "` is to be **replaced** with the index of the part, starting from `1` and going up to `b`. Additionally, the length of each resulting part (including its suffix) should be **equal** to `limit`, except for the last part whose length can be **at most** `limit`.

The resulting parts should be formed such that when their suffixes are removed and they are all concatenated **in order**, they should be equal to `message`. Also, the result should contain as few parts as possible.

Return _the parts_ `message` _would be split into as an array of strings_. If it is impossible to split `message` as required, return _an empty array_.

**Example 1:**

**Input:** message =  "this is really a very awesome message ", limit = 9
**Output:** \[ "thi<1/14> ", "s i<2/14> ", "s r<3/14> ", "eal<4/14> ", "ly <5/14> ", "a v<6/14> ", "ery<7/14> ", " aw<8/14> ", "eso<9/14> ", "me<10/14> ", " m<11/14> ", "es<12/14> ", "sa<13/14> ", "ge<14/14> "\]
**Explanation:**
The first 9 parts take 3 characters each from the beginning of message.
The next 5 parts take 2 characters each to finish splitting message. 
In this example, each part, including the last, has length 9. 
It can be shown it is not possible to split message into less than 14 parts.

**Example 2:**

**Input:** message =  "short message ", limit = 15
**Output:** \[ "short mess<1/2> ", "age<2/2> "\]
**Explanation:**
Under the given constraints, the string can be split into two parts: 
- The first part comprises of the first 10 characters, and has a length 15.
- The next part comprises of the last 3 characters, and has a length 8.

**Constraints:**

*   `1 <= message.length <= 104`
*   `message` consists only of lowercase English letters and `' '`.
*   `1 <= limit <= 104`
Convert the Temperature

You are given a non-negative floating point number rounded to two decimal places `celsius`, that denotes the **temperature in Celsius**.

You should convert Celsius into **Kelvin** and **Fahrenheit** and return it as an array `ans = [kelvin, fahrenheit]`.

Return _the array `ans`._ Answers within `10-5` of the actual answer will be accepted.

**Note that:**

*   `Kelvin = Celsius + 273.15`
*   `Fahrenheit = Celsius * 1.80 + 32.00`

**Example 1:**

**Input:** celsius = 36.50
**Output:** \[309.65000,97.70000\]
**Explanation:** Temperature at 36.50 Celsius converted in Kelvin is 309.65 and converted in Fahrenheit is 97.70.

**Example 2:**

**Input:** celsius = 122.11
**Output:** \[395.26000,251.79800\]
**Explanation:** Temperature at 122.11 Celsius converted in Kelvin is 395.26 and converted in Fahrenheit is 251.798.

**Constraints:**

*   `0 <= celsius <= 1000`
Number of Subarrays With LCM Equal to K

Given an integer array `nums` and an integer `k`, return _the number of **subarrays** of_ `nums` _where the least common multiple of the subarray's elements is_ `k`.

A **subarray** is a contiguous non-empty sequence of elements within an array.

The **least common multiple of an array** is the smallest positive integer that is divisible by all the array elements.

**Example 1:**

**Input:** nums = \[3,6,2,7,1\], k = 6
**Output:** 4
**Explanation:** The subarrays of nums where 6 is the least common multiple of all the subarray's elements are:
- \[**3**,**6**,2,7,1\]
- \[**3**,**6**,**2**,7,1\]
- \[3,**6**,2,7,1\]
- \[3,**6**,**2**,7,1\]

**Example 2:**

**Input:** nums = \[3\], k = 2
**Output:** 0
**Explanation:** There are no subarrays of nums where 2 is the least common multiple of all the subarray's elements.

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i], k <= 1000`
Minimum Number of Operations to Sort a Binary Tree by Level

You are given the `root` of a binary tree with **unique values**.

In one operation, you can choose any two nodes **at the same level** and swap their values.

Return _the minimum number of operations needed to make the values at each level sorted in a **strictly increasing order**_.

The **level** of a node is the number of edges along the path between it and the root node_._

**Example 1:**

**Input:** root = \[1,4,3,7,6,8,5,null,null,null,null,9,null,10\]
**Output:** 3
**Explanation:**
- Swap 4 and 3. The 2nd level becomes \[3,4\].
- Swap 7 and 5. The 3rd level becomes \[5,6,8,7\].
- Swap 8 and 7. The 3rd level becomes \[5,6,7,8\].
We used 3 operations so return 3.
It can be proven that 3 is the minimum number of operations needed.

**Example 2:**

**Input:** root = \[1,3,2,7,6,5,4\]
**Output:** 3
**Explanation:**
- Swap 3 and 2. The 2nd level becomes \[2,3\].
- Swap 7 and 4. The 3rd level becomes \[4,6,5,7\].
- Swap 6 and 5. The 3rd level becomes \[4,5,6,7\].
We used 3 operations so return 3.
It can be proven that 3 is the minimum number of operations needed.

**Example 3:**

**Input:** root = \[1,2,3,4,5,6\]
**Output:** 0
**Explanation:** Each level is already sorted in increasing order so return 0.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 105]`.
*   `1 <= Node.val <= 105`
*   All the values of the tree are **unique**.
Maximum Number of Non-overlapping Palindrome Substrings

You are given a string `s` and a **positive** integer `k`.

Select a set of **non-overlapping** substrings from the string `s` that satisfy the following conditions:

*   The **length** of each substring is **at least** `k`.
*   Each substring is a **palindrome**.

Return _the **maximum** number of substrings in an optimal selection_.

A **substring** is a contiguous sequence of characters within a string.

**Example 1:**

**Input:** s =  "abaccdbbd ", k = 3
**Output:** 2
**Explanation:** We can select the substrings underlined in s =  "**aba**cc**dbbd** ". Both  "aba " and  "dbbd " are palindromes and have a length of at least k = 3.
It can be shown that we cannot find a selection with more than two valid substrings.

**Example 2:**

**Input:** s =  "adbcda ", k = 2
**Output:** 0
**Explanation:** There is no palindrome substring of length at least 2 in the string.

**Constraints:**

*   `1 <= k <= s.length <= 2000`
*   `s` consists of lowercase English letters.