bowang0911/leetcode huggingface dataset:
Maximum Font to Fit a Sentence in a Screen

You are given a string `text`. We want to display `text` on a screen of width `w` and height `h`. You can choose any font size from array `fonts`, which contains the available font sizes **in ascending order**.

You can use the `FontInfo` interface to get the width and height of any character at any available font size.

The `FontInfo` interface is defined as such:

interface FontInfo {
  // Returns the width of character ch on the screen using font size fontSize.
  // O(1) per call
  public int getWidth(int fontSize, char ch);

  // Returns the height of any character on the screen using font size fontSize.
  // O(1) per call
  public int getHeight(int fontSize);
}

The calculated width of `text` for some `fontSize` is the **sum** of every `getWidth(fontSize, text[i])` call for each `0 <= i < text.length` (**0-indexed**). The calculated height of `text` for some `fontSize` is `getHeight(fontSize)`. Note that `text` is displayed on a **single line**.

It is guaranteed that `FontInfo` will return the same value if you call `getHeight` or `getWidth` with the same parameters.

It is also guaranteed that for any font size `fontSize` and any character `ch`:

*   `getHeight(fontSize) <= getHeight(fontSize+1)`
*   `getWidth(fontSize, ch) <= getWidth(fontSize+1, ch)`

Return _the maximum font size you can use to display_ `text` _on the screen_. If `text` cannot fit on the display with any font size, return `-1`.

**Example 1:**

**Input:** text =  "helloworld ", w = 80, h = 20, fonts = \[6,8,10,12,14,16,18,24,36\]
**Output:** 6

**Example 2:**

**Input:** text =  "leetcode ", w = 1000, h = 50, fonts = \[1,2,4\]
**Output:** 4

**Example 3:**

**Input:** text =  "easyquestion ", w = 100, h = 100, fonts = \[10,15,20,25\]
**Output:** -1

**Constraints:**

*   `1 <= text.length <= 50000`
*   `text` contains only lowercase English letters.
*   `1 <= w <= 107`
*   `1 <= h <= 104`
*   `1 <= fonts.length <= 105`
*   `1 <= fonts[i] <= 105`
*   `fonts` is sorted in ascending order and does not contain duplicates.
Mean of Array After Removing Some Elements

Given an integer array `arr`, return _the mean of the remaining integers after removing the smallest `5%` and the largest `5%` of the elements._

Answers within `10-5` of the **actual answer** will be considered accepted.

**Example 1:**

**Input:** arr = \[1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3\]
**Output:** 2.00000
**Explanation:** After erasing the minimum and the maximum values of this array, all elements are equal to 2, so the mean is 2.

**Example 2:**

**Input:** arr = \[6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0\]
**Output:** 4.00000

**Example 3:**

**Input:** arr = \[6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,3,8,5,10,8,6,6,1,0,6,10,8,2,3,4\]
**Output:** 4.77778

**Constraints:**

*   `20 <= arr.length <= 1000`
*   `arr.length` **is a multiple** of `20`.
*   `0 <= arr[i] <= 105`
Coordinate With Maximum Network Quality

You are given an array of network towers `towers`, where `towers[i] = [xi, yi, qi]` denotes the `ith` network tower with location `(xi, yi)` and quality factor `qi`. All the coordinates are **integral coordinates** on the X-Y plane, and the distance between the two coordinates is the **Euclidean distance**.

You are also given an integer `radius` where a tower is **reachable** if the distance is **less than or equal to** `radius`. Outside that distance, the signal becomes garbled, and the tower is **not reachable**.

The signal quality of the `ith` tower at a coordinate `(x, y)` is calculated with the formula `⌊qi / (1 + d)⌋`, where `d` is the distance between the tower and the coordinate. The **network quality** at a coordinate is the sum of the signal qualities from all the **reachable** towers.

Return _the array_ `[cx, cy]` _representing the **integral** coordinate_ `(cx, cy)` _where the **network quality** is maximum. If there are multiple coordinates with the same **network quality**, return the lexicographically minimum **non-negative** coordinate._

