bowang0911/leetcode huggingface dataset:
Lowest Common Ancestor of Deepest Leaves

Given the `root` of a binary tree, return _the lowest common ancestor of its deepest leaves_.

Recall that:

*   The node of a binary tree is a leaf if and only if it has no children
*   The depth of the root of the tree is `0`. if the depth of a node is `d`, the depth of each of its children is `d + 1`.
*   The lowest common ancestor of a set `S` of nodes, is the node `A` with the largest depth such that every node in `S` is in the subtree with root `A`.

**Example 1:**

**Input:** root = \[3,5,1,6,2,0,8,null,null,7,4\]
**Output:** \[2,7,4\]
**Explanation:** We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest leaf-nodes of the tree.
Note that nodes 6, 0, and 8 are also leaf nodes, but the depth of them is 2, but the depth of nodes 7 and 4 is 3.

**Example 2:**

**Input:** root = \[1\]
**Output:** \[1\]
**Explanation:** The root is the deepest node in the tree, and it's the lca of itself.

**Example 3:**

**Input:** root = \[0,1,3,null,2\]
**Output:** \[2\]
**Explanation:** The deepest leaf node in the tree is 2, the lca of one node is itself.

**Constraints:**

*   The number of nodes in the tree will be in the range `[1, 1000]`.
*   `0 <= Node.val <= 1000`
*   The values of the nodes in the tree are **unique**.

**Note:** This question is the same as 865: [https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/](https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/)
Longest Well-Performing Interval

We are given `hours`, a list of the number of hours worked per day for a given employee.

A day is considered to be a _tiring day_ if and only if the number of hours worked is (strictly) greater than `8`.

A _well-performing interval_ is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.

Return the length of the longest well-performing interval.

**Example 1:**

**Input:** hours = \[9,9,6,0,6,6,9\]
**Output:** 3
**Explanation:** The longest well-performing interval is \[9,9,6\].

**Example 2:**

**Input:** hours = \[6,6,6\]
**Output:** 0

**Constraints:**

*   `1 <= hours.length <= 104`
*   `0 <= hours[i] <= 16`
Smallest Sufficient Team

In a project, you have a list of required skills `req_skills`, and a list of people. The `ith` person `people[i]` contains a list of skills that the person has.

Consider a sufficient team: a set of people such that for every required skill in `req_skills`, there is at least one person in the team who has that skill. We can represent these teams by the index of each person.

*   For example, `team = [0, 1, 3]` represents the people with skills `people[0]`, `people[1]`, and `people[3]`.

Return _any sufficient team of the smallest possible size, represented by the index of each person_. You may return the answer in **any order**.

It is **guaranteed** an answer exists.

**Example 1:**

**Input:** req\_skills = \["java","nodejs","reactjs"\], people = \[\["java"\],\["nodejs"\],\["nodejs","reactjs"\]\]
**Output:** \[0,2\]

**Example 2:**

**Input:** req\_skills = \["algorithms","math","java","reactjs","csharp","aws"\], people = \[\["algorithms","math","java"\],\["algorithms","math","reactjs"\],\["java","csharp","aws"\],\["reactjs","csharp"\],\["csharp","math"\],\["aws","java"\]\]
**Output:** \[1,2\]

**Constraints:**

*   `1 <= req_skills.length <= 16`
*   `1 <= req_skills[i].length <= 16`
*   `req_skills[i]` consists of lowercase English letters.
*   All the strings of `req_skills` are **unique**.
*   `1 <= people.length <= 60`
*   `0 <= people[i].length <= 16`
*   `1 <= people[i][j].length <= 16`
*   `people[i][j]` consists of lowercase English letters.
*   All the strings of `people[i]` are **unique**.
*   Every skill in `people[i]` is a skill in `req_skills`.
*   It is guaranteed a sufficient team exists.
Number of Equivalent Domino Pairs

Given a list of `dominoes`, `dominoes[i] = [a, b]` is **equivalent to** `dominoes[j] = [c, d]` if and only if either (`a == c` and `b == d`), or (`a == d` and `b == c`) - that is, one domino can be rotated to be equal to another domino.

