bowang0911/leetcode huggingface dataset:
Set Mismatch

You have a set of integers `s`, which originally contains all the numbers from `1` to `n`. Unfortunately, due to some error, one of the numbers in `s` got duplicated to another number in the set, which results in **repetition of one** number and **loss of another** number.

You are given an integer array `nums` representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return _them in the form of an array_.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   `2 <= nums.length <= 104`
*   `1 <= nums[i] <= 104`
Maximum Length of Pair Chain

You are given an array of `n` pairs `pairs` where `pairs[i] = [lefti, righti]` and `lefti < righti`.

A pair `p2 = [c, d]` **follows** a pair `p1 = [a, b]` if `b < c`. A **chain** of pairs can be formed in this fashion.

Return _the length longest chain which can be formed_.

You do not need to use up all the given intervals. You can select pairs in any order.

**Example 1:**

**Input:** pairs = \[\[1,2\],\[2,3\],\[3,4\]\]
**Output:** 2
**Explanation:** The longest chain is \[1,2\] -> \[3,4\].

**Example 2:**

**Input:** pairs = \[\[1,2\],\[7,8\],\[4,5\]\]
**Output:** 3
**Explanation:** The longest chain is \[1,2\] -> \[4,5\] -> \[7,8\].

**Constraints:**

*   `n == pairs.length`
*   `1 <= n <= 1000`
*   `-1000 <= lefti < righti <= 1000`
Palindromic Substrings

Given a string `s`, return _the number of **palindromic substrings** in it_.

A string is a **palindrome** when it reads the same backward as forward.

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

**Example 1:**

**Input:** s =  "abc "
**Output:** 3
**Explanation:** Three palindromic strings:  "a ",  "b ",  "c ".

**Example 2:**

