bowang0911/leetcode huggingface dataset:
My Calendar III

A `k`\-booking happens when `k` events have some non-empty intersection (i.e., there is some time that is common to all `k` events.)

You are given some events `[startTime, endTime)`, after each given event, return an integer `k` representing the maximum `k`\-booking between all the previous events.

Implement the `MyCalendarThree` class:

*   `MyCalendarThree()` Initializes the object.
*   `int book(int startTime, int endTime)` Returns an integer `k` representing the largest integer such that there exists a `k`\-booking in the calendar.

**Example 1:**

**Input**
\[ "MyCalendarThree ",  "book ",  "book ",  "book ",  "book ",  "book ",  "book "\]
\[\[\], \[10, 20\], \[50, 60\], \[10, 40\], \[5, 15\], \[5, 10\], \[25, 55\]\]
**Output**
\[null, 1, 1, 2, 3, 3, 3\]

**Explanation**
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15); // return 3
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3

**Constraints:**

*   `0 <= startTime < endTime <= 109`
*   At most `400` calls will be made to `book`.
Flood Fill

An image is represented by an `m x n` integer grid `image` where `image[i][j]` represents the pixel value of the image.

You are also given three integers `sr`, `sc`, and `color`. You should perform a **flood fill** on the image starting from the pixel `image[sr][sc]`.

To perform a **flood fill**, consider the starting pixel, plus any pixels connected **4-directionally** to the starting pixel of the same color as the starting pixel, plus any pixels connected **4-directionally** to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with `color`.

Return _the modified image after performing the flood fill_.

**Example 1:**

**Input:** image = \[\[1,1,1\],\[1,1,0\],\[1,0,1\]\], sr = 1, sc = 1, color = 2
**Output:** \[\[2,2,2\],\[2,2,0\],\[2,0,1\]\]
**Explanation:** From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

**Example 2:**

**Input:** image = \[\[0,0,0\],\[0,0,0\]\], sr = 0, sc = 0, color = 0
**Output:** \[\[0,0,0\],\[0,0,0\]\]
**Explanation:** The starting pixel is already colored 0, so no changes are made to the image.

**Constraints:**

*   `m == image.length`
*   `n == image[i].length`
*   `1 <= m, n <= 50`
*   `0 <= image[i][j], color < 216`
*   `0 <= sr < m`
*   `0 <= sc < n`
Sentence Similarity

We can represent a sentence as an array of words, for example, the sentence `"I am happy with leetcode "` can be represented as `arr = [ "I ", "am ",happy ", "with ", "leetcode "]`.

Given two sentences `sentence1` and `sentence2` each represented as a string array and given an array of string pairs `similarPairs` where `similarPairs[i] = [xi, yi]` indicates that the two words `xi` and `yi` are similar.

Return _`true` if `sentence1` and `sentence2` are similar, or `false` if they are not similar_.

Two sentences are similar if:

*   They have **the same length** (i.e., the same number of words)
*   `sentence1[i]` and `sentence2[i]` are similar.

Notice that a word is always similar to itself, also notice that the similarity relation is not transitive. For example, if the words `a` and `b` are similar, and the words `b` and `c` are similar, `a` and `c` are **not necessarily similar**.

**Example 1:**

**Input:** sentence1 = \[ "great ", "acting ", "skills "\], sentence2 = \[ "fine ", "drama ", "talent "\], similarPairs = \[\[ "great ", "fine "\],\[ "drama ", "acting "\],\[ "skills ", "talent "\]\]
**Output:** true
**Explanation:** The two sentences have the same length and each word i of sentence1 is also similar to the corresponding word in sentence2.

**Example 2:**

**Input:** sentence1 = \[ "great "\], sentence2 = \[ "great "\], similarPairs = \[\]
**Output:** true
**Explanation:** A word is similar to itself.

**Example 3:**

**Input:** sentence1 = \[ "great "\], sentence2 = \[ "doubleplus ", "good "\], similarPairs = \[\[ "great ", "doubleplus "\]\]
**Output:** false
**Explanation:** As they don't have the same length, we return false.

**Constraints:**

*   `1 <= sentence1.length, sentence2.length <= 1000`
*   `1 <= sentence1[i].length, sentence2[i].length <= 20`
*   `sentence1[i]` and `sentence2[i]` consist of English letters.
*   `0 <= similarPairs.length <= 1000`
*   `similarPairs[i].length == 2`
*   `1 <= xi.length, yi.length <= 20`
*   `xi` and `yi` consist of lower-case and upper-case English letters.
*   All the pairs `(xi, yi)` are **distinct**.
Asteroid Collision

