bowang0911/leetcode huggingface dataset:
The Maze III

There is a ball in a `maze` with empty spaces (represented as `0`) and walls (represented as `1`). The ball can go through the empty spaces by rolling **up, down, left or right**, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction. There is also a hole in this maze. The ball will drop into the hole if it rolls onto the hole.

Given the `m x n` `maze`, the ball's position `ball` and the hole's position `hole`, where `ball = [ballrow, ballcol]` and `hole = [holerow, holecol]`, return _a string_ `instructions` _of all the instructions that the ball should follow to drop in the hole with the **shortest distance** possible_. If there are multiple valid instructions, return the **lexicographically minimum** one. If the ball can't drop in the hole, return `"impossible "`.

If there is a way for the ball to drop in the hole, the answer `instructions` should contain the characters `'u'` (i.e., up), `'d'` (i.e., down), `'l'` (i.e., left), and `'r'` (i.e., right).

The **distance** is the number of **empty spaces** traveled by the ball from the start position (excluded) to the destination (included).

You may assume that **the borders of the maze are all walls** (see examples).

**Example 1:**

**Input:** maze = \[\[0,0,0,0,0\],\[1,1,0,0,1\],\[0,0,0,0,0\],\[0,1,0,0,1\],\[0,1,0,0,0\]\], ball = \[4,3\], hole = \[0,1\]
**Output:**  "lul "
**Explanation:** There are two shortest ways for the ball to drop into the hole.
The first way is left -> up -> left, represented by  "lul ".
The second way is up -> left, represented by 'ul'.
Both ways have shortest distance 6, but the first way is lexicographically smaller because 'l' < 'u'. So the output is  "lul ".

**Example 2:**

**Input:** maze = \[\[0,0,0,0,0\],\[1,1,0,0,1\],\[0,0,0,0,0\],\[0,1,0,0,1\],\[0,1,0,0,0\]\], ball = \[4,3\], hole = \[3,0\]
**Output:**  "impossible "
**Explanation:** The ball cannot reach the hole.

**Example 3:**

**Input:** maze = \[\[0,0,0,0,0,0,0\],\[0,0,1,0,0,1,0\],\[0,0,0,0,1,0,0\],\[0,0,0,0,0,0,1\]\], ball = \[0,4\], hole = \[3,5\]
**Output:**  "dldr "

**Constraints:**

*   `m == maze.length`
*   `n == maze[i].length`
*   `1 <= m, n <= 100`
*   `maze[i][j]` is `0` or `1`.
*   `ball.length == 2`
*   `hole.length == 2`
*   `0 <= ballrow, holerow <= m`
*   `0 <= ballcol, holecol <= n`
*   Both the ball and the hole exist in an empty space, and they will not be in the same position initially.
*   The maze contains **at least 2 empty spaces**.
Keyboard Row

Given an array of strings `words`, return _the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below_.

In the **American keyboard**:

*   the first row consists of the characters `"qwertyuiop "`,
*   the second row consists of the characters `"asdfghjkl "`, and
*   the third row consists of the characters `"zxcvbnm "`.

**Example 1:**

**Input:** words = \[ "Hello ", "Alaska ", "Dad ", "Peace "\]
**Output:** \[ "Alaska ", "Dad "\]

**Example 2:**

**Input:** words = \[ "omk "\]
**Output:** \[\]

**Example 3:**

**Input:** words = \[ "adsdf ", "sfd "\]
**Output:** \[ "adsdf ", "sfd "\]

**Constraints:**

*   `1 <= words.length <= 20`
*   `1 <= words[i].length <= 100`
*   `words[i]` consists of English letters (both lowercase and uppercase).
Find Mode in Binary Search Tree

