bowang0911/leetcode huggingface dataset:
Average Salary Excluding the Minimum and Maximum Salary

You are given an array of **unique** integers `salary` where `salary[i]` is the salary of the `ith` employee.

Return _the average salary of employees excluding the minimum and maximum salary_. Answers within `10-5` of the actual answer will be accepted.

**Example 1:**

**Input:** salary = \[4000,3000,1000,2000\]
**Output:** 2500.00000
**Explanation:** Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500

**Example 2:**

**Input:** salary = \[1000,2000,3000\]
**Output:** 2000.00000
**Explanation:** Minimum salary and maximum salary are 1000 and 3000 respectively.
Average salary excluding minimum and maximum salary is (2000) / 1 = 2000

**Constraints:**

*   `3 <= salary.length <= 100`
*   `1000 <= salary[i] <= 106`
*   All the integers of `salary` are **unique**.
The kth Factor of n

You are given two positive integers `n` and `k`. A factor of an integer `n` is defined as an integer `i` where `n % i == 0`.

Consider a list of all factors of `n` sorted in **ascending order**, return _the_ `kth` _factor_ in this list or return `-1` if `n` has less than `k` factors.

**Example 1:**

**Input:** n = 12, k = 3
**Output:** 3
**Explanation:** Factors list is \[1, 2, 3, 4, 6, 12\], the 3rd factor is 3.

**Example 2:**

**Input:** n = 7, k = 2
**Output:** 7
**Explanation:** Factors list is \[1, 7\], the 2nd factor is 7.

**Example 3:**

**Input:** n = 4, k = 4
**Output:** -1
**Explanation:** Factors list is \[1, 2, 4\], there is only 3 factors. We should return -1.

**Constraints:**

*   `1 <= k <= n <= 1000`

**Follow up:**

Could you solve this problem in less than O(n) complexity?
Longest Subarray of 1's After Deleting One Element

Given a binary array `nums`, you should delete one element from it.

Return _the size of the longest non-empty subarray containing only_ `1`_'s in the resulting array_. Return `0` if there is no such subarray.

**Example 1:**

**Input:** nums = \[1,1,0,1\]
**Output:** 3
**Explanation:** After deleting the number in position 2, \[1,1,1\] contains 3 numbers with value of 1's.

**Example 2:**

**Input:** nums = \[0,1,1,1,0,1,1,0,1\]
**Output:** 5
**Explanation:** After deleting the number in position 4, \[0,1,1,1,1,1,0,1\] longest subarray with value of 1's is \[1,1,1,1,1\].

**Example 3:**

**Input:** nums = \[1,1,1\]
**Output:** 2
**Explanation:** You must delete one element.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `nums[i]` is either `0` or `1`.
Parallel Courses II

You are given an integer `n`, which indicates that there are `n` courses labeled from `1` to `n`. You are also given an array `relations` where `relations[i] = [prevCoursei, nextCoursei]`, representing a prerequisite relationship between course `prevCoursei` and course `nextCoursei`: course `prevCoursei` has to be taken before course `nextCoursei`. Also, you are given the integer `k`.

In one semester, you can take **at most** `k` courses as long as you have taken all the prerequisites in the **previous** semesters for the courses you are taking.

Return _the **minimum** number of semesters needed to take all courses_. The testcases will be generated such that it is possible to take every course.

**Example 1:**

**Input:** n = 4, relations = \[\[2,1\],\[3,1\],\[1,4\]\], k = 2
**Output:** 3
**Explanation:** The figure above represents the given graph.
In the first semester, you can take courses 2 and 3.
In the second semester, you can take course 1.
In the third semester, you can take course 4.

**Example 2:**

**Input:** n = 5, relations = \[\[2,1\],\[3,1\],\[4,1\],\[1,5\]\], k = 2
**Output:** 4
**Explanation:** The figure above represents the given graph.
In the first semester, you can only take courses 2 and 3 since you cannot take more than two per semester.
In the second semester, you can take course 4.
In the third semester, you can take course 1.
In the fourth semester, you can take course 5.

**Constraints:**

*   `1 <= n <= 15`
*   `1 <= k <= n`
*   `0 <= relations.length <= n * (n-1) / 2`
*   `relations[i].length == 2`
*   `1 <= prevCoursei, nextCoursei <= n`
*   `prevCoursei != nextCoursei`
*   All the pairs `[prevCoursei, nextCoursei]` are **unique**.
*   The given graph is a directed acyclic graph.
Path Crossing