We are given an array `asteroids` of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

**Example 1:**

**Input:** asteroids = \[5,10,-5\]
**Output:** \[5,10\]
**Explanation:** The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

**Example 2:**

**Input:** asteroids = \[8,-8\]
**Output:** \[\]
**Explanation:** The 8 and -8 collide exploding each other.

**Example 3:**

**Input:** asteroids = \[10,2,-5\]
**Output:** \[10\]
**Explanation:** The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

**Constraints:**

*   `2 <= asteroids.length <= 104`
*   `-1000 <= asteroids[i] <= 1000`
*   `asteroids[i] != 0`
Parse Lisp Expression

You are given a string expression representing a Lisp-like expression to return the integer value of.

The syntax for these expressions is given as follows.

*   An expression is either an integer, let expression, add expression, mult expression, or an assigned variable. Expressions always evaluate to a single integer.
*   (An integer could be positive or negative.)
*   A let expression takes the form `"(let v1 e1 v2 e2 ... vn en expr) "`, where let is always the string `"let "`, then there are one or more pairs of alternating variables and expressions, meaning that the first variable `v1` is assigned the value of the expression `e1`, the second variable `v2` is assigned the value of the expression `e2`, and so on sequentially; and then the value of this let expression is the value of the expression `expr`.
*   An add expression takes the form `"(add e1 e2) "` where add is always the string `"add "`, there are always two expressions `e1`, `e2` and the result is the addition of the evaluation of `e1` and the evaluation of `e2`.
*   A mult expression takes the form `"(mult e1 e2) "` where mult is always the string `"mult "`, there are always two expressions `e1`, `e2` and the result is the multiplication of the evaluation of e1 and the evaluation of e2.
*   For this question, we will use a smaller subset of variable names. A variable starts with a lowercase letter, then zero or more lowercase letters or digits. Additionally, for your convenience, the names `"add "`, `"let "`, and `"mult "` are protected and will never be used as variable names.
*   Finally, there is the concept of scope. When an expression of a variable name is evaluated, within the context of that evaluation, the innermost scope (in terms of parentheses) is checked first for the value of that variable, and then outer scopes are checked sequentially. It is guaranteed that every expression is legal. Please see the examples for more details on the scope.

**Example 1:**

**Input:** expression =  "(let x 2 (mult x (let x 3 y 4 (add x y)))) "
**Output:** 14
**Explanation:** In the expression (add x y), when checking for the value of the variable x,
we check from the innermost scope to the outermost in the context of the variable we are trying to evaluate.
Since x = 3 is found first, the value of x is 3.

**Example 2:**

**Input:** expression =  "(let x 3 x 2 x) "
**Output:** 2
**Explanation:** Assignment in let statements is processed sequentially.

**Example 3:**

**Input:** expression =  "(let x 1 y 2 x (add x y) (add x y)) "
**Output:** 5
**Explanation:** The first (add x y) evaluates as 3, and is assigned to x.
The second (add x y) evaluates as 3+2 = 5.

**Constraints:**

*   `1 <= expression.length <= 2000`
*   There are no leading or trailing spaces in `expression`.
*   All tokens are separated by a single space in `expression`.
*   The answer and all intermediate calculations of that answer are guaranteed to fit in a **32-bit** integer.
*   The expression is guaranteed to be legal and evaluate to an integer.
Sentence Similarity II

We can represent a sentence as an array of words, for example, the sentence `"I am happy with leetcode "` can be represented as `arr = [ "I ", "am ",happy ", "with ", "leetcode "]`.

Given two sentences `sentence1` and `sentence2` each represented as a string array and given an array of string pairs `similarPairs` where `similarPairs[i] = [xi, yi]` indicates that the two words `xi` and `yi` are similar.

Return `true` _if `sentence1` and `sentence2` are similar, or_ `false` _if they are not similar_.

Two sentences are similar if:

*   They have **the same length** (i.e., the same number of words)
*   `sentence1[i]` and `sentence2[i]` are similar.

Notice that a word is always similar to itself, also notice that the similarity relation is transitive. For example, if the words `a` and `b` are similar, and the words `b` and `c` are similar, then `a` and `c` are **similar**.

**Example 1:**

