bowang0911/leetcode huggingface dataset:
Closest Divisors

Given an integer `num`, find the closest two integers in absolute difference whose product equals `num + 1` or `num + 2`.

Return the two integers in any order.

**Example 1:**

**Input:** num = 8
**Output:** \[3,3\]
**Explanation:** For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.

**Example 2:**

**Input:** num = 123
**Output:** \[5,25\]

**Example 3:**

**Input:** num = 999
**Output:** \[40,25\]

**Constraints:**

*   `1 <= num <= 10^9`
Largest Multiple of Three

Given an array of digits `digits`, return _the largest multiple of **three** that can be formed by concatenating some of the given digits in **any order**_. If there is no answer return an empty string.

Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.

**Example 1:**

**Input:** digits = \[8,1,9\]
**Output:**  "981 "

**Example 2:**

**Input:** digits = \[8,6,7,1,0\]
**Output:**  "8760 "

**Example 3:**

**Input:** digits = \[1\]
**Output:**  " "

**Constraints:**

*   `1 <= digits.length <= 104`
*   `0 <= digits[i] <= 9`
How Many Numbers Are Smaller Than the Current Number

Given the array `nums`, for each `nums[i]` find out how many numbers in the array are smaller than it. That is, for each `nums[i]` you have to count the number of valid `j's` such that `j != i` **and** `nums[j] < nums[i]`.

Return the answer in an array.

**Example 1:**

**Input:** nums = \[8,1,2,2,3\]
**Output:** \[4,0,1,1,3\]
**Explanation:** 
For nums\[0\]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 
For nums\[1\]=1 does not exist any smaller number than it.
For nums\[2\]=2 there exist one smaller number than it (1). 
For nums\[3\]=2 there exist one smaller number than it (1). 
For nums\[4\]=3 there exist three smaller numbers than it (1, 2 and 2).

**Example 2:**

**Input:** nums = \[6,5,4,8\]
**Output:** \[2,1,0,3\]

**Example 3:**

**Input:** nums = \[7,7,7,7\]
**Output:** \[0,0,0,0\]

**Constraints:**

*   `2 <= nums.length <= 500`
*   `0 <= nums[i] <= 100`
Rank Teams by Votes

In a special ranking system, each voter gives a rank from highest to lowest to all teams participating in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

You are given an array of strings `votes` which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return _a string of all teams **sorted** by the ranking system_.

**Example 1:**

**Input:** votes = \[ "ABC ", "ACB ", "ABC ", "ACB ", "ACB "\]
**Output:**  "ACB "
**Explanation:** 
Team A was ranked first place by 5 voters. No other team was voted as first place, so team A is the first team.
Team B was ranked second by 2 voters and ranked third by 3 voters.
Team C was ranked second by 3 voters and ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team, and team B is the third.

**Example 2:**

**Input:** votes = \[ "WXYZ ", "XYZW "\]
**Output:**  "XWYZ "
**Explanation:**
X is the winner due to the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position. 

**Example 3:**

**Input:** votes = \[ "ZMNAGUEDSJYLBOPHRQICWFXTVK "\]
**Output:**  "ZMNAGUEDSJYLBOPHRQICWFXTVK "
**Explanation:** Only one voter, so their votes are used for the ranking.

**Constraints:**

*   `1 <= votes.length <= 1000`
*   `1 <= votes[i].length <= 26`
*   `votes[i].length == votes[j].length` for `0 <= i, j < votes.length`.
*   `votes[i][j]` is an English **uppercase** letter.
*   All characters of `votes[i]` are unique.
*   All the characters that occur in `votes[0]` **also occur** in `votes[j]` where `1 <= j < votes.length`.
Linked List in Binary Tree

Given a binary tree `root` and a linked list with `head` as the first node.

Return True if all the elements in the linked list starting from the `head` correspond to some _downward path_ connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

**Example 1:**

**Input:** head = \[4,2,8\], root = \[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3\]
**Output:** true
**Explanation:** Nodes in blue form a subpath in the binary Tree.  

**Example 2:**

**Input:** head = \[1,4,2,6\], root = \[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3\]
**Output:** true

**Example 3:**

