bowang0911/leetcode huggingface dataset:
Trim a Binary Search Tree

Given the `root` of a binary search tree and the lowest and highest boundaries as `low` and `high`, trim the tree so that all its elements lies in `[low, high]`. Trimming the tree should **not** change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a **unique answer**.

Return _the root of the trimmed binary search tree_. Note that the root may change depending on the given bounds.

**Example 1:**

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

**Example 2:**

**Input:** root = \[3,0,4,null,2,null,null,1\], low = 1, high = 3
**Output:** \[3,2,null,1\]

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `0 <= Node.val <= 104`
*   The value of each node in the tree is **unique**.
*   `root` is guaranteed to be a valid binary search tree.
*   `0 <= low <= high <= 104`
Maximum Swap

You are given an integer `num`. You can swap two digits at most once to get the maximum valued number.

Return _the maximum valued number you can get_.

**Example 1:**

**Input:** num = 2736
**Output:** 7236
**Explanation:** Swap the number 2 and the number 7.

**Example 2:**

**Input:** num = 9973
**Output:** 9973
**Explanation:** No swap.

**Constraints:**

*   `0 <= num <= 108`
Second Minimum Node In a Binary Tree

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly `two` or `zero` sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes. More formally, the property `root.val = min(root.left.val, root.right.val)` always holds.

Given such a binary tree, you need to output the **second minimum** value in the set made of all the nodes' value in the whole tree.

If no such second minimum value exists, output -1 instead.

**Example 1:**

**Input:** root = \[2,2,5,null,null,5,7\]
**Output:** 5
**Explanation:** The smallest value is 2, the second smallest value is 5.

**Example 2:**

**Input:** root = \[2,2,2\]
**Output:** -1
**Explanation:** The smallest value is 2, but there isn't any second smallest value.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 25]`.
*   `1 <= Node.val <= 231 - 1`
*   `root.val == min(root.left.val, root.right.val)` for each internal node of the tree.
Bulb Switcher II

There is a room with `n` bulbs labeled from `1` to `n` that all are turned on initially, and **four buttons** on the wall. Each of the four buttons has a different functionality where:

*   **Button 1:** Flips the status of all the bulbs.
*   **Button 2:** Flips the status of all the bulbs with even labels (i.e., `2, 4, ...`).
*   **Button 3:** Flips the status of all the bulbs with odd labels (i.e., `1, 3, ...`).
*   **Button 4:** Flips the status of all the bulbs with a label `j = 3k + 1` where `k = 0, 1, 2, ...` (i.e., `1, 4, 7, 10, ...`).

You must make **exactly** `presses` button presses in total. For each press, you may pick **any** of the four buttons to press.

Given the two integers `n` and `presses`, return _the number of **different possible statuses** after performing all_ `presses` _button presses_.

**Example 1:**

**Input:** n = 1, presses = 1
**Output:** 2
**Explanation:** Status can be:
- \[off\] by pressing button 1
- \[on\] by pressing button 2

**Example 2:**

**Input:** n = 2, presses = 1
**Output:** 3
**Explanation:** Status can be:
- \[off, off\] by pressing button 1
- \[on, off\] by pressing button 2
- \[off, on\] by pressing button 3

**Example 3:**

**Input:** n = 3, presses = 1
**Output:** 4
**Explanation:** Status can be:
- \[off, off, off\] by pressing button 1
- \[off, on, off\] by pressing button 2
- \[on, off, on\] by pressing button 3
- \[off, on, on\] by pressing button 4

**Constraints:**

*   `1 <= n <= 1000`
*   `0 <= presses <= 1000`
Number of Longest Increasing Subsequence

Given an integer array `nums`, return _the number of longest increasing subsequences._

**Notice** that the sequence has to be **strictly** increasing.

**Example 1:**

**Input:** nums = \[1,3,5,4,7\]
**Output:** 2
**Explanation:** The two longest increasing subsequences are \[1, 3, 4, 7\] and \[1, 3, 5, 7\].

**Example 2:**

**Input:** nums = \[2,2,2,2,2\]
**Output:** 5
**Explanation:** The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

**Constraints:**

*   `1 <= nums.length <= 2000`
*   `-106 <= nums[i] <= 106`
Longest Continuous Increasing Subsequence

Given an unsorted array of integers `nums`, return _the length of the longest **continuous increasing subsequence** (i.e. subarray)_. The subsequence must be **strictly** increasing.

A **continuous increasing subsequence** is defined by two indices `l` and `r` (`l < r`) such that it is `[nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]` and for each `l <= i < r`, `nums[i] < nums[i + 1]`.