**Input:** sentence1 = \[ "great ", "acting ", "skills "\], sentence2 = \[ "fine ", "drama ", "talent "\], similarPairs = \[\[ "great ", "good "\],\[ "fine ", "good "\],\[ "drama ", "acting "\],\[ "skills ", "talent "\]\]
**Output:** true
**Explanation:** The two sentences have the same length and each word i of sentence1 is also similar to the corresponding word in sentence2.

**Example 2:**

**Input:** sentence1 = \[ "I ", "love ", "leetcode "\], sentence2 = \[ "I ", "love ", "onepiece "\], similarPairs = \[\[ "manga ", "onepiece "\],\[ "platform ", "anime "\],\[ "leetcode ", "platform "\],\[ "anime ", "manga "\]\]
**Output:** true
**Explanation:**  "leetcode " -->  "platform " -->  "anime " -->  "manga " -->  "onepiece ".
Since  "leetcode is similar to  "onepiece " and the first two words are the same, the two sentences are similar.

**Example 3:**

**Input:** sentence1 = \[ "I ", "love ", "leetcode "\], sentence2 = \[ "I ", "love ", "onepiece "\], similarPairs = \[\[ "manga ", "hunterXhunter "\],\[ "platform ", "anime "\],\[ "leetcode ", "platform "\],\[ "anime ", "manga "\]\]
**Output:** false
**Explanation:**  "leetcode " is not similar to  "onepiece ".

**Constraints:**

*   `1 <= sentence1.length, sentence2.length <= 1000`
*   `1 <= sentence1[i].length, sentence2[i].length <= 20`
*   `sentence1[i]` and `sentence2[i]` consist of lower-case and upper-case English letters.
*   `0 <= similarPairs.length <= 2000`
*   `similarPairs[i].length == 2`
*   `1 <= xi.length, yi.length <= 20`
*   `xi` and `yi` consist of English letters.
Monotone Increasing Digits

An integer has **monotone increasing digits** if and only if each pair of adjacent digits `x` and `y` satisfy `x <= y`.

Given an integer `n`, return _the largest number that is less than or equal to_ `n` _with **monotone increasing digits**_.

**Example 1:**

**Input:** n = 10
**Output:** 9

**Example 2:**

**Input:** n = 1234
**Output:** 1234

**Example 3:**

**Input:** n = 332
**Output:** 299

**Constraints:**

*   `0 <= n <= 109`
Daily Temperatures

Given an array of integers `temperatures` represents the daily temperatures, return _an array_ `answer` _such that_ `answer[i]` _is the number of days you have to wait after the_ `ith` _day to get a warmer temperature_. If there is no future day for which this is possible, keep `answer[i] == 0` instead.

**Example 1:**

**Input:** temperatures = \[73,74,75,71,69,72,76,73\]
**Output:** \[1,1,4,2,1,1,0,0\]

**Example 2:**

**Input:** temperatures = \[30,40,50,60\]
**Output:** \[1,1,1,0\]

**Example 3:**

**Input:** temperatures = \[30,60,90\]
**Output:** \[1,1,0\]

**Constraints:**

*   `1 <= temperatures.length <= 105`
*   `30 <= temperatures[i] <= 100`
Delete and Earn

You are given an integer array `nums`. You want to maximize the number of points you get by performing the following operation any number of times:

*   Pick any `nums[i]` and delete it to earn `nums[i]` points. Afterwards, you must delete **every** element equal to `nums[i] - 1` and **every** element equal to `nums[i] + 1`.

Return _the **maximum number of points** you can earn by applying the above operation some number of times_.

**Example 1:**

**Input:** nums = \[3,4,2\]
**Output:** 6
**Explanation:** You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = \[2\].
- Delete 2 to earn 2 points. nums = \[\].
You earn a total of 6 points.

**Example 2:**

**Input:** nums = \[2,2,3,3,3,4\]
**Output:** 9
**Explanation:** You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = \[3,3\].
- Delete a 3 again to earn 3 points. nums = \[3\].
- Delete a 3 once more to earn 3 points. nums = \[\].
You earn a total of 9 points.

**Constraints:**

*   `1 <= nums.length <= 2 * 104`
*   `1 <= nums[i] <= 104`
Cherry Pickup

You are given an `n x n` `grid` representing a field of cherries, each cell is one of three possible integers.

*   `0` means the cell is empty, so you can pass through,
*   `1` means the cell contains a cherry that you can pick up and pass through, or
*   `-1` means the cell contains a thorn that blocks your way.