**Input:** head = \[1,4,2,6,8\], root = \[1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3\]
**Output:** false
**Explanation:** There is no path in the binary tree that contains all the elements of the linked list from `head`.

**Constraints:**

*   The number of nodes in the tree will be in the range `[1, 2500]`.
*   The number of nodes in the list will be in the range `[1, 100]`.
*   `1 <= Node.val <= 100` for each node in the linked list and binary tree.
Minimum Cost to Make at Least One Valid Path in a Grid

Given an `m x n` grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of `grid[i][j]` can be:

*   `1` which means go to the cell to the right. (i.e go from `grid[i][j]` to `grid[i][j + 1]`)
*   `2` which means go to the cell to the left. (i.e go from `grid[i][j]` to `grid[i][j - 1]`)
*   `3` which means go to the lower cell. (i.e go from `grid[i][j]` to `grid[i + 1][j]`)
*   `4` which means go to the upper cell. (i.e go from `grid[i][j]` to `grid[i - 1][j]`)

Notice that there could be some signs on the cells of the grid that point outside the grid.

You will initially start at the upper left cell `(0, 0)`. A valid path in the grid is a path that starts from the upper left cell `(0, 0)` and ends at the bottom-right cell `(m - 1, n - 1)` following the signs on the grid. The valid path does not have to be the shortest.

You can modify the sign on a cell with `cost = 1`. You can modify the sign on a cell **one time only**.

Return _the minimum cost to make the grid have at least one valid path_.

**Example 1:**

**Input:** grid = \[\[1,1,1,1\],\[2,2,2,2\],\[1,1,1,1\],\[2,2,2,2\]\]
**Output:** 3
**Explanation:** You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.

**Example 2:**

**Input:** grid = \[\[1,1,3\],\[3,2,2\],\[1,1,4\]\]
**Output:** 0
**Explanation:** You can follow the path from (0, 0) to (2, 2).

**Example 3:**

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

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 100`
*   `1 <= grid[i][j] <= 4`
Increasing Decreasing String

You are given a string `s`. Reorder the string using the following algorithm:

1.  Pick the **smallest** character from `s` and **append** it to the result.
2.  Pick the **smallest** character from `s` which is greater than the last appended character to the result and **append** it.
3.  Repeat step 2 until you cannot pick more characters.
4.  Pick the **largest** character from `s` and **append** it to the result.
5.  Pick the **largest** character from `s` which is smaller than the last appended character to the result and **append** it.
6.  Repeat step 5 until you cannot pick more characters.
7.  Repeat the steps from 1 to 6 until you pick all characters from `s`.

In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.

Return _the result string after sorting_ `s` _with this algorithm_.

**Example 1:**

**Input:** s =  "aaaabbbbcccc "
**Output:**  "abccbaabccba "
**Explanation:** After steps 1, 2 and 3 of the first iteration, result =  "abc "
After steps 4, 5 and 6 of the first iteration, result =  "abccba "
First iteration is done. Now s =  "aabbcc " and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result =  "abccbaabc "
After steps 4, 5 and 6 of the second iteration, result =  "abccbaabccba "

**Example 2:**

**Input:** s =  "rat "
**Output:**  "art "
**Explanation:** The word  "rat " becomes  "art " after re-ordering it with the mentioned algorithm.

**Constraints:**

*   `1 <= s.length <= 500`
*   `s` consists of only lowercase English letters.
Find the Longest Substring Containing Vowels in Even Counts

Given the string `s`, return the size of the longest substring containing each vowel an even number of times. That is, 'a', 'e', 'i', 'o', and 'u' must appear an even number of times.

**Example 1:**

**Input:** s =  "eleetminicoworoep "
**Output:** 13
**Explanation:** The longest substring is  "leetminicowor " which contains two each of the vowels: **e**, **i** and **o** and zero of the vowels: **a** and **u**.

**Example 2:**

**Input:** s =  "leetcodeisgreat "
**Output:** 5
**Explanation:** The longest substring is  "leetc " which contains two e's.

**Example 3:**

**Input:** s =  "bcbcbc "
**Output:** 6
**Explanation:** In this case, the given string  "bcbcbc " is the longest because all vowels: **a**, **e**, **i**, **o** and **u** appear zero times.

**Constraints:**

*   `1 <= s.length <= 5 x 10^5`
*   `s` contains only lowercase English letters.

It is the empty string, or It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string.
Longest ZigZag Path in a Binary Tree

You are given the `root` of a binary tree.

A ZigZag path for a binary tree is defined as follow:

*   Choose **any** node in the binary tree and a direction (right or left).
*   If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
*   Change the direction from right to left or from left to right.
*   Repeat the second and third steps until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return _the longest **ZigZag** path contained in that tree_.

**Example 1:**

**Input:** root = \[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1\]
**Output:** 3
**Explanation:** Longest ZigZag path in blue nodes (right -> left -> right).

**Example 2:**

**Input:** root = \[1,1,1,null,1,null,null,1,1,null,1\]
**Output:** 4
**Explanation:** Longest ZigZag path in blue nodes (left -> right -> left -> right).

**Example 3:**

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

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 5 * 104]`.
*   `1 <= Node.val <= 100`
Maximum Sum BST in Binary Tree

