bowang0911/leetcode huggingface dataset:
Rank Transform of a Matrix

Given an `m x n` `matrix`, return _a new matrix_ `answer` _where_ `answer[row][col]` _is the_ _**rank** of_ `matrix[row][col]`.

The **rank** is an **integer** that represents how large an element is compared to other elements. It is calculated using the following rules:

*   The rank is an integer starting from `1`.
*   If two elements `p` and `q` are in the **same row or column**, then:
    *   If `p < q` then `rank(p) < rank(q)`
    *   If `p == q` then `rank(p) == rank(q)`
    *   If `p > q` then `rank(p) > rank(q)`
*   The **rank** should be as **small** as possible.

The test cases are generated so that `answer` is unique under the given rules.

**Example 1:**

**Input:** matrix = \[\[1,2\],\[3,4\]\]
**Output:** \[\[1,2\],\[2,3\]\]
**Explanation:**
The rank of matrix\[0\]\[0\] is 1 because it is the smallest integer in its row and column.
The rank of matrix\[0\]\[1\] is 2 because matrix\[0\]\[1\] > matrix\[0\]\[0\] and matrix\[0\]\[0\] is rank 1.
The rank of matrix\[1\]\[0\] is 2 because matrix\[1\]\[0\] > matrix\[0\]\[0\] and matrix\[0\]\[0\] is rank 1.
The rank of matrix\[1\]\[1\] is 3 because matrix\[1\]\[1\] > matrix\[0\]\[1\], matrix\[1\]\[1\] > matrix\[1\]\[0\], and both matrix\[0\]\[1\] and matrix\[1\]\[0\] are rank 2.

**Example 2:**

**Input:** matrix = \[\[7,7\],\[7,7\]\]
**Output:** \[\[1,1\],\[1,1\]\]

**Example 3:**