**Input:** s =  "aaa "
**Output:** 6
**Explanation:** Six palindromic strings:  "a ",  "a ",  "a ",  "aa ",  "aa ",  "aaa ".

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s` consists of lowercase English letters.
Replace Words

In English, we have a concept called **root**, which can be followed by some other word to form another longer word - let's call this word **successor**. For example, when the **root** `"an "` is followed by the **successor** word `"other "`, we can form a new word `"another "`.

Given a `dictionary` consisting of many **roots** and a `sentence` consisting of words separated by spaces, replace all the **successors** in the sentence with the **root** forming it. If a **successor** can be replaced by more than one **root**, replace it with the **root** that has **the shortest length**.

Return _the `sentence`_ after the replacement.

**Example 1:**

**Input:** dictionary = \[ "cat ", "bat ", "rat "\], sentence =  "the cattle was rattled by the battery "
**Output:**  "the cat was rat by the bat "

**Example 2:**

**Input:** dictionary = \[ "a ", "b ", "c "\], sentence =  "aadsfasf absbs bbab cadsfafs "
**Output:**  "a a b c "

**Constraints:**

*   `1 <= dictionary.length <= 1000`
*   `1 <= dictionary[i].length <= 100`
*   `dictionary[i]` consists of only lower-case letters.
*   `1 <= sentence.length <= 106`
*   `sentence` consists of only lower-case letters and spaces.
*   The number of words in `sentence` is in the range `[1, 1000]`
*   The length of each word in `sentence` is in the range `[1, 1000]`
*   Every two consecutive words in `sentence` will be separated by exactly one space.
*   `sentence` does not have leading or trailing spaces.
Dota2 Senate

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the Senate wants to decide on a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise **one** of the two rights:

*   **Ban one senator's right:** A senator can make another senator lose all his rights in this and all the following rounds.
*   **Announce the victory:** If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and decide on the change in the game.

Given a string `senate` representing each senator's party belonging. The character `'R'` and `'D'` represent the Radiant party and the Dire party. Then if there are `n` senators, the size of the given string will be `n`.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party. Predict which party will finally announce the victory and change the Dota2 game. The output should be `"Radiant "` or `"Dire "`.

**Example 1:**

**Input:** senate =  "RD "
**Output:**  "Radiant "
**Explanation:** 
The first senator comes from Radiant and he can just ban the next senator's right in round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And in round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

**Example 2:**

**Input:** senate =  "RDD "
**Output:**  "Dire "
**Explanation:** 
The first senator comes from Radiant and he can just ban the next senator's right in round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And the third senator comes from Dire and he can ban the first senator's right in round 1. 
And in round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

**Constraints:**

*   `n == senate.length`
*   `1 <= n <= 104`
*   `senate[i]` is either `'R'` or `'D'`.
2 Keys Keyboard

There is only one character `'A'` on the screen of a notepad. You can perform one of two operations on this notepad for each step:

*   Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
*   Paste: You can paste the characters which are copied last time.

Given an integer `n`, return _the minimum number of operations to get the character_ `'A'` _exactly_ `n` _times on the screen_.

**Example 1:**

**Input:** n = 3
**Output:** 3
**Explanation:** Initially, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

**Example 2:**

**Input:** n = 1
**Output:** 0

**Constraints:**

*   `1 <= n <= 1000`
4 Keys Keyboard

Imagine you have a special keyboard with the following keys:

*   A: Print one `'A'` on the screen.
*   Ctrl-A: Select the whole screen.
*   Ctrl-C: Copy selection to buffer.
*   Ctrl-V: Print buffer on screen appending it after what has already been printed.

Given an integer n, return _the maximum number of_ `'A'` _you can print on the screen with **at most**_ `n` _presses on the keys_.

**Example 1:**

**Input:** n = 3
**Output:** 3
**Explanation:** We can at most get 3 A's on screen by pressing the following key sequence:
A, A, A

**Example 2:**

**Input:** n = 7
**Output:** 9
**Explanation:** We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

**Constraints:**

*   `1 <= n <= 50`
Find Duplicate Subtrees

Given the `root` of a binary tree, return all **duplicate subtrees**.

For each kind of duplicate subtrees, you only need to return the root node of any **one** of them.

Two trees are **duplicate** if they have the **same structure** with the **same node values**.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   The number of the nodes in the tree will be in the range `[1, 5000]`
*   `-200 <= Node.val <= 200`
Two Sum IV - Input is a BST

Given the `root` of a binary search tree and an integer `k`, return `true` _if there exist two elements in the BST such that their sum is equal to_ `k`, _or_ `false` _otherwise_.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `-104 <= Node.val <= 104`
*   `root` is guaranteed to be a **valid** binary search tree.
*   `-105 <= k <= 105`
Maximum Binary Tree

You are given an integer array `nums` with no duplicates. A **maximum binary tree** can be built recursively from `nums` using the following algorithm:

1.  Create a root node whose value is the maximum value in `nums`.
2.  Recursively build the left subtree on the **subarray prefix** to the **left** of the maximum value.
3.  Recursively build the right subtree on the **subarray suffix** to the **right** of the maximum value.

Return _the **maximum binary tree** built from_ `nums`.

**Example 1:**

**Input:** nums = \[3,2,1,6,0,5\]
**Output:** \[6,3,5,null,2,0,null,null,1\]
**Explanation:** The recursive calls are as follow:
- The largest value in \[3,2,1,6,0,5\] is 6. Left prefix is \[3,2,1\] and right suffix is \[0,5\].
    - The largest value in \[3,2,1\] is 3. Left prefix is \[\] and right suffix is \[2,1\].
        - Empty array, so no child.
        - The largest value in \[2,1\] is 2. Left prefix is \[\] and right suffix is \[1\].
            - Empty array, so no child.
            - Only one element, so child is a node with value 1.
    - The largest value in \[0,5\] is 5. Left prefix is \[0\] and right suffix is \[\].
        - Only one element, so child is a node with value 0.
        - Empty array, so no child.

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `0 <= nums[i] <= 1000`
*   All integers in `nums` are **unique**.
Print Binary Tree

Given the `root` of a binary tree, construct a **0-indexed** `m x n` string matrix `res` that represents a **formatted layout** of the tree. The formatted layout matrix should be constructed using the following rules:

*   The **height** of the tree is `height` and the number of rows `m` should be equal to `height + 1`.
*   The number of columns `n` should be equal to `2height+1 - 1`.
*   Place the **root node** in the **middle** of the **top row** (more formally, at location `res[0][(n-1)/2]`).
*   For each node that has been placed in the matrix at position `res[r][c]`, place its **left child** at `res[r+1][c-2height-r-1]` and its **right child** at `res[r+1][c+2height-r-1]`.
*   Continue this process until all the nodes in the tree have been placed.
*   Any empty cells should contain the empty string `" "`.

Return _the constructed matrix_ `res`.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 210]`.
*   `-99 <= Node.val <= 99`
*   The depth of the tree will be in the range `[1, 10]`.
Coin Path

