bowang0911/leetcode huggingface dataset:
Number of Islands II

You are given an empty 2D binary grid `grid` of size `m x n`. The grid represents a map where `0`'s represent water and `1`'s represent land. Initially, all the cells of `grid` are water cells (i.e., all the cells are `0`'s).

We may perform an add land operation which turns the water at position into a land. You are given an array `positions` where `positions[i] = [ri, ci]` is the position `(ri, ci)` at which we should operate the `ith` operation.

Return _an array of integers_ `answer` _where_ `answer[i]` _is the number of islands after turning the cell_ `(ri, ci)` _into a land_.

An **island** is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

**Example 1:**

**Input:** m = 3, n = 3, positions = \[\[0,0\],\[0,1\],\[1,2\],\[2,1\]\]
**Output:** \[1,1,2,3\]
**Explanation:**
Initially, the 2d grid is filled with water.
- Operation #1: addLand(0, 0) turns the water at grid\[0\]\[0\] into a land. We have 1 island.
- Operation #2: addLand(0, 1) turns the water at grid\[0\]\[1\] into a land. We still have 1 island.
- Operation #3: addLand(1, 2) turns the water at grid\[1\]\[2\] into a land. We have 2 islands.
- Operation #4: addLand(2, 1) turns the water at grid\[2\]\[1\] into a land. We have 3 islands.

**Example 2:**

**Input:** m = 1, n = 1, positions = \[\[0,0\]\]
**Output:** \[1\]

**Constraints:**

*   `1 <= m, n, positions.length <= 104`
*   `1 <= m * n <= 104`
*   `positions[i].length == 2`
*   `0 <= ri < m`
*   `0 <= ci < n`

**Follow up:** Could you solve it in time complexity `O(k log(mn))`, where `k == positions.length`?
Additive Number

An **additive number** is a string whose digits can form an **additive sequence**.

A valid **additive sequence** should contain **at least** three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits, return `true` if it is an **additive number** or `false` otherwise.

**Note:** Numbers in the additive sequence **cannot** have leading zeros, so sequence `1, 2, 03` or `1, 02, 3` is invalid.

**Example 1:**

**Input:**  "112358 "
**Output:** true
**Explanation:** 
The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

**Example 2:**

**Input:**  "199100199 "
**Output:** true
**Explanation:** 
The additive sequence is: 1, 99, 100, 199. 
1 + 99 = 100, 99 + 100 = 199

**Constraints:**

*   `1 <= num.length <= 35`
*   `num` consists only of digits.

**Follow up:** How would you handle overflow for very large input integers?
Range Sum Query - Mutable

Given an integer array `nums`, handle multiple queries of the following types:

1.  **Update** the value of an element in `nums`.
2.  Calculate the **sum** of the elements of `nums` between indices `left` and `right` **inclusive** where `left <= right`.

Implement the `NumArray` class:

*   `NumArray(int[] nums)` Initializes the object with the integer array `nums`.
*   `void update(int index, int val)` **Updates** the value of `nums[index]` to be `val`.
*   `int sumRange(int left, int right)` Returns the **sum** of the elements of `nums` between indices `left` and `right` **inclusive** (i.e. `nums[left] + nums[left + 1] + ... + nums[right]`).

**Example 1:**

**Input**
\[ "NumArray ",  "sumRange ",  "update ",  "sumRange "\]
\[\[\[1, 3, 5\]\], \[0, 2\], \[1, 2\], \[0, 2\]\]
**Output**
\[null, 9, null, 8\]

**Explanation**
NumArray numArray = new NumArray(\[1, 3, 5\]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = \[1, 2, 5\]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

**Constraints:**

*   `1 <= nums.length <= 3 * 104`
*   `-100 <= nums[i] <= 100`
*   `0 <= index < nums.length`
*   `-100 <= val <= 100`
*   `0 <= left <= right < nums.length`
*   At most `3 * 104` calls will be made to `update` and `sumRange`.
Range Sum Query 2D - Mutable

Given a 2D matrix `matrix`, handle multiple queries of the following types:

1.  **Update** the value of a cell in `matrix`.
2.  Calculate the **sum** of the elements of `matrix` inside the rectangle defined by its **upper left corner** `(row1, col1)` and **lower right corner** `(row2, col2)`.

Implement the NumMatrix class:

*   `NumMatrix(int[][] matrix)` Initializes the object with the integer matrix `matrix`.
*   `void update(int row, int col, int val)` **Updates** the value of `matrix[row][col]` to be `val`.
*   `int sumRegion(int row1, int col1, int row2, int col2)` Returns the **sum** of the elements of `matrix` inside the rectangle defined by its **upper left corner** `(row1, col1)` and **lower right corner** `(row2, col2)`.

**Example 1:**

**Input**
\[ "NumMatrix ",  "sumRegion ",  "update ",  "sumRegion "\]
\[\[\[\[3, 0, 1, 4, 2\], \[5, 6, 3, 2, 1\], \[1, 2, 0, 1, 5\], \[4, 1, 0, 1, 7\], \[1, 0, 3, 0, 5\]\]\], \[2, 1, 4, 3\], \[3, 2, 2\], \[2, 1, 4, 3\]\]
**Output**
\[null, 8, null, 10\]

**Explanation**
NumMatrix numMatrix = new NumMatrix(\[\[3, 0, 1, 4, 2\], \[5, 6, 3, 2, 1\], \[1, 2, 0, 1, 5\], \[4, 1, 0, 1, 7\], \[1, 0, 3, 0, 5\]\]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e. sum of the left red rectangle)
numMatrix.update(3, 2, 2);       // matrix changes from left image to right image
numMatrix.sumRegion(2, 1, 4, 3); // return 10 (i.e. sum of the right red rectangle)

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m, n <= 200`
*   `-1000 <= matrix[i][j] <= 1000`
*   `0 <= row < m`
*   `0 <= col < n`
*   `-1000 <= val <= 1000`
*   `0 <= row1 <= row2 < m`
*   `0 <= col1 <= col2 < n`
*   At most `5000` calls will be made to `sumRegion` and `update`.
Best Time to Buy and Sell Stock with Cooldown

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 as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

*   After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

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

**Example 1:**

**Input:** prices = \[1,2,3,0,2\]
**Output:** 3
**Explanation:** transactions = \[buy, sell, cooldown, buy, sell\]

**Example 2:**

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

**Constraints:**

*   `1 <= prices.length <= 5000`
*   `0 <= prices[i] <= 1000`
Minimum Height Trees

A tree is an undirected graph in which any two vertices are connected by _exactly_ one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of `n` nodes labelled from `0` to `n - 1`, and an array of `n - 1` `edges` where `edges[i] = [ai, bi]` indicates that there is an undirected edge between the two nodes `ai` and `bi` in the tree, you can choose any node of the tree as the root. When you select a node `x` as the root, the result tree has height `h`. Among all possible rooted trees, those with minimum height (i.e. `min(h)`) are called **minimum height trees** (MHTs).

Return _a list of all **MHTs'** root labels_. You can return the answer in **any order**.

The **height** of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

**Example 1:**

**Input:** n = 4, edges = \[\[1,0\],\[1,2\],\[1,3\]\]
**Output:** \[1\]
**Explanation:** As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

**Example 2:**

**Input:** n = 6, edges = \[\[3,0\],\[3,1\],\[3,2\],\[3,4\],\[5,4\]\]
**Output:** \[3,4\]

**Constraints:**

*   `1 <= n <= 2 * 104`
*   `edges.length == n - 1`
*   `0 <= ai, bi < n`
*   `ai != bi`
*   All the pairs `(ai, bi)` are distinct.
*   The given input is **guaranteed** to be a tree and there will be **no repeated** edges.
Sparse Matrix Multiplication

Given two [sparse matrices](https://en.wikipedia.org/wiki/Sparse_matrix) `mat1` of size `m x k` and `mat2` of size `k x n`, return the result of `mat1 x mat2`. You may assume that multiplication is always possible.

**Example 1:**

**Input:** mat1 = \[\[1,0,0\],\[-1,0,3\]\], mat2 = \[\[7,0,0\],\[0,0,0\],\[0,0,1\]\]
**Output:** \[\[7,0,0\],\[-7,0,3\]\]

**Example 2:**

**Input:** mat1 = \[\[0\]\], mat2 = \[\[0\]\]
**Output:** \[\[0\]\]

**Constraints:**

*   `m == mat1.length`
*   `k == mat1[i].length == mat2.length`
*   `n == mat2[i].length`
*   `1 <= m, n, k <= 100`
*   `-100 <= mat1[i][j], mat2[i][j] <= 100`
Burst Balloons

You are given `n` balloons, indexed from `0` to `n - 1`. Each balloon is painted with a number on it represented by an array `nums`. You are asked to burst all the balloons.

If you burst the `ith` balloon, you will get `nums[i - 1] * nums[i] * nums[i + 1]` coins. If `i - 1` or `i + 1` goes out of bounds of the array, then treat it as if there is a balloon with a `1` painted on it.

Return _the maximum coins you can collect by bursting the balloons wisely_.

**Example 1:**

**Input:** nums = \[3,1,5,8\]
**Output:** 167
**Explanation:**
nums = \[3,1,5,8\] --> \[3,5,8\] --> \[3,8\] --> \[8\] --> \[\]
coins =  3\*1\*5    +   3\*5\*8   +  1\*3\*8  + 1\*8\*1 = 167

**Example 2:**

**Input:** nums = \[1,5\]
**Output:** 10

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 300`
*   `0 <= nums[i] <= 100`
Super Ugly Number

A **super ugly number** is a positive integer whose prime factors are in the array `primes`.

Given an integer `n` and an array of integers `primes`, return _the_ `nth` _**super ugly number**_.

The `nth` **super ugly number** is **guaranteed** to fit in a **32-bit** signed integer.

**Example 1:**

**Input:** n = 12, primes = \[2,7,13,19\]
**Output:** 32
**Explanation:** \[1,2,4,7,8,13,14,16,19,26,28,32\] is the sequence of the first 12 super ugly numbers given primes = \[2,7,13,19\].

**Example 2:**

**Input:** n = 1, primes = \[2,3,5\]
**Output:** 1
**Explanation:** 1 has no prime factors, therefore all of its prime factors are in the array primes = \[2,3,5\].

**Constraints:**

*   `1 <= n <= 105`
*   `1 <= primes.length <= 100`
*   `2 <= primes[i] <= 1000`
*   `primes[i]` is **guaranteed** to be a prime number.
*   All the values of `primes` are **unique** and sorted in **ascending order**.
Binary Tree Vertical Order Traversal

Given the `root` of a binary tree, return _**the vertical order traversal** of its nodes' values_. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from **left to right**.

**Example 1:**

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

**Example 2:**

**Input:** root = \[3,9,8,4,0,1,7\]
**Output:** \[\[4\],\[9\],\[3,0,1\],\[8\],\[7\]\]

**Example 3:**

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

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 100]`.
*   `-100 <= Node.val <= 100`
Count of Smaller Numbers After Self

Given an integer array `nums`, return _an integer array_ `counts` _where_ `counts[i]` _is the number of smaller elements to the right of_ `nums[i]`.

**Example 1:**

**Input:** nums = \[5,2,6,1\]
**Output:** \[2,1,1,0\]
**Explanation:**
To the right of 5 there are **2** smaller elements (2 and 1).
To the right of 2 there is only **1** smaller element (1).
To the right of 6 there is **1** smaller element (1).
To the right of 1 there is **0** smaller element.

**Example 2:**

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

**Example 3:**

**Input:** nums = \[-1,-1\]
**Output:** \[0,0\]

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-104 <= nums[i] <= 104`
Remove Duplicate Letters

Given a string `s`, remove duplicate letters so that every letter appears once and only once. You must make sure your result is **the smallest in lexicographical order** among all possible results.

**Example 1:**

**Input:** s =  "bcabc "
**Output:**  "abc "

**Example 2:**

**Input:** s =  "cbacdcbc "
**Output:**  "acdb "

**Constraints:**

*   `1 <= s.length <= 104`
*   `s` consists of lowercase English letters.

**Note:** This question is the same as 1081: [https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/](https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/)
Shortest Distance from All Buildings

You are given an `m x n` grid `grid` of values `0`, `1`, or `2`, where:

*   each `0` marks **an empty land** that you can pass by freely,
*   each `1` marks **a building** that you cannot pass through, and
*   each `2` marks **an obstacle** that you cannot pass through.

You want to build a house on an empty land that reaches all buildings in the **shortest total travel** distance. You can only move up, down, left, and right.

Return _the **shortest travel distance** for such a house_. If it is not possible to build such a house according to the above rules, return `-1`.

The **total travel distance** is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using [Manhattan Distance](http://en.wikipedia.org/wiki/Taxicab_geometry), where `distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|`.

**Example 1:**

**Input:** grid = \[\[1,0,2,0,1\],\[0,0,0,0,0\],\[0,0,1,0,0\]\]
**Output:** 7
**Explanation:** Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2).
The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal.
So return 7.

**Example 2:**

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

**Example 3:**

**Input:** grid = \[\[1\]\]
**Output:** -1

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 50`
*   `grid[i][j]` is either `0`, `1`, or `2`.
*   There will be **at least one** building in the `grid`.
Maximum Product of Word Lengths

Given a string array `words`, return _the maximum value of_ `length(word[i]) * length(word[j])` _where the two words do not share common letters_. If no such two words exist, return `0`.

**Example 1:**

**Input:** words = \[ "abcw ", "baz ", "foo ", "bar ", "xtfn ", "abcdef "\]
**Output:** 16
**Explanation:** The two words can be  "abcw ",  "xtfn ".

**Example 2:**

**Input:** words = \[ "a ", "ab ", "abc ", "d ", "cd ", "bcd ", "abcd "\]
**Output:** 4
**Explanation:** The two words can be  "ab ",  "cd ".

**Example 3:**

**Input:** words = \[ "a ", "aa ", "aaa ", "aaaa "\]
**Output:** 0
**Explanation:** No such pair of words.

**Constraints:**

*   `2 <= words.length <= 1000`
*   `1 <= words[i].length <= 1000`
*   `words[i]` consists only of lowercase English letters.
Bulb Switcher

There are `n` bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.

On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the `ith` round, you toggle every `i` bulb. For the `nth` round, you only toggle the last bulb.

Return _the number of bulbs that are on after `n` rounds_.

**Example 1:**

**Input:** n = 3
**Output:** 1
**Explanation:** At first, the three bulbs are \[off, off, off\].
After the first round, the three bulbs are \[on, on, on\].
After the second round, the three bulbs are \[on, off, on\].
After the third round, the three bulbs are \[on, off, off\]. 
So you should return 1 because there is only one bulb is on.

**Example 2:**

**Input:** n = 0
**Output:** 0

**Example 3:**

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

**Constraints:**

*   `0 <= n <= 109`
Generalized Abbreviation

A word's **generalized abbreviation** can be constructed by taking any number of **non-overlapping** and **non-adjacent** substrings and replacing them with their respective lengths.

*   For example, `"abcde "` can be abbreviated into:
    *   `"a3e "` ( `"bcd "` turned into `"3 "`)
    *   `"1bcd1 "` ( `"a "` and `"e "` both turned into `"1 "`)
    *   `"5 "` ( `"abcde "` turned into `"5 "`)
    *   `"abcde "` (no substrings replaced)
*   However, these abbreviations are **invalid**:
    *   `"23 "` ( `"ab "` turned into `"2 "` and `"cde "` turned into `"3 "`) is invalid as the substrings chosen are adjacent.
    *   `"22de "` ( `"ab "` turned into `"2 "` and `"bc "` turned into `"2 "`) is invalid as the substring chosen overlap.

Given a string `word`, return _a list of all the possible **generalized abbreviations** of_ `word`. Return the answer in **any order**.

**Example 1:**

**Input:** word = "word"
**Output:** \["4","3d","2r1","2rd","1o2","1o1d","1or1","1ord","w3","w2d","w1r1","w1rd","wo2","wo1d","wor1","word"\]

**Example 2:**

**Input:** word = "a"
**Output:** \["1","a"\]

**Constraints:**

*   `1 <= word.length <= 15`
*   `word` consists of only lowercase English letters.
Create Maximum Number

You are given two integer arrays `nums1` and `nums2` of lengths `m` and `n` respectively. `nums1` and `nums2` represent the digits of two numbers. You are also given an integer `k`.

Create the maximum number of length `k <= m + n` from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the `k` digits representing the answer.

**Example 1:**

**Input:** nums1 = \[3,4,6,5\], nums2 = \[9,1,2,5,8,3\], k = 5
**Output:** \[9,8,6,5,3\]

**Example 2:**

**Input:** nums1 = \[6,7\], nums2 = \[6,0,4\], k = 5
**Output:** \[6,7,6,0,4\]

**Example 3:**

**Input:** nums1 = \[3,9\], nums2 = \[8,9\], k = 3
**Output:** \[9,8,9\]

**Constraints:**

*   `m == nums1.length`
*   `n == nums2.length`
*   `1 <= m, n <= 500`
*   `0 <= nums1[i], nums2[i] <= 9`
*   `1 <= k <= m + n`
Coin Change

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.

Return _the fewest number of coins that you need to make up that amount_. If that amount of money cannot be made up by any combination of the coins, return `-1`.

You may assume that you have an infinite number of each kind of coin.

**Example 1:**

**Input:** coins = \[1,2,5\], amount = 11
**Output:** 3
**Explanation:** 11 = 5 + 5 + 1

**Example 2:**

**Input:** coins = \[2\], amount = 3
**Output:** -1

**Example 3:**

**Input:** coins = \[1\], amount = 0
**Output:** 0

**Constraints:**

*   `1 <= coins.length <= 12`
*   `1 <= coins[i] <= 231 - 1`
*   `0 <= amount <= 104`
Number of Connected Components in an Undirected Graph

You have a graph of `n` nodes. You are given an integer `n` and an array `edges` where `edges[i] = [ai, bi]` indicates that there is an edge between `ai` and `bi` in the graph.

Return _the number of connected components in the graph_.

**Example 1:**

**Input:** n = 5, edges = \[\[0,1\],\[1,2\],\[3,4\]\]
**Output:** 2

**Example 2:**

**Input:** n = 5, edges = \[\[0,1\],\[1,2\],\[2,3\],\[3,4\]\]
**Output:** 1

**Constraints:**

*   `1 <= n <= 2000`
*   `1 <= edges.length <= 5000`
*   `edges[i].length == 2`
*   `0 <= ai <= bi < n`
*   `ai != bi`
*   There are no repeated edges.
Wiggle Sort II

Given an integer array `nums`, reorder it such that `nums[0] < nums[1] > nums[2] < nums[3]...`.

You may assume the input array always has a valid answer.

**Example 1:**

**Input:** nums = \[1,5,1,1,6,4\]
**Output:** \[1,6,1,5,1,4\]
**Explanation:** \[1,4,1,5,1,6\] is also accepted.

**Example 2:**

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

**Constraints:**

*   `1 <= nums.length <= 5 * 104`
*   `0 <= nums[i] <= 5000`
*   It is guaranteed that there will be an answer for the given input `nums`.

**Follow Up:** Can you do it in `O(n)` time and/or **in-place** with `O(1)` extra space?
Maximum Size Subarray Sum Equals k

Given an integer array `nums` and an integer `k`, return _the maximum length of a_ _subarray_ _that sums to_ `k`. If there is not one, return `0` instead.

**Example 1:**

**Input:** nums = \[1,-1,5,-2,3\], k = 3
**Output:** 4
**Explanation:** The subarray \[1, -1, 5, -2\] sums to 3 and is the longest.

**Example 2:**

**Input:** nums = \[-2,-1,2,1\], k = 1
**Output:** 2
**Explanation:** The subarray \[-1, 2\] sums to 1 and is the longest.

**Constraints:**

*   `1 <= nums.length <= 2 * 105`
*   `-104 <= nums[i] <= 104`
*   `-109 <= k <= 109`
Power of Three

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

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

**Example 1:**

**Input:** n = 27
**Output:** true
**Explanation:** 27 = 33

**Example 2:**

**Input:** n = 0
**Output:** false
**Explanation:** There is no x where 3x = 0.

**Example 3:**

**Input:** n = -1
**Output:** false
**Explanation:** There is no x where 3x = (-1).

**Constraints:**

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

**Follow up:** Could you solve it without loops/recursion?
Count of Range Sum

Given an integer array `nums` and two integers `lower` and `upper`, return _the number of range sums that lie in_ `[lower, upper]` _inclusive_.

Range sum `S(i, j)` is defined as the sum of the elements in `nums` between indices `i` and `j` inclusive, where `i <= j`.

**Example 1:**

**Input:** nums = \[-2,5,-1\], lower = -2, upper = 2
**Output:** 3
**Explanation:** The three ranges are: \[0,0\], \[2,2\], and \[0,2\] and their respective sums are: -2, -1, 2.

**Example 2:**

**Input:** nums = \[0\], lower = 0, upper = 0
**Output:** 1

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-231 <= nums[i] <= 231 - 1`
*   `-105 <= lower <= upper <= 105`
*   The answer is **guaranteed** to fit in a **32-bit** integer.
Odd Even Linked List

Given the `head` of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return _the reordered list_.

The **first** node is considered **odd**, and the **second** node is **even**, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in `O(1)` extra space complexity and `O(n)` time complexity.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

*   The number of nodes in the linked list is in the range `[0, 104]`.
*   `-106 <= Node.val <= 106`
Longest Increasing Path in a Matrix

Given an `m x n` integers `matrix`, return _the length of the longest increasing path in_ `matrix`.

From each cell, you can either move in four directions: left, right, up, or down. You **may not** move **diagonally** or move **outside the boundary** (i.e., wrap-around is not allowed).

**Example 1:**

**Input:** matrix = \[\[9,9,4\],\[6,6,8\],\[2,1,1\]\]
**Output:** 4
**Explanation:** The longest increasing path is `[1, 2, 6, 9]`.

**Example 2:**

**Input:** matrix = \[\[3,4,5\],\[3,2,6\],\[2,2,1\]\]
**Output:** 4
**Explanation:** The longest increasing path is `[3, 4, 5, 6]`. Moving diagonally is not allowed.

**Example 3:**

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

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m, n <= 200`
*   `0 <= matrix[i][j] <= 231 - 1`
Patching Array

Given a sorted integer array `nums` and an integer `n`, add/patch elements to the array such that any number in the range `[1, n]` inclusive can be formed by the sum of some elements in the array.

Return _the minimum number of patches required_.

**Example 1:**

**Input:** nums = \[1,3\], n = 6
**Output:** 1
Explanation:
Combinations of nums are \[1\], \[3\], \[1,3\], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: \[1\], \[2\], \[3\], \[1,3\], \[2,3\], \[1,2,3\].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range \[1, 6\].
So we only need 1 patch.

**Example 2:**

**Input:** nums = \[1,5,10\], n = 20
**Output:** 2
Explanation: The two patches can be \[2, 4\].

**Example 3:**

**Input:** nums = \[1,2,2\], n = 5
**Output:** 0

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= 104`
*   `nums` is sorted in **ascending order**.
*   `1 <= n <= 231 - 1`