Given the `root` of a binary search tree (BST) with duplicates, return _all the [mode(s)](https://en.wikipedia.org/wiki/Mode_(statistics)) (i.e., the most frequently occurred element) in it_.

If the tree has more than one mode, return them in **any order**.

Assume a BST is defined as follows:

*   The left subtree of a node contains only nodes with keys **less than or equal to** the node's key.
*   The right subtree of a node contains only nodes with keys **greater than or equal to** the node's key.
*   Both the left and right subtrees must also be binary search trees.

**Example 1:**

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

**Example 2:**

**Input:** root = \[0\]
**Output:** \[0\]

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `-105 <= Node.val <= 105`

**Follow up:** Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
IPO

Suppose LeetCode will start its **IPO** soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the **IPO**. Since it has limited resources, it can only finish at most `k` distinct projects before the **IPO**. Help LeetCode design the best way to maximize its total capital after finishing at most `k` distinct projects.

You are given `n` projects where the `ith` project has a pure profit `profits[i]` and a minimum capital of `capital[i]` is needed to start it.

Initially, you have `w` capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

Pick a list of **at most** `k` distinct projects from given projects to **maximize your final capital**, and return _the final maximized capital_.

The answer is guaranteed to fit in a 32-bit signed integer.

**Example 1:**

**Input:** k = 2, w = 0, profits = \[1,2,3\], capital = \[0,1,1\]
**Output:** 4
**Explanation:** Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

**Example 2:**

**Input:** k = 3, w = 0, profits = \[1,2,3\], capital = \[0,1,2\]
**Output:** 6

**Constraints:**

*   `1 <= k <= 105`
*   `0 <= w <= 109`
*   `n == profits.length`
*   `n == capital.length`
*   `1 <= n <= 105`
*   `0 <= profits[i] <= 104`
*   `0 <= capital[i] <= 109`
Next Greater Element II

Given a circular integer array `nums` (i.e., the next element of `nums[nums.length - 1]` is `nums[0]`), return _the **next greater number** for every element in_ `nums`.

The **next greater number** of a number `x` is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return `-1` for this number.

**Example 1:**

**Input:** nums = \[1,2,1\]
**Output:** \[2,-1,2\]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number. 
The second 1's next greater number needs to search circularly, which is also 2.

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 104`
*   `-109 <= nums[i] <= 109`
Base 7

Given an integer `num`, return _a string of its **base 7** representation_.

**Example 1:**

**Input:** num = 100
**Output:** "202"

**Example 2:**

**Input:** num = -7
**Output:** "-10"

**Constraints:**

*   `-107 <= num <= 107`
The Maze II

There is a ball in a `maze` with empty spaces (represented as `0`) and walls (represented as `1`). The ball can go through the empty spaces by rolling **up, down, left or right**, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the `m x n` `maze`, the ball's `start` position and the `destination`, where `start = [startrow, startcol]` and `destination = [destinationrow, destinationcol]`, return _the shortest **distance** for the ball to stop at the destination_. If the ball cannot stop at `destination`, return `-1`.

The **distance** is the number of **empty spaces** traveled by the ball from the start position (excluded) to the destination (included).

You may assume that **the borders of the maze are all walls** (see examples).

**Example 1:**

**Input:** maze = \[\[0,0,1,0,0\],\[0,0,0,0,0\],\[0,0,0,1,0\],\[1,1,0,1,1\],\[0,0,0,0,0\]\], start = \[0,4\], destination = \[4,4\]
**Output:** 12
**Explanation:** One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

**Example 2:**

**Input:** maze = \[\[0,0,1,0,0\],\[0,0,0,0,0\],\[0,0,0,1,0\],\[1,1,0,1,1\],\[0,0,0,0,0\]\], start = \[0,4\], destination = \[3,2\]
**Output:** -1
**Explanation:** There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.

**Example 3:**

**Input:** maze = \[\[0,0,0,0,0\],\[1,1,0,0,1\],\[0,0,0,0,0\],\[0,1,0,0,1\],\[0,1,0,0,0\]\], start = \[4,3\], destination = \[0,1\]
**Output:** -1

**Constraints:**

*   `m == maze.length`
*   `n == maze[i].length`
*   `1 <= m, n <= 100`
*   `maze[i][j]` is `0` or `1`.
*   `start.length == 2`
*   `destination.length == 2`
*   `0 <= startrow, destinationrow < m`
*   `0 <= startcol, destinationcol < n`
*   Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
*   The maze contains **at least 2 empty spaces**.
Relative Ranks

You are given an integer array `score` of size `n`, where `score[i]` is the score of the `ith` athlete in a competition. All the scores are guaranteed to be **unique**.

The athletes are **placed** based on their scores, where the `1st` place athlete has the highest score, the `2nd` place athlete has the `2nd` highest score, and so on. The placement of each athlete determines their rank:

*   The `1st` place athlete's rank is `"Gold Medal "`.
*   The `2nd` place athlete's rank is `"Silver Medal "`.
*   The `3rd` place athlete's rank is `"Bronze Medal "`.
*   For the `4th` place to the `nth` place athlete, their rank is their placement number (i.e., the `xth` place athlete's rank is `"x "`).

Return an array `answer` of size `n` where `answer[i]` is the **rank** of the `ith` athlete.

**Example 1:**

**Input:** score = \[5,4,3,2,1\]
**Output:** \[ "Gold Medal ", "Silver Medal ", "Bronze Medal ", "4 ", "5 "\]
**Explanation:** The placements are \[1st, 2nd, 3rd, 4th, 5th\].

**Example 2:**

**Input:** score = \[10,3,8,9,4\]
**Output:** \[ "Gold Medal ", "5 ", "Bronze Medal ", "Silver Medal ", "4 "\]
**Explanation:** The placements are \[1st, 5th, 3rd, 2nd, 4th\].

**Constraints:**

*   `n == score.length`
*   `1 <= n <= 104`
*   `0 <= score[i] <= 106`
*   All the values in `score` are **unique**.
Perfect Number

A [**perfect number**](https://en.wikipedia.org/wiki/Perfect_number) is a **positive integer** that is equal to the sum of its **positive divisors**, excluding the number itself. A **divisor** of an integer `x` is an integer that can divide `x` evenly.

Given an integer `n`, return `true` _if_ `n` _is a perfect number, otherwise return_ `false`.

**Example 1:**

**Input:** num = 28
**Output:** true
**Explanation:** 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

**Example 2:**

**Input:** num = 7
**Output:** false

**Constraints:**

*   `1 <= num <= 108`
Most Frequent Subtree Sum

Given the `root` of a binary tree, return the most frequent **subtree sum**. If there is a tie, return all the values with the highest frequency in any order.

The **subtree sum** of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

**Example 1:**

**Input:** root = \[5,2,-3\]
**Output:** \[2,-3,4\]

**Example 2:**

**Input:** root = \[5,2,-5\]
**Output:** \[2\]

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `-105 <= Node.val <= 105`
Fibonacci Number

The **Fibonacci numbers**, commonly denoted `F(n)` form a sequence, called the **Fibonacci sequence**, such that each number is the sum of the two preceding ones, starting from `0` and `1`. That is,

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

Given `n`, calculate `F(n)`.

**Example 1:**

**Input:** n = 2
**Output:** 1
**Explanation:** F(2) = F(1) + F(0) = 1 + 0 = 1.

**Example 2:**

**Input:** n = 3
**Output:** 2
**Explanation:** F(3) = F(2) + F(1) = 1 + 1 = 2.

**Example 3:**

**Input:** n = 4
**Output:** 3
**Explanation:** F(4) = F(3) + F(2) = 2 + 1 = 3.

**Constraints:**

*   `0 <= n <= 30`
Inorder Successor in BST II

Given a `node` in a binary search tree, return _the in-order successor of that node in the BST_. If that node has no in-order successor, return `null`.

The successor of a `node` is the node with the smallest key greater than `node.val`.

You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node. Below is the definition for `Node`:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

**Example 1:**

**Input:** tree = \[2,1,3\], node = 1
**Output:** 2
**Explanation:** 1's in-order successor node is 2. Note that both the node and the return value is of Node type.

**Example 2:**

**Input:** tree = \[5,3,6,2,4,null,null,1\], node = 6
**Output:** null
**Explanation:** There is no in-order successor of the current node, so the answer is null.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `-105 <= Node.val <= 105`
*   All Nodes will have unique values.

**Follow up:** Could you solve it without looking up any of the node's values?
Find Bottom Left Tree Value

Given the `root` of a binary tree, return the leftmost value in the last row of the tree.

**Example 1:**

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

**Example 2:**

**Input:** root = \[1,2,3,4,null,5,6,null,null,7\]
**Output:** 7

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `-231 <= Node.val <= 231 - 1`
Freedom Trail

In the video game Fallout 4, the quest **"Road to Freedom "** requires players to reach a metal dial called the **"Freedom Trail Ring "** and use the dial to spell a specific keyword to open the door.

Given a string `ring` that represents the code engraved on the outer ring and another string `key` that represents the keyword that needs to be spelled, return _the minimum number of steps to spell all the characters in the keyword_.

Initially, the first character of the ring is aligned at the `"12:00 "` direction. You should spell all the characters in `key` one by one by rotating `ring` clockwise or anticlockwise to make each character of the string key aligned at the `"12:00 "` direction and then by pressing the center button.

At the stage of rotating the ring to spell the key character `key[i]`:

1.  You can rotate the ring clockwise or anticlockwise by one place, which counts as **one step**. The final purpose of the rotation is to align one of `ring`'s characters at the `"12:00 "` direction, where this character must equal `key[i]`.
2.  If the character `key[i]` has been aligned at the `"12:00 "` direction, press the center button to spell, which also counts as **one step**. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.

**Example 1:**

**Input:** ring =  "godding ", key =  "gd "
**Output:** 4
**Explanation:**
For the first key character 'g', since it is already in place, we just need 1 step to spell this character. 
For the second key character 'd', we need to rotate the ring  "godding " anticlockwise by two steps to make it become  "ddinggo ".
Also, we need 1 more step for spelling.
So the final output is 4.

**Example 2:**

**Input:** ring =  "godding ", key =  "godding "
**Output:** 13

**Constraints:**

*   `1 <= ring.length, key.length <= 100`
*   `ring` and `key` consist of only lower case English letters.
*   It is guaranteed that `key` could always be spelled by rotating `ring`.
Find Largest Value in Each Tree Row

Given the `root` of a binary tree, return _an array of the largest value in each row_ of the tree **(0-indexed)**.

**Example 1:**

**Input:** root = \[1,3,2,5,3,null,9\]
**Output:** \[1,3,9\]

**Example 2:**

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

**Constraints:**

*   The number of nodes in the tree will be in the range `[0, 104]`.
*   `-231 <= Node.val <= 231 - 1`
Longest Palindromic Subsequence

Given a string `s`, find _the longest palindromic **subsequence**'s length in_ `s`.

A **subsequence** is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

**Example 1:**

**Input:** s =  "bbbab "
**Output:** 4
**Explanation:** One possible longest palindromic subsequence is  "bbbb ".

**Example 2:**

**Input:** s =  "cbbd "
**Output:** 2
**Explanation:** One possible longest palindromic subsequence is  "bb ".

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s` consists only of lowercase English letters.
Super Washing Machines

You have `n` super washing machines on a line. Initially, each washing machine has some dresses or is empty.

For each move, you could choose any `m` (`1 <= m <= n`) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time.

Given an integer array `machines` representing the number of dresses in each washing machine from left to right on the line, return _the minimum number of moves to make all the washing machines have the same number of dresses_. If it is not possible to do it, return `-1`.

**Example 1:**

**Input:** machines = \[1,0,5\]
**Output:** 3
**Explanation:**
1st move:    1     0 <-- 5    =>    1     1     4
2nd move:    1 <-- 1 <-- 4    =>    2     1     3
3rd move:    2     1 <-- 3    =>    2     2     2

**Example 2:**

**Input:** machines = \[0,3,0\]
**Output:** 2
**Explanation:**
1st move:    0 <-- 3     0    =>    1     2     0
2nd move:    1     2 --> 0    =>    1     1     1

**Example 3:**

**Input:** machines = \[0,2,0\]
**Output:** -1
**Explanation:**
It's impossible to make all three washing machines have the same number of dresses.

**Constraints:**

*   `n == machines.length`
*   `1 <= n <= 104`
*   `0 <= machines[i] <= 105`
Coin Change II

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.

Return _the number of combinations that make up that amount_. If that amount of money cannot be made up by any combination of the coins, return `0`.

You may assume that you have an infinite number of each kind of coin.

The answer is **guaranteed** to fit into a signed **32-bit** integer.

**Example 1:**

**Input:** amount = 5, coins = \[1,2,5\]
**Output:** 4
**Explanation:** there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

**Example 2:**

**Input:** amount = 3, coins = \[2\]
**Output:** 0
**Explanation:** the amount of 3 cannot be made up just with coins of 2.

**Example 3:**

**Input:** amount = 10, coins = \[10\]
**Output:** 1

**Constraints:**

*   `1 <= coins.length <= 300`
*   `1 <= coins[i] <= 5000`
*   All the values of `coins` are **unique**.
*   `0 <= amount <= 5000`
Random Flip Matrix

There is an `m x n` binary grid `matrix` with all the values set `0` initially. Design an algorithm to randomly pick an index `(i, j)` where `matrix[i][j] == 0` and flips it to `1`. All the indices `(i, j)` where `matrix[i][j] == 0` should be equally likely to be returned.

Optimize your algorithm to minimize the number of calls made to the **built-in** random function of your language and optimize the time and space complexity.

Implement the `Solution` class:

*   `Solution(int m, int n)` Initializes the object with the size of the binary matrix `m` and `n`.
*   `int[] flip()` Returns a random index `[i, j]` of the matrix where `matrix[i][j] == 0` and flips it to `1`.
*   `void reset()` Resets all the values of the matrix to be `0`.

**Example 1:**

**Input**
\[ "Solution ",  "flip ",  "flip ",  "flip ",  "reset ",  "flip "\]
\[\[3, 1\], \[\], \[\], \[\], \[\], \[\]\]
**Output**
\[null, \[1, 0\], \[2, 0\], \[0, 0\], null, \[2, 0\]\]

**Explanation**
Solution solution = new Solution(3, 1);
solution.flip();  // return \[1, 0\], \[0,0\], \[1,0\], and \[2,0\] should be equally likely to be returned.
solution.flip();  // return \[2, 0\], Since \[1,0\] was returned, \[2,0\] and \[0,0\]
solution.flip();  // return \[0, 0\], Based on the previously returned indices, only \[0,0\] can be returned.
solution.reset(); // All the values are reset to 0 and can be returned.
solution.flip();  // return \[2, 0\], \[0,0\], \[1,0\], and \[2,0\] should be equally likely to be returned.

**Constraints:**

*   `1 <= m, n <= 104`
*   There will be at least one free cell for each call to `flip`.
*   At most `1000` calls will be made to `flip` and `reset`.
Detect Capital

We define the usage of capitals in a word to be right when one of the following cases holds:

*   All letters in this word are capitals, like `"USA "`.
*   All letters in this word are not capitals, like `"leetcode "`.
*   Only the first letter in this word is capital, like `"Google "`.

Given a string `word`, return `true` if the usage of capitals in it is right.

**Example 1:**

**Input:** word = "USA"
**Output:** true

**Example 2:**

**Input:** word = "FlaG"
**Output:** false

**Constraints:**

*   `1 <= word.length <= 100`
*   `word` consists of lowercase and uppercase English letters.
Longest Uncommon Subsequence I

Given two strings `a` and `b`, return _the length of the **longest uncommon subsequence** between_ `a` _and_ `b`. If the longest uncommon subsequence does not exist, return `-1`.

An **uncommon subsequence** between two strings is a string that is a **subsequence of one but not the other**.

A **subsequence** of a string `s` is a string that can be obtained after deleting any number of characters from `s`.

*   For example, `"abc "` is a subsequence of `"aebdc "` because you can delete the underlined characters in `"aebdc "` to get `"abc "`. Other subsequences of `"aebdc "` include `"aebdc "`, `"aeb "`, and `" "` (empty string).

**Example 1:**

**Input:** a =  "aba ", b =  "cdc "
**Output:** 3
**Explanation:** One longest uncommon subsequence is  "aba " because  "aba " is a subsequence of  "aba " but not  "cdc ".
Note that  "cdc " is also a longest uncommon subsequence.

**Example 2:**

**Input:** a =  "aaa ", b =  "bbb "
**Output:** 3
**Explanation:** The longest uncommon subsequences are  "aaa " and  "bbb ".

**Example 3:**

**Input:** a =  "aaa ", b =  "aaa "
**Output:** -1
**Explanation:** Every subsequence of string a is also a subsequence of string b. Similarly, every subsequence of string b is also a subsequence of string a.

**Constraints:**

*   `1 <= a.length, b.length <= 100`
*   `a` and `b` consist of lower-case English letters.
Longest Uncommon Subsequence II

Given an array of strings `strs`, return _the length of the **longest uncommon subsequence** between them_. If the longest uncommon subsequence does not exist, return `-1`.

An **uncommon subsequence** between an array of strings is a string that is a **subsequence of one string but not the others**.

A **subsequence** of a string `s` is a string that can be obtained after deleting any number of characters from `s`.

*   For example, `"abc "` is a subsequence of `"aebdc "` because you can delete the underlined characters in `"aebdc "` to get `"abc "`. Other subsequences of `"aebdc "` include `"aebdc "`, `"aeb "`, and `" "` (empty string).

**Example 1:**

**Input:** strs = \["aba","cdc","eae"\]
**Output:** 3

**Example 2:**

**Input:** strs = \["aaa","aaa","aa"\]
**Output:** -1

**Constraints:**

*   `2 <= strs.length <= 50`
*   `1 <= strs[i].length <= 10`
*   `strs[i]` consists of lowercase English letters.