**Note:**

*   A coordinate `(x1, y1)` is lexicographically smaller than `(x2, y2)` if either:
    *   `x1 < x2`, or
    *   `x1 == x2` and `y1 < y2`.
*   `⌊val⌋` is the greatest integer less than or equal to `val` (the floor function).

**Example 1:**

**Input:** towers = \[\[1,2,5\],\[2,1,7\],\[3,1,9\]\], radius = 2
**Output:** \[2,1\]
**Explanation:** At coordinate (2, 1) the total quality is 13.
- Quality of 7 from (2, 1) results in ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- Quality of 5 from (1, 2) results in ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- Quality of 9 from (3, 1) results in ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
No other coordinate has a higher network quality.

**Example 2:**

**Input:** towers = \[\[23,11,21\]\], radius = 9
**Output:** \[23,11\]
**Explanation:** Since there is only one tower, the network quality is highest right at the tower's location.

**Example 3:**

**Input:** towers = \[\[1,2,13\],\[2,1,7\],\[0,1,9\]\], radius = 2
**Output:** \[1,2\]
**Explanation:** Coordinate (1, 2) has the highest network quality.

**Constraints:**

*   `1 <= towers.length <= 50`
*   `towers[i].length == 3`
*   `0 <= xi, yi, qi <= 50`
*   `1 <= radius <= 50`
Number of Sets of K Non-Overlapping Line Segments

Given `n` points on a 1-D plane, where the `ith` point (from `0` to `n-1`) is at `x = i`, find the number of ways we can draw **exactly** `k` **non-overlapping** line segments such that each segment covers two or more points. The endpoints of each segment must have **integral coordinates**. The `k` line segments **do not** have to cover all `n` points, and they are **allowed** to share endpoints.

Return _the number of ways we can draw_ `k` _non-overlapping line segments__._ Since this number can be huge, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** n = 4, k = 2
**Output:** 5
**Explanation:** The two line segments are shown in red and blue.
The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

**Example 2:**

**Input:** n = 3, k = 1
**Output:** 3
**Explanation:** The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.

**Example 3:**

**Input:** n = 30, k = 7
**Output:** 796297179
**Explanation:** The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 109 + 7 gives us 796297179.

**Constraints:**

*   `2 <= n <= 1000`
*   `1 <= k <= n-1`
Fancy Sequence

Write an API that generates fancy sequences using the `append`, `addAll`, and `multAll` operations.

Implement the `Fancy` class:

*   `Fancy()` Initializes the object with an empty sequence.
*   `void append(val)` Appends an integer `val` to the end of the sequence.
*   `void addAll(inc)` Increments all existing values in the sequence by an integer `inc`.
*   `void multAll(m)` Multiplies all existing values in the sequence by an integer `m`.
*   `int getIndex(idx)` Gets the current value at index `idx` (0-indexed) of the sequence **modulo** `109 + 7`. If the index is greater or equal than the length of the sequence, return `-1`.

**Example 1:**

**Input**
\[ "Fancy ",  "append ",  "addAll ",  "append ",  "multAll ",  "getIndex ",  "addAll ",  "append ",  "multAll ",  "getIndex ",  "getIndex ",  "getIndex "\]
\[\[\], \[2\], \[3\], \[7\], \[2\], \[0\], \[3\], \[10\], \[2\], \[0\], \[1\], \[2\]\]
**Output**
\[null, null, null, null, null, 10, null, null, null, 26, 34, 20\]

**Explanation**
Fancy fancy = new Fancy();
fancy.append(2);   // fancy sequence: \[2\]
fancy.addAll(3);   // fancy sequence: \[2+3\] -> \[5\]
fancy.append(7);   // fancy sequence: \[5, 7\]
fancy.multAll(2);  // fancy sequence: \[5\*2, 7\*2\] -> \[10, 14\]
fancy.getIndex(0); // return 10
fancy.addAll(3);   // fancy sequence: \[10+3, 14+3\] -> \[13, 17\]
fancy.append(10);  // fancy sequence: \[13, 17, 10\]
fancy.multAll(2);  // fancy sequence: \[13\*2, 17\*2, 10\*2\] -> \[26, 34, 20\]
fancy.getIndex(0); // return 26
fancy.getIndex(1); // return 34
fancy.getIndex(2); // return 20

