bowang0911/leetcode huggingface dataset:
Convert Sorted List to Binary Search Tree

Given the `head` of a singly linked list where elements are sorted in **ascending order**, convert _it to a_ **_height-balanced_** _binary search tree_.

**Example 1:**

**Input:** head = \[-10,-3,0,5,9\]
**Output:** \[0,-3,9,-10,null,5\]
**Explanation:** One possible answer is \[0,-3,9,-10,null,5\], which represents the shown height balanced BST.

**Example 2:**

**Input:** head = \[\]
**Output:** \[\]

**Constraints:**

*   The number of nodes in `head` is in the range `[0, 2 * 104]`.
*   `-105 <= Node.val <= 105`
Balanced Binary Tree

Given a binary tree, determine if it is **height-balanced**.

**Example 1:**

**Input:** root = \[3,9,20,null,null,15,7\]
**Output:** true

**Example 2:**

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

**Example 3:**

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

**Constraints:**

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

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

**Note:** A leaf is a node with no children.

**Example 1:**

**Input:** root = \[3,9,20,null,null,15,7\]
**Output:** 2

**Example 2:**

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

**Constraints:**

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

Given the `root` of a binary tree and an integer `targetSum`, return `true` if the tree has a **root-to-leaf** path such that adding up all the values along the path equals `targetSum`.

A **leaf** is a node with no children.

**Example 1:**

**Input:** root = \[5,4,8,11,null,13,4,7,2,null,null,null,1\], targetSum = 22
**Output:** true
**Explanation:** The root-to-leaf path with the target sum is shown.

**Example 2:**

**Input:** root = \[1,2,3\], targetSum = 5
**Output:** false
**Explanation:** There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

**Example 3:**

**Input:** root = \[\], targetSum = 0
**Output:** false
**Explanation:** Since the tree is empty, there are no root-to-leaf paths.

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 5000]`.
*   `-1000 <= Node.val <= 1000`
*   `-1000 <= targetSum <= 1000`
Path Sum II

Given the `root` of a binary tree and an integer `targetSum`, return _all **root-to-leaf** paths where the sum of the node values in the path equals_ `targetSum`_. Each path should be returned as a list of the node **values**, not node references_.

A **root-to-leaf** path is a path starting from the root and ending at any leaf node. A **leaf** is a node with no children.

**Example 1:**

**Input:** root = \[5,4,8,11,null,13,4,7,2,null,null,5,1\], targetSum = 22
**Output:** \[\[5,4,11,2\],\[5,8,4,5\]\]
**Explanation:** There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

**Example 2:**

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

**Example 3:**

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

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 5000]`.
*   `-1000 <= Node.val <= 1000`
*   `-1000 <= targetSum <= 1000`
Flatten Binary Tree to Linked List

Given the `root` of a binary tree, flatten the tree into a "linked list ":

*   The "linked list " should use the same `TreeNode` class where the `right` child pointer points to the next node in the list and the `left` child pointer is always `null`.
*   The "linked list " should be in the same order as a [**pre-order** **traversal**](https://en.wikipedia.org/wiki/Tree_traversal#Pre-order,_NLR) of the binary tree.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

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

**Follow up:** Can you flatten the tree in-place (with `O(1)` extra space)?
Distinct Subsequences

Given two strings `s` and `t`, return _the number of distinct_ **_subsequences_** _of_ `s` _which equals_ `t`.

The test cases are generated so that the answer fits on a 32-bit signed integer.

**Example 1:**

**Input:** s =  "rabbbit ", t =  "rabbit "
**Output:** 3
**Explanation:**
As shown below, there are 3 ways you can generate  "rabbit " from s.
`**rabb**b**it**`
`**ra**b**bbit**`
`**rab**b**bit**`

**Example 2:**

**Input:** s =  "babgbag ", t =  "bag "
**Output:** 5
**Explanation:**
As shown below, there are 5 ways you can generate  "bag " from s.
`**ba**b**g**bag`
`**ba**bgba**g**`
`**b**abgb**ag**`
`ba**b**gb**ag**`
`babg**bag**`

**Constraints:**

*   `1 <= s.length, t.length <= 1000`
*   `s` and `t` consist of English letters.
Populating Next Right Pointers in Each Node

You are given a **perfect binary tree** where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node \*left;
  Node \*right;
  Node \*next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`.

Initially, all next pointers are set to `NULL`.

**Example 1:**

**Input:** root = \[1,2,3,4,5,6,7\]
**Output:** \[1,#,2,3,#,4,5,6,7,#\]
**Explanation:** Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

**Example 2:**

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

**Constraints:**

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

**Follow-up:**

*   You may only use constant extra space.
*   The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.
Populating Next Right Pointers in Each Node II

Given a binary tree

struct Node {
  int val;
  Node \*left;
  Node \*right;
  Node \*next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`.

Initially, all next pointers are set to `NULL`.

**Example 1:**

**Input:** root = \[1,2,3,4,5,null,7\]
**Output:** \[1,#,2,3,#,4,5,7,#\]
**Explanation:** Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

**Example 2:**

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

**Constraints:**

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

**Follow-up:**

*   You may only use constant extra space.
*   The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.
Pascal's Triangle

Given an integer `numRows`, return the first numRows of **Pascal's triangle**.

In **Pascal's triangle**, each number is the sum of the two numbers directly above it as shown:

**Example 1:**

**Input:** numRows = 5
**Output:** \[\[1\],\[1,1\],\[1,2,1\],\[1,3,3,1\],\[1,4,6,4,1\]\]

**Example 2:**

**Input:** numRows = 1
**Output:** \[\[1\]\]

**Constraints:**

*   `1 <= numRows <= 30`
Pascal's Triangle II

Given an integer `rowIndex`, return the `rowIndexth` (**0-indexed**) row of the **Pascal's triangle**.

In **Pascal's triangle**, each number is the sum of the two numbers directly above it as shown:

**Example 1:**

**Input:** rowIndex = 3
**Output:** \[1,3,3,1\]

**Example 2:**

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

**Example 3:**

**Input:** rowIndex = 1
**Output:** \[1,1\]

**Constraints:**

*   `0 <= rowIndex <= 33`

**Follow up:** Could you optimize your algorithm to use only `O(rowIndex)` extra space?
Triangle

Given a `triangle` array, return _the minimum path sum from top to bottom_.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index `i` on the current row, you may move to either index `i` or index `i + 1` on the next row.

**Example 1:**

**Input:** triangle = \[\[2\],\[3,4\],\[6,5,7\],\[4,1,8,3\]\]
**Output:** 11
**Explanation:** The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

**Example 2:**

**Input:** triangle = \[\[-10\]\]
**Output:** -10

**Constraints:**

*   `1 <= triangle.length <= 200`
*   `triangle[0].length == 1`
*   `triangle[i].length == triangle[i - 1].length + 1`
*   `-104 <= triangle[i][j] <= 104`

**Follow up:** Could you do this using only `O(n)` extra space, where `n` is the total number of rows in the triangle?
Best Time to Buy and Sell Stock

You are given an array `prices` where `prices[i]` is the price of a given stock on the `ith` day.

You want to maximize your profit by choosing a **single day** to buy one stock and choosing a **different day in the future** to sell that stock.

Return _the maximum profit you can achieve from this transaction_. If you cannot achieve any profit, return `0`.

**Example 1:**

**Input:** prices = \[7,1,5,3,6,4\]
**Output:** 5
**Explanation:** Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

**Example 2:**

**Input:** prices = \[7,6,4,3,1\]
**Output:** 0
**Explanation:** In this case, no transactions are done and the max profit = 0.

**Constraints:**

*   `1 <= prices.length <= 105`
*   `0 <= prices[i] <= 104`
Best Time to Buy and Sell Stock II

You are given an integer array `prices` where `prices[i]` is the price of a given stock on the `ith` day.

On each day, you may decide to buy and/or sell the stock. You can only hold **at most one** share of the stock at any time. However, you can buy it then immediately sell it on the **same day**.

Find and return _the **maximum** profit you can achieve_.

**Example 1:**

**Input:** prices = \[7,1,5,3,6,4\]
**Output:** 7
**Explanation:** Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

**Example 2:**

**Input:** prices = \[1,2,3,4,5\]
**Output:** 4
**Explanation:** Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

**Example 3:**

**Input:** prices = \[7,6,4,3,1\]
**Output:** 0
**Explanation:** There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

**Constraints:**

*   `1 <= prices.length <= 3 * 104`
*   `0 <= prices[i] <= 104`
Best Time to Buy and Sell Stock III

You are given an array `prices` where `prices[i]` is the price of a given stock on the `ith` day.

Find the maximum profit you can achieve. You may complete **at most two transactions**.

**Note:** You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

**Example 1:**

**Input:** prices = \[3,3,5,0,0,3,1,4\]
**Output:** 6
**Explanation:** Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

**Example 2:**

**Input:** prices = \[1,2,3,4,5\]
**Output:** 4
**Explanation:** Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

**Example 3:**

**Input:** prices = \[7,6,4,3,1\]
**Output:** 0
**Explanation:** In this case, no transaction is done, i.e. max profit = 0.

**Constraints:**

*   `1 <= prices.length <= 105`
*   `0 <= prices[i] <= 105`
Binary Tree Maximum Path Sum

A **path** in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence **at most once**. Note that the path does not need to pass through the root.

The **path sum** of a path is the sum of the node's values in the path.

Given the `root` of a binary tree, return _the maximum **path sum** of any **non-empty** path_.

**Example 1:**

**Input:** root = \[1,2,3\]
**Output:** 6
**Explanation:** The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

**Example 2:**

**Input:** root = \[-10,9,20,null,null,15,7\]
**Output:** 42
**Explanation:** The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

**Constraints:**

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

A phrase is a **palindrome** if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string `s`, return `true` _if it is a **palindrome**, or_ `false` _otherwise_.

**Example 1:**

**Input:** s =  "A man, a plan, a canal: Panama "
**Output:** true
**Explanation:**  "amanaplanacanalpanama " is a palindrome.

**Example 2:**

**Input:** s =  "race a car "
**Output:** false
**Explanation:**  "raceacar " is not a palindrome.

**Example 3:**

**Input:** s =  "  "
**Output:** true
**Explanation:** s is an empty string  " " after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

**Constraints:**

*   `1 <= s.length <= 2 * 105`
*   `s` consists only of printable ASCII characters.
Word Ladder II

A **transformation sequence** from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words `beginWord -> s1 -> s2 -> ... -> sk` such that:

*   Every adjacent pair of words differs by a single letter.
*   Every `si` for `1 <= i <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`.
*   `sk == endWord`

Given two words, `beginWord` and `endWord`, and a dictionary `wordList`, return _all the **shortest transformation sequences** from_ `beginWord` _to_ `endWord`_, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words_ `[beginWord, s1, s2, ..., sk]`.

**Example 1:**

**Input:** beginWord =  "hit ", endWord =  "cog ", wordList = \[ "hot ", "dot ", "dog ", "lot ", "log ", "cog "\]
**Output:** \[\[ "hit ", "hot ", "dot ", "dog ", "cog "\],\[ "hit ", "hot ", "lot ", "log ", "cog "\]\]
**Explanation:** There are 2 shortest transformation sequences:
 "hit " ->  "hot " ->  "dot " ->  "dog " ->  "cog "
 "hit " ->  "hot " ->  "lot " ->  "log " ->  "cog "

**Example 2:**

**Input:** beginWord =  "hit ", endWord =  "cog ", wordList = \[ "hot ", "dot ", "dog ", "lot ", "log "\]
**Output:** \[\]
**Explanation:** The endWord  "cog " is not in wordList, therefore there is no valid transformation sequence.

**Constraints:**

*   `1 <= beginWord.length <= 5`
*   `endWord.length == beginWord.length`
*   `1 <= wordList.length <= 500`
*   `wordList[i].length == beginWord.length`
*   `beginWord`, `endWord`, and `wordList[i]` consist of lowercase English letters.
*   `beginWord != endWord`
*   All the words in `wordList` are **unique**.
*   The **sum** of all shortest transformation sequences does not exceed `105`.
Word Ladder

A **transformation sequence** from word `beginWord` to word `endWord` using a dictionary `wordList` is a sequence of words `beginWord -> s1 -> s2 -> ... -> sk` such that:

*   Every adjacent pair of words differs by a single letter.
*   Every `si` for `1 <= i <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`.
*   `sk == endWord`

Given two words, `beginWord` and `endWord`, and a dictionary `wordList`, return _the **number of words** in the **shortest transformation sequence** from_ `beginWord` _to_ `endWord`_, or_ `0` _if no such sequence exists._

**Example 1:**

**Input:** beginWord =  "hit ", endWord =  "cog ", wordList = \[ "hot ", "dot ", "dog ", "lot ", "log ", "cog "\]
**Output:** 5
**Explanation:** One shortest transformation sequence is  "hit " ->  "hot " ->  "dot " ->  "dog " -> cog ", which is 5 words long.

**Example 2:**

**Input:** beginWord =  "hit ", endWord =  "cog ", wordList = \[ "hot ", "dot ", "dog ", "lot ", "log "\]
**Output:** 0
**Explanation:** The endWord  "cog " is not in wordList, therefore there is no valid transformation sequence.

**Constraints:**

*   `1 <= beginWord.length <= 10`
*   `endWord.length == beginWord.length`
*   `1 <= wordList.length <= 5000`
*   `wordList[i].length == beginWord.length`
*   `beginWord`, `endWord`, and `wordList[i]` consist of lowercase English letters.
*   `beginWord != endWord`
*   All the words in `wordList` are **unique**.
Longest Consecutive Sequence

Given an unsorted array of integers `nums`, return _the length of the longest consecutive elements sequence._

You must write an algorithm that runs in `O(n)` time.

**Example 1:**

**Input:** nums = \[100,4,200,1,3,2\]
**Output:** 4
**Explanation:** The longest consecutive elements sequence is `[1, 2, 3, 4]`. Therefore its length is 4.

**Example 2:**

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

**Constraints:**

*   `0 <= nums.length <= 105`
*   `-109 <= nums[i] <= 109`
Sum Root to Leaf Numbers

You are given the `root` of a binary tree containing digits from `0` to `9` only.

Each root-to-leaf path in the tree represents a number.

*   For example, the root-to-leaf path `1 -> 2 -> 3` represents the number `123`.

Return _the total sum of all root-to-leaf numbers_. Test cases are generated so that the answer will fit in a **32-bit** integer.

A **leaf** node is a node with no children.

**Example 1:**

**Input:** root = \[1,2,3\]
**Output:** 25
**Explanation:**
The root-to-leaf path `1->2` represents the number `12`.
The root-to-leaf path `1->3` represents the number `13`.
Therefore, sum = 12 + 13 = `25`.

**Example 2:**

**Input:** root = \[4,9,0,5,1\]
**Output:** 1026
**Explanation:**
The root-to-leaf path `4->9->5` represents the number 495.
The root-to-leaf path `4->9->1` represents the number 491.
The root-to-leaf path `4->0` represents the number 40.
Therefore, sum = 495 + 491 + 40 = `1026`.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 1000]`.
*   `0 <= Node.val <= 9`
*   The depth of the tree will not exceed `10`.
Surrounded Regions

Given an `m x n` matrix `board` containing `'X'` and `'O'`, _capture all regions that are 4-directionally surrounded by_ `'X'`.

A region is **captured** by flipping all `'O'`s into `'X'`s in that surrounded region.

**Example 1:**

**Input:** board = \[\[ "X ", "X ", "X ", "X "\],\[ "X ", "O ", "O ", "X "\],\[ "X ", "X ", "O ", "X "\],\[ "X ", "O ", "X ", "X "\]\]
**Output:** \[\[ "X ", "X ", "X ", "X "\],\[ "X ", "X ", "X ", "X "\],\[ "X ", "X ", "X ", "X "\],\[ "X ", "O ", "X ", "X "\]\]
**Explanation:** Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.

**Example 2:**

**Input:** board = \[\[ "X "\]\]
**Output:** \[\[ "X "\]\]

**Constraints:**

*   `m == board.length`
*   `n == board[i].length`
*   `1 <= m, n <= 200`
*   `board[i][j]` is `'X'` or `'O'`.
Palindrome Partitioning

Given a string `s`, partition `s` such that every substring of the partition is a **palindrome**. Return _all possible palindrome partitioning of_ `s`.

**Example 1:**

**Input:** s = "aab"
**Output:** \[\["a","a","b"\],\["aa","b"\]\]

**Example 2:**

**Input:** s = "a"
**Output:** \[\["a"\]\]

**Constraints:**

*   `1 <= s.length <= 16`
*   `s` contains only lowercase English letters.
Palindrome Partitioning II

Given a string `s`, partition `s` such that every substring of the partition is a palindrome.

Return _the **minimum** cuts needed for a palindrome partitioning of_ `s`.

**Example 1:**

**Input:** s =  "aab "
**Output:** 1
**Explanation:** The palindrome partitioning \[ "aa ", "b "\] could be produced using 1 cut.

**Example 2:**

**Input:** s =  "a "
**Output:** 0

**Example 3:**

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

**Constraints:**

*   `1 <= s.length <= 2000`
*   `s` consists of lowercase English letters only.
Clone Graph

Given a reference of a node in a **[connected](https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Connected_graph)** undirected graph.

Return a [**deep copy**](https://en.wikipedia.org/wiki/Object_copying#Deep_copy) (clone) of the graph.

Each node in the graph contains a value (`int`) and a list (`List[Node]`) of its neighbors.

class Node {
    public int val;
    public List neighbors;
}

**Test case format:**

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with `val == 1`, the second node with `val == 2`, and so on. The graph is represented in the test case using an adjacency list.

**An adjacency list** is a collection of unordered **lists** used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with `val = 1`. You must return the **copy of the given node** as a reference to the cloned graph.

**Example 1:**

**Input:** adjList = \[\[2,4\],\[1,3\],\[2,4\],\[1,3\]\]
**Output:** \[\[2,4\],\[1,3\],\[2,4\],\[1,3\]\]
**Explanation:** There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

**Example 2:**

**Input:** adjList = \[\[\]\]
**Output:** \[\[\]\]
**Explanation:** Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

**Example 3:**

**Input:** adjList = \[\]
**Output:** \[\]
**Explanation:** This an empty graph, it does not have any nodes.

**Constraints:**

*   The number of nodes in the graph is in the range `[0, 100]`.
*   `1 <= Node.val <= 100`
*   `Node.val` is unique for each node.
*   There are no repeated edges and no self-loops in the graph.
*   The Graph is connected and all nodes can be visited starting from the given node.