You are given an integer array `coins` (**1-indexed**) of length `n` and an integer `maxJump`. You can jump to any index `i` of the array `coins` if `coins[i] != -1` and you have to pay `coins[i]` when you visit index `i`. In addition to that, if you are currently at index `i`, you can only jump to any index `i + k` where `i + k <= n` and `k` is a value in the range `[1, maxJump]`.

You are initially positioned at index `1` (`coins[1]` is not `-1`). You want to find the path that reaches index n with the minimum cost.

Return an integer array of the indices that you will visit in order so that you can reach index n with the minimum cost. If there are multiple paths with the same cost, return the **lexicographically smallest** such path. If it is not possible to reach index n, return an empty array.

A path `p1 = [Pa1, Pa2, ..., Pax]` of length `x` is **lexicographically smaller** than `p2 = [Pb1, Pb2, ..., Pbx]` of length `y`, if and only if at the first `j` where `Paj` and `Pbj` differ, `Paj < Pbj`; when no such `j` exists, then `x < y`.

**Example 1:**

**Input:** coins = \[1,2,4,-1,2\], maxJump = 2
**Output:** \[1,3,5\]

**Example 2:**

**Input:** coins = \[1,2,4,-1,2\], maxJump = 1
**Output:** \[\]

**Constraints:**

*   `1 <= coins.length <= 1000`
*   `-1 <= coins[i] <= 100`
*   `coins[1] != -1`
*   `1 <= maxJump <= 100`
Robot Return to Origin

There is a robot starting at the position `(0, 0)`, the origin, on a 2D plane. Given a sequence of its moves, judge if this robot **ends up at** `(0, 0)` after it completes its moves.

You are given a string `moves` that represents the move sequence of the robot where `moves[i]` represents its `ith` move. Valid moves are `'R'` (right), `'L'` (left), `'U'` (up), and `'D'` (down).

Return `true` _if the robot returns to the origin after it finishes all of its moves, or_ `false` _otherwise_.

**Note**: The way that the robot is "facing " is irrelevant. `'R'` will always make the robot move to the right once, `'L'` will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.

**Example 1:**

**Input:** moves =  "UD "
**Output:** true
**Explanation**: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.

**Example 2:**

**Input:** moves =  "LL "
**Output:** false
**Explanation**: The robot moves left twice. It ends up two  "moves " to the left of the origin. We return false because it is not at the origin at the end of its moves.

**Constraints:**

*   `1 <= moves.length <= 2 * 104`
*   `moves` only contains the characters `'U'`, `'D'`, `'L'` and `'R'`.
Find K Closest Elements

Given a **sorted** integer array `arr`, two integers `k` and `x`, return the `k` closest integers to `x` in the array. The result should also be sorted in ascending order.

An integer `a` is closer to `x` than an integer `b` if:

*   `|a - x| < |b - x|`, or
*   `|a - x| == |b - x|` and `a < b`

**Example 1:**

**Input:** arr = \[1,2,3,4,5\], k = 4, x = 3
**Output:** \[1,2,3,4\]

**Example 2:**

**Input:** arr = \[1,2,3,4,5\], k = 4, x = -1
**Output:** \[1,2,3,4\]

**Constraints:**

*   `1 <= k <= arr.length`
*   `1 <= arr.length <= 104`
*   `arr` is sorted in **ascending** order.
*   `-104 <= arr[i], x <= 104`
Split Array into Consecutive Subsequences

You are given an integer array `nums` that is **sorted in non-decreasing order**.

Determine if it is possible to split `nums` into **one or more subsequences** such that **both** of the following conditions are true:

*   Each subsequence is a **consecutive increasing sequence** (i.e. each integer is **exactly one** more than the previous integer).
*   All subsequences have a length of `3` **or more**.

Return `true` _if you can split_ `nums` _according to the above conditions, or_ `false` _otherwise_.

A **subsequence** of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., `[1,3,5]` is a subsequence of `[1,2,3,4,5]` while `[1,3,2]` is not).

**Example 1:**

**Input:** nums = \[1,2,3,3,4,5\]
**Output:** true
**Explanation:** nums can be split into the following subsequences:
\[**1**,**2**,**3**,3,4,5\] --> 1, 2, 3
\[1,2,3,**3**,**4**,**5**\] --> 3, 4, 5

**Example 2:**

**Input:** nums = \[1,2,3,3,4,4,5,5\]
**Output:** true
**Explanation:** nums can be split into the following subsequences:
\[**1**,**2**,**3**,3,**4**,4,**5**,5\] --> 1, 2, 3, 4, 5
\[1,2,3,**3**,4,**4**,5,**5**\] --> 3, 4, 5

**Example 3:**

**Input:** nums = \[1,2,3,4,4,5\]
**Output:** false
**Explanation:** It is impossible to split nums into consecutive increasing subsequences of length 3 or more.

**Constraints:**

*   `1 <= nums.length <= 104`
*   `-1000 <= nums[i] <= 1000`
*   `nums` is sorted in **non-decreasing** order.
Remove 9

Start from integer `1`, remove any integer that contains `9` such as `9`, `19`, `29`...

Now, you will have a new integer sequence `[1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...]`.

Given an integer `n`, return _the_ `nth` (**1-indexed**) integer in the new sequence.

**Example 1:**

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

**Example 2:**

**Input:** n = 10
**Output:** 11

**Constraints:**

*   `1 <= n <= 8 * 108`
Image Smoother

An **image smoother** is a filter of the size `3 x 3` that can be applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells (i.e., the average of the nine cells in the blue smoother). If one or more of the surrounding cells of a cell is not present, we do not consider it in the average (i.e., the average of the four cells in the red smoother).

Given an `m x n` integer matrix `img` representing the grayscale of an image, return _the image after applying the smoother on each cell of it_.

**Example 1:**

**Input:** img = \[\[1,1,1\],\[1,0,1\],\[1,1,1\]\]
**Output:** \[\[0,0,0\],\[0,0,0\],\[0,0,0\]\]
**Explanation:**
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

**Example 2:**