**Constraints:**

*   `1 <= val, inc, m <= 100`
*   `0 <= idx <= 105`
*   At most `105` calls total will be made to `append`, `addAll`, `multAll`, and `getIndex`.
Largest Substring Between Two Equal Characters

Given a string `s`, return _the length of the longest substring between two equal characters, excluding the two characters._ If there is no such substring return `-1`.

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

**Example 1:**

**Input:** s =  "aa "
**Output:** 0
**Explanation:** The optimal substring here is an empty substring between the two `'a's`.

**Example 2:**

**Input:** s =  "abca "
**Output:** 2
**Explanation:** The optimal substring here is  "bc ".

**Example 3:**

**Input:** s =  "cbzxy "
**Output:** -1
**Explanation:** There are no characters that appear twice in s.

**Constraints:**

*   `1 <= s.length <= 300`
*   `s` contains only lowercase English letters.
Lexicographically Smallest String After Applying Operations

You are given a string `s` of **even length** consisting of digits from `0` to `9`, and two integers `a` and `b`.

You can apply either of the following two operations any number of times and in any order on `s`:

*   Add `a` to all odd indices of `s` **(0-indexed)**. Digits post `9` are cycled back to `0`. For example, if `s = "3456 "` and `a = 5`, `s` becomes `"3951 "`.
*   Rotate `s` to the right by `b` positions. For example, if `s = "3456 "` and `b = 1`, `s` becomes `"6345 "`.

Return _the **lexicographically smallest** string you can obtain by applying the above operations any number of times on_ `s`.

A string `a` is lexicographically smaller than a string `b` (of the same length) if in the first position where `a` and `b` differ, string `a` has a letter that appears earlier in the alphabet than the corresponding letter in `b`. For example, `"0158 "` is lexicographically smaller than `"0190 "` because the first position they differ is at the third letter, and `'5'` comes before `'9'`.

**Example 1:**

**Input:** s =  "5525 ", a = 9, b = 2
**Output:**  "2050 "
**Explanation:** We can apply the following operations:
Start:   "5525 "
Rotate:  "2555 "
Add:     "2454 "
Add:     "2353 "
Rotate:  "5323 "
Add:     "5222 "
Add:     "5121 "
Rotate:  "2151 "
​​​​​​​Add:     "2050 "​​​​​​​​​​​​
There is no way to obtain a string that is lexicographically smaller then  "2050 ".

**Example 2:**

**Input:** s =  "74 ", a = 5, b = 1
**Output:**  "24 "
**Explanation:** We can apply the following operations:
Start:   "74 "
Rotate:  "47 "
​​​​​​​Add:     "42 "
​​​​​​​Rotate:  "24 "​​​​​​​​​​​​
There is no way to obtain a string that is lexicographically smaller then  "24 ".

**Example 3:**

**Input:** s =  "0011 ", a = 4, b = 2
**Output:**  "0011 "
**Explanation:** There are no sequence of operations that will give us a lexicographically smaller string than  "0011 ".

**Constraints:**

*   `2 <= s.length <= 100`
*   `s.length` is even.
*   `s` consists of digits from `0` to `9` only.
*   `1 <= a <= 9`
*   `1 <= b <= s.length - 1`
Best Team With No Conflicts

You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the **sum** of scores of all the players in the team.

However, the basketball team is not allowed to have **conflicts**. A **conflict** exists if a younger player has a **strictly higher** score than an older player. A conflict does **not** occur between players of the same age.

Given two lists, `scores` and `ages`, where each `scores[i]` and `ages[i]` represents the score and age of the `ith` player, respectively, return _the highest overall score of all possible basketball teams_.

**Example 1:**