**Example 1:**

**Input:** nums = \[1,3,5,4,7\]
**Output:** 3
**Explanation:** The longest continuous increasing subsequence is \[1,3,5\] with length 3.
Even though \[1,3,5,7\] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

**Example 2:**

**Input:** nums = \[2,2,2,2,2\]
**Output:** 1
**Explanation:** The longest continuous increasing subsequence is \[2\] with length 1. Note that it must be strictly
increasing.

**Constraints:**

*   `1 <= nums.length <= 104`
*   `-109 <= nums[i] <= 109`
Cut Off Trees for Golf Event

You are asked to cut off all the trees in a forest for a golf event. The forest is represented as an `m x n` matrix. In this matrix:

*   `0` means the cell cannot be walked through.
*   `1` represents an empty cell that can be walked through.
*   A number greater than `1` represents a tree in a cell that can be walked through, and this number is the tree's height.

In one step, you can walk in any of the four directions: north, east, south, and west. If you are standing in a cell with a tree, you can choose whether to cut it off.

You must cut off the trees in order from shortest to tallest. When you cut off a tree, the value at its cell becomes `1` (an empty cell).

Starting from the point `(0, 0)`, return _the minimum steps you need to walk to cut off all the trees_. If you cannot cut off all the trees, return `-1`.

**Note:** The input is generated such that no two trees have the same height, and there is at least one tree needs to be cut off.

**Example 1:**

**Input:** forest = \[\[1,2,3\],\[0,0,4\],\[7,6,5\]\]
**Output:** 6
**Explanation:** Following the path above allows you to cut off the trees from shortest to tallest in 6 steps.

**Example 2:**

**Input:** forest = \[\[1,2,3\],\[0,0,0\],\[7,6,5\]\]
**Output:** -1
**Explanation:** The trees in the bottom row cannot be accessed as the middle row is blocked.

**Example 3:**

**Input:** forest = \[\[2,3,4\],\[0,0,5\],\[8,7,6\]\]
**Output:** 6
**Explanation:** You can follow the same path as Example 1 to cut off all the trees.
Note that you can cut off the first tree at (0, 0) before making any steps.

**Constraints:**

*   `m == forest.length`
*   `n == forest[i].length`
*   `1 <= m, n <= 50`
*   `0 <= forest[i][j] <= 109`
*   Heights of all trees are **distinct**.
Implement Magic Dictionary

Design a data structure that is initialized with a list of **different** words. Provided a string, you should determine if you can change exactly one character in this string to match any word in the data structure.

Implement the `MagicDictionary` class:

*   `MagicDictionary()` Initializes the object.
*   `void buildDict(String[] dictionary)` Sets the data structure with an array of distinct strings `dictionary`.
*   `bool search(String searchWord)` Returns `true` if you can change **exactly one character** in `searchWord` to match any string in the data structure, otherwise returns `false`.

**Example 1:**

**Input**
\[ "MagicDictionary ",  "buildDict ",  "search ",  "search ",  "search ",  "search "\]
\[\[\], \[\[ "hello ",  "leetcode "\]\], \[ "hello "\], \[ "hhllo "\], \[ "hell "\], \[ "leetcoded "\]\]
**Output**
\[null, null, false, true, false, false\]

**Explanation**
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict(\[ "hello ",  "leetcode "\]);
magicDictionary.search( "hello "); // return False
magicDictionary.search( "hhllo "); // We can change the second 'h' to 'e' to match  "hello " so we return True
magicDictionary.search( "hell "); // return False
magicDictionary.search( "leetcoded "); // return False

**Constraints:**

*   `1 <= dictionary.length <= 100`
*   `1 <= dictionary[i].length <= 100`
*   `dictionary[i]` consists of only lower-case English letters.
*   All the strings in `dictionary` are **distinct**.
*   `1 <= searchWord.length <= 100`
*   `searchWord` consists of only lower-case English letters.
*   `buildDict` will be called only once before `search`.
*   At most `100` calls will be made to `search`.
Map Sum Pairs

Design a map that allows you to do the following:

*   Maps a string key to a given value.
*   Returns the sum of the values that have a key with a prefix equal to a given string.

Implement the `MapSum` class:

*   `MapSum()` Initializes the `MapSum` object.
*   `void insert(String key, int val)` Inserts the `key-val` pair into the map. If the `key` already existed, the original `key-value` pair will be overridden to the new one.
*   `int sum(string prefix)` Returns the sum of all the pairs' value whose `key` starts with the `prefix`.

