bowang0911/leetcode huggingface dataset:
Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use **preorder traversal**. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as `'#'`.

For example, the above binary tree can be serialized to the string `"9,3,4,#,#,1,#,#,2,#,6,#,# "`, where `'#'` represents a null node.

Given a string of comma-separated values `preorder`, return `true` if it is a correct preorder traversal serialization of a binary tree.

It is **guaranteed** that each comma-separated value in the string must be either an integer or a character `'#'` representing null pointer.

You may assume that the input format is always valid.

*   For example, it could never contain two consecutive commas, such as `"1,,3 "`.

**Note:** You are not allowed to reconstruct the tree.

**Example 1:**

**Input:** preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
**Output:** true

**Example 2:**

**Input:** preorder = "1,#"
**Output:** false

**Example 3:**

**Input:** preorder = "9,#,#,1"
**Output:** false

**Constraints:**

*   `1 <= preorder.length <= 104`
*   `preorder` consist of integers in the range `[0, 100]` and `'#'` separated by commas `','`.
Reconstruct Itinerary

You are given a list of airline `tickets` where `tickets[i] = [fromi, toi]` represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from `"JFK "`, thus, the itinerary must begin with `"JFK "`. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

*   For example, the itinerary `[ "JFK ", "LGA "]` has a smaller lexical order than `[ "JFK ", "LGB "]`.

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

**Example 1:**

**Input:** tickets = \[\[ "MUC ", "LHR "\],\[ "JFK ", "MUC "\],\[ "SFO ", "SJC "\],\[ "LHR ", "SFO "\]\]
**Output:** \[ "JFK ", "MUC ", "LHR ", "SFO ", "SJC "\]

**Example 2:**

**Input:** tickets = \[\[ "JFK ", "SFO "\],\[ "JFK ", "ATL "\],\[ "SFO ", "ATL "\],\[ "ATL ", "JFK "\],\[ "ATL ", "SFO "\]\]
**Output:** \[ "JFK ", "ATL ", "JFK ", "SFO ", "ATL ", "SFO "\]
**Explanation:** Another possible reconstruction is \[ "JFK ", "SFO ", "ATL ", "JFK ", "ATL ", "SFO "\] but it is larger in lexical order.

**Constraints:**

*   `1 <= tickets.length <= 300`
*   `tickets[i].length == 2`
*   `fromi.length == 3`
*   `toi.length == 3`
*   `fromi` and `toi` consist of uppercase English letters.
*   `fromi != toi`
Largest BST Subtree

Given the root of a binary tree, find the largest subtree, which is also a Binary Search Tree (BST), where the largest means subtree has the largest number of nodes.

A **Binary Search Tree (BST)** is a tree in which all the nodes follow the below-mentioned properties:

*   The left subtree values are less than the value of their parent (root) node's value.
*   The right subtree values are greater than the value of their parent (root) node's value.

**Note:** A subtree must include all of its descendants.

**Example 1:**

**Input:** root = \[10,5,15,1,8,null,7\]
**Output:** 3
**Explanation:** The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

**Example 2:**

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

**Constraints:**

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

**Follow up:** Can you figure out ways to solve it with `O(n)` time complexity?
Increasing Triplet Subsequence

Given an integer array `nums`, return `true` _if there exists a triple of indices_ `(i, j, k)` _such that_ `i < j < k` _and_ `nums[i] < nums[j] < nums[k]`. If no such indices exists, return `false`.

**Example 1:**

**Input:** nums = \[1,2,3,4,5\]
**Output:** true
**Explanation:** Any triplet where i < j < k is valid.

**Example 2:**

**Input:** nums = \[5,4,3,2,1\]
**Output:** false
**Explanation:** No triplet exists.

**Example 3:**

**Input:** nums = \[2,1,5,0,4,6\]
**Output:** true
**Explanation:** The triplet (3, 4, 5) is valid because nums\[3\] == 0 < nums\[4\] == 4 < nums\[5\] == 6.

**Constraints:**

*   `1 <= nums.length <= 5 * 105`
*   `-231 <= nums[i] <= 231 - 1`

**Follow up:** Could you implement a solution that runs in `O(n)` time complexity and `O(1)` space complexity?
Self Crossing

You are given an array of integers `distance`.