**Input:** scores = \[1,3,5,10,15\], ages = \[1,2,3,4,5\]
**Output:** 34
**Explanation:** You can choose all the players.

**Example 2:**

**Input:** scores = \[4,5,6,5\], ages = \[2,1,2,1\]
**Output:** 16
**Explanation:** It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.

**Example 3:**

**Input:** scores = \[1,2,3,5\], ages = \[8,9,10,1\]
**Output:** 6
**Explanation:** It is best to choose the first 3 players. 

**Constraints:**

*   `1 <= scores.length, ages.length <= 1000`
*   `scores.length == ages.length`
*   `1 <= scores[i] <= 106`
*   `1 <= ages[i] <= 1000`
Graph Connectivity With Threshold

We have `n` cities labeled from `1` to `n`. Two different cities with labels `x` and `y` are directly connected by a bidirectional road if and only if `x` and `y` share a common divisor **strictly greater** than some `threshold`. More formally, cities with labels `x` and `y` have a road between them if there exists an integer `z` such that all of the following are true:

*   `x % z == 0`,
*   `y % z == 0`, and
*   `z > threshold`.

Given the two integers, `n` and `threshold`, and an array of `queries`, you must determine for each `queries[i] = [ai, bi]` if cities `ai` and `bi` are connected directly or indirectly. (i.e. there is some path between them).

Return _an array_ `answer`_, where_ `answer.length == queries.length` _and_ `answer[i]` _is_ `true` _if for the_ `ith` _query, there is a path between_ `ai` _and_ `bi`_, or_ `answer[i]` _is_ `false` _if there is no path._

**Example 1:**

**Input:** n = 6, threshold = 2, queries = \[\[1,4\],\[2,5\],\[3,6\]\]
**Output:** \[false,false,true\]
**Explanation:** The divisors for each number:
1:   1
2:   1, 2
3:   1, 3
4:   1, 2, 4
5:   1, 5
6:   1, 2, 3, 6
Using the underlined divisors above the threshold, only cities 3 and 6 share a common divisor, so they are the
only ones directly connected. The result of each query:
\[1,4\]   1 is not connected to 4
\[2,5\]   2 is not connected to 5
\[3,6\]   3 is connected to 6 through path 3--6

**Example 2:**

**Input:** n = 6, threshold = 0, queries = \[\[4,5\],\[3,4\],\[3,2\],\[2,6\],\[1,3\]\]
**Output:** \[true,true,true,true,true\]
**Explanation:** The divisors for each number are the same as the previous example. However, since the threshold is 0,
all divisors can be used. Since all numbers share 1 as a divisor, all cities are connected.

**Example 3:**

**Input:** n = 5, threshold = 1, queries = \[\[4,5\],\[4,5\],\[3,2\],\[2,3\],\[3,4\]\]
**Output:** \[false,false,false,false,false\]
**Explanation:** Only cities 2 and 4 share a common divisor 2 which is strictly greater than the threshold 1, so they are the only ones directly connected.
Please notice that there can be multiple queries for the same pair of nodes \[x, y\], and that the query \[x, y\] is equivalent to the query \[y, x\].

**Constraints:**

*   `2 <= n <= 104`
*   `0 <= threshold <= n`
*   `1 <= queries.length <= 105`
*   `queries[i].length == 2`
*   `1 <= ai, bi <= cities`
*   `ai != bi`
Design an Expression Tree With Evaluate Function

Given the `postfix` tokens of an arithmetic expression, build and return _the binary expression tree that represents this expression._

**Postfix** notation is a notation for writing arithmetic expressions in which the operands (numbers) appear before their operators. For example, the postfix tokens of the expression `4*(5-(7+2))` are represented in the array `postfix = [ "4 ", "5 ", "7 ", "2 ", "+ ", "- ", "* "]`.

The class `Node` is an interface you should use to implement the binary expression tree. The returned tree will be tested using the `evaluate` function, which is supposed to evaluate the tree's value. You should not remove the `Node` class; however, you can modify it as you wish, and you can define other classes to implement it if needed.