**Input:** img = \[\[100,200,100\],\[200,50,200\],\[100,200,100\]\]
**Output:** \[\[137,141,137\],\[141,138,141\],\[137,141,137\]\]
**Explanation:**
For the points (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137
For the points (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141
For the point (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138

**Constraints:**

*   `m == img.length`
*   `n == img[i].length`
*   `1 <= m, n <= 200`
*   `0 <= img[i][j] <= 255`
Maximum Width of Binary Tree

Given the `root` of a binary tree, return _the **maximum width** of the given tree_.

The **maximum width** of a tree is the maximum **width** among all levels.

The **width** of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is **guaranteed** that the answer will in the range of a **32-bit** signed integer.

**Example 1:**

**Input:** root = \[1,3,2,5,3,null,9\]
**Output:** 4
**Explanation:** The maximum width exists in the third level with length 4 (5,3,null,9).

**Example 2:**

**Input:** root = \[1,3,2,5,null,null,9,6,null,7\]
**Output:** 7
**Explanation:** The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).

**Example 3:**

**Input:** root = \[1,3,2,5\]
**Output:** 2
**Explanation:** The maximum width exists in the second level with length 2 (3,2).

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 3000]`.
*   `-100 <= Node.val <= 100`
Equal Tree Partition

Given the `root` of a binary tree, return `true` _if you can partition the tree into two trees with equal sums of values after removing exactly one edge on the original tree_.

**Example 1:**

**Input:** root = \[5,10,10,null,null,2,3\]
**Output:** true

**Example 2:**

**Input:** root = \[1,2,10,null,null,2,20\]
**Output:** false
**Explanation:** You cannot split the tree into two trees with equal sums after removing exactly one edge on the tree.

**Constraints:**

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

There is a strange printer with the following two special properties:

*   The printer can only print a sequence of **the same character** each time.
*   At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.

Given a string `s`, return _the minimum number of turns the printer needed to print it_.

**Example 1:**

**Input:** s =  "aaabbb "
**Output:** 2
**Explanation:** Print  "aaa " first and then print  "bbb ".

**Example 2:**

**Input:** s =  "aba "
**Output:** 2
**Explanation:** Print  "aaa " first and then print  "b " from the second place of the string, which will cover the existing character 'a'.

**Constraints:**

*   `1 <= s.length <= 100`
*   `s` consists of lowercase English letters.
Non-decreasing Array

Given an array `nums` with `n` integers, your task is to check if it could become non-decreasing by modifying **at most one element**.

We define an array is non-decreasing if `nums[i] <= nums[i + 1]` holds for every `i` (**0-based**) such that (`0 <= i <= n - 2`).

**Example 1:**

**Input:** nums = \[4,2,3\]
**Output:** true
**Explanation:** You could modify the first 4 to 1 to get a non-decreasing array.

**Example 2:**

**Input:** nums = \[4,2,1\]
**Output:** false
**Explanation:** You cannot get a non-decreasing array by modifying at most one element.

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 104`
*   `-105 <= nums[i] <= 105`
Path Sum IV

If the depth of a tree is smaller than `5`, then this tree can be represented by an array of three-digit integers. For each integer in this array:

*   The hundreds digit represents the depth `d` of this node where `1 <= d <= 4`.
*   The tens digit represents the position `p` of this node in the level it belongs to where `1 <= p <= 8`. The position is the same as that in a full binary tree.
*   The units digit represents the value `v` of this node where `0 <= v <= 9`.

Given an array of **ascending** three-digit integers `nums` representing a binary tree with a depth smaller than `5`, return _the sum of all paths from the root towards the leaves_.

It is **guaranteed** that the given array represents a valid connected binary tree.

**Example 1:**

**Input:** nums = \[113,215,221\]
**Output:** 12
**Explanation:** The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

**Example 2:**

**Input:** nums = \[113,221\]
**Output:** 4
**Explanation:** The tree that the list represents is shown. 
The path sum is (3 + 1) = 4.

**Constraints:**

*   `1 <= nums.length <= 15`
*   `110 <= nums[i] <= 489`
*   `nums` represents a valid binary tree with depth less than `5`.
Beautiful Arrangement II

Given two integers `n` and `k`, construct a list `answer` that contains `n` different positive integers ranging from `1` to `n` and obeys the following requirement:

*   Suppose this list is `answer = [a1, a2, a3, ... , an]`, then the list `[|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|]` has exactly `k` distinct integers.

Return _the list_ `answer`. If there multiple valid answers, return **any of them**.

**Example 1:**

**Input:** n = 3, k = 1
**Output:** \[1,2,3\]
Explanation: The \[1,2,3\] has three different positive integers ranging from 1 to 3, and the \[1,1\] has exactly 1 distinct integer: 1

**Example 2:**

**Input:** n = 3, k = 2
**Output:** \[1,3,2\]
Explanation: The \[1,3,2\] has three different positive integers ranging from 1 to 3, and the \[2,1\] has exactly 2 distinct integers: 1 and 2.

**Constraints:**

*   `1 <= k < n <= 104`
Kth Smallest Number in Multiplication Table

Nearly everyone has used the [Multiplication Table](https://en.wikipedia.org/wiki/Multiplication_table). The multiplication table of size `m x n` is an integer matrix `mat` where `mat[i][j] == i * j` (**1-indexed**).

Given three integers `m`, `n`, and `k`, return _the_ `kth` _smallest element in the_ `m x n` _multiplication table_.

**Example 1:**

**Input:** m = 3, n = 3, k = 5
**Output:** 3
**Explanation:** The 5th smallest number is 3.

**Example 2:**

**Input:** m = 2, n = 3, k = 6
**Output:** 6
**Explanation:** The 6th smallest number is 6.

**Constraints:**

*   `1 <= m, n <= 3 * 104`
*   `1 <= k <= m * n`