**Example 1:**

**Input**
\[ "MapSum ",  "insert ",  "sum ",  "insert ",  "sum "\]
\[\[\], \[ "apple ", 3\], \[ "ap "\], \[ "app ", 2\], \[ "ap "\]\]
**Output**
\[null, null, 3, null, 5\]

**Explanation**
MapSum mapSum = new MapSum();
mapSum.insert( "apple ", 3);  
mapSum.sum( "ap ");           // return 3 (apple = 3)
mapSum.insert( "app ", 2);    
mapSum.sum( "ap ");           // return 5 (apple + app = 3 + 2 = 5)

**Constraints:**

*   `1 <= key.length, prefix.length <= 50`
*   `key` and `prefix` consist of only lowercase English letters.
*   `1 <= val <= 1000`
*   At most `50` calls will be made to `insert` and `sum`.
Valid Parenthesis String

Given a string `s` containing only three types of characters: `'('`, `')'` and `'*'`, return `true` _if_ `s` _is **valid**_.

The following rules define a **valid** string:

*   Any left parenthesis `'('` must have a corresponding right parenthesis `')'`.
*   Any right parenthesis `')'` must have a corresponding left parenthesis `'('`.
*   Left parenthesis `'('` must go before the corresponding right parenthesis `')'`.
*   `'*'` could be treated as a single right parenthesis `')'` or a single left parenthesis `'('` or an empty string `" "`.

**Example 1:**

**Input:** s = "()"
**Output:** true

**Example 2:**

**Input:** s = "(\*)"
**Output:** true

**Example 3:**

**Input:** s = "(\*))"
**Output:** true

**Constraints:**

*   `1 <= s.length <= 100`
*   `s[i]` is `'('`, `')'` or `'*'`.
24 Game

You are given an integer array `cards` of length `4`. You have four cards, each containing a number in the range `[1, 9]`. You should arrange the numbers on these cards in a mathematical expression using the operators `['+', '-', '*', '/']` and the parentheses `'('` and `')'` to get the value 24.

You are restricted with the following rules:

*   The division operator `'/'` represents real division, not integer division.
    *   For example, `4 / (1 - 2 / 3) = 4 / (1 / 3) = 12`.
*   Every operation done is between two numbers. In particular, we cannot use `'-'` as a unary operator.
    *   For example, if `cards = [1, 1, 1, 1]`, the expression `"-1 - 1 - 1 - 1 "` is **not allowed**.
*   You cannot concatenate numbers together
    *   For example, if `cards = [1, 2, 1, 2]`, the expression `"12 + 12 "` is not valid.

Return `true` if you can get such expression that evaluates to `24`, and `false` otherwise.

**Example 1:**

**Input:** cards = \[4,1,8,7\]
**Output:** true
**Explanation:** (8-4) \* (7-1) = 24

**Example 2:**

**Input:** cards = \[1,2,1,2\]
**Output:** false

**Constraints:**

*   `cards.length == 4`
*   `1 <= cards[i] <= 9`
Valid Palindrome II

Given a string `s`, return `true` _if the_ `s` _can be palindrome after deleting **at most one** character from it_.

**Example 1:**

**Input:** s =  "aba "
**Output:** true

**Example 2:**

**Input:** s =  "abca "
**Output:** true
**Explanation:** You could delete the character 'c'.

**Example 3:**

**Input:** s =  "abc "
**Output:** false

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of lowercase English letters.
Next Closest Time

Given a `time` represented in the format `"HH:MM "`, form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, `"01:34 "`, `"12:09 "` are all valid. `"1:34 "`, `"12:9 "` are all invalid.

**Example 1:**

**Input:** time =  "19:34 "
**Output:**  "19:39 "
**Explanation:** The next closest time choosing from digits **1**, **9**, **3**, **4**, is **19:39**, which occurs 5 minutes later.
It is not **19:33**, because this occurs 23 hours and 59 minutes later.

**Example 2:**

**Input:** time =  "23:59 "
**Output:**  "22:22 "
**Explanation:** The next closest time choosing from digits **2**, **3**, **5**, **9**, is **22:22**.
It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

**Constraints:**

*   `time.length == 5`
*   `time` is a valid time in the form `"HH:MM "`.
*   `0 <= HH < 24`
*   `0 <= MM < 60`
Baseball Game

You are keeping the scores for a baseball game with strange rules. At the beginning of the game, you start with an empty record.

You are given a list of strings `operations`, where `operations[i]` is the `ith` operation you must apply to the record and is one of the following:

*   An integer `x`.
    *   Record a new score of `x`.