Return _the maximum number of cherries you can collect by following the rules below_:

*   Starting at the position `(0, 0)` and reaching `(n - 1, n - 1)` by moving right or down through valid path cells (cells with value `0` or `1`).
*   After reaching `(n - 1, n - 1)`, returning to `(0, 0)` by moving left or up through valid path cells.
*   When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell `0`.
*   If there is no valid path between `(0, 0)` and `(n - 1, n - 1)`, then no cherries can be collected.

**Example 1:**

**Input:** grid = \[\[0,1,-1\],\[1,0,-1\],\[1,1,1\]\]
**Output:** 5
**Explanation:** The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes \[\[0,1,-1\],\[0,0,-1\],\[0,0,0\]\].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.

**Example 2:**

**Input:** grid = \[\[1,1,-1\],\[1,-1,1\],\[-1,1,1\]\]
**Output:** 0

**Constraints:**

*   `n == grid.length`
*   `n == grid[i].length`
*   `1 <= n <= 50`
*   `grid[i][j]` is `-1`, `0`, or `1`.
*   `grid[0][0] != -1`
*   `grid[n - 1][n - 1] != -1`
Closest Leaf in a Binary Tree

Given the `root` of a binary tree where every node has **a unique value** and a target integer `k`, return _the value of the **nearest leaf node** to the target_ `k` _in the tree_.

**Nearest to a leaf** means the least number of edges traveled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

**Example 1:**

**Input:** root = \[1,3,2\], k = 1
**Output:** 2
**Explanation:** Either 2 or 3 is the nearest leaf node to the target of 1.

**Example 2:**

**Input:** root = \[1\], k = 1
**Output:** 1
**Explanation:** The nearest leaf node is the root node itself.

**Example 3:**