Given a string `path`, where `path[i] = 'N'`, `'S'`, `'E'` or `'W'`, each representing moving one unit north, south, east, or west, respectively. You start at the origin `(0, 0)` on a 2D plane and walk on the path specified by `path`.

Return `true` _if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited_. Return `false` otherwise.

**Example 1:**

**Input:** path =  "NES "
**Output:** false 
**Explanation:** Notice that the path doesn't cross any point more than once.

**Example 2:**

**Input:** path =  "NESWW "
**Output:** true
**Explanation:** Notice that the path visits the origin twice.

**Constraints:**

*   `1 <= path.length <= 104`
*   `path[i]` is either `'N'`, `'S'`, `'E'`, or `'W'`.
Number of Subsequences That Satisfy the Given Sum Condition

You are given an array of integers `nums` and an integer `target`.

Return _the number of **non-empty** subsequences of_ `nums` _such that the sum of the minimum and maximum element on it is less or equal to_ `target`. Since the answer may be too large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** nums = \[3,5,6,7\], target = 9
**Output:** 4
**Explanation:** There are 4 subsequences that satisfy the condition.
\[3\] -> Min value + max value <= target (3 + 3 <= 9)
\[3,5\] -> (3 + 5 <= 9)
\[3,5,6\] -> (3 + 6 <= 9)
\[3,6\] -> (3 + 6 <= 9)

**Example 2:**

**Input:** nums = \[3,3,6,8\], target = 10
**Output:** 6
**Explanation:** There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
\[3\] , \[3\] , \[3,3\], \[3,6\] , \[3,6\] , \[3,3,6\]

**Example 3:**