Return _the number of pairs_ `(i, j)` _for which_ `0 <= i < j < dominoes.length`_, and_ `dominoes[i]` _is **equivalent to**_ `dominoes[j]`.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   `1 <= dominoes.length <= 4 * 104`
*   `dominoes[i].length == 2`
*   `1 <= dominoes[i][j] <= 9`
Shortest Path with Alternating Colors

You are given an integer `n`, the number of nodes in a directed graph where the nodes are labeled from `0` to `n - 1`. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays `redEdges` and `blueEdges` where:

*   `redEdges[i] = [ai, bi]` indicates that there is a directed red edge from node `ai` to node `bi` in the graph, and
*   `blueEdges[j] = [uj, vj]` indicates that there is a directed blue edge from node `uj` to node `vj` in the graph.

Return an array `answer` of length `n`, where each `answer[x]` is the length of the shortest path from node `0` to node `x` such that the edge colors alternate along the path, or `-1` if such a path does not exist.

**Example 1:**

**Input:** n = 3, redEdges = \[\[0,1\],\[1,2\]\], blueEdges = \[\]
**Output:** \[0,1,-1\]

**Example 2:**

**Input:** n = 3, redEdges = \[\[0,1\]\], blueEdges = \[\[2,1\]\]
**Output:** \[0,1,-1\]

**Constraints:**

*   `1 <= n <= 100`
*   `0 <= redEdges.length, blueEdges.length <= 400`
*   `redEdges[i].length == blueEdges[j].length == 2`
*   `0 <= ai, bi, uj, vj < n`
Minimum Cost Tree From Leaf Values

Given an array `arr` of positive integers, consider all binary trees such that:

*   Each node has either `0` or `2` children;
*   The values of `arr` correspond to the values of each **leaf** in an in-order traversal of the tree.
*   The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively.

Among all possible binary trees considered, return _the smallest possible sum of the values of each non-leaf node_. It is guaranteed this sum fits into a **32-bit** integer.

A node is a **leaf** if and only if it has zero children.

**Example 1:**

**Input:** arr = \[6,2,4\]
**Output:** 32
**Explanation:** There are two possible trees shown.
The first has a non-leaf node sum 36, and the second has non-leaf node sum 32.

**Example 2:**

**Input:** arr = \[4,11\]
**Output:** 44

**Constraints:**

*   `2 <= arr.length <= 40`
*   `1 <= arr[i] <= 15`
*   It is guaranteed that the answer fits into a **32-bit** signed integer (i.e., it is less than 231).
Maximum of Absolute Value Expression

Given two arrays of integers with equal lengths, return the maximum value of:

`|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|`

where the maximum is taken over all `0 <= i, j < arr1.length`.

**Example 1:**

**Input:** arr1 = \[1,2,3,4\], arr2 = \[-1,4,5,6\]
**Output:** 13

**Example 2:**

**Input:** arr1 = \[1,-2,-5,0,10\], arr2 = \[0,-2,-1,-7,-4\]
**Output:** 20

**Constraints:**

*   `2 <= arr1.length == arr2.length <= 40000`
*   `-10^6 <= arr1[i], arr2[i] <= 10^6`
Largest Unique Number

Given an integer array `nums`, return _the largest integer that only occurs once_. If no integer occurs once, return `-1`.

**Example 1:**

**Input:** nums = \[5,7,3,9,4,9,8,3,1\]
**Output:** 8
**Explanation:** The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it is the answer.

**Example 2:**

**Input:** nums = \[9,9,8,8\]
**Output:** -1
**Explanation:** There is no number that occurs only once.

**Constraints:**

*   `1 <= nums.length <= 2000`
*   `0 <= nums[i] <= 1000`
Armstrong Number

Given an integer `n`, return `true` _if and only if it is an **Armstrong number**_.

The `k`\-digit number `n` is an Armstrong number if and only if the `kth` power of each digit sums to `n`.

**Example 1:**

**Input:** n = 153
**Output:** true
**Explanation:** 153 is a 3-digit number, and 153 = 13 + 53 + 33.

**Example 2:**

**Input:** n = 123
**Output:** false
**Explanation:** 123 is a 3-digit number, and 123 != 13 + 23 + 33 = 36.

