bowang0911/leetcode huggingface dataset:
Fair Candy Swap

Alice and Bob have a different total number of candies. You are given two integer arrays `aliceSizes` and `bobSizes` where `aliceSizes[i]` is the number of candies of the `ith` box of candy that Alice has and `bobSizes[j]` is the number of candies of the `jth` box of candy that Bob has.

Since they are friends, they would like to exchange one candy box each so that after the exchange, they both have the same total amount of candy. The total amount of candy a person has is the sum of the number of candies in each box they have.

Return a_n integer array_ `answer` _where_ `answer[0]` _is the number of candies in the box that Alice must exchange, and_ `answer[1]` _is the number of candies in the box that Bob must exchange_. If there are multiple answers, you may **return any** one of them. It is guaranteed that at least one answer exists.

**Example 1:**

**Input:** aliceSizes = \[1,1\], bobSizes = \[2,2\]
**Output:** \[1,2\]

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   `1 <= aliceSizes.length, bobSizes.length <= 104`
*   `1 <= aliceSizes[i], bobSizes[j] <= 105`
*   Alice and Bob have a different total number of candies.
*   There will be at least one valid answer for the given input.
Construct Binary Tree from Preorder and Postorder Traversal

Given two integer arrays, `preorder` and `postorder` where `preorder` is the preorder traversal of a binary tree of **distinct** values and `postorder` is the postorder traversal of the same tree, reconstruct and return _the binary tree_.

If there exist multiple answers, you can **return any** of them.

**Example 1:**

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

**Example 2:**

**Input:** preorder = \[1\], postorder = \[1\]
**Output:** \[1\]

**Constraints:**

*   `1 <= preorder.length <= 30`
*   `1 <= preorder[i] <= preorder.length`
*   All the values of `preorder` are **unique**.
*   `postorder.length == preorder.length`
*   `1 <= postorder[i] <= postorder.length`
*   All the values of `postorder` are **unique**.
*   It is guaranteed that `preorder` and `postorder` are the preorder traversal and postorder traversal of the same binary tree.
Find and Replace Pattern

Given a list of strings `words` and a string `pattern`, return _a list of_ `words[i]` _that match_ `pattern`. You may return the answer in **any order**.

A word matches the pattern if there exists a permutation of letters `p` so that after replacing every letter `x` in the pattern with `p(x)`, we get the desired word.

Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.

**Example 1:**

**Input:** words = \[ "abc ", "deq ", "mee ", "aqq ", "dkd ", "ccc "\], pattern =  "abb "
**Output:** \[ "mee ", "aqq "\]
**Explanation:**  "mee " matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
 "ccc " does not match the pattern because {a -> c, b -> c, ...} is not a permutation, since a and b map to the same letter.

**Example 2:**

**Input:** words = \[ "a ", "b ", "c "\], pattern =  "a "
**Output:** \[ "a ", "b ", "c "\]

**Constraints:**

*   `1 <= pattern.length <= 20`
*   `1 <= words.length <= 50`
*   `words[i].length == pattern.length`
*   `pattern` and `words[i]` are lowercase English letters.
Sum of Subsequence Widths

The **width** of a sequence is the difference between the maximum and minimum elements in the sequence.

Given an array of integers `nums`, return _the sum of the **widths** of all the non-empty **subsequences** of_ `nums`. Since the answer may be very large, return it **modulo** `109 + 7`.

A **subsequence** is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, `[3,6,2,7]` is a subsequence of the array `[0,3,1,6,2,2,7]`.

**Example 1:**

**Input:** nums = \[2,1,3\]
**Output:** 6
Explanation: The subsequences are \[1\], \[2\], \[3\], \[2,1\], \[2,3\], \[1,3\], \[2,1,3\].
The corresponding widths are 0, 0, 0, 1, 1, 2, 2.
The sum of these widths is 6.

**Example 2:**