**Input:** matrix = \[\[20,-21,14\],\[-19,4,19\],\[22,-47,24\],\[-19,4,19\]\]
**Output:** \[\[4,2,3\],\[1,3,4\],\[5,1,6\],\[1,3,4\]\]

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m, n <= 500`
*   `-109 <= matrix[row][col] <= 109`
Add Two Polynomials Represented as Linked Lists

A polynomial linked list is a special type of linked list where every node represents a term in a polynomial expression.

Each node has three attributes:

*   `coefficient`: an integer representing the number multiplier of the term. The coefficient of the term `**9**x4` is `9`.
*   `power`: an integer representing the exponent. The power of the term `9x**4**` is `4`.
*   `next`: a pointer to the next node in the list, or `null` if it is the last node of the list.

For example, the polynomial `5x3 + 4x - 7` is represented by the polynomial linked list illustrated below:

The polynomial linked list must be in its standard form: the polynomial must be in **strictly** descending order by its `power` value. Also, terms with a `coefficient` of `0` are omitted.

Given two polynomial linked list heads, `poly1` and `poly2`, add the polynomials together and return _the head of the sum of the polynomials_.

**`PolyNode` format:**

The input/output format is as a list of `n` nodes, where each node is represented as its `[coefficient, power]`. For example, the polynomial `5x3 + 4x - 7` would be represented as: `[[5,3],[4,1],[-7,0]]`.

**Example 1:**

**Input:** poly1 = \[\[1,1\]\], poly2 = \[\[1,0\]\]
**Output:** \[\[1,1\],\[1,0\]\]
**Explanation:** poly1 = x. poly2 = 1. The sum is x + 1.

**Example 2:**

**Input:** poly1 = \[\[2,2\],\[4,1\],\[3,0\]\], poly2 = \[\[3,2\],\[-4,1\],\[-1,0\]\]
**Output:** \[\[5,2\],\[2,0\]\]
**Explanation:** poly1 = 2x2 + 4x + 3. poly2 = 3x2 - 4x - 1. The sum is 5x2 + 2. Notice that we omit the  "0x " term.

**Example 3:**

**Input:** poly1 = \[\[1,2\]\], poly2 = \[\[-1,2\]\]
**Output:** \[\]
**Explanation:** The sum is 0. We return an empty list.

**Constraints:**

*   `0 <= n <= 104`
*   `-109 <= PolyNode.coefficient <= 109`
*   `PolyNode.coefficient != 0`
*   `0 <= PolyNode.power <= 109`
*   `PolyNode.power > PolyNode.next.power`
Sort Array by Increasing Frequency

Given an array of integers `nums`, sort the array in **increasing** order based on the frequency of the values. If multiple values have the same frequency, sort them in **decreasing** order.

Return the _sorted array_.

**Example 1:**

**Input:** nums = \[1,1,2,2,2,3\]
**Output:** \[3,1,1,2,2,2\]
**Explanation:** '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.

**Example 2:**

**Input:** nums = \[2,3,1,3,2\]
**Output:** \[1,3,3,2,2\]
**Explanation:** '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.

**Example 3:**

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

**Constraints:**

*   `1 <= nums.length <= 100`
*   `-100 <= nums[i] <= 100`
Widest Vertical Area Between Two Points Containing No Points

Given `n` `points` on a 2D plane where `points[i] = [xi, yi]`, Return _the **widest vertical area** between two points such that no points are inside the area._

A **vertical area** is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The **widest vertical area** is the one with the maximum width.

Note that points **on the edge** of a vertical area **are not** considered included in the area.

**Example 1:**

​

**Input:** points = \[\[8,7\],\[9,9\],\[7,4\],\[9,7\]\]
**Output:** 1
**Explanation:** Both the red and the blue area are optimal.

**Example 2:**

**Input:** points = \[\[3,1\],\[9,0\],\[1,0\],\[1,4\],\[5,3\],\[8,8\]\]
**Output:** 3

**Constraints:**

*   `n == points.length`
*   `2 <= n <= 105`
*   `points[i].length == 2`
*   `0 <= xi, yi <= 109`
Count Substrings That Differ by One Character

Given two strings `s` and `t`, find the number of ways you can choose a non-empty substring of `s` and replace a **single character** by a different character such that the resulting substring is a substring of `t`. In other words, find the number of substrings in `s` that differ from some substring in `t` by **exactly** one character.

For example, the underlined substrings in `"computer "` and `"computation "` only differ by the `'e'`/`'a'`, so this is a valid way.

Return _the number of substrings that satisfy the condition above._

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

**Example 1:**

**Input:** s =  "aba ", t =  "baba "
**Output:** 6
**Explanation:** The following are the pairs of substrings from s and t that differ by exactly 1 character:
( "aba ",  "baba ")
( "aba ",  "baba ")
( "aba ",  "baba ")
( "aba ",  "baba ")
( "aba ",  "baba ")
( "aba ",  "baba ")
The underlined portions are the substrings that are chosen from s and t.

​​**Example 2:**

**Input:** s =  "ab ", t =  "bb "
**Output:** 3
**Explanation:** The following are the pairs of substrings from s and t that differ by 1 character:
( "ab ",  "bb ")
( "ab ",  "bb ")
( "ab ",  "bb ")
​​​​The underlined portions are the substrings that are chosen from s and t.

**Constraints:**

*   `1 <= s.length, t.length <= 100`
*   `s` and `t` consist of lowercase English letters only.
Number of Ways to Form a Target String Given a Dictionary

You are given a list of strings of the **same length** `words` and a string `target`.

Your task is to form `target` using the given `words` under the following rules:

*   `target` should be formed from left to right.
*   To form the `ith` character (**0-indexed**) of `target`, you can choose the `kth` character of the `jth` string in `words` if `target[i] = words[j][k]`.
*   Once you use the `kth` character of the `jth` string of `words`, you **can no longer** use the `xth` character of any string in `words` where `x <= k`. In other words, all characters to the left of or at index `k` become unusuable for every string.
*   Repeat the process until you form the string `target`.

**Notice** that you can use **multiple characters** from the **same string** in `words` provided the conditions above are met.

Return _the number of ways to form `target` from `words`_. Since the answer may be too large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** words = \[ "acca ", "bbbb ", "caca "\], target =  "aba "
**Output:** 6
**Explanation:** There are 6 ways to form target.
 "aba " -> index 0 ( "acca "), index 1 ( "bbbb "), index 3 ( "caca ")
 "aba " -> index 0 ( "acca "), index 2 ( "bbbb "), index 3 ( "caca ")
 "aba " -> index 0 ( "acca "), index 1 ( "bbbb "), index 3 ( "acca ")
 "aba " -> index 0 ( "acca "), index 2 ( "bbbb "), index 3 ( "acca ")
 "aba " -> index 1 ( "caca "), index 2 ( "bbbb "), index 3 ( "acca ")
 "aba " -> index 1 ( "caca "), index 2 ( "bbbb "), index 3 ( "caca ")

**Example 2:**

**Input:** words = \[ "abba ", "baab "\], target =  "bab "
**Output:** 4
**Explanation:** There are 4 ways to form target.
 "bab " -> index 0 ( "baab "), index 1 ( "baab "), index 2 ( "abba ")
 "bab " -> index 0 ( "baab "), index 1 ( "baab "), index 3 ( "baab ")
 "bab " -> index 0 ( "baab "), index 2 ( "baab "), index 3 ( "baab ")
 "bab " -> index 1 ( "abba "), index 2 ( "baab "), index 3 ( "baab ")

**Constraints:**

*   `1 <= words.length <= 1000`
*   `1 <= words[i].length <= 1000`
*   All strings in `words` have the same length.
*   `1 <= target.length <= 1000`
*   `words[i]` and `target` contain only lowercase English letters.
Check Array Formation Through Concatenation

You are given an array of **distinct** integers `arr` and an array of integer arrays `pieces`, where the integers in `pieces` are **distinct**. Your goal is to form `arr` by concatenating the arrays in `pieces` **in any order**. However, you are **not** allowed to reorder the integers in each array `pieces[i]`.

Return `true` _if it is possible_ _to form the array_ `arr` _from_ `pieces`. Otherwise, return `false`.

**Example 1:**

**Input:** arr = \[15,88\], pieces = \[\[88\],\[15\]\]
**Output:** true
**Explanation:** Concatenate \[15\] then \[88\]

**Example 2:**

**Input:** arr = \[49,18,16\], pieces = \[\[16,18,49\]\]
**Output:** false
**Explanation:** Even though the numbers match, we cannot reorder pieces\[0\].

**Example 3:**

**Input:** arr = \[91,4,64,78\], pieces = \[\[78\],\[4,64\],\[91\]\]
**Output:** true
**Explanation:** Concatenate \[91\] then \[4,64\] then \[78\]

**Constraints:**

*   `1 <= pieces.length <= arr.length <= 100`
*   `sum(pieces[i].length) == arr.length`
*   `1 <= pieces[i].length <= arr.length`
*   `1 <= arr[i], pieces[i][j] <= 100`
*   The integers in `arr` are **distinct**.
*   The integers in `pieces` are **distinct** (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).
Count Sorted Vowel Strings

Given an integer `n`, return _the number of strings of length_ `n` _that consist only of vowels (_`a`_,_ `e`_,_ `i`_,_ `o`_,_ `u`_) and are **lexicographically sorted**._

A string `s` is **lexicographically sorted** if for all valid `i`, `s[i]` is the same as or comes before `s[i+1]` in the alphabet.

**Example 1:**

**Input:** n = 1
**Output:** 5
**Explanation:** The 5 sorted strings that consist of vowels only are `[ "a ", "e ", "i ", "o ", "u "].`

**Example 2:**

**Input:** n = 2
**Output:** 15
**Explanation:** The 15 sorted strings that consist of vowels only are
\[ "aa ", "ae ", "ai ", "ao ", "au ", "ee ", "ei ", "eo ", "eu ", "ii ", "io ", "iu ", "oo ", "ou ", "uu "\].
Note that  "ea " is not a valid string since 'e' comes after 'a' in the alphabet.

**Example 3:**

**Input:** n = 33
**Output:** 66045

**Constraints:**

*   `1 <= n <= 50`
Furthest Building You Can Reach

You are given an integer array `heights` representing the heights of buildings, some `bricks`, and some `ladders`.

You start your journey from building `0` and move to the next building by possibly using bricks or ladders.

While moving from building `i` to building `i+1` (**0-indexed**),

*   If the current building's height is **greater than or equal** to the next building's height, you do **not** need a ladder or bricks.
*   If the current building's height is **less than** the next building's height, you can either use **one ladder** or `(h[i+1] - h[i])` **bricks**.

_Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally._

**Example 1:**

**Input:** heights = \[4,2,7,6,9,14,12\], bricks = 5, ladders = 1
**Output:** 4
**Explanation:** Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

**Example 2:**

**Input:** heights = \[4,12,2,7,3,18,20,3,19\], bricks = 10, ladders = 2
**Output:** 7

**Example 3:**

**Input:** heights = \[14,3,19,3\], bricks = 17, ladders = 0
**Output:** 3

**Constraints:**

*   `1 <= heights.length <= 105`
*   `1 <= heights[i] <= 106`
*   `0 <= bricks <= 109`
*   `0 <= ladders <= heights.length`
Kth Smallest Instructions

Bob is standing at cell `(0, 0)`, and he wants to reach `destination`: `(row, column)`. He can only travel **right** and **down**. You are going to help Bob by providing **instructions** for him to reach `destination`.

The **instructions** are represented as a string, where each character is either:

*   `'H'`, meaning move horizontally (go **right**), or
*   `'V'`, meaning move vertically (go **down**).

Multiple **instructions** will lead Bob to `destination`. For example, if `destination` is `(2, 3)`, both `"HHHVV "` and `"HVHVH "` are valid **instructions**.

However, Bob is very picky. Bob has a lucky number `k`, and he wants the `kth` **lexicographically smallest instructions** that will lead him to `destination`. `k` is **1-indexed**.

Given an integer array `destination` and an integer `k`, return _the_ `kth` _**lexicographically smallest instructions** that will take Bob to_ `destination`.

**Example 1:**

**Input:** destination = \[2,3\], k = 1
**Output:**  "HHHVV "
**Explanation:** All the instructions that reach (2, 3) in lexicographic order are as follows:
\[ "HHHVV ",  "HHVHV ",  "HHVVH ",  "HVHHV ",  "HVHVH ",  "HVVHH ",  "VHHHV ",  "VHHVH ",  "VHVHH ",  "VVHHH "\].

**Example 2:**

**Input:** destination = \[2,3\], k = 2
**Output:**  "HHVHV "

**Example 3:**

**Input:** destination = \[2,3\], k = 3
**Output:**  "HHVVH "

**Constraints:**

*   `destination.length == 2`
*   `1 <= row, column <= 15`
*   `1 <= k <= nCr(row + column, row)`, where `nCr(a, b)` denotes `a` choose `b`​​​​​.
Lowest Common Ancestor of a Binary Tree II

Given the `root` of a binary tree, return _the lowest common ancestor (LCA) of two given nodes,_ `p` _and_ `q`. If either node `p` or `q` **does not exist** in the tree, return `null`. All values of the nodes in the tree are **unique**.

According to the **[definition of LCA on Wikipedia](https://en.wikipedia.org/wiki/Lowest_common_ancestor)**: "The lowest common ancestor of two nodes `p` and `q` in a binary tree `T` is the lowest node that has both `p` and `q` as **descendants** (where we allow **a node to be a descendant of itself**) ". A **descendant** of a node `x` is a node `y` that is on the path from node `x` to some leaf node.

**Example 1:**

**Input:** root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 1
**Output:** 3
**Explanation:** The LCA of nodes 5 and 1 is 3.

**Example 2:**

**Input:** root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 4
**Output:** 5
**Explanation:** The LCA of nodes 5 and 4 is 5. A node can be a descendant of itself according to the definition of LCA.

**Example 3:**

**Input:** root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 10
**Output:** null
**Explanation:** Node 10 does not exist in the tree, so return null.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `-109 <= Node.val <= 109`
*   All `Node.val` are **unique**.
*   `p != q`

**Follow up:** Can you find the LCA traversing the tree, without checking nodes existence?
Get Maximum in Generated Array

You are given an integer `n`. A **0-indexed** integer array `nums` of length `n + 1` is generated in the following way:

*   `nums[0] = 0`
*   `nums[1] = 1`
*   `nums[2 * i] = nums[i]` when `2 <= 2 * i <= n`
*   `nums[2 * i + 1] = nums[i] + nums[i + 1]` when `2 <= 2 * i + 1 <= n`

Return _the **maximum** integer in the array_ `nums`​​​.

**Example 1:**

**Input:** n = 7
**Output:** 3
**Explanation:** According to the given rules:
  nums\[0\] = 0
  nums\[1\] = 1
  nums\[(1 \* 2) = 2\] = nums\[1\] = 1
  nums\[(1 \* 2) + 1 = 3\] = nums\[1\] + nums\[2\] = 1 + 1 = 2
  nums\[(2 \* 2) = 4\] = nums\[2\] = 1
  nums\[(2 \* 2) + 1 = 5\] = nums\[2\] + nums\[3\] = 1 + 2 = 3
  nums\[(3 \* 2) = 6\] = nums\[3\] = 2
  nums\[(3 \* 2) + 1 = 7\] = nums\[3\] + nums\[4\] = 2 + 1 = 3
Hence, nums = \[0,1,1,2,1,3,2,3\], and the maximum is max(0,1,1,2,1,3,2,3) = 3.

**Example 2:**

**Input:** n = 2
**Output:** 1
**Explanation:** According to the given rules, nums = \[0,1,1\]. The maximum is max(0,1,1) = 1.

**Example 3:**

**Input:** n = 3
**Output:** 2
**Explanation:** According to the given rules, nums = \[0,1,1,2\]. The maximum is max(0,1,1,2) = 2.

**Constraints:**

*   `0 <= n <= 100`
Minimum Deletions to Make Character Frequencies Unique

A string `s` is called **good** if there are no two different characters in `s` that have the same **frequency**.

Given a string `s`, return _the **minimum** number of characters you need to delete to make_ `s` _**good**._

The **frequency** of a character in a string is the number of times it appears in the string. For example, in the string `"aab "`, the **frequency** of `'a'` is `2`, while the **frequency** of `'b'` is `1`.

**Example 1:**

**Input:** s =  "aab "
**Output:** 0
**Explanation:** `s` is already good.

**Example 2:**

**Input:** s =  "aaabbbcc "
**Output:** 2
**Explanation:** You can delete two 'b's resulting in the good string  "aaabcc ".
Another way it to delete one 'b' and one 'c' resulting in the good string  "aaabbc ".

**Example 3:**

**Input:** s =  "ceabaacb "
**Output:** 2
**Explanation:** You can delete both 'c's resulting in the good string  "eabaab ".
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` contains only lowercase English letters.
Sell Diminishing-Valued Colored Balls