You start at the point `(0, 0)` on an **X-Y plane,** and you move `distance[0]` meters to the north, then `distance[1]` meters to the west, `distance[2]` meters to the south, `distance[3]` meters to the east, and so on. In other words, after each move, your direction changes counter-clockwise.

Return `true` _if your path crosses itself or_ `false` _if it does not_.

**Example 1:**

**Input:** distance = \[2,1,1,2\]
**Output:** true
**Explanation:** The path crosses itself at the point (0, 1).

**Example 2:**

**Input:** distance = \[1,2,3,4\]
**Output:** false
**Explanation:** The path does not cross itself at any point.

**Example 3:**

**Input:** distance = \[1,1,1,2,1\]
**Output:** true
**Explanation:** The path crosses itself at the point (0, 0).

**Constraints:**

*   `1 <= distance.length <= 105`
*   `1 <= distance[i] <= 105`
Palindrome Pairs

You are given a **0-indexed** array of **unique** strings `words`.

A **palindrome pair** is a pair of integers `(i, j)` such that:

*   `0 <= i, j < words.length`,
*   `i != j`, and
*   `words[i] + words[j]` (the concatenation of the two strings) is a palindrome.

Return _an array of all the **palindrome pairs** of_ `words`.

**Example 1:**

**Input:** words = \[ "abcd ", "dcba ", "lls ", "s ", "sssll "\]
**Output:** \[\[0,1\],\[1,0\],\[3,2\],\[2,4\]\]
**Explanation:** The palindromes are \[ "abcddcba ", "dcbaabcd ", "slls ", "llssssll "\]

**Example 2:**

**Input:** words = \[ "bat ", "tab ", "cat "\]
**Output:** \[\[0,1\],\[1,0\]\]
**Explanation:** The palindromes are \[ "battab ", "tabbat "\]

**Example 3:**

**Input:** words = \[ "a ", " "\]
**Output:** \[\[0,1\],\[1,0\]\]
**Explanation:** The palindromes are \[ "a ", "a "\]

**Constraints:**

*   `1 <= words.length <= 5000`
*   `0 <= words[i].length <= 300`
*   `words[i]` consists of lowercase English letters.
House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called `root`.

Besides the `root`, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if **two directly-linked houses were broken into on the same night**.

Given the `root` of the binary tree, return _the maximum amount of money the thief can rob **without alerting the police**_.

**Example 1:**

**Input:** root = \[3,2,3,null,3,null,1\]
**Output:** 7
**Explanation:** Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

**Example 2:**

**Input:** root = \[3,4,5,1,3,null,1\]
**Output:** 9
**Explanation:** Maximum amount of money the thief can rob = 4 + 5 = 9.

**Constraints:**

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

Given an integer `n`, return _an array_ `ans` _of length_ `n + 1` _such that for each_ `i` (`0 <= i <= n`)_,_ `ans[i]` _is the **number of**_ `1`_**'s** in the binary representation of_ `i`.

**Example 1:**

**Input:** n = 2
**Output:** \[0,1,1\]
**Explanation:**
0 --> 0
1 --> 1
2 --> 10

**Example 2:**

**Input:** n = 5
**Output:** \[0,1,1,2,1,2\]
**Explanation:**
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

**Constraints:**

*   `0 <= n <= 105`

**Follow up:**

*   It is very easy to come up with a solution with a runtime of `O(n log n)`. Can you do it in linear time `O(n)` and possibly in a single pass?
*   Can you do it without using any built-in function (i.e., like `__builtin_popcount` in C++)?
Nested List Weight Sum

You are given a nested list of integers `nestedList`. Each element is either an integer or a list whose elements may also be integers or other lists.

The **depth** of an integer is the number of lists that it is inside of. For example, the nested list `[1,[2,2],[[3],2],1]` has each integer's value set to its **depth**.

Return _the sum of each integer in_ `nestedList` _multiplied by its **depth**_.

**Example 1:**

**Input:** nestedList = \[\[1,1\],2,\[1,1\]\]
**Output:** 10
**Explanation:** Four 1's at depth 2, one 2 at depth 1. 1\*2 + 1\*2 + 2\*1 + 1\*2 + 1\*2 = 10.

**Example 2:**

**Input:** nestedList = \[1,\[4,\[6\]\]\]
**Output:** 27
**Explanation:** One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1\*1 + 4\*2 + 6\*3 = 27.

**Example 3:**

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

**Constraints:**