**Constraints:**

*   `1 <= n <= 108`
Connecting Cities With Minimum Cost

There are `n` cities labeled from `1` to `n`. You are given the integer `n` and an array `connections` where `connections[i] = [xi, yi, costi]` indicates that the cost of connecting city `xi` and city `yi` (bidirectional connection) is `costi`.

Return _the minimum **cost** to connect all the_ `n` _cities such that there is at least one path between each pair of cities_. If it is impossible to connect all the `n` cities, return `-1`,

The **cost** is the sum of the connections' costs used.

**Example 1:**

**Input:** n = 3, connections = \[\[1,2,5\],\[1,3,6\],\[2,3,1\]\]
**Output:** 6
**Explanation:** Choosing any 2 edges will connect all cities so we choose the minimum 2.

**Example 2:**

**Input:** n = 4, connections = \[\[1,2,3\],\[3,4,4\]\]
**Output:** -1
**Explanation:** There is no way to connect all cities even if all edges are used.

**Constraints:**

*   `1 <= n <= 104`
*   `1 <= connections.length <= 104`
*   `connections[i].length == 3`
*   `1 <= xi, yi <= n`
*   `xi != yi`
*   `0 <= costi <= 105`
Parallel Courses

You are given an integer `n`, which indicates that there are `n` courses labeled from `1` to `n`. You are also given an array `relations` where `relations[i] = [prevCoursei, nextCoursei]`, representing a prerequisite relationship between course `prevCoursei` and course `nextCoursei`: course `prevCoursei` has to be taken before course `nextCoursei`.

In one semester, you can take **any number** of courses as long as you have taken all the prerequisites in the **previous** semester for the courses you are taking.

Return _the **minimum** number of semesters needed to take all courses_. If there is no way to take all the courses, return `-1`.

**Example 1:**

**Input:** n = 3, relations = \[\[1,3\],\[2,3\]\]
**Output:** 2
**Explanation:** The figure above represents the given graph.
In the first semester, you can take courses 1 and 2.
In the second semester, you can take course 3.

**Example 2:**

**Input:** n = 3, relations = \[\[1,2\],\[2,3\],\[3,1\]\]
**Output:** -1
**Explanation:** No course can be studied because they are prerequisites of each other.

**Constraints:**

*   `1 <= n <= 5000`
*   `1 <= relations.length <= 5000`
*   `relations[i].length == 2`
*   `1 <= prevCoursei, nextCoursei <= n`
*   `prevCoursei != nextCoursei`
*   All the pairs `[prevCoursei, nextCoursei]` are **unique**.
N-th Tribonacci Number

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given `n`, return the value of Tn.

**Example 1:**

**Input:** n = 4
**Output:** 4
**Explanation:**
T\_3 = 0 + 1 + 1 = 2
T\_4 = 1 + 1 + 2 = 4

**Example 2:**

**Input:** n = 25
**Output:** 1389537

**Constraints:**

*   `0 <= n <= 37`
*   The answer is guaranteed to fit within a 32-bit integer, ie. `answer <= 2^31 - 1`.
Alphabet Board Path

On an alphabet board, we start at position `(0, 0)`, corresponding to character `board[0][0]`.

Here, `board = [ "abcde ", "fghij ", "klmno ", "pqrst ", "uvwxy ", "z "]`, as shown in the diagram below.

We may make the following moves:

*   `'U'` moves our position up one row, if the position exists on the board;
*   `'D'` moves our position down one row, if the position exists on the board;
*   `'L'` moves our position left one column, if the position exists on the board;
*   `'R'` moves our position right one column, if the position exists on the board;
*   `'!'` adds the character `board[r][c]` at our current position `(r, c)` to the answer.

(Here, the only positions that exist on the board are positions with letters on them.)

Return a sequence of moves that makes our answer equal to `target` in the minimum number of moves. You may return any path that does so.

**Example 1:**

**Input:** target = "leet"
**Output:** "DDR!UURRR!!DDD!"

**Example 2:**

**Input:** target = "code"
**Output:** "RR!DDRR!UUL!R!"

**Constraints:**