**Input:** root = \[1,2,3,4,null,null,null,5,null,6\], k = 2
**Output:** 3
**Explanation:** The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 1000]`.
*   `1 <= Node.val <= 1000`
*   All the values of the tree are **unique**.
*   There exist some node in the tree where `Node.val == k`.
Network Delay Time

You are given a network of `n` nodes, labeled from `1` to `n`. You are also given `times`, a list of travel times as directed edges `times[i] = (ui, vi, wi)`, where `ui` is the source node, `vi` is the target node, and `wi` is the time it takes for a signal to travel from source to target.

We will send a signal from a given node `k`. Return _the **minimum** time it takes for all the_ `n` _nodes to receive the signal_. If it is impossible for all the `n` nodes to receive the signal, return `-1`.

**Example 1:**

**Input:** times = \[\[2,1,1\],\[2,3,1\],\[3,4,1\]\], n = 4, k = 2
**Output:** 2

**Example 2:**

**Input:** times = \[\[1,2,1\]\], n = 2, k = 1
**Output:** 1

**Example 3:**

**Input:** times = \[\[1,2,1\]\], n = 2, k = 2
**Output:** -1

**Constraints:**

*   `1 <= k <= n <= 100`
*   `1 <= times.length <= 6000`
*   `times[i].length == 3`
*   `1 <= ui, vi <= n`
*   `ui != vi`
*   `0 <= wi <= 100`
*   All the pairs `(ui, vi)` are **unique**. (i.e., no multiple edges.)
Find Smallest Letter Greater Than Target

You are given an array of characters `letters` that is sorted in **non-decreasing order**, and a character `target`. There are **at least two different** characters in `letters`.

Return _the smallest character in_ `letters` _that is lexicographically greater than_ `target`. If such a character does not exist, return the first character in `letters`.

**Example 1:**

**Input:** letters = \[ "c ", "f ", "j "\], target =  "a "
**Output:**  "c "
**Explanation:** The smallest character that is lexicographically greater than 'a' in letters is 'c'.

**Example 2:**

**Input:** letters = \[ "c ", "f ", "j "\], target =  "c "
**Output:**  "f "
**Explanation:** The smallest character that is lexicographically greater than 'c' in letters is 'f'.

**Example 3:**

**Input:** letters = \[ "x ", "x ", "y ", "y "\], target =  "z "
**Output:**  "x "
**Explanation:** There are no characters in letters that is lexicographically greater than 'z' so we return letters\[0\].

**Constraints:**

*   `2 <= letters.length <= 104`
*   `letters[i]` is a lowercase English letter.
*   `letters` is sorted in **non-decreasing** order.
*   `letters` contains at least two different characters.
*   `target` is a lowercase English letter.
Prefix and Suffix Search

Design a special dictionary that searches the words in it by a prefix and a suffix.

Implement the `WordFilter` class:

*   `WordFilter(string[] words)` Initializes the object with the `words` in the dictionary.
*   `f(string pref, string suff)` Returns _the index of the word in the dictionary,_ which has the prefix `pref` and the suffix `suff`. If there is more than one valid index, return **the largest** of them. If there is no such word in the dictionary, return `-1`.

**Example 1:**

**Input**
\[ "WordFilter ",  "f "\]
\[\[\[ "apple "\]\], \[ "a ",  "e "\]\]
**Output**
\[null, 0\]
**Explanation**
WordFilter wordFilter = new WordFilter(\[ "apple "\]);
wordFilter.f( "a ",  "e "); // return 0, because the word at index 0 has prefix =  "a " and suffix =  "e ".

**Constraints:**

*   `1 <= words.length <= 104`
*   `1 <= words[i].length <= 7`
*   `1 <= pref.length, suff.length <= 7`
*   `words[i]`, `pref` and `suff` consist of lowercase English letters only.
*   At most `104` calls will be made to the function `f`.
Min Cost Climbing Stairs

You are given an integer array `cost` where `cost[i]` is the cost of `ith` step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index `0`, or the step with index `1`.

Return _the minimum cost to reach the top of the floor_.

**Example 1:**

**Input:** cost = \[10,15,20\]
**Output:** 15
**Explanation:** You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

**Example 2:**

**Input:** cost = \[1,100,1,1,1,100,1,1,100,1\]
**Output:** 6
**Explanation:** You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

**Constraints:**

*   `2 <= cost.length <= 1000`
*   `0 <= cost[i] <= 999`
Largest Number At Least Twice of Others

You are given an integer array `nums` where the largest integer is **unique**.

Determine whether the largest element in the array is **at least twice** as much as every other number in the array. If it is, return _the **index** of the largest element, or return_ `-1` _otherwise_.

**Example 1:**

**Input:** nums = \[3,6,1,0\]
**Output:** 1
**Explanation:** 6 is the largest integer.
For every other number in the array x, 6 is at least twice as big as x.
The index of value 6 is 1, so we return 1.

**Example 2:**

**Input:** nums = \[1,2,3,4\]
**Output:** -1
**Explanation:** 4 is less than twice the value of 3, so we return -1.

**Constraints:**

*   `2 <= nums.length <= 50`
*   `0 <= nums[i] <= 100`
*   The largest element in `nums` is unique.
Shortest Completing Word

Given a string `licensePlate` and an array of strings `words`, find the **shortest completing** word in `words`.

A **completing** word is a word that **contains all the letters** in `licensePlate`. **Ignore numbers and spaces** in `licensePlate`, and treat letters as **case insensitive**. If a letter appears more than once in `licensePlate`, then it must appear in the word the same number of times or more.

For example, if `licensePlate` `= "aBc 12c "`, then it contains letters `'a'`, `'b'` (ignoring case), and `'c'` twice. Possible **completing** words are `"abccdef "`, `"caaacab "`, and `"cbca "`.

Return _the shortest **completing** word in_ `words`_._ It is guaranteed an answer exists. If there are multiple shortest **completing** words, return the **first** one that occurs in `words`.

**Example 1:**

**Input:** licensePlate =  "1s3 PSt ", words = \[ "step ", "steps ", "stripe ", "stepple "\]
**Output:**  "steps "
**Explanation:** licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'.
 "step " contains 't' and 'p', but only contains 1 's'.
 "steps " contains 't', 'p', and both 's' characters.
 "stripe " is missing an 's'.
 "stepple " is missing an 's'.
Since  "steps " is the only word containing all the letters, that is the answer.

**Example 2:**

**Input:** licensePlate =  "1s3 456 ", words = \[ "looks ", "pest ", "stew ", "show "\]
**Output:**  "pest "
**Explanation:** licensePlate only contains the letter 's'. All the words contain 's', but among these  "pest ",  "stew ", and  "show " are shortest. The answer is  "pest " because it is the word that appears earliest of the 3.

**Constraints:**

*   `1 <= licensePlate.length <= 7`
*   `licensePlate` contains digits, letters (uppercase or lowercase), or space `' '`.
*   `1 <= words.length <= 1000`
*   `1 <= words[i].length <= 15`
*   `words[i]` consists of lower case English letters.