*   `'+'`.
    *   Record a new score that is the sum of the previous two scores.
*   `'D'`.
    *   Record a new score that is the double of the previous score.
*   `'C'`.
    *   Invalidate the previous score, removing it from the record.

Return _the sum of all the scores on the record after applying all the operations_.

The test cases are generated such that the answer and all intermediate calculations fit in a **32-bit** integer and that all operations are valid.

**Example 1:**

**Input:** ops = \[ "5 ", "2 ", "C ", "D ", "+ "\]
**Output:** 30
**Explanation:**
 "5 " - Add 5 to the record, record is now \[5\].
 "2 " - Add 2 to the record, record is now \[5, 2\].
 "C " - Invalidate and remove the previous score, record is now \[5\].
 "D " - Add 2 \* 5 = 10 to the record, record is now \[5, 10\].
 "+ " - Add 5 + 10 = 15 to the record, record is now \[5, 10, 15\].
The total sum is 5 + 10 + 15 = 30.

**Example 2:**

**Input:** ops = \[ "5 ", "-2 ", "4 ", "C ", "D ", "9 ", "+ ", "+ "\]
**Output:** 27
**Explanation:**
 "5 " - Add 5 to the record, record is now \[5\].
 "-2 " - Add -2 to the record, record is now \[5, -2\].
 "4 " - Add 4 to the record, record is now \[5, -2, 4\].
 "C " - Invalidate and remove the previous score, record is now \[5, -2\].
 "D " - Add 2 \* -2 = -4 to the record, record is now \[5, -2, -4\].
 "9 " - Add 9 to the record, record is now \[5, -2, -4, 9\].
 "+ " - Add -4 + 9 = 5 to the record, record is now \[5, -2, -4, 9, 5\].
 "+ " - Add 9 + 5 = 14 to the record, record is now \[5, -2, -4, 9, 5, 14\].
The total sum is 5 + -2 + -4 + 9 + 5 + 14 = 27.

**Example 3:**

**Input:** ops = \[ "1 ", "C "\]
**Output:** 0
**Explanation:**
 "1 " - Add 1 to the record, record is now \[1\].
 "C " - Invalidate and remove the previous score, record is now \[\].
Since the record is empty, the total sum is 0.

**Constraints:**

*   `1 <= operations.length <= 1000`
*   `operations[i]` is `"C "`, `"D "`, `"+ "`, or a string representing an integer in the range `[-3 * 104, 3 * 104]`.
*   For operation `"+ "`, there will always be at least two previous scores on the record.
*   For operations `"C "` and `"D "`, there will always be at least one previous score on the record.
K Empty Slots

You have `n` bulbs in a row numbered from `1` to `n`. Initially, all the bulbs are turned off. We turn on **exactly one** bulb every day until all bulbs are on after `n` days.

You are given an array `bulbs` of length `n` where `bulbs[i] = x` means that on the `(i+1)th` day, we will turn on the bulb at position `x` where `i` is **0-indexed** and `x` is **1-indexed.**

Given an integer `k`, return _the **minimum day number** such that there exists two **turned on** bulbs that have **exactly** `k` bulbs between them that are **all turned off**. If there isn't such day, return `-1`._

**Example 1:**

**Input:** bulbs = \[1,3,2\], k = 1
**Output:** 2
**Explanation:**
On the first day: bulbs\[0\] = 1, first bulb is turned on: \[1,0,0\]
On the second day: bulbs\[1\] = 3, third bulb is turned on: \[1,0,1\]
On the third day: bulbs\[2\] = 2, second bulb is turned on: \[1,1,1\]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.

**Example 2:**

**Input:** bulbs = \[1,2,3\], k = 1
**Output:** -1

**Constraints:**

*   `n == bulbs.length`
*   `1 <= n <= 2 * 104`
*   `1 <= bulbs[i] <= n`
*   `bulbs` is a permutation of numbers from `1` to `n`.
*   `0 <= k <= 2 * 104`
Redundant Connection

In this problem, a tree is an **undirected graph** that is connected and has no cycles.

You are given a graph that started as a tree with `n` nodes labeled from `1` to `n`, with one additional edge added. The added edge has two **different** vertices chosen from `1` to `n`, and was not an edge that already existed. The graph is represented as an array `edges` of length `n` where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the graph.

Return _an edge that can be removed so that the resulting graph is a tree of_ `n` _nodes_. If there are multiple answers, return the answer that occurs last in the input.

**Example 1:**

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

**Example 2:**