You have an `inventory` of different colored balls, and there is a customer that wants `orders` balls of **any** color.

The customer weirdly values the colored balls. Each colored ball's value is the number of balls **of that color** you currently have in your `inventory`. For example, if you own `6` yellow balls, the customer would pay `6` for the first yellow ball. After the transaction, there are only `5` yellow balls left, so the next yellow ball is then valued at `5` (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, `inventory`, where `inventory[i]` represents the number of balls of the `ith` color that you initially own. You are also given an integer `orders`, which represents the total number of balls that the customer wants. You can sell the balls **in any order**.

Return _the **maximum** total value that you can attain after selling_ `orders` _colored balls_. As the answer may be too large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** inventory = \[2,5\], orders = 4
**Output:** 14
**Explanation:** Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.

**Example 2:**

**Input:** inventory = \[3,5\], orders = 6
**Output:** 19
**Explanation:** Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2).
The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.

**Constraints:**

*   `1 <= inventory.length <= 105`
*   `1 <= inventory[i] <= 109`
*   `1 <= orders <= min(sum(inventory[i]), 109)`
Create Sorted Array through Instructions

Given an integer array `instructions`, you are asked to create a sorted array from the elements in `instructions`. You start with an empty container `nums`. For each element from **left to right** in `instructions`, insert it into `nums`. The **cost** of each insertion is the **minimum** of the following:

*   The number of elements currently in `nums` that are **strictly less than** `instructions[i]`.
*   The number of elements currently in `nums` that are **strictly greater than** `instructions[i]`.

For example, if inserting element `3` into `nums = [1,2,3,5]`, the **cost** of insertion is `min(2, 1)` (elements `1` and `2` are less than `3`, element `5` is greater than `3`) and `nums` will become `[1,2,3,3,5]`.

Return _the **total cost** to insert all elements from_ `instructions` _into_ `nums`. Since the answer may be large, return it **modulo** `109 + 7`

**Example 1:**

**Input:** instructions = \[1,5,6,2\]
**Output:** 1
**Explanation:** Begin with nums = \[\].
Insert 1 with cost min(0, 0) = 0, now nums = \[1\].
Insert 5 with cost min(1, 0) = 0, now nums = \[1,5\].
Insert 6 with cost min(2, 0) = 0, now nums = \[1,5,6\].
Insert 2 with cost min(1, 2) = 1, now nums = \[1,2,5,6\].
The total cost is 0 + 0 + 0 + 1 = 1.

**Example 2:**

**Input:** instructions = \[1,2,3,6,5,4\]
**Output:** 3
**Explanation:** Begin with nums = \[\].
Insert 1 with cost min(0, 0) = 0, now nums = \[1\].
Insert 2 with cost min(1, 0) = 0, now nums = \[1,2\].
Insert 3 with cost min(2, 0) = 0, now nums = \[1,2,3\].
Insert 6 with cost min(3, 0) = 0, now nums = \[1,2,3,6\].
Insert 5 with cost min(3, 1) = 1, now nums = \[1,2,3,5,6\].
Insert 4 with cost min(3, 2) = 2, now nums = \[1,2,3,4,5,6\].
The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.