**Input:** nums = \[2\]
**Output:** 0

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 105`
Surface Area of 3D Shapes

You are given an `n x n` `grid` where you have placed some `1 x 1 x 1` cubes. Each value `v = grid[i][j]` represents a tower of `v` cubes placed on top of cell `(i, j)`.

After placing these cubes, you have decided to glue any directly adjacent cubes to each other, forming several irregular 3D shapes.

Return _the total surface area of the resulting shapes_.

**Note:** The bottom face of each shape counts toward its surface area.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   `n == grid.length == grid[i].length`
*   `1 <= n <= 50`
*   `0 <= grid[i][j] <= 50`
Groups of Special-Equivalent Strings

You are given an array of strings of the same length `words`.

In one **move**, you can swap any two even indexed characters or any two odd indexed characters of a string `words[i]`.

Two strings `words[i]` and `words[j]` are **special-equivalent** if after any number of moves, `words[i] == words[j]`.

*   For example, `words[i] = "zzxy "` and `words[j] = "xyzz "` are **special-equivalent** because we may make the moves `"zzxy " -> "xzzy " -> "xyzz "`.

A **group of special-equivalent strings** from `words` is a non-empty subset of words such that:

*   Every pair of strings in the group are special equivalent, and
*   The group is the largest size possible (i.e., there is not a string `words[i]` not in the group such that `words[i]` is special-equivalent to every string in the group).

Return _the number of **groups of special-equivalent strings** from_ `words`.

**Example 1:**

**Input:** words = \[ "abcd ", "cdab ", "cbad ", "xyzz ", "zzxy ", "zzyx "\]
**Output:** 3
**Explanation:** 
One group is \[ "abcd ",  "cdab ",  "cbad "\], since they are all pairwise special equivalent, and none of the other strings is all pairwise special equivalent to these.
The other two groups are \[ "xyzz ",  "zzxy "\] and \[ "zzyx "\].
Note that in particular,  "zzxy " is not special equivalent to  "zzyx ".

**Example 2:**

**Input:** words = \[ "abc ", "acb ", "bac ", "bca ", "cab ", "cba "\]
**Output:** 3

**Constraints:**

*   `1 <= words.length <= 1000`
*   `1 <= words[i].length <= 20`
*   `words[i]` consist of lowercase English letters.
*   All the strings are of the same length.
All Possible Full Binary Trees

Given an integer `n`, return _a list of all possible **full binary trees** with_ `n` _nodes_. Each node of each tree in the answer must have `Node.val == 0`.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in **any order**.

A **full binary tree** is a binary tree where each node has exactly `0` or `2` children.

**Example 1:**

**Input:** n = 7
**Output:** \[\[0,0,0,null,null,0,0,null,null,0,0\],\[0,0,0,null,null,0,0,0,0\],\[0,0,0,0,0,0,0\],\[0,0,0,0,0,null,null,null,null,0,0\],\[0,0,0,0,0,null,null,0,0\]\]

**Example 2:**

**Input:** n = 3
**Output:** \[\[0,0,0\]\]

**Constraints:**

*   `1 <= n <= 20`
Maximum Frequency Stack

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the `FreqStack` class:

*   `FreqStack()` constructs an empty frequency stack.
*   `void push(int val)` pushes an integer `val` onto the top of the stack.
*   `int pop()` removes and returns the most frequent element in the stack.
    *   If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

**Example 1:**

**Input**
\[ "FreqStack ",  "push ",  "push ",  "push ",  "push ",  "push ",  "push ",  "pop ",  "pop ",  "pop ",  "pop "\]
\[\[\], \[5\], \[7\], \[5\], \[7\], \[4\], \[5\], \[\], \[\], \[\], \[\]\]
**Output**
\[null, null, null, null, null, null, null, 5, 7, 5, 4\]

**Explanation**
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is \[5\]
freqStack.push(7); // The stack is \[5,7\]
freqStack.push(5); // The stack is \[5,7,5\]
freqStack.push(7); // The stack is \[5,7,5,7\]
freqStack.push(4); // The stack is \[5,7,5,7,4\]
freqStack.push(5); // The stack is \[5,7,5,7,4,5\]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes \[5,7,5,7,4\].
freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes \[5,7,5,4\].
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes \[5,7,4\].
freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes \[5,7\].

**Constraints:**

*   `0 <= val <= 109`
*   At most `2 * 104` calls will be made to `push` and `pop`.
*   It is guaranteed that there will be at least one element in the stack before calling `pop`.
Monotonic Array

An array is **monotonic** if it is either monotone increasing or monotone decreasing.

An array `nums` is monotone increasing if for all `i <= j`, `nums[i] <= nums[j]`. An array `nums` is monotone decreasing if for all `i <= j`, `nums[i] >= nums[j]`.

Given an integer array `nums`, return `true` _if the given array is monotonic, or_ `false` _otherwise_.

**Example 1:**

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

**Example 2:**

**Input:** nums = \[6,5,4,4\]
**Output:** true

**Example 3:**

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

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-105 <= nums[i] <= 105`
Increasing Order Search Tree