*   `1 <= nestedList.length <= 50`
*   The values of the integers in the nested list is in the range `[-100, 100]`.
*   The maximum **depth** of any integer is less than or equal to `50`.
Longest Substring with At Most K Distinct Characters

Given a string `s` and an integer `k`, return _the length of the longest_ _substring_ _of_ `s` _that contains at most_ `k` _**distinct** characters_.

**Example 1:**

**Input:** s =  "eceba ", k = 2
**Output:** 3
**Explanation:** The substring is  "ece " with length 3.

**Example 2:**

**Input:** s =  "aa ", k = 1
**Output:** 2
**Explanation:** The substring is  "aa " with length 2.

**Constraints:**

*   `1 <= s.length <= 5 * 104`
*   `0 <= k <= 50`
Flatten Nested List Iterator

You are given a nested list of integers `nestedList`. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the `NestedIterator` class:

*   `NestedIterator(List nestedList)` Initializes the iterator with the nested list `nestedList`.
*   `int next()` Returns the next integer in the nested list.
*   `boolean hasNext()` Returns `true` if there are still some integers in the nested list and `false` otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = \[\]
while iterator.hasNext()
    append iterator.next() to the end of res
return res

If `res` matches the expected flattened list, then your code will be judged as correct.

**Example 1:**

**Input:** nestedList = \[\[1,1\],2,\[1,1\]\]
**Output:** \[1,1,2,1,1\]
**Explanation:** By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: \[1,1,2,1,1\].

**Example 2:**

**Input:** nestedList = \[1,\[4,\[6\]\]\]
**Output:** \[1,4,6\]
**Explanation:** By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: \[1,4,6\].

**Constraints:**

*   `1 <= nestedList.length <= 500`
*   The values of the integers in the nested list is in the range `[-106, 106]`.
Power of Four

Given an integer `n`, return _`true` if it is a power of four. Otherwise, return `false`_.

An integer `n` is a power of four, if there exists an integer `x` such that `n == 4x`.

**Example 1:**

**Input:** n = 16
**Output:** true

**Example 2:**

**Input:** n = 5
**Output:** false

**Example 3:**

**Input:** n = 1
**Output:** true

**Constraints:**

*   `-231 <= n <= 231 - 1`

**Follow up:** Could you solve it without loops/recursion?
Integer Break

Given an integer `n`, break it into the sum of `k` **positive integers**, where `k >= 2`, and maximize the product of those integers.

Return _the maximum product you can get_.

**Example 1:**

**Input:** n = 2
**Output:** 1
**Explanation:** 2 = 1 + 1, 1 \* 1 = 1.

**Example 2:**

**Input:** n = 10
**Output:** 36
**Explanation:** 10 = 3 + 3 + 4, 3 \* 3 \* 4 = 36.

**Constraints:**

*   `2 <= n <= 58`
Reverse String

Write a function that reverses a string. The input string is given as an array of characters `s`.