**Input:** edges = \[\[1,2\],\[2,3\],\[3,4\],\[1,4\],\[1,5\]\]
**Output:** \[1,4\]

**Constraints:**

*   `n == edges.length`
*   `3 <= n <= 1000`
*   `edges[i].length == 2`
*   `1 <= ai < bi <= edges.length`
*   `ai != bi`
*   There are no repeated edges.
*   The given graph is connected.
Redundant Connection II

In this problem, a rooted tree is a **directed** graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.

The given input is a directed graph that started as a rooted tree with `n` nodes (with distinct values from `1` to `n`), with one additional directed edge added. The added edge has two different vertices chosen from `1` to `n`, and was not an edge that already existed.

The resulting graph is given as a 2D-array of `edges`. Each element of `edges` is a pair `[ui, vi]` that represents a **directed** edge connecting nodes `ui` and `vi`, where `ui` is a parent of child `vi`.

Return _an edge that can be removed so that the resulting graph is a rooted tree of_ `n` _nodes_. If there are multiple answers, return the answer that occurs last in the given 2D-array.

**Example 1:**

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

**Example 2:**

**Input:** edges = \[\[1,2\],\[2,3\],\[3,4\],\[4,1\],\[1,5\]\]
**Output:** \[4,1\]

**Constraints:**

*   `n == edges.length`
*   `3 <= n <= 1000`
*   `edges[i].length == 2`
*   `1 <= ui, vi <= n`
*   `ui != vi`
Repeated String Match

Given two strings `a` and `b`, return _the minimum number of times you should repeat string_ `a` _so that string_ `b` _is a substring of it_. If it is impossible for `b`​​​​​​ to be a substring of `a` after repeating it, return `-1`.

**Notice:** string `"abc "` repeated 0 times is `" "`, repeated 1 time is `"abc "` and repeated 2 times is `"abcabc "`.

**Example 1:**

**Input:** a =  "abcd ", b =  "cdabcdab "
**Output:** 3
**Explanation:** We return 3 because by repeating a three times  "ab**cdabcdab**cd ", b is a substring of it.

**Example 2:**

**Input:** a =  "a ", b =  "aa "
**Output:** 2

**Constraints:**

*   `1 <= a.length, b.length <= 104`
*   `a` and `b` consist of lowercase English letters.
Longest Univalue Path

Given the `root` of a binary tree, return _the length of the longest path, where each node in the path has the same value_. This path may or may not pass through the root.

**The length of the path** between two nodes is represented by the number of edges between them.

**Example 1:**

**Input:** root = \[5,4,5,1,1,null,5\]
**Output:** 2
**Explanation:** The shown image shows that the longest path of the same value (i.e. 5).

**Example 2:**

**Input:** root = \[1,4,5,4,4,null,5\]
**Output:** 2
**Explanation:** The shown image shows that the longest path of the same value (i.e. 4).

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 104]`.
*   `-1000 <= Node.val <= 1000`
*   The depth of the tree will not exceed `1000`.
Knight Probability in Chessboard

On an `n x n` chessboard, a knight starts at the cell `(row, column)` and attempts to make exactly `k` moves. The rows and columns are **0-indexed**, so the top-left cell is `(0, 0)`, and the bottom-right cell is `(n - 1, n - 1)`.

A chess knight has eight possible moves it can make, as illustrated below. Each move is two cells in a cardinal direction, then one cell in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly `k` moves or has moved off the chessboard.

Return _the probability that the knight remains on the board after it has stopped moving_.

**Example 1:**

**Input:** n = 3, k = 2, row = 0, column = 0
**Output:** 0.06250
**Explanation:** There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

**Example 2:**

**Input:** n = 1, k = 0, row = 0, column = 0
**Output:** 1.00000

**Constraints:**

*   `1 <= n <= 25`
*   `0 <= k <= 100`
*   `0 <= row, column <= n - 1`
Maximum Sum of 3 Non-Overlapping Subarrays

Given an integer array `nums` and an integer `k`, find three non-overlapping subarrays of length `k` with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (**0-indexed**). If there are multiple answers, return the lexicographically smallest one.

**Example 1:**

**Input:** nums = \[1,2,1,2,6,7,5,1\], k = 2
**Output:** \[0,3,5\]
**Explanation:** Subarrays \[1, 2\], \[2, 6\], \[7, 5\] correspond to the starting indices \[0, 3, 5\].
We could have also taken \[2, 1\], but an answer of \[1, 3, 5\] would be lexicographically larger.

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 2 * 104`
*   `1 <= nums[i] < 216`
*   `1 <= k <= floor(nums.length / 3)`