Given the `root` of a binary search tree, rearrange the tree in **in-order** so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   The number of nodes in the given tree will be in the range `[1, 100]`.
*   `0 <= Node.val <= 1000`
Bitwise ORs of Subarrays

Given an integer array `arr`, return _the number of distinct bitwise ORs of all the non-empty subarrays of_ `arr`.

The bitwise OR of a subarray is the bitwise OR of each integer in the subarray. The bitwise OR of a subarray of one integer is that integer.

A **subarray** is a contiguous non-empty sequence of elements within an array.

**Example 1:**

**Input:** arr = \[0\]
**Output:** 1
**Explanation:** There is only one possible result: 0.

**Example 2:**

**Input:** arr = \[1,1,2\]
**Output:** 3
**Explanation:** The possible subarrays are \[1\], \[1\], \[2\], \[1, 1\], \[1, 2\], \[1, 1, 2\].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.

**Example 3:**

**Input:** arr = \[1,2,4\]
**Output:** 6
**Explanation:** The possible results are 1, 2, 3, 4, 6, and 7.

**Constraints:**

*   `1 <= arr.length <= 5 * 104`
*   `0 <= arr[i] <= 109`
Orderly Queue

You are given a string `s` and an integer `k`. You can choose one of the first `k` letters of `s` and append it at the end of the string..

Return _the lexicographically smallest string you could have after applying the mentioned step any number of moves_.

**Example 1:**

**Input:** s =  "cba ", k = 1
**Output:**  "acb "
**Explanation:** 
In the first move, we move the 1st character 'c' to the end, obtaining the string  "bac ".
In the second move, we move the 1st character 'b' to the end, obtaining the final result  "acb ".

**Example 2:**

**Input:** s =  "baaca ", k = 3
**Output:**  "aaabc "
**Explanation:** 
In the first move, we move the 1st character 'b' to the end, obtaining the string  "aacab ".
In the second move, we move the 3rd character 'c' to the end, obtaining the final result  "aaabc ".

**Constraints:**

*   `1 <= k <= s.length <= 1000`
*   `s` consist of lowercase English letters.
RLE Iterator

We can use run-length encoding (i.e., **RLE**) to encode a sequence of integers. In a run-length encoded array of even length `encoding` (**0-indexed**), for all even `i`, `encoding[i]` tells us the number of times that the non-negative integer value `encoding[i + 1]` is repeated in the sequence.

*   For example, the sequence `arr = [8,8,8,5,5]` can be encoded to be `encoding = [3,8,2,5]`. `encoding = [3,8,0,9,2,5]` and `encoding = [2,8,1,8,2,5]` are also valid **RLE** of `arr`.

Given a run-length encoded array, design an iterator that iterates through it.

Implement the `RLEIterator` class:

*   `RLEIterator(int[] encoded)` Initializes the object with the encoded array `encoded`.
*   `int next(int n)` Exhausts the next `n` elements and returns the last element exhausted in this way. If there is no element left to exhaust, return `-1` instead.

**Example 1:**

**Input**
\[ "RLEIterator ",  "next ",  "next ",  "next ",  "next "\]
\[\[\[3, 8, 0, 9, 2, 5\]\], \[2\], \[1\], \[1\], \[2\]\]
**Output**
\[null, 8, 8, 5, -1\]

**Explanation**
RLEIterator rLEIterator = new RLEIterator(\[3, 8, 0, 9, 2, 5\]); // This maps to the sequence \[8,8,8,5,5\].
rLEIterator.next(2); // exhausts 2 terms of the sequence, returning 8. The remaining sequence is now \[8, 5, 5\].
rLEIterator.next(1); // exhausts 1 term of the sequence, returning 8. The remaining sequence is now \[5, 5\].
rLEIterator.next(1); // exhausts 1 term of the sequence, returning 5. The remaining sequence is now \[5\].
rLEIterator.next(2); // exhausts 2 terms, returning -1. This is because the first term exhausted was 5,
but the second term did not exist. Since the last term exhausted does not exist, we return -1.