**Example 3:**

**Input:** instructions = \[1,3,3,3,2,4,2,1,2\]
**Output:** 4
**Explanation:** Begin with nums = \[\].
Insert 1 with cost min(0, 0) = 0, now nums = \[1\].
Insert 3 with cost min(1, 0) = 0, now nums = \[1,3\].
Insert 3 with cost min(1, 0) = 0, now nums = \[1,3,3\].
Insert 3 with cost min(1, 0) = 0, now nums = \[1,3,3,3\].
Insert 2 with cost min(1, 3) = 1, now nums = \[1,2,3,3,3\].
Insert 4 with cost min(5, 0) = 0, now nums = \[1,2,3,3,3,4\].
​​​​​​​Insert 2 with cost min(1, 4) = 1, now nums = \[1,2,2,3,3,3,4\].
​​​​​​​Insert 1 with cost min(0, 6) = 0, now nums = \[1,1,2,2,3,3,3,4\].
​​​​​​​Insert 2 with cost min(2, 4) = 2, now nums = \[1,1,2,2,2,3,3,3,4\].
The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.

**Constraints:**

*   `1 <= instructions.length <= 105`
*   `1 <= instructions[i] <= 105`
Lowest Common Ancestor of a Binary Tree III

Given two nodes of a binary tree `p` and `q`, return _their lowest common ancestor (LCA)_.

Each node will have a reference to its parent node. The definition for `Node` is below:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

According to the **[definition of LCA on Wikipedia](https://en.wikipedia.org/wiki/Lowest_common_ancestor)**: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow **a node to be a descendant of itself**). "

**Example 1:**

**Input:** root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 1
**Output:** 3
**Explanation:** The LCA of nodes 5 and 1 is 3.

**Example 2:**

**Input:** root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 4
**Output:** 5
**Explanation:** The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.

**Example 3:**

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

**Constraints:**

*   The number of nodes in the tree is in the range `[2, 105]`.
*   `-109 <= Node.val <= 109`
*   All `Node.val` are **unique**.
*   `p != q`
*   `p` and `q` exist in the tree.