bowang0911/leetcode huggingface dataset:
Max Increase to Keep City Skyline

There is a city composed of `n x n` blocks, where each block contains a single building shaped like a vertical square prism. You are given a **0-indexed** `n x n` integer matrix `grid` where `grid[r][c]` represents the **height** of the building located in the block at row `r` and column `c`.

A city's **skyline** is the outer contour formed by all the building when viewing the side of the city from a distance. The **skyline** from each cardinal direction north, east, south, and west may be different.

We are allowed to increase the height of **any number of buildings by any amount** (the amount can be different per building). The height of a `0`\-height building can also be increased. However, increasing the height of a building should **not** affect the city's **skyline** from any cardinal direction.

Return _the **maximum total sum** that the height of the buildings can be increased by **without** changing the city's **skyline** from any cardinal direction_.

**Example 1:**

**Input:** grid = \[\[3,0,8,4\],\[2,4,5,7\],\[9,2,6,3\],\[0,3,1,0\]\]
**Output:** 35
**Explanation:** The building heights are shown in the center of the above image.
The skylines when viewed from each cardinal direction are drawn in red.
The grid after increasing the height of buildings without affecting skylines is:
gridNew = \[ \[8, 4, 8, 7\],
            \[7, 4, 7, 7\],
            \[9, 4, 8, 7\],
            \[3, 3, 3, 3\] \]

**Example 2:**

**Input:** grid = \[\[0,0,0\],\[0,0,0\],\[0,0,0\]\]
**Output:** 0
**Explanation:** Increasing the height of any building will result in the skyline changing.

**Constraints:**

*   `n == grid.length`
*   `n == grid[r].length`
*   `2 <= n <= 50`
*   `0 <= grid[r][c] <= 100`
Soup Servings

There are two types of soup: **type A** and **type B**. Initially, we have `n` ml of each type of soup. There are four kinds of operations:

1.  Serve `100` ml of **soup A** and `0` ml of **soup B**,
2.  Serve `75` ml of **soup A** and `25` ml of **soup B**,
3.  Serve `50` ml of **soup A** and `50` ml of **soup B**, and
4.  Serve `25` ml of **soup A** and `75` ml of **soup B**.

When we serve some soup, we give it to someone, and we no longer have it. Each turn, we will choose from the four operations with an equal probability `0.25`. If the remaining volume of soup is not enough to complete the operation, we will serve as much as possible. We stop once we no longer have some quantity of both types of soup.

**Note** that we do not have an operation where all `100` ml's of **soup B** are used first.

Return _the probability that **soup A** will be empty first, plus half the probability that **A** and **B** become empty at the same time_. Answers within `10-5` of the actual answer will be accepted.

**Example 1:**

**Input:** n = 50
**Output:** 0.62500
**Explanation:** If we choose the first two operations, A will become empty first.
For the third operation, A and B will become empty at the same time.
For the fourth operation, B will become empty first.
So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 \* (1 + 1 + 0.5 + 0) = 0.625.

**Example 2:**

**Input:** n = 100
**Output:** 0.71875

**Constraints:**

*   `0 <= n <= 109`
Expressive Words

Sometimes people repeat letters to represent extra feeling. For example:

*   `"hello " -> "heeellooo "`
*   `"hi " -> "hiiii "`

In these strings like `"heeellooo "`, we have groups of adjacent letters that are all the same: `"h "`, `"eee "`, `"ll "`, `"ooo "`.

You are given a string `s` and an array of query strings `words`. A query word is **stretchy** if it can be made to be equal to `s` by any number of applications of the following extension operation: choose a group consisting of characters `c`, and add some number of characters `c` to the group so that the size of the group is **three or more**.

*   For example, starting with `"hello "`, we could do an extension on the group `"o "` to get `"hellooo "`, but we cannot get `"helloo "` since the group `"oo "` has a size less than three. Also, we could do another extension like `"ll " -> "lllll "` to get `"helllllooo "`. If `s = "helllllooo "`, then the query word `"hello "` would be **stretchy** because of these two extension operations: `query = "hello " -> "hellooo " -> "helllllooo " = s`.

Return _the number of query strings that are **stretchy**_.

**Example 1:**

**Input:** s =  "heeellooo ", words = \[ "hello ",  "hi ",  "helo "\]
**Output:** 1
**Explanation:** 
We can extend  "e " and  "o " in the word  "hello " to get  "heeellooo ".
We can't extend  "helo " to get  "heeellooo " because the group  "ll " is not size 3 or more.

**Example 2:**

**Input:** s =  "zzzzzyyyyy ", words = \[ "zzyy ", "zy ", "zyy "\]
**Output:** 3