**Input:** nums = \[2,3,3,4,6,7\], target = 12
**Output:** 61
**Explanation:** There are 63 non-empty subsequences, two of them do not satisfy the condition (\[6,7\], \[7\]).
Number of valid subsequences (63 - 2 = 61).

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 106`
*   `1 <= target <= 106`
Max Value of Equation

You are given an array `points` containing the coordinates of points on a 2D plane, sorted by the x-values, where `points[i] = [xi, yi]` such that `xi < xj` for all `1 <= i < j <= points.length`. You are also given an integer `k`.

Return _the maximum value of the equation_ `yi + yj + |xi - xj|` where `|xi - xj| <= k` and `1 <= i < j <= points.length`.

It is guaranteed that there exists at least one pair of points that satisfy the constraint `|xi - xj| <= k`.

**Example 1:**

**Input:** points = \[\[1,3\],\[2,0\],\[5,10\],\[6,-10\]\], k = 1
**Output:** 4
**Explanation:** The first two points satisfy the condition |xi - xj| <= 1 and if we calculate the equation we get 3 + 0 + |1 - 2| = 4. Third and fourth points also satisfy the condition and give a value of 10 + -10 + |5 - 6| = 1.
No other pairs satisfy the condition, so we return the max of 4 and 1.

**Example 2:**

**Input:** points = \[\[0,0\],\[3,0\],\[9,2\]\], k = 3
**Output:** 3
**Explanation:** Only the first two points have an absolute difference of 3 or less in the x-values, and give the value of 0 + 0 + |0 - 3| = 3.

**Constraints:**

*   `2 <= points.length <= 105`
*   `points[i].length == 2`
*   `-108 <= xi, yi <= 108`
*   `0 <= k <= 2 * 108`
*   `xi < xj` for all `1 <= i < j <= points.length`
*   `xi` form a strictly increasing sequence.
Can Make Arithmetic Progression From Sequence

A sequence of numbers is called an **arithmetic progression** if the difference between any two consecutive elements is the same.

Given an array of numbers `arr`, return `true` _if the array can be rearranged to form an **arithmetic progression**. Otherwise, return_ `false`.

**Example 1:**

**Input:** arr = \[3,5,1\]
**Output:** true
**Explanation:** We can reorder the elements as \[1,3,5\] or \[5,3,1\] with differences 2 and -2 respectively, between each consecutive elements.

**Example 2:**

**Input:** arr = \[1,2,4\]
**Output:** false
**Explanation:** There is no way to reorder the elements to obtain an arithmetic progression.

**Constraints:**

*   `2 <= arr.length <= 1000`
*   `-106 <= arr[i] <= 106`
Last Moment Before All Ants Fall Out of a Plank

We have a wooden plank of the length `n` **units**. Some ants are walking on the plank, each ant moves with a speed of **1 unit per second**. Some of the ants move to the **left**, the other move to the **right**.

When two ants moving in two **different** directions meet at some point, they change their directions and continue moving again. Assume changing directions does not take any additional time.

When an ant reaches **one end** of the plank at a time `t`, it falls out of the plank immediately.

Given an integer `n` and two integer arrays `left` and `right`, the positions of the ants moving to the left and the right, return _the moment when the last ant(s) fall out of the plank_.

**Example 1:**

**Input:** n = 4, left = \[4,3\], right = \[0,1\]
**Output:** 4
**Explanation:** In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

**Example 2:**

**Input:** n = 7, left = \[\], right = \[0,1,2,3,4,5,6,7\]
**Output:** 7
**Explanation:** All ants are going to the right, the ant at index 0 needs 7 seconds to fall.

**Example 3:**

**Input:** n = 7, left = \[0,1,2,3,4,5,6,7\], right = \[\]
**Output:** 7
**Explanation:** All ants are going to the left, the ant at index 7 needs 7 seconds to fall.

**Constraints:**

*   `1 <= n <= 104`
*   `0 <= left.length <= n + 1`
*   `0 <= left[i] <= n`
*   `0 <= right.length <= n + 1`
*   `0 <= right[i] <= n`
*   `1 <= left.length + right.length <= n + 1`
*   All values of `left` and `right` are unique, and each value can appear **only in one** of the two arrays.
Count Submatrices With All Ones

Given an `m x n` binary matrix `mat`, _return the number of **submatrices** that have all ones_.

**Example 1:**

**Input:** mat = \[\[1,0,1\],\[1,1,0\],\[1,1,0\]\]
**Output:** 13
**Explanation:** 
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2. 
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

**Example 2:**

**Input:** mat = \[\[0,1,1,0\],\[0,1,1,1\],\[1,1,1,0\]\]
**Output:** 24
**Explanation:** 
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3. 
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2. 
There are 2 rectangles of side 3x1. 
There is 1 rectangle of side 3x2. 
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.

**Constraints:**

*   `1 <= m, n <= 150`
*   `mat[i][j]` is either `0` or `1`.
Minimum Possible Integer After at Most K Adjacent Swaps On Digits

You are given a string `num` representing **the digits** of a very large integer and an integer `k`. You are allowed to swap any two adjacent digits of the integer **at most** `k` times.

Return _the minimum integer you can obtain also as a string_.

**Example 1:**

**Input:** num =  "4321 ", k = 4
**Output:**  "1342 "
**Explanation:** The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

**Example 2:**

**Input:** num =  "100 ", k = 1
**Output:**  "010 "
**Explanation:** It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

**Example 3:**

**Input:** num =  "36789 ", k = 1000
**Output:**  "36789 "
**Explanation:** We can keep the number without any swaps.

**Constraints:**

*   `1 <= num.length <= 3 * 104`
*   `num` consists of only **digits** and does not contain **leading zeros**.
*   `1 <= k <= 109`
Find Root of N-Ary Tree

You are given all the nodes of an **[N-ary tree](https://leetcode.com/explore/learn/card/n-ary-tree/)** as an array of `Node` objects, where each node has a **unique value**.

Return _the **root** of the N-ary tree_.

**Custom testing:**

An N-ary tree can be serialized as represented in its level order traversal where each group of children is separated by the `null` value (see examples).

For example, the above tree is serialized as `[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]`.

The testing will be done in the following way:

1.  The **input data** should be provided as a serialization of the tree.
2.  The driver code will construct the tree from the serialized input data and put each `Node` object into an array **in an arbitrary order**.
3.  The driver code will pass the array to `findRoot`, and your function should find and return the root `Node` object in the array.
4.  The driver code will take the returned `Node` object and serialize it. If the serialized value and the input data are the **same**, the test **passes**.

**Example 1:**

**Input:** tree = \[1,null,3,2,4,null,5,6\]
**Output:** \[1,null,3,2,4,null,5,6\]
**Explanation:** The tree from the input data is shown above.
The driver code creates the tree and gives findRoot the Node objects in an arbitrary order.
For example, the passed array could be \[Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)\] or \[Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)\].
The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data.
The input data and serialized Node(1) are the same, so the test passes.

**Example 2:**

**Input:** tree = \[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14\]
**Output:** \[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14\]

**Constraints:**

*   The total number of nodes is between `[1, 5 * 104]`.
*   Each node has a **unique** value.

**Follow up:**

*   Could you solve this problem in constant space complexity with a linear time algorithm?
Reformat Date

Given a `date` string in the form `Day Month Year`, where:

*   `Day` is in the set `{ "1st ", "2nd ", "3rd ", "4th ", ..., "30th ", "31st "}`.
*   `Month` is in the set `{ "Jan ", "Feb ", "Mar ", "Apr ", "May ", "Jun ", "Jul ", "Aug ", "Sep ", "Oct ", "Nov ", "Dec "}`.
*   `Year` is in the range `[1900, 2100]`.

Convert the date string to the format `YYYY-MM-DD`, where:

*   `YYYY` denotes the 4 digit year.
*   `MM` denotes the 2 digit month.
*   `DD` denotes the 2 digit day.

**Example 1:**

**Input:** date =  "20th Oct 2052 "
**Output:**  "2052-10-20 "

**Example 2:**

**Input:** date =  "6th Jun 1933 "
**Output:**  "1933-06-06 "

**Example 3:**

**Input:** date =  "26th May 1960 "
**Output:**  "1960-05-26 "

**Constraints:**

*   The given dates are guaranteed to be valid, so no error handling is necessary.
Range Sum of Sorted Subarray Sums

You are given the array `nums` consisting of `n` positive integers. You computed the sum of all non-empty continuous subarrays from the array and then sorted them in non-decreasing order, creating a new array of `n * (n + 1) / 2` numbers.

_Return the sum of the numbers from index_ `left` _to index_ `right` (**indexed from 1**)_, inclusive, in the new array._ Since the answer can be a huge number return it modulo `109 + 7`.

**Example 1:**

**Input:** nums = \[1,2,3,4\], n = 4, left = 1, right = 5
**Output:** 13 
**Explanation:** All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array \[1, 2, 3, 3, 4, 5, 6, 7, 9, 10\]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13. 

**Example 2:**

**Input:** nums = \[1,2,3,4\], n = 4, left = 3, right = 4
**Output:** 6
**Explanation:** The given array is the same as example 1. We have the new array \[1, 2, 3, 3, 4, 5, 6, 7, 9, 10\]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.

**Example 3:**

**Input:** nums = \[1,2,3,4\], n = 4, left = 1, right = 10
**Output:** 50

**Constraints:**

*   `n == nums.length`
*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= 100`
*   `1 <= left <= right <= n * (n + 1) / 2`
Minimum Difference Between Largest and Smallest Value in Three Moves