Given a **binary tree** `root`, return _the maximum sum of all keys of **any** sub-tree which is also a Binary Search Tree (BST)_.

Assume a BST is defined as follows:

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

**Example 1:**

**Input:** root = \[1,4,3,2,4,2,5,null,null,null,null,null,null,4,6\]
**Output:** 20
**Explanation:** Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.

**Example 2:**

**Input:** root = \[4,3,null,1,2\]
**Output:** 2
**Explanation:** Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.

**Example 3:**

**Input:** root = \[-4,-2,-5\]
**Output:** 0
**Explanation:** All values are negatives. Return an empty BST.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 4 * 104]`.
*   `-4 * 104 <= Node.val <= 4 * 104`
Generate a String With Characters That Have Odd Counts

Given an integer `n`, _return a string with `n` characters such that each character in such string occurs **an odd number of times**_.

The returned string must contain only lowercase English letters. If there are multiples valid strings, return **any** of them.

**Example 1:**

**Input:** n = 4
**Output:**  "pppz "
**Explanation:**  "pppz " is a valid string since the character 'p' occurs three times and the character 'z' occurs once. Note that there are many other valid strings such as  "ohhh " and  "love ".

**Example 2:**

**Input:** n = 2
**Output:**  "xy "
**Explanation:**  "xy " is a valid string since the characters 'x' and 'y' occur once. Note that there are many other valid strings such as  "ag " and  "ur ".

**Example 3:**

**Input:** n = 7
**Output:**  "holasss "

**Constraints:**

*   `1 <= n <= 500`
Number of Times Binary String Is Prefix-Aligned

You have a **1-indexed** binary string of length `n` where all the bits are `0` initially. We will flip all the bits of this binary string (i.e., change them from `0` to `1`) one by one. You are given a **1-indexed** integer array `flips` where `flips[i]` indicates that the bit at index `i` will be flipped in the `ith` step.

A binary string is **prefix-aligned** if, after the `ith` step, all the bits in the **inclusive** range `[1, i]` are ones and all the other bits are zeros.

Return _the number of times the binary string is **prefix-aligned** during the flipping process_.

**Example 1:**

**Input:** flips = \[3,2,4,1,5\]
**Output:** 2
**Explanation:** The binary string is initially  "00000 ".
After applying step 1: The string becomes  "00100 ", which is not prefix-aligned.
After applying step 2: The string becomes  "01100 ", which is not prefix-aligned.
After applying step 3: The string becomes  "01110 ", which is not prefix-aligned.
After applying step 4: The string becomes  "11110 ", which is prefix-aligned.
After applying step 5: The string becomes  "11111 ", which is prefix-aligned.
We can see that the string was prefix-aligned 2 times, so we return 2.

**Example 2:**

**Input:** flips = \[4,1,2,3\]
**Output:** 1
**Explanation:** The binary string is initially  "0000 ".
After applying step 1: The string becomes  "0001 ", which is not prefix-aligned.
After applying step 2: The string becomes  "1001 ", which is not prefix-aligned.
After applying step 3: The string becomes  "1101 ", which is not prefix-aligned.
After applying step 4: The string becomes  "1111 ", which is prefix-aligned.
We can see that the string was prefix-aligned 1 time, so we return 1.

**Constraints:**

*   `n == flips.length`
*   `1 <= n <= 5 * 104`
*   `flips` is a permutation of the integers in the range `[1, n]`.
Time Needed to Inform All Employees

A company has `n` employees with a unique ID for each employee from `0` to `n - 1`. The head of the company is the one with `headID`.

Each employee has one direct manager given in the `manager` array where `manager[i]` is the direct manager of the `i-th` employee, `manager[headID] = -1`. Also, it is guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the company employees of an urgent piece of news. He will inform his direct subordinates, and they will inform their subordinates, and so on until all employees know about the urgent news.

The `i-th` employee needs `informTime[i]` minutes to inform all of his direct subordinates (i.e., After informTime\[i\] minutes, all his direct subordinates can start spreading the news).

Return _the number of minutes_ needed to inform all the employees about the urgent news.

**Example 1:**

**Input:** n = 1, headID = 0, manager = \[-1\], informTime = \[0\]
**Output:** 0
**Explanation:** The head of the company is the only employee in the company.

**Example 2:**

**Input:** n = 6, headID = 2, manager = \[2,2,-1,2,2,2\], informTime = \[0,0,1,0,0,0\]
**Output:** 1
**Explanation:** The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

**Constraints:**

*   `1 <= n <= 105`
*   `0 <= headID < n`
*   `manager.length == n`
*   `0 <= manager[i] < n`
*   `manager[headID] == -1`
*   `informTime.length == n`
*   `0 <= informTime[i] <= 1000`
*   `informTime[i] == 0` if employee `i` has no subordinates.
*   It is **guaranteed** that all the employees can be informed.
Frog Position After T Seconds

Given an undirected tree consisting of `n` vertices numbered from `1` to `n`. A frog starts jumping from **vertex 1**. In one second, the frog jumps from its current vertex to another **unvisited** vertex if they are directly connected. The frog can not jump back to a visited vertex. In case the frog can jump to several vertices, it jumps randomly to one of them with the same probability. Otherwise, when the frog can not jump to any unvisited vertex, it jumps forever on the same vertex.

The edges of the undirected tree are given in the array `edges`, where `edges[i] = [ai, bi]` means that exists an edge connecting the vertices `ai` and `bi`.

_Return the probability that after `t` seconds the frog is on the vertex `target`._ Answers within `10-5` of the actual answer will be accepted.

**Example 1:**

**Input:** n = 7, edges = \[\[1,2\],\[1,3\],\[1,7\],\[2,4\],\[2,6\],\[3,5\]\], t = 2, target = 4
**Output:** 0.16666666666666666 
**Explanation:** The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after **second 1** and then jumping with 1/2 probability to vertex 4 after **second 2**. Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 \* 1/2 = 1/6 = 0.16666666666666666. 

**Example 2:**

**Input:** n = 7, edges = \[\[1,2\],\[1,3\],\[1,7\],\[2,4\],\[2,6\],\[3,5\]\], t = 1, target = 7
**Output:** 0.3333333333333333
**Explanation:** The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after **second 1**. 

**Constraints:**

*   `1 <= n <= 100`
*   `edges.length == n - 1`
*   `edges[i].length == 2`
*   `1 <= ai, bi <= n`
*   `1 <= t <= 50`
*   `1 <= target <= n`
Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Given two binary trees `original` and `cloned` and given a reference to a node `target` in the original tree.

The `cloned` tree is a **copy of** the `original` tree.

Return _a reference to the same node_ in the `cloned` tree.

**Note** that you are **not allowed** to change any of the two trees or the `target` node and the answer **must be** a reference to a node in the `cloned` tree.

**Example 1:**

**Input:** tree = \[7,4,3,null,null,6,19\], target = 3
**Output:** 3
**Explanation:** In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

**Example 2:**

**Input:** tree = \[7\], target =  7
**Output:** 7

**Example 3:**

**Input:** tree = \[8,null,6,null,5,null,4,null,3,null,2,null,1\], target = 4
**Output:** 4

**Constraints:**

*   The number of nodes in the `tree` is in the range `[1, 104]`.
*   The values of the nodes of the `tree` are unique.
*   `target` node is a node from the `original` tree and is not `null`.

**Follow up:** Could you solve the problem if repeated values on the tree are allowed?
Lucky Numbers in a Matrix

Given an `m x n` matrix of **distinct** numbers, return _all **lucky numbers** in the matrix in **any** order_.

A **lucky number** is an element of the matrix such that it is the minimum element in its row and maximum in its column.

**Example 1:**

**Input:** matrix = \[\[3,7,8\],\[9,11,13\],\[15,16,17\]\]
**Output:** \[15\]
**Explanation:** 15 is the only lucky number since it is the minimum in its row and the maximum in its column.

**Example 2:**

**Input:** matrix = \[\[1,10,4,2\],\[9,3,8,7\],\[15,16,17,12\]\]
**Output:** \[12\]
**Explanation:** 12 is the only lucky number since it is the minimum in its row and the maximum in its column.

**Example 3:**

**Input:** matrix = \[\[7,8\],\[1,2\]\]
**Output:** \[7\]
**Explanation:** 7 is the only lucky number since it is the minimum in its row and the maximum in its column.

**Constraints:**

*   `m == mat.length`
*   `n == mat[i].length`
*   `1 <= n, m <= 50`
*   `1 <= matrix[i][j] <= 105`.
*   All elements in the matrix are distinct.
Design a Stack With Increment Operation

Design a stack that supports increment operations on its elements.

Implement the `CustomStack` class:

*   `CustomStack(int maxSize)` Initializes the object with `maxSize` which is the maximum number of elements in the stack.
*   `void push(int x)` Adds `x` to the top of the stack if the stack has not reached the `maxSize`.
*   `int pop()` Pops and returns the top of the stack or `-1` if the stack is empty.
*   `void inc(int k, int val)` Increments the bottom `k` elements of the stack by `val`. If there are less than `k` elements in the stack, increment all the elements in the stack.

**Example 1:**

**Input**
\[ "CustomStack ", "push ", "push ", "pop ", "push ", "push ", "push ", "increment ", "increment ", "pop ", "pop ", "pop ", "pop "\]
\[\[3\],\[1\],\[2\],\[\],\[2\],\[3\],\[4\],\[5,100\],\[2,100\],\[\],\[\],\[\],\[\]\]
**Output**
\[null,null,null,2,null,null,null,null,null,103,202,201,-1\]
**Explanation**
CustomStack stk = new CustomStack(3); // Stack is Empty \[\]
stk.push(1);                          // stack becomes \[1\]
stk.push(2);                          // stack becomes \[1, 2\]
stk.pop();                            // return 2 --> Return top of the stack 2, stack becomes \[1\]
stk.push(2);                          // stack becomes \[1, 2\]
stk.push(3);                          // stack becomes \[1, 2, 3\]
stk.push(4);                          // stack still \[1, 2, 3\], Do not add another elements as size is 4
stk.increment(5, 100);                // stack becomes \[101, 102, 103\]
stk.increment(2, 100);                // stack becomes \[201, 202, 103\]
stk.pop();                            // return 103 --> Return top of the stack 103, stack becomes \[201, 202\]
stk.pop();                            // return 202 --> Return top of the stack 202, stack becomes \[201\]
stk.pop();                            // return 201 --> Return top of the stack 201, stack becomes \[\]
stk.pop();                            // return -1 --> Stack is empty return -1.

**Constraints:**

*   `1 <= maxSize, x, k <= 1000`
*   `0 <= val <= 100`
*   At most `1000` calls will be made to each method of `increment`, `push` and `pop` each separately.
Balance a Binary Search Tree

Given the `root` of a binary search tree, return _a **balanced** binary search tree with the same node values_. If there is more than one answer, return **any of them**.

A binary search tree is **balanced** if the depth of the two subtrees of every node never differs by more than `1`.

**Example 1:**

**Input:** root = \[1,null,2,null,3,null,4,null,null\]
**Output:** \[2,1,3,null,null,null,4\]
**Explanation:** This is not the only correct answer, \[3,1,4,null,2\] is also correct.

**Example 2:**

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

**Constraints:**

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