**Constraints:**

*   `1 <= s.length, words.length <= 100`
*   `1 <= words[i].length <= 100`
*   `s` and `words[i]` consist of lowercase letters.
Chalkboard XOR Game

You are given an array of integers `nums` represents the numbers written on a chalkboard.

Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first. If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become `0`, then that player loses. The bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is `0`.

Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to `0`, then that player wins.

Return `true` _if and only if Alice wins the game, assuming both players play optimally_.

**Example 1:**

**Input:** nums = \[1,1,2\]
**Output:** false
**Explanation:** 
Alice has two choices: erase 1 or erase 2. 
If she erases 1, the nums array becomes \[1, 2\]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 2 = 3. Now Bob can remove any element he wants, because Alice will be the one to erase the last element and she will lose. 
If Alice erases 2 first, now nums become \[1, 1\]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `0 <= nums[i] < 216`
Subdomain Visit Count

A website domain `"discuss.leetcode.com "` consists of various subdomains. At the top level, we have `"com "`, at the next level, we have `"leetcode.com "` and at the lowest level, `"discuss.leetcode.com "`. When we visit a domain like `"discuss.leetcode.com "`, we will also visit the parent domains `"leetcode.com "` and `"com "` implicitly.

A **count-paired domain** is a domain that has one of the two formats `"rep d1.d2.d3 "` or `"rep d1.d2 "` where `rep` is the number of visits to the domain and `d1.d2.d3` is the domain itself.

*   For example, `"9001 discuss.leetcode.com "` is a **count-paired domain** that indicates that `discuss.leetcode.com` was visited `9001` times.

Given an array of **count-paired domains** `cpdomains`, return _an array of the **count-paired domains** of each subdomain in the input_. You may return the answer in **any order**.

**Example 1:**

**Input:** cpdomains = \[ "9001 discuss.leetcode.com "\]
**Output:** \[ "9001 leetcode.com ", "9001 discuss.leetcode.com ", "9001 com "\]
**Explanation:** We only have one website domain:  "discuss.leetcode.com ".
As discussed above, the subdomain  "leetcode.com " and  "com " will also be visited. So they will all be visited 9001 times.

**Example 2:**

**Input:** cpdomains = \[ "900 google.mail.com ",  "50 yahoo.com ",  "1 intel.mail.com ",  "5 wiki.org "\]
**Output:** \[ "901 mail.com ", "50 yahoo.com ", "900 google.mail.com ", "5 wiki.org ", "5 org ", "1 intel.mail.com ", "951 com "\]
**Explanation:** We will visit  "google.mail.com " 900 times,  "yahoo.com " 50 times,  "intel.mail.com " once and  "wiki.org " 5 times.
For the subdomains, we will visit  "mail.com " 900 + 1 = 901 times,  "com " 900 + 50 + 1 = 951 times, and  "org " 5 times.

**Constraints:**

*   `1 <= cpdomain.length <= 100`
*   `1 <= cpdomain[i].length <= 100`
*   `cpdomain[i]` follows either the `"repi d1i.d2i.d3i "` format or the `"repi d1i.d2i "` format.
*   `repi` is an integer in the range `[1, 104]`.
*   `d1i`, `d2i`, and `d3i` consist of lowercase English letters.
Largest Triangle Area

Given an array of points on the **X-Y** plane `points` where `points[i] = [xi, yi]`, return _the area of the largest triangle that can be formed by any three different points_. Answers within `10-5` of the actual answer will be accepted.

**Example 1:**

**Input:** points = \[\[0,0\],\[0,1\],\[1,0\],\[0,2\],\[2,0\]\]
**Output:** 2.00000
**Explanation:** The five points are shown in the above figure. The red triangle is the largest.

**Example 2:**

**Input:** points = \[\[1,0\],\[0,0\],\[0,1\]\]
**Output:** 0.50000

**Constraints:**

*   `3 <= points.length <= 50`
*   `-50 <= xi, yi <= 50`
*   All the given points are **unique**.
Largest Sum of Averages

You are given an integer array `nums` and an integer `k`. You can partition the array into **at most** `k` non-empty adjacent subarrays. The **score** of a partition is the sum of the averages of each subarray.

Note that the partition must use every integer in `nums`, and that the score is not necessarily an integer.

Return _the maximum **score** you can achieve of all the possible partitions_. Answers within `10-6` of the actual answer will be accepted.

**Example 1:**

**Input:** nums = \[9,1,2,3,9\], k = 3
**Output:** 20.00000
**Explanation:** 
The best choice is to partition nums into \[9\], \[1, 2, 3\], \[9\]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into \[9, 1\], \[2\], \[3, 9\], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