You are given an integer array `nums`.

In one move, you can choose one element of `nums` and change it to **any value**.

Return _the minimum difference between the largest and smallest value of `nums` **after performing at most three moves**_.

**Example 1:**

**Input:** nums = \[5,3,2,4\]
**Output:** 0
**Explanation:** We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes \[5,3,3,4\].
In the second move, change 4 to 3. nums becomes \[5,3,3,3\].
In the third move, change 5 to 3. nums becomes \[3,3,3,3\].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

**Example 2:**

**Input:** nums = \[1,5,0,10,14\]
**Output:** 1
**Explanation:** We can make at most 3 moves.
In the first move, change 5 to 0. nums becomes \[1,0,0,10,14\].
In the second move, change 10 to 0. nums becomes \[1,0,0,0,14\].
In the third move, change 14 to 1. nums becomes \[1,0,0,0,1\].
After performing 3 moves, the difference between the minimum and maximum is 1 - 0 = 0.
It can be shown that there is no way to make the difference 0 in 3 moves.

**Example 3:**

**Input:** nums = \[3,100,20\]
**Output:** 0
**Explanation:** We can make at most 3 moves.
In the first move, change 100 to 7. nums becomes \[4,7,20\].
In the second move, change 20 to 7. nums becomes \[4,7,7\].
In the third move, change 4 to 3. nums becomes \[7,7,7\].
After performing 3 moves, the difference between the minimum and maximum is 7 - 7 = 0.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-109 <= nums[i] <= 109`
Stone Game IV

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are `n` stones in a pile. On each player's turn, that player makes a _move_ consisting of removing **any** non-zero **square number** of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer `n`, return `true` if and only if Alice wins the game otherwise return `false`, assuming both players play optimally.

**Example 1:**

**Input:** n = 1
**Output:** true
**Explanation:** Alice can remove 1 stone winning the game because Bob doesn't have any moves.

**Example 2:**

**Input:** n = 2
**Output:** false
**Explanation:** Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

**Example 3:**

**Input:** n = 4
**Output:** true
**Explanation:** n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

**Constraints:**

*   `1 <= n <= 105`
Number of Good Pairs

Given an array of integers `nums`, return _the number of **good pairs**_.

A pair `(i, j)` is called _good_ if `nums[i] == nums[j]` and `i` < `j`.

**Example 1:**

**Input:** nums = \[1,2,3,1,1,3\]
**Output:** 4
**Explanation:** There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

**Example 2:**

**Input:** nums = \[1,1,1,1\]
**Output:** 6
**Explanation:** Each pair in the array are _good_.

**Example 3:**

**Input:** nums = \[1,2,3\]
**Output:** 0

**Constraints:**

*   `1 <= nums.length <= 100`
*   `1 <= nums[i] <= 100`
Number of Substrings With Only 1s

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 `109 + 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 <= 105`
*   `s[i]` is either `'0'` or `'1'`.
Path with Maximum Probability

You are given an undirected weighted graph of `n` nodes (0-indexed), represented by an edge list where `edges[i] = [a, b]` is an undirected edge connecting the nodes `a` and `b` with a probability of success of traversing that edge `succProb[i]`.

Given two nodes `start` and `end`, find the path with the maximum probability of success to go from `start` to `end` and return its success probability.

If there is no path from `start` to `end`, **return 0**. Your answer will be accepted if it differs from the correct answer by at most **1e-5**.

**Example 1:**

**Input:** n = 3, edges = \[\[0,1\],\[1,2\],\[0,2\]\], succProb = \[0.5,0.5,0.2\], start = 0, end = 2
**Output:** 0.25000
**Explanation:** There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 \* 0.5 = 0.25.

**Example 2:**

**Input:** n = 3, edges = \[\[0,1\],\[1,2\],\[0,2\]\], succProb = \[0.5,0.5,0.3\], start = 0, end = 2
**Output:** 0.30000

**Example 3:**

**Input:** n = 3, edges = \[\[0,1\]\], succProb = \[0.5\], start = 0, end = 2
**Output:** 0.00000
**Explanation:** There is no path between 0 and 2.

**Constraints:**

*   `2 <= n <= 10^4`
*   `0 <= start, end < n`
*   `start != end`
*   `0 <= a, b < n`
*   `a != b`
*   `0 <= succProb.length == edges.length <= 2*10^4`
*   `0 <= succProb[i] <= 1`
*   There is at most one edge between every two nodes.
Best Position for a Service Centre

A delivery company wants to build a new service center in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new center in a position such that **the sum of the euclidean distances to all customers is minimum**.

Given an array `positions` where `positions[i] = [xi, yi]` is the position of the `ith` customer on the map, return _the minimum sum of the euclidean distances_ to all customers.

In other words, you need to choose the position of the service center `[xcentre, ycentre]` such that the following formula is minimized:

Answers within `10-5` of the actual value will be accepted.

**Example 1:**

**Input:** positions = \[\[0,1\],\[1,0\],\[1,2\],\[2,1\]\]
**Output:** 4.00000
**Explanation:** As shown, you can see that choosing \[xcentre, ycentre\] = \[1, 1\] will make the distance to each customer = 1, the sum of all distances is 4 which is the minimum possible we can achieve.

**Example 2:**

**Input:** positions = \[\[1,1\],\[3,3\]\]
**Output:** 2.82843
**Explanation:** The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843

**Constraints:**

*   `1 <= positions.length <= 50`
*   `positions[i].length == 2`
*   `0 <= xi, yi <= 100`

F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) for n >= 2.