A **[binary expression tree](https://en.wikipedia.org/wiki/Binary_expression_tree)** is a kind of binary tree used to represent arithmetic expressions. Each node of a binary expression tree has either zero or two children. Leaf nodes (nodes with 0 children) correspond to operands (numbers), and internal nodes (nodes with two children) correspond to the operators `'+'` (addition), `'-'` (subtraction), `'*'` (multiplication), and `'/'` (division).

It's guaranteed that no subtree will yield a value that exceeds `109` in absolute value, and all the operations are valid (i.e., no division by zero).

**Follow up:** Could you design the expression tree such that it is more modular? For example, is your design able to support additional operators without making changes to your existing `evaluate` implementation?

**Example 1:**

**Input:** s = \[ "3 ", "4 ", "+ ", "2 ", "\* ", "7 ", "/ "\]
**Output:** 2
**Explanation:** this expression evaluates to the above binary tree with expression (`(3+4)*2)/7) = 14/7 = 2.`

**Example 2:**

**Input:** s = \[ "4 ", "5 ", "2 ", "7 ", "+ ", "- ", "\* "\]
**Output:** -16
**Explanation:** this expression evaluates to the above binary tree with expression 4\*(5-`(2+7)) = 4*(-4) = -16.`

**Constraints:**

*   `1 <= s.length < 100`
*   `s.length` is odd.
*   `s` consists of numbers and the characters `'+'`, `'-'`, `'*'`, and `'/'`.
*   If `s[i]` is a number, its integer representation is no more than `105`.
*   It is guaranteed that `s` is a valid expression.
*   The absolute value of the result and intermediate values will not exceed `109`.
*   It is guaranteed that no expression will include division by zero.
Slowest Key

A newly designed keypad was tested, where a tester pressed a sequence of `n` keys, one at a time.

You are given a string `keysPressed` of length `n`, where `keysPressed[i]` was the `ith` key pressed in the testing sequence, and a sorted list `releaseTimes`, where `releaseTimes[i]` was the time the `ith` key was released. Both arrays are **0-indexed**. The `0th` key was pressed at the time `0`, and every subsequent key was pressed at the **exact** time the previous key was released.

The tester wants to know the key of the keypress that had the **longest duration**. The `ith` keypress had a **duration** of `releaseTimes[i] - releaseTimes[i - 1]`, and the `0th` keypress had a duration of `releaseTimes[0]`.

Note that the same key could have been pressed multiple times during the test, and these multiple presses of the same key **may not** have had the same **duration**.

_Return the key of the keypress that had the **longest duration**. If there are multiple such keypresses, return the lexicographically largest key of the keypresses._

**Example 1:**

**Input:** releaseTimes = \[9,29,49,50\], keysPressed =  "cbcd "
**Output:**  "c "
**Explanation:** The keypresses were as follows:
Keypress for 'c' had a duration of 9 (pressed at time 0 and released at time 9).
Keypress for 'b' had a duration of 29 - 9 = 20 (pressed at time 9 right after the release of the previous character and released at time 29).
Keypress for 'c' had a duration of 49 - 29 = 20 (pressed at time 29 right after the release of the previous character and released at time 49).
Keypress for 'd' had a duration of 50 - 49 = 1 (pressed at time 49 right after the release of the previous character and released at time 50).
The longest of these was the keypress for 'b' and the second keypress for 'c', both with duration 20.
'c' is lexicographically larger than 'b', so the answer is 'c'.

**Example 2:**

**Input:** releaseTimes = \[12,23,36,46,62\], keysPressed =  "spuda "
**Output:**  "a "
**Explanation:** The keypresses were as follows:
Keypress for 's' had a duration of 12.
Keypress for 'p' had a duration of 23 - 12 = 11.
Keypress for 'u' had a duration of 36 - 23 = 13.
Keypress for 'd' had a duration of 46 - 36 = 10.
Keypress for 'a' had a duration of 62 - 46 = 16.
The longest of these was the keypress for 'a' with duration 16.

**Constraints:**

*   `releaseTimes.length == n`
*   `keysPressed.length == n`
*   `2 <= n <= 1000`
*   `1 <= releaseTimes[i] <= 109`
*   `releaseTimes[i] < releaseTimes[i+1]`
*   `keysPressed` contains only lowercase English letters.
Arithmetic Subarrays

A sequence of numbers is called **arithmetic** if it consists of at least two elements, and the difference between every two consecutive elements is the same. More formally, a sequence `s` is arithmetic if and only if `s[i+1] - s[i] == s[1] - s[0]` for all valid `i`.

For example, these are **arithmetic** sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not **arithmetic**:

1, 1, 2, 5, 7

You are given an array of `n` integers, `nums`, and two arrays of `m` integers each, `l` and `r`, representing the `m` range queries, where the `ith` query is the range `[l[i], r[i]]`. All the arrays are **0-indexed**.

Return _a list of_ `boolean` _elements_ `answer`_, where_ `answer[i]` _is_ `true` _if the subarray_ `nums[l[i]], nums[l[i]+1], ... , nums[r[i]]` _can be **rearranged** to form an **arithmetic** sequence, and_ `false` _otherwise._

**Example 1:**

**Input:** nums = `[4,6,5,9,3,7]`, l = `[0,0,2]`, r = `[2,3,5]`
**Output:** `[true,false,true]`
**Explanation:**
In the 0th query, the subarray is \[4,6,5\]. This can be rearranged as \[6,5,4\], which is an arithmetic sequence.
In the 1st query, the subarray is \[4,6,5,9\]. This cannot be rearranged as an arithmetic sequence.
In the 2nd query, the subarray is `[5,9,3,7]. This` can be rearranged as `[3,5,7,9]`, which is an arithmetic sequence.

**Example 2:**

**Input:** nums = \[-12,-9,-3,-12,-6,15,20,-25,-20,-15,-10\], l = \[0,1,6,4,8,7\], r = \[4,4,9,7,9,10\]
**Output:** \[false,true,false,false,true,true\]

**Constraints:**

*   `n == nums.length`
*   `m == l.length`
*   `m == r.length`
*   `2 <= n <= 500`
*   `1 <= m <= 500`
*   `0 <= l[i] < r[i] < n`
*   `-105 <= nums[i] <= 105`
Path With Minimum Effort

You are a hiker preparing for an upcoming hike. You are given `heights`, a 2D array of size `rows x columns`, where `heights[row][col]` represents the height of cell `(row, col)`. You are situated in the top-left cell, `(0, 0)`, and you hope to travel to the bottom-right cell, `(rows-1, columns-1)` (i.e., **0-indexed**). You can move **up**, **down**, **left**, or **right**, and you wish to find a route that requires the minimum **effort**.

A route's **effort** is the **maximum absolute difference** in heights between two consecutive cells of the route.

Return _the minimum **effort** required to travel from the top-left cell to the bottom-right cell._

**Example 1:**

**Input:** heights = \[\[1,2,2\],\[3,8,2\],\[5,3,5\]\]
**Output:** 2
**Explanation:** The route of \[1,3,5,3,5\] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of \[1,2,2,2,5\], where the maximum absolute difference is 3.

**Example 2:**

**Input:** heights = \[\[1,2,3\],\[3,8,4\],\[5,3,5\]\]
**Output:** 1
**Explanation:** The route of \[1,2,3,4,5\] has a maximum absolute difference of 1 in consecutive cells, which is better than route \[1,3,5,3,5\].

**Example 3:**

**Input:** heights = \[\[1,2,1,1,1\],\[1,2,1,2,1\],\[1,2,1,2,1\],\[1,2,1,2,1\],\[1,1,1,2,1\]\]
**Output:** 0
**Explanation:** This route does not require any effort.

**Constraints:**

*   `rows == heights.length`
*   `columns == heights[i].length`
*   `1 <= rows, columns <= 100`
*   `1 <= heights[i][j] <= 106`