**Example 2:**

**Input:** nums = \[1,2,3,4,5,6,7\], k = 4
**Output:** 20.50000

**Constraints:**

*   `1 <= nums.length <= 100`
*   `1 <= nums[i] <= 104`
*   `1 <= k <= nums.length`
Binary Tree Pruning

Given the `root` of a binary tree, return _the same tree where every subtree (of the given tree) not containing a_ `1` _has been removed_.

A subtree of a node `node` is `node` plus every node that is a descendant of `node`.

**Example 1:**

**Input:** root = \[1,null,0,0,1\]
**Output:** \[1,null,0,null,1\]
**Explanation:** 
Only the red nodes satisfy the property  "every subtree not containing a 1 ".
The diagram on the right represents the answer.

**Example 2:**

**Input:** root = \[1,0,1,0,0,0,1\]
**Output:** \[1,null,1,null,1\]

**Example 3:**

**Input:** root = \[1,1,0,1,1,0,1,0\]
**Output:** \[1,1,0,1,1,null,1\]

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 200]`.
*   `Node.val` is either `0` or `1`.
Bus Routes

You are given an array `routes` representing bus routes where `routes[i]` is a bus route that the `ith` bus repeats forever.

*   For example, if `routes[0] = [1, 5, 7]`, this means that the `0th` bus travels in the sequence `1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...` forever.

You will start at the bus stop `source` (You are not on any bus initially), and you want to go to the bus stop `target`. You can travel between bus stops by buses only.

Return _the least number of buses you must take to travel from_ `source` _to_ `target`. Return `-1` if it is not possible.

**Example 1:**

**Input:** routes = \[\[1,2,7\],\[3,6,7\]\], source = 1, target = 6
**Output:** 2
**Explanation:** The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

**Example 2:**

**Input:** routes = \[\[7,12\],\[4,5,15\],\[6\],\[15,19\],\[9,12,13\]\], source = 15, target = 12
**Output:** -1

**Constraints:**

*   `1 <= routes.length <= 500`.
*   `1 <= routes[i].length <= 105`
*   All the values of `routes[i]` are **unique**.
*   `sum(routes[i].length) <= 105`
*   `0 <= routes[i][j] < 106`
*   `0 <= source, target < 106`
Ambiguous Coordinates

We had some 2-dimensional coordinates, like `"(1, 3) "` or `"(2, 0.5) "`. Then, we removed all commas, decimal points, and spaces and ended up with the string s.

*   For example, `"(1, 3) "` becomes `s = "(13) "` and `"(2, 0.5) "` becomes `s = "(205) "`.

Return _a list of strings representing all possibilities for what our original coordinates could have been_.

Our original representation never had extraneous zeroes, so we never started with numbers like `"00 "`, `"0.0 "`, `"0.00 "`, `"1.0 "`, `"001 "`, `"00.01 "`, or any other number that can be represented with fewer digits. Also, a decimal point within a number never occurs without at least one digit occurring before it, so we never started with numbers like `".1 "`.

The final answer list can be returned in any order. All coordinates in the final answer have exactly one space between them (occurring after the comma.)

**Example 1:**

**Input:** s =  "(123) "
**Output:** \[ "(1, 2.3) ", "(1, 23) ", "(1.2, 3) ", "(12, 3) "\]

**Example 2:**

**Input:** s =  "(0123) "
**Output:** \[ "(0, 1.23) ", "(0, 12.3) ", "(0, 123) ", "(0.1, 2.3) ", "(0.1, 23) ", "(0.12, 3) "\]
**Explanation:** 0.0, 00, 0001 or 00.01 are not allowed.

**Example 3:**

**Input:** s =  "(00011) "
**Output:** \[ "(0, 0.011) ", "(0.001, 1) "\]

**Constraints:**

*   `4 <= s.length <= 12`
*   `s[0] == '('` and `s[s.length - 1] == ')'`.
*   The rest of `s` are digits.
Linked List Components

You are given the `head` of a linked list containing unique integer values and an integer array `nums` that is a subset of the linked list values.

Return _the number of connected components in_ `nums` _where two values are connected if they appear **consecutively** in the linked list_.

**Example 1:**

**Input:** head = \[0,1,2,3\], nums = \[0,1,3\]
**Output:** 2
**Explanation:** 0 and 1 are connected, so \[0, 1\] and \[3\] are the two connected components.

**Example 2:**

**Input:** head = \[0,1,2,3,4\], nums = \[0,3,1,4\]
**Output:** 2
**Explanation:** 0 and 1 are connected, 3 and 4 are connected, so \[0, 1\] and \[3, 4\] are the two connected components.

**Constraints:**

*   The number of nodes in the linked list is `n`.
*   `1 <= n <= 104`
*   `0 <= Node.val < n`
*   All the values `Node.val` are **unique**.
*   `1 <= nums.length <= n`
*   `0 <= nums[i] < n`
*   All the values of `nums` are **unique**.
Race Car

Your car starts at position `0` and speed `+1` on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions `'A'` (accelerate) and `'R'` (reverse):

*   When you get an instruction `'A'`, your car does the following:
    *   `position += speed`
    *   `speed *= 2`
*   When you get an instruction `'R'`, your car does the following:
    *   If your speed is positive then `speed = -1`
    *   otherwise `speed = 1`Your position stays the same.

For example, after commands `"AAR "`, your car goes to positions `0 --> 1 --> 3 --> 3`, and your speed goes to `1 --> 2 --> 4 --> -1`.

Given a target position `target`, return _the length of the shortest sequence of instructions to get there_.

**Example 1:**

**Input:** target = 3
**Output:** 2
**Explanation:** 
The shortest instruction sequence is  "AA ".
Your position goes from 0 --> 1 --> 3.

**Example 2:**

**Input:** target = 6
**Output:** 5
**Explanation:** 
The shortest instruction sequence is  "AAARA ".
Your position goes from 0 --> 1 --> 3 --> 7 --> 7 --> 6.

**Constraints:**

*   `1 <= target <= 104`
Most Common Word

Given a string `paragraph` and a string array of the banned words `banned`, return _the most frequent word that is not banned_. It is **guaranteed** there is **at least one word** that is not banned, and that the answer is **unique**.

The words in `paragraph` are **case-insensitive** and the answer should be returned in **lowercase**.

**Example 1:**

**Input:** paragraph =  "Bob hit a ball, the hit BALL flew far after it was hit. ", banned = \[ "hit "\]
**Output:**  "ball "
**Explanation:** 
 "hit " occurs 3 times, but it is a banned word.
 "ball " occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as  "ball, "), 
and that  "hit " isn't the answer even though it occurs more because it is banned.

**Example 2:**

**Input:** paragraph =  "a. ", banned = \[\]
**Output:**  "a "

**Constraints:**

*   `1 <= paragraph.length <= 1000`
*   paragraph consists of English letters, space `' '`, or one of the symbols: `"!?',;. "`.
*   `0 <= banned.length <= 100`
*   `1 <= banned[i].length <= 10`
*   `banned[i]` consists of only lowercase English letters.
Short Encoding of Words

A **valid encoding** of an array of `words` is any reference string `s` and array of indices `indices` such that:

*   `words.length == indices.length`
*   The reference string `s` ends with the `'#'` character.
*   For each index `indices[i]`, the **substring** of `s` starting from `indices[i]` and up to (but not including) the next `'#'` character is equal to `words[i]`.

Given an array of `words`, return _the **length of the shortest reference string**_ `s` _possible of any **valid encoding** of_ `words`_._

**Example 1:**

**Input:** words = \[ "time ",  "me ",  "bell "\]
**Output:** 10
**Explanation:** A valid encoding would be s = ` "time#bell# " and indices = [0, 2, 5`\].
words\[0\] =  "time ", the substring of s starting from indices\[0\] = 0 to the next '#' is underlined in  "time#bell# "
words\[1\] =  "me ", the substring of s starting from indices\[1\] = 2 to the next '#' is underlined in  "time#bell# "
words\[2\] =  "bell ", the substring of s starting from indices\[2\] = 5 to the next '#' is underlined in  "time#bell\# "

**Example 2:**

**Input:** words = \[ "t "\]
**Output:** 2
**Explanation:** A valid encoding would be s =  "t# " and indices = \[0\].

**Constraints:**

*   `1 <= words.length <= 2000`
*   `1 <= words[i].length <= 7`
*   `words[i]` consists of only lowercase letters.
Shortest Distance to a Character

Given a string `s` and a character `c` that occurs in `s`, return _an array of integers_ `answer` _where_ `answer.length == s.length` _and_ `answer[i]` _is the **distance** from index_ `i` _to the **closest** occurrence of character_ `c` _in_ `s`.

The **distance** between two indices `i` and `j` is `abs(i - j)`, where `abs` is the absolute value function.

**Example 1:**

**Input:** s =  "loveleetcode ", c =  "e "
**Output:** \[3,2,1,0,1,0,0,1,2,2,1,0\]
**Explanation:** The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

**Example 2:**

**Input:** s =  "aaab ", c =  "b "
**Output:** \[3,2,1,0\]

**Constraints:**

*   `1 <= s.length <= 104`
*   `s[i]` and `c` are lowercase English letters.
*   It is guaranteed that `c` occurs at least once in `s`.
Card Flipping Game

You are given two **0-indexed** integer arrays `fronts` and `backs` of length `n`, where the `ith` card has the positive integer `fronts[i]` printed on the front and `backs[i]` printed on the back. Initially, each card is placed on a table such that the front number is facing up and the other is facing down. You may flip over any number of cards (possibly zero).

After flipping the cards, an integer is considered **good** if it is facing down on some card and **not** facing up on any card.

Return _the minimum possible good integer after flipping the cards_. If there are no good integers, return `0`.

**Example 1:**

**Input:** fronts = \[1,2,4,4,7\], backs = \[1,3,4,1,3\]
**Output:** 2
**Explanation:**
If we flip the second card, the face up numbers are \[1,3,4,4,7\] and the face down are \[1,2,4,1,3\].
2 is the minimum good integer as it appears facing down but not facing up.
It can be shown that 2 is the minimum possible good integer obtainable after flipping some cards.

**Example 2:**

**Input:** fronts = \[1\], backs = \[1\]
**Output:** 0
**Explanation:**
There are no good integers no matter how we flip the cards, so we return 0.

**Constraints:**

*   `n == fronts.length == backs.length`
*   `1 <= n <= 1000`
*   `1 <= fronts[i], backs[i] <= 2000`
Binary Trees With Factors

Given an array of unique integers, `arr`, where each integer `arr[i]` is strictly greater than `1`.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node's value should be equal to the product of the values of its children.

Return _the number of binary trees we can make_. The answer may be too large so return the answer **modulo** `109 + 7`.

**Example 1:**

**Input:** arr = \[2,4\]
**Output:** 3
**Explanation:** We can make these trees: `[2], [4], [4, 2, 2]`

**Example 2:**

**Input:** arr = \[2,4,5,10\]
**Output:** 7
**Explanation:** We can make these trees: `[2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]`.

**Constraints:**

*   `1 <= arr.length <= 1000`
*   `2 <= arr[i] <= 109`
*   All the values of `arr` are **unique**.
Goat Latin

You are given a string `sentence` that consist of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to "Goat Latin " (a made-up language similar to Pig Latin.) The rules of Goat Latin are as follows:

*   If a word begins with a vowel (`'a'`, `'e'`, `'i'`, `'o'`, or `'u'`), append `"ma "` to the end of the word.
    *   For example, the word `"apple "` becomes `"applema "`.
*   If a word begins with a consonant (i.e., not a vowel), remove the first letter and append it to the end, then add `"ma "`.
    *   For example, the word `"goat "` becomes `"oatgma "`.
*   Add one letter `'a'` to the end of each word per its word index in the sentence, starting with `1`.
    *   For example, the first word gets `"a "` added to the end, the second word gets `"aa "` added to the end, and so on.

Return _the final sentence representing the conversion from sentence to Goat Latin_.

**Example 1:**

**Input:** sentence = "I speak Goat Latin"
**Output:** "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

**Example 2:**

**Input:** sentence = "The quick brown fox jumped over the lazy dog"
**Output:** "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

**Constraints:**

*   `1 <= sentence.length <= 150`
*   `sentence` consists of English letters and spaces.
*   `sentence` has no leading or trailing spaces.
*   All the words in `sentence` are separated by a single space.
Friends Of Appropriate Ages

There are `n` persons on a social media website. You are given an integer array `ages` where `ages[i]` is the age of the `ith` person.

A Person `x` will not send a friend request to a person `y` (`x != y`) if any of the following conditions is true:

*   `age[y] <= 0.5 * age[x] + 7`
*   `age[y] > age[x]`
*   `age[y] > 100 && age[x] < 100`

Otherwise, `x` will send a friend request to `y`.

Note that if `x` sends a request to `y`, `y` will not necessarily send a request to `x`. Also, a person will not send a friend request to themself.

Return _the total number of friend requests made_.

**Example 1:**

**Input:** ages = \[16,16\]
**Output:** 2
**Explanation:** 2 people friend request each other.

**Example 2:**

**Input:** ages = \[16,17,18\]
**Output:** 2
**Explanation:** Friend requests are made 17 -> 16, 18 -> 17.

**Example 3:**

**Input:** ages = \[20,30,100,110,120\]
**Output:** 3
**Explanation:** Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

**Constraints:**

*   `n == ages.length`
*   `1 <= n <= 2 * 104`
*   `1 <= ages[i] <= 120`