*   `1 <= target.length <= 100`
*   `target` consists only of English lowercase letters.
Largest 1-Bordered Square

Given a 2D `grid` of `0`s and `1`s, return the number of elements in the largest **square** subgrid that has all `1`s on its **border**, or `0` if such a subgrid doesn't exist in the `grid`.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   `1 <= grid.length <= 100`
*   `1 <= grid[0].length <= 100`
*   `grid[i][j]` is `0` or `1`
Stone Game II

Alice and Bob continue their games with piles of stones. There are a number of piles **arranged in a row**, and each pile has a positive integer number of stones `piles[i]`. The objective of the game is to end with the most stones.

Alice and Bob take turns, with Alice starting first. Initially, `M = 1`.

On each player's turn, that player can take **all the stones** in the **first** `X` remaining piles, where `1 <= X <= 2M`. Then, we set `M = max(M, X)`.

The game continues until all the stones have been taken.

Assuming Alice and Bob play optimally, return the maximum number of stones Alice can get.

**Example 1:**

**Input:** piles = \[2,7,9,4,4\]
**Output:** 10
**Explanation:**  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

**Example 2:**

**Input:** piles = \[1,2,3,4,5,100\]
**Output:** 104

**Constraints:**

*   `1 <= piles.length <= 100`
*   `1 <= piles[i] <= 104`
Longest Common Subsequence

Given two strings `text1` and `text2`, return _the length of their longest **common subsequence**._ If there is no **common subsequence**, return `0`.

A **subsequence** of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

*   For example, `"ace "` is a subsequence of `"abcde "`.

A **common subsequence** of two strings is a subsequence that is common to both strings.

**Example 1:**

**Input:** text1 =  "abcde ", text2 =  "ace " 
**Output:** 3  
**Explanation:** The longest common subsequence is  "ace " and its length is 3.

**Example 2:**

**Input:** text1 =  "abc ", text2 =  "abc "
**Output:** 3
**Explanation:** The longest common subsequence is  "abc " and its length is 3.

**Example 3:**

**Input:** text1 =  "abc ", text2 =  "def "
**Output:** 0
**Explanation:** There is no such common subsequence, so the result is 0.

**Constraints:**

*   `1 <= text1.length, text2.length <= 1000`
*   `text1` and `text2` consist of only lowercase English characters.
Decrease Elements To Make Array Zigzag

Given an array `nums` of integers, a _move_ consists of choosing any element and **decreasing it by 1**.

An array `A` is a _zigzag array_ if either:

*   Every even-indexed element is greater than adjacent elements, ie. `A[0] > A[1] < A[2] > A[3] < A[4] > ...`
*   OR, every odd-indexed element is greater than adjacent elements, ie. `A[0] < A[1] > A[2] < A[3] > A[4] < ...`

Return the minimum number of moves to transform the given array `nums` into a zigzag array.

**Example 1:**