You must do this by modifying the input array [in-place](https://en.wikipedia.org/wiki/In-place_algorithm) with `O(1)` extra memory.

**Example 1:**

**Input:** s = \["h","e","l","l","o"\]
**Output:** \["o","l","l","e","h"\]

**Example 2:**

**Input:** s = \["H","a","n","n","a","h"\]
**Output:** \["h","a","n","n","a","H"\]

**Constraints:**

*   `1 <= s.length <= 105`
*   `s[i]` is a [printable ascii character](https://en.wikipedia.org/wiki/ASCII#Printable_characters).
Reverse Vowels of a String

Given a string `s`, reverse only all the vowels in the string and return it.

The vowels are `'a'`, `'e'`, `'i'`, `'o'`, and `'u'`, and they can appear in both lower and upper cases, more than once.

**Example 1:**

**Input:** s = "hello"
**Output:** "holle"

**Example 2:**

**Input:** s = "leetcode"
**Output:** "leotcede"

**Constraints:**

*   `1 <= s.length <= 3 * 105`
*   `s` consist of **printable ASCII** characters.
Moving Average from Data Stream

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Implement the `MovingAverage` class:

*   `MovingAverage(int size)` Initializes the object with the size of the window `size`.
*   `double next(int val)` Returns the moving average of the last `size` values of the stream.

**Example 1:**

**Input**
\[ "MovingAverage ",  "next ",  "next ",  "next ",  "next "\]
\[\[3\], \[1\], \[10\], \[3\], \[5\]\]
**Output**
\[null, 1.0, 5.5, 4.66667, 6.0\]

**Explanation**
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // return 1.0 = 1 / 1
movingAverage.next(10); // return 5.5 = (1 + 10) / 2
movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3

**Constraints:**

*   `1 <= size <= 1000`
*   `-105 <= val <= 105`
*   At most `104` calls will be made to `next`.
Top K Frequent Elements

Given an integer array `nums` and an integer `k`, return _the_ `k` _most frequent elements_. You may return the answer in **any order**.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-104 <= nums[i] <= 104`
*   `k` is in the range `[1, the number of unique elements in the array]`.
*   It is **guaranteed** that the answer is **unique**.

**Follow up:** Your algorithm's time complexity must be better than `O(n log n)`, where n is the array's size.
Design Tic-Tac-Toe

Assume the following rules are for the tic-tac-toe game on an `n x n` board between two players:

1.  A move is guaranteed to be valid and is placed on an empty block.
2.  Once a winning condition is reached, no more moves are allowed.
3.  A player who succeeds in placing `n` of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the `TicTacToe` class:

*   `TicTacToe(int n)` Initializes the object the size of the board `n`.
*   `int move(int row, int col, int player)` Indicates that the player with id `player` plays at the cell `(row, col)` of the board. The move is guaranteed to be a valid move, and the two players alternate in making moves. Return
    *   `0` if there is **no winner** after the move,
    *   `1` if **player 1** is the winner after the move, or
    *   `2` if **player 2** is the winner after the move.

**Example 1:**

**Input**
\[ "TicTacToe ",  "move ",  "move ",  "move ",  "move ",  "move ",  "move ",  "move "\]
\[\[3\], \[0, 0, 1\], \[0, 2, 2\], \[2, 2, 1\], \[1, 1, 2\], \[2, 0, 1\], \[1, 0, 2\], \[2, 1, 1\]\]
**Output**
\[null, 0, 0, 0, 0, 0, 0, 1\]

**Explanation**
TicTacToe ticTacToe = new TicTacToe(3);
Assume that player 1 is  "X " and player 2 is  "O " in the board.
ticTacToe.move(0, 0, 1); // return 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

ticTacToe.move(0, 2, 2); // return 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

ticTacToe.move(2, 2, 1); // return 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

ticTacToe.move(1, 1, 2); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

ticTacToe.move(2, 0, 1); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

ticTacToe.move(1, 0, 2); // return 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

ticTacToe.move(2, 1, 1); // return 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

**Constraints:**

*   `2 <= n <= 100`
*   player is `1` or `2`.
*   `0 <= row, col < n`
*   `(row, col)` are **unique** for each different call to `move`.
*   At most `n2` calls will be made to `move`.

**Follow-up:** Could you do better than `O(n2)` per `move()` operation?
Intersection of Two Arrays

Given two integer arrays `nums1` and `nums2`, return _an array of their intersection_. Each element in the result must be **unique** and you may return the result in **any order**.

**Example 1:**

**Input:** nums1 = \[1,2,2,1\], nums2 = \[2,2\]
**Output:** \[2\]

**Example 2:**

**Input:** nums1 = \[4,9,5\], nums2 = \[9,4,9,8,4\]
**Output:** \[9,4\]
**Explanation:** \[4,9\] is also accepted.

**Constraints:**

*   `1 <= nums1.length, nums2.length <= 1000`
*   `0 <= nums1[i], nums2[i] <= 1000`
Intersection of Two Arrays II

Given two integer arrays `nums1` and `nums2`, return _an array of their intersection_. Each element in the result must appear as many times as it shows in both arrays and you may return the result in **any order**.

**Example 1:**

**Input:** nums1 = \[1,2,2,1\], nums2 = \[2,2\]
**Output:** \[2,2\]

**Example 2:**

**Input:** nums1 = \[4,9,5\], nums2 = \[9,4,9,8,4\]
**Output:** \[4,9\]
**Explanation:** \[9,4\] is also accepted.

**Constraints:**

*   `1 <= nums1.length, nums2.length <= 1000`
*   `0 <= nums1[i], nums2[i] <= 1000`

**Follow up:**

*   What if the given array is already sorted? How would you optimize your algorithm?
*   What if `nums1`'s size is small compared to `nums2`'s size? Which algorithm is better?
*   What if elements of `nums2` are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
Android Unlock Patterns

Android devices have a special lock screen with a `3 x 3` grid of dots. Users can set an "unlock pattern " by connecting the dots in a specific sequence, forming a series of joined line segments where each segment's endpoints are two consecutive dots in the sequence. A sequence of `k` dots is a **valid** unlock pattern if both of the following are true:

*   All the dots in the sequence are **distinct**.
*   If the line segment connecting two consecutive dots in the sequence passes through the **center** of any other dot, the other dot **must have previously appeared** in the sequence. No jumps through the center non-selected dots are allowed.
    *   For example, connecting dots `2` and `9` without dots `5` or `6` appearing beforehand is valid because the line from dot `2` to dot `9` does not pass through the center of either dot `5` or `6`.
    *   However, connecting dots `1` and `3` without dot `2` appearing beforehand is invalid because the line from dot `1` to dot `3` passes through the center of dot `2`.

Here are some example valid and invalid unlock patterns:

*   The 1st pattern `[4,1,3,6]` is invalid because the line connecting dots `1` and `3` pass through dot `2`, but dot `2` did not previously appear in the sequence.
*   The 2nd pattern `[4,1,9,2]` is invalid because the line connecting dots `1` and `9` pass through dot `5`, but dot `5` did not previously appear in the sequence.
*   The 3rd pattern `[2,4,1,3,6]` is valid because it follows the conditions. The line connecting dots `1` and `3` meets the condition because dot `2` previously appeared in the sequence.
*   The 4th pattern `[6,5,4,1,9,2]` is valid because it follows the conditions. The line connecting dots `1` and `9` meets the condition because dot `5` previously appeared in the sequence.

Given two integers `m` and `n`, return _the **number of unique and valid unlock patterns** of the Android grid lock screen that consist of **at least**_ `m` _keys and **at most**_ `n` _keys._

Two unlock patterns are considered **unique** if there is a dot in one sequence that is not in the other, or the order of the dots is different.

**Example 1:**

**Input:** m = 1, n = 1
**Output:** 9

**Example 2:**

**Input:** m = 1, n = 2
**Output:** 65

**Constraints:**

*   `1 <= m, n <= 9`
Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers `a1, a2, ..., an`, summarize the numbers seen so far as a list of disjoint intervals.

Implement the `SummaryRanges` class:

*   `SummaryRanges()` Initializes the object with an empty stream.
*   `void addNum(int value)` Adds the integer `value` to the stream.
*   `int[][] getIntervals()` Returns a summary of the integers in the stream currently as a list of disjoint intervals `[starti, endi]`. The answer should be sorted by `starti`.

**Example 1:**

**Input**
\[ "SummaryRanges ",  "addNum ",  "getIntervals ",  "addNum ",  "getIntervals ",  "addNum ",  "getIntervals ",  "addNum ",  "getIntervals ",  "addNum ",  "getIntervals "\]
\[\[\], \[1\], \[\], \[3\], \[\], \[7\], \[\], \[2\], \[\], \[6\], \[\]\]
**Output**
\[null, null, \[\[1, 1\]\], null, \[\[1, 1\], \[3, 3\]\], null, \[\[1, 1\], \[3, 3\], \[7, 7\]\], null, \[\[1, 3\], \[7, 7\]\], null, \[\[1, 3\], \[6, 7\]\]\]

**Explanation**
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = \[1\]
summaryRanges.getIntervals(); // return \[\[1, 1\]\]
summaryRanges.addNum(3);      // arr = \[1, 3\]
summaryRanges.getIntervals(); // return \[\[1, 1\], \[3, 3\]\]
summaryRanges.addNum(7);      // arr = \[1, 3, 7\]
summaryRanges.getIntervals(); // return \[\[1, 1\], \[3, 3\], \[7, 7\]\]
summaryRanges.addNum(2);      // arr = \[1, 2, 3, 7\]
summaryRanges.getIntervals(); // return \[\[1, 3\], \[7, 7\]\]
summaryRanges.addNum(6);      // arr = \[1, 2, 3, 6, 7\]
summaryRanges.getIntervals(); // return \[\[1, 3\], \[6, 7\]\]

**Constraints:**

*   `0 <= value <= 104`
*   At most `3 * 104` calls will be made to `addNum` and `getIntervals`.
*   At most `102` calls will be made to `getIntervals`.

**Follow up:** What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?