**Constraints:**

*   `2 <= encoding.length <= 1000`
*   `encoding.length` is even.
*   `0 <= encoding[i] <= 109`
*   `1 <= n <= 109`
*   At most `1000` calls will be made to `next`.
Online Stock Span

Design an algorithm that collects daily price quotes for some stock and returns **the span** of that stock's price for the current day.

The **span** of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.

*   For example, if the prices of the stock in the last four days is `[7,2,1,2]` and the price of the stock today is `2`, then the span of today is `4` because starting from today, the price of the stock was less than or equal `2` for `4` consecutive days.
*   Also, if the prices of the stock in the last four days is `[7,34,1,2]` and the price of the stock today is `8`, then the span of today is `3` because starting from today, the price of the stock was less than or equal `8` for `3` consecutive days.

Implement the `StockSpanner` class:

*   `StockSpanner()` Initializes the object of the class.
*   `int next(int price)` Returns the **span** of the stock's price given that today's price is `price`.

**Example 1:**

**Input**
\[ "StockSpanner ",  "next ",  "next ",  "next ",  "next ",  "next ",  "next ",  "next "\]
\[\[\], \[100\], \[80\], \[60\], \[70\], \[60\], \[75\], \[85\]\]
**Output**
\[null, 1, 1, 1, 2, 1, 4, 6\]

**Explanation**
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80);  // return 1
stockSpanner.next(60);  // return 1
stockSpanner.next(70);  // return 2
stockSpanner.next(60);  // return 1
stockSpanner.next(75);  // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85);  // return 6

**Constraints:**

*   `1 <= price <= 105`
*   At most `104` calls will be made to `next`.
Numbers At Most N Given Digit Set

Given an array of `digits` which is sorted in **non-decreasing** order. You can write numbers using each `digits[i]` as many times as we want. For example, if `digits = ['1','3','5']`, we may write numbers such as `'13'`, `'551'`, and `'1351315'`.

Return _the number of positive integers that can be generated_ that are less than or equal to a given integer `n`.

**Example 1:**

**Input:** digits = \[ "1 ", "3 ", "5 ", "7 "\], n = 100
**Output:** 20
**Explanation:** 
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

**Example 2:**

**Input:** digits = \[ "1 ", "4 ", "9 "\], n = 1000000000
**Output:** 29523
**Explanation:** 
We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,
81 four digit numbers, 243 five digit numbers, 729 six digit numbers,
2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.
In total, this is 29523 integers that can be written using the digits array.

**Example 3:**

**Input:** digits = \[ "7 "\], n = 8
**Output:** 1

**Constraints:**

*   `1 <= digits.length <= 9`
*   `digits[i].length == 1`
*   `digits[i]` is a digit from `'1'` to `'9'`.
*   All the values in `digits` are **unique**.
*   `digits` is sorted in **non-decreasing** order.
*   `1 <= n <= 109`
Valid Permutations for DI Sequence

You are given a string `s` of length `n` where `s[i]` is either:

*   `'D'` means decreasing, or
*   `'I'` means increasing.

A permutation `perm` of `n + 1` integers of all the integers in the range `[0, n]` is called a **valid permutation** if for all valid `i`:

*   If `s[i] == 'D'`, then `perm[i] > perm[i + 1]`, and
*   If `s[i] == 'I'`, then `perm[i] < perm[i + 1]`.

Return _the number of **valid permutations**_ `perm`. Since the answer may be large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** s =  "DID "
**Output:** 5
**Explanation:** The 5 valid permutations of (0, 1, 2, 3) are:
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)

**Example 2:**

**Input:** s =  "D "
**Output:** 1

**Constraints:**

*   `n == s.length`
*   `1 <= n <= 200`
*   `s[i]` is either `'I'` or `'D'`.
Fruit Into Baskets

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array `fruits` where `fruits[i]` is the **type** of fruit the `ith` tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

*   You only have **two** baskets, and each basket can only hold a **single type** of fruit. There is no limit on the amount of fruit each basket can hold.
*   Starting from any tree of your choice, you must pick **exactly one fruit** from **every** tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
*   Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array `fruits`, return _the **maximum** number of fruits you can pick_.

**Example 1:**

**Input:** fruits = \[1,2,1\]
**Output:** 3
**Explanation:** We can pick from all 3 trees.

**Example 2:**

**Input:** fruits = \[0,1,2,2\]
**Output:** 3
**Explanation:** We can pick from trees \[1,2,2\].
If we had started at the first tree, we would only pick from trees \[0,1\].

**Example 3:**

**Input:** fruits = \[1,2,3,2,2\]
**Output:** 4
**Explanation:** We can pick from trees \[2,3,2,2\].
If we had started at the first tree, we would only pick from trees \[1,2\].

**Constraints:**

*   `1 <= fruits.length <= 105`
*   `0 <= fruits[i] < fruits.length`
Sort Array By Parity

Given an integer array `nums`, move all the even integers at the beginning of the array followed by all the odd integers.

Return _**any array** that satisfies this condition_.

**Example 1:**

**Input:** nums = \[3,1,2,4\]
**Output:** \[2,4,3,1\]
**Explanation:** The outputs \[4,2,3,1\], \[2,4,1,3\], and \[4,2,1,3\] would also be accepted.

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 5000`
*   `0 <= nums[i] <= 5000`
Super Palindromes

Let's say a positive integer is a **super-palindrome** if it is a palindrome, and it is also the square of a palindrome.

Given two positive integers `left` and `right` represented as strings, return _the number of **super-palindromes** integers in the inclusive range_ `[left, right]`.

**Example 1:**

**Input:** left =  "4 ", right =  "1000 "
**Output:** 4
**Explanation**: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 \* 26 = 676, but 26 is not a palindrome.

**Example 2:**

**Input:** left =  "1 ", right =  "2 "
**Output:** 1

**Constraints:**

*   `1 <= left.length, right.length <= 18`
*   `left` and `right` consist of only digits.
*   `left` and `right` cannot have leading zeros.
*   `left` and `right` represent integers in the range `[1, 1018 - 1]`.
*   `left` is less than or equal to `right`.
Sum of Subarray Minimums

Given an array of integers arr, find the sum of `min(b)`, where `b` ranges over every (contiguous) subarray of `arr`. Since the answer may be large, return the answer **modulo** `109 + 7`.

**Example 1:**

**Input:** arr = \[3,1,2,4\]
**Output:** 17
**Explanation:** 
Subarrays are \[3\], \[1\], \[2\], \[4\], \[3,1\], \[1,2\], \[2,4\], \[3,1,2\], \[1,2,4\], \[3,1,2,4\]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.

**Example 2:**

**Input:** arr = \[11,81,94,43,3\]
**Output:** 444

**Constraints:**

*   `1 <= arr.length <= 3 * 104`
*   `1 <= arr[i] <= 3 * 104`
Smallest Range I

You are given an integer array `nums` and an integer `k`.

In one operation, you can choose any index `i` where `0 <= i < nums.length` and change `nums[i]` to `nums[i] + x` where `x` is an integer from the range `[-k, k]`. You can apply this operation **at most once** for each index `i`.

The **score** of `nums` is the difference between the maximum and minimum elements in `nums`.

Return _the minimum **score** of_ `nums` _after applying the mentioned operation at most once for each index in it_.

**Example 1:**

**Input:** nums = \[1\], k = 0
**Output:** 0
**Explanation:** The score is max(nums) - min(nums) = 1 - 1 = 0.

**Example 2:**

**Input:** nums = \[0,10\], k = 2
**Output:** 6
**Explanation:** Change nums to be \[2, 8\]. The score is max(nums) - min(nums) = 8 - 2 = 6.

**Example 3:**

**Input:** nums = \[1,3,6\], k = 3
**Output:** 0
**Explanation:** Change nums to be \[4, 4, 4\]. The score is max(nums) - min(nums) = 4 - 4 = 0.

**Constraints:**

*   `1 <= nums.length <= 104`
*   `0 <= nums[i] <= 104`
*   `0 <= k <= 104`