**Input:** nums = \[1,2,3\]
**Output:** 2
**Explanation:** We can decrease 2 to 0 or 3 to 1.

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= 1000`
Binary Tree Coloring Game

Two players play a turn based game on a binary tree. We are given the `root` of this binary tree, and the number of nodes `n` in the tree. `n` is odd, and each node has a distinct value from `1` to `n`.

Initially, the first player names a value `x` with `1 <= x <= n`, and the second player names a value `y` with `1 <= y <= n` and `y != x`. The first player colors the node with value `x` red, and the second player colors the node with value `y` blue.

Then, the players take turns starting with the first player. In each turn, that player chooses a node of their color (red if player 1, blue if player 2) and colors an **uncolored** neighbor of the chosen node (either the left child, right child, or parent of the chosen node.)

If (and only if) a player cannot choose such a node in this way, they must pass their turn. If both players pass their turn, the game ends, and the winner is the player that colored more nodes.

You are the second player. If it is possible to choose such a `y` to ensure you win the game, return `true`. If it is not possible, return `false`.

**Example 1:**

**Input:** root = \[1,2,3,4,5,6,7,8,9,10,11\], n = 11, x = 3
**Output:** true
**Explanation:** The second player can choose the node with value 2.

**Example 2:**

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

**Constraints:**

*   The number of nodes in the tree is `n`.
*   `1 <= x <= n <= 100`
*   `n` is odd.
*   1 <= Node.val <= n
*   All the values of the tree are **unique**.
Snapshot Array

Implement a SnapshotArray that supports the following interface:

*   `SnapshotArray(int length)` initializes an array-like data structure with the given length. **Initially, each element equals 0**.
*   `void set(index, val)` sets the element at the given `index` to be equal to `val`.
*   `int snap()` takes a snapshot of the array and returns the `snap_id`: the total number of times we called `snap()` minus `1`.
*   `int get(index, snap_id)` returns the value at the given `index`, at the time we took the snapshot with the given `snap_id`

**Example 1:**

**Input:** \[ "SnapshotArray ", "set ", "snap ", "set ", "get "\]
\[\[3\],\[0,5\],\[\],\[0,6\],\[0,0\]\]
**Output:** \[null,null,0,null,5\]
**Explanation:** 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array\[0\] = 5
snapshotArr.snap();  // Take a snapshot, return snap\_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array\[0\] with snap\_id = 0, return 5

**Constraints:**

*   `1 <= length <= 5 * 104`
*   `0 <= index < length`
*   `0 <= val <= 109`
*   `0 <= snap_id <` (the total number of times we call `snap()`)
*   At most `5 * 104` calls will be made to `set`, `snap`, and `get`.
Longest Chunked Palindrome Decomposition

You are given a string `text`. You should split it to k substrings `(subtext1, subtext2, ..., subtextk)` such that:

*   `subtexti` is a **non-empty** string.
*   The concatenation of all the substrings is equal to `text` (i.e., `subtext1 + subtext2 + ... + subtextk == text`).
*   `subtexti == subtextk - i + 1` for all valid values of `i` (i.e., `1 <= i <= k`).

Return the largest possible value of `k`.

**Example 1:**

**Input:** text =  "ghiabcdefhelloadamhelloabcdefghi "
**Output:** 7
**Explanation:** We can split the string on  "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi) ".

**Example 2:**

**Input:** text =  "merchant "
**Output:** 1
**Explanation:** We can split the string on  "(merchant) ".

**Example 3:**

**Input:** text =  "antaprezatepzapreanta "
**Output:** 11
**Explanation:** We can split the string on  "(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a) ".

**Constraints:**

*   `1 <= text.length <= 1000`
*   `text` consists only of lowercase English characters.
Check If a Number Is Majority Element in a Sorted Array

Given an integer array `nums` sorted in non-decreasing order and an integer `target`, return `true` _if_ `target` _is a **majority** element, or_ `false` _otherwise_.

A **majority** element in an array `nums` is an element that appears more than `nums.length / 2` times in the array.

**Example 1:**

**Input:** nums = \[2,4,5,5,5,5,5,6,6\], target = 5
**Output:** true
**Explanation:** The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

**Example 2:**

**Input:** nums = \[10,100,101,101\], target = 101
**Output:** false
**Explanation:** The value 101 appears 2 times and the length of the array is 4.
Thus, 101 is not a majority element because 2 > 4/2 is false.

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i], target <= 109`
*   `nums` is sorted in non-decreasing order.
Minimum Swaps to Group All 1's Together

Given a binary array `data`, return the minimum number of swaps required to group all `1`'s present in the array together in **any place** in the array.

**Example 1:**

**Input:** data = \[1,0,1,0,1\]
**Output:** 1
**Explanation:** There are 3 ways to group all 1's together:
\[1,1,1,0,0\] using 1 swap.
\[0,1,1,1,0\] using 2 swaps.
\[0,0,1,1,1\] using 1 swap.
The minimum is 1.

**Example 2:**

**Input:** data = \[0,0,0,1,0\]
**Output:** 0
**Explanation:** Since there is only one 1 in the array, no swaps are needed.

**Example 3:**

**Input:** data = \[1,0,1,0,1,0,0,1,1,0,1\]
**Output:** 3
**Explanation:** One possible solution that uses 3 swaps is \[0,0,0,0,0,1,1,1,1,1,1\].

**Constraints:**

*   `1 <= data.length <= 105`
*   `data[i]` is either `0` or `1`.