bowang0911/leetcode huggingface dataset:
Ways to Split Array Into Three Subarrays

A split of an integer array is **good** if:

*   The array is split into three **non-empty** contiguous subarrays - named `left`, `mid`, `right` respectively from left to right.
*   The sum of the elements in `left` is less than or equal to the sum of the elements in `mid`, and the sum of the elements in `mid` is less than or equal to the sum of the elements in `right`.

Given `nums`, an array of **non-negative** integers, return _the number of **good** ways to split_ `nums`. As the number may be too large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** nums = \[1,1,1\]
**Output:** 1
**Explanation:** The only good way to split nums is \[1\] \[1\] \[1\].

**Example 2:**

**Input:** nums = \[1,2,2,2,5,0\]
**Output:** 3
**Explanation:** There are three good ways of splitting nums:
\[1\] \[2\] \[2,2,5,0\]
\[1\] \[2,2\] \[2,5,0\]
\[1,2\] \[2,2\] \[5,0\]

**Example 3:**

**Input:** nums = \[3,2,1\]
**Output:** 0
**Explanation:** There is no good way to split nums.

**Constraints:**

*   `3 <= nums.length <= 105`
*   `0 <= nums[i] <= 104`
Minimum Operations to Make a Subsequence

You are given an array `target` that consists of **distinct** integers and another integer array `arr` that **can** have duplicates.

In one operation, you can insert any integer at any position in `arr`. For example, if `arr = [1,4,1,2]`, you can add `3` in the middle and make it `[1,4,3,1,2]`. Note that you can insert the integer at the very beginning or end of the array.

Return _the **minimum** number of operations needed to make_ `target` _a **subsequence** of_ `arr`_._

A **subsequence** of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, `[2,7,4]` is a subsequence of `[4,2,3,7,2,1,4]` (the underlined elements), while `[2,4,2]` is not.

**Example 1:**

**Input:** target = \[5,1,3\], `arr` = \[9,4,2,3,4\]
**Output:** 2
**Explanation:** You can add 5 and 1 in such a way that makes `arr` = \[5,9,4,1,2,3,4\], then target will be a subsequence of `arr`.

**Example 2:**

**Input:** target = \[6,4,8,1,3,2\], `arr` = \[4,7,6,2,3,8,6,1\]
**Output:** 3

**Constraints:**

*   `1 <= target.length, arr.length <= 105`
*   `1 <= target[i], arr[i] <= 109`
*   `target` contains no duplicates.
Sum Of Special Evenly-Spaced Elements In Array

You are given a **0-indexed** integer array `nums` consisting of `n` non-negative integers.

You are also given an array `queries`, where `queries[i] = [xi, yi]`. The answer to the `ith` query is the sum of all `nums[j]` where `xi <= j < n` and `(j - xi)` is divisible by `yi`.

Return _an array_ `answer` _where_ `answer.length == queries.length` _and_ `answer[i]` _is the answer to the_ `ith` _query **modulo**_ `109 + 7`.

**Example 1:**

**Input:** nums = \[0,1,2,3,4,5,6,7\], queries = \[\[0,3\],\[5,1\],\[4,2\]\]
**Output:** \[9,18,10\]
**Explanation:** The answers of the queries are as follows:
1) The j indices that satisfy this query are 0, 3, and 6. nums\[0\] + nums\[3\] + nums\[6\] = 9
2) The j indices that satisfy this query are 5, 6, and 7. nums\[5\] + nums\[6\] + nums\[7\] = 18
3) The j indices that satisfy this query are 4 and 6. nums\[4\] + nums\[6\] = 10

**Example 2:**

**Input:** nums = \[100,200,101,201,102,202,103,203\], queries = \[\[0,7\]\]
**Output:** \[303\]

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 5 * 104`
*   `0 <= nums[i] <= 109`
*   `1 <= queries.length <= 1.5 * 105`
*   `0 <= xi < n`
*   `1 <= yi <= 5 * 104`
Calculate Money in Leetcode Bank

Hercy wants to save money for his first car. He puts money in the Leetcode bank **every day**.

He starts by putting in `$1` on Monday, the first day. Every day from Tuesday to Sunday, he will put in `$1` more than the day before. On every subsequent Monday, he will put in `$1` more than the **previous Monday**.

Given `n`, return _the total amount of money he will have in the Leetcode bank at the end of the_ `nth` _day._

**Example 1:**

**Input:** n = 4
**Output:** 10
**Explanation:** After the 4th day, the total is 1 + 2 + 3 + 4 = 10.

**Example 2:**

**Input:** n = 10
**Output:** 37
**Explanation:** After the 10th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37. Notice that on the 2nd Monday, Hercy only puts in $2.

**Example 3:**

**Input:** n = 20
**Output:** 96
**Explanation:** After the 20th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96.

**Constraints:**

*   `1 <= n <= 1000`
Maximum Score From Removing Substrings

You are given a string `s` and two integers `x` and `y`. You can perform two types of operations any number of times.

*   Remove substring `"ab "` and gain `x` points.
    *   For example, when removing `"ab "` from `"cabxbae "` it becomes `"cxbae "`.
*   Remove substring `"ba "` and gain `y` points.
    *   For example, when removing `"ba "` from `"cabxbae "` it becomes `"cabxe "`.

Return _the maximum points you can gain after applying the above operations on_ `s`.

**Example 1:**

**Input:** s =  "cdbcbbaaabab ", x = 4, y = 5
**Output:** 19
**Explanation:**
- Remove the  "ba " underlined in  "cdbcbbaaabab ". Now, s =  "cdbcbbaaab " and 5 points are added to the score.
- Remove the  "ab " underlined in  "cdbcbbaaab ". Now, s =  "cdbcbbaa " and 4 points are added to the score.
- Remove the  "ba " underlined in  "cdbcbbaa ". Now, s =  "cdbcba " and 5 points are added to the score.
- Remove the  "ba " underlined in  "cdbcba ". Now, s =  "cdbc " and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

**Example 2:**

**Input:** s =  "aabbaaxybbaabb ", x = 5, y = 4
**Output:** 20

**Constraints:**

*   `1 <= s.length <= 105`
*   `1 <= x, y <= 104`
*   `s` consists of lowercase English letters.
Construct the Lexicographically Largest Valid Sequence

Given an integer `n`, find a sequence that satisfies all of the following:

*   The integer `1` occurs once in the sequence.
*   Each integer between `2` and `n` occurs twice in the sequence.
*   For every integer `i` between `2` and `n`, the **distance** between the two occurrences of `i` is exactly `i`.

The **distance** between two numbers on the sequence, `a[i]` and `a[j]`, is the absolute difference of their indices, `|j - i|`.

Return _the **lexicographically largest** sequence__. It is guaranteed that under the given constraints, there is always a solution._

A sequence `a` is lexicographically larger than a sequence `b` (of the same length) if in the first position where `a` and `b` differ, sequence `a` has a number greater than the corresponding number in `b`. For example, `[0,1,9,0]` is lexicographically larger than `[0,1,5,6]` because the first position they differ is at the third number, and `9` is greater than `5`.

**Example 1:**

**Input:** n = 3
**Output:** \[3,1,2,3,2\]
**Explanation:** \[2,3,2,1,3\] is also a valid sequence, but \[3,1,2,3,2\] is the lexicographically largest valid sequence.

**Example 2:**

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

**Constraints:**

*   `1 <= n <= 20`
Number Of Ways To Reconstruct A Tree

You are given an array `pairs`, where `pairs[i] = [xi, yi]`, and:

*   There are no duplicates.
*   `xi < yi`

Let `ways` be the number of rooted trees that satisfy the following conditions:

*   The tree consists of nodes whose values appeared in `pairs`.
*   A pair `[xi, yi]` exists in `pairs` **if and only if** `xi` is an ancestor of `yi` or `yi` is an ancestor of `xi`.
*   **Note:** the tree does not have to be a binary tree.

Two ways are considered to be different if there is at least one node that has different parents in both ways.

Return:

*   `0` if `ways == 0`
*   `1` if `ways == 1`
*   `2` if `ways > 1`

A **rooted tree** is a tree that has a single root node, and all edges are oriented to be outgoing from the root.

An **ancestor** of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.

**Example 1:**

**Input:** pairs = \[\[1,2\],\[2,3\]\]
**Output:** 1
**Explanation:** There is exactly one valid rooted tree, which is shown in the above figure.

**Example 2:**

**Input:** pairs = \[\[1,2\],\[2,3\],\[1,3\]\]
**Output:** 2
**Explanation:** There are multiple valid rooted trees. Three of them are shown in the above figures.

**Example 3:**

**Input:** pairs = \[\[1,2\],\[2,3\],\[2,4\],\[1,5\]\]
**Output:** 0
**Explanation:** There are no valid rooted trees.

**Constraints:**

*   `1 <= pairs.length <= 105`
*   `1 <= xi < yi <= 500`
*   The elements in `pairs` are unique.
Decode XORed Array

There is a **hidden** integer array `arr` that consists of `n` non-negative integers.

It was encoded into another integer array `encoded` of length `n - 1`, such that `encoded[i] = arr[i] XOR arr[i + 1]`. For example, if `arr = [1,0,2,1]`, then `encoded = [1,2,3]`.

You are given the `encoded` array. You are also given an integer `first`, that is the first element of `arr`, i.e. `arr[0]`.

Return _the original array_ `arr`. It can be proved that the answer exists and is unique.

**Example 1:**

**Input:** encoded = \[1,2,3\], first = 1
**Output:** \[1,0,2,1\]
**Explanation:** If arr = \[1,0,2,1\], then first = 1 and encoded = \[1 XOR 0, 0 XOR 2, 2 XOR 1\] = \[1,2,3\]

**Example 2:**

**Input:** encoded = \[6,2,7,3\], first = 4
**Output:** \[4,2,0,7,4\]

**Constraints:**

*   `2 <= n <= 104`
*   `encoded.length == n - 1`
*   `0 <= encoded[i] <= 105`
*   `0 <= first <= 105`
Swapping Nodes in a Linked List

You are given the `head` of a linked list, and an integer `k`.

Return _the head of the linked list after **swapping** the values of the_ `kth` _node from the beginning and the_ `kth` _node from the end (the list is **1-indexed**)._

**Example 1:**

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

**Example 2:**

**Input:** head = \[7,9,6,6,7,8,3,0,9,5\], k = 5
**Output:** \[7,9,6,6,8,7,3,0,9,5\]

**Constraints:**

*   The number of nodes in the list is `n`.
*   `1 <= k <= n <= 105`
*   `0 <= Node.val <= 100`
Minimize Hamming Distance After Swap Operations

You are given two integer arrays, `source` and `target`, both of length `n`. You are also given an array `allowedSwaps` where each `allowedSwaps[i] = [ai, bi]` indicates that you are allowed to swap the elements at index `ai` and index `bi` **(0-indexed)** of array `source`. Note that you can swap elements at a specific pair of indices **multiple** times and in **any** order.

The **Hamming distance** of two arrays of the same length, `source` and `target`, is the number of positions where the elements are different. Formally, it is the number of indices `i` for `0 <= i <= n-1` where `source[i] != target[i]` **(0-indexed)**.

Return _the **minimum Hamming distance** of_ `source` _and_ `target` _after performing **any** amount of swap operations on array_ `source`_._

**Example 1:**

**Input:** source = \[1,2,3,4\], target = \[2,1,4,5\], allowedSwaps = \[\[0,1\],\[2,3\]\]
**Output:** 1
**Explanation:** source can be transformed the following way:
- Swap indices 0 and 1: source = \[2,1,3,4\]
- Swap indices 2 and 3: source = \[2,1,4,3\]
The Hamming distance of source and target is 1 as they differ in 1 position: index 3.

**Example 2:**

**Input:** source = \[1,2,3,4\], target = \[1,3,2,4\], allowedSwaps = \[\]
**Output:** 2
**Explanation:** There are no allowed swaps.
The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.

**Example 3:**

**Input:** source = \[5,1,2,4,3\], target = \[1,5,4,2,3\], allowedSwaps = \[\[0,4\],\[4,2\],\[1,3\],\[1,4\]\]
**Output:** 0

**Constraints:**

*   `n == source.length == target.length`
*   `1 <= n <= 105`
*   `1 <= source[i], target[i] <= 105`
*   `0 <= allowedSwaps.length <= 105`
*   `allowedSwaps[i].length == 2`
*   `0 <= ai, bi <= n - 1`
*   `ai != bi`
Find Minimum Time to Finish All Jobs

You are given an integer array `jobs`, where `jobs[i]` is the amount of time it takes to complete the `ith` job.

There are `k` workers that you can assign jobs to. Each job should be assigned to **exactly** one worker. The **working time** of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the **maximum working time** of any worker is **minimized**.

_Return the **minimum** possible **maximum working time** of any assignment._

**Example 1:**

**Input:** jobs = \[3,2,3\], k = 3
**Output:** 3
**Explanation:** By assigning each person one job, the maximum time is 3.

**Example 2:**

**Input:** jobs = \[1,2,4,7,8\], k = 2
**Output:** 11
**Explanation:** Assign the jobs the following way:
Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11)
Worker 2: 4, 7 (working time = 4 + 7 = 11)
The maximum working time is 11.

**Constraints:**

*   `1 <= k <= jobs.length <= 12`
*   `1 <= jobs[i] <= 107`
Checking Existence of Edge Length Limited Paths II

An undirected graph of `n` nodes is defined by `edgeList`, where `edgeList[i] = [ui, vi, disi]` denotes an edge between nodes `ui` and `vi` with distance `disi`. Note that there may be **multiple** edges between two nodes, and the graph may not be connected.

Implement the `DistanceLimitedPathsExist` class:

*   `DistanceLimitedPathsExist(int n, int[][] edgeList)` Initializes the class with an undirected graph.
*   `boolean query(int p, int q, int limit)` Returns `true` if there exists a path from `p` to `q` such that each edge on the path has a distance **strictly less than** `limit`, and otherwise `false`.

**Example 1:**

**Input**
\[ "DistanceLimitedPathsExist ",  "query ",  "query ",  "query ",  "query "\]
\[\[6, \[\[0, 2, 4\], \[0, 3, 2\], \[1, 2, 3\], \[2, 3, 1\], \[4, 5, 5\]\]\], \[2, 3, 2\], \[1, 3, 3\], \[2, 0, 3\], \[0, 5, 6\]\]
**Output**
\[null, true, false, true, false\]

**Explanation**
DistanceLimitedPathsExist distanceLimitedPathsExist = new DistanceLimitedPathsExist(6, \[\[0, 2, 4\], \[0, 3, 2\], \[1, 2, 3\], \[2, 3, 1\], \[4, 5, 5\]\]);
distanceLimitedPathsExist.query(2, 3, 2); // return true. There is an edge from 2 to 3 of distance 1, which is less than 2.
distanceLimitedPathsExist.query(1, 3, 3); // return false. There is no way to go from 1 to 3 with distances **strictly** less than 3.
distanceLimitedPathsExist.query(2, 0, 3); // return true. There is a way to go from 2 to 0 with distance < 3: travel from 2 to 3 to 0.
distanceLimitedPathsExist.query(0, 5, 6); // return false. There are no paths from 0 to 5.

`**Constraints:**`

*   `2 <= n <= 104`
*   `0 <= edgeList.length <= 104`
*   `edgeList[i].length == 3`
*   `0 <= ui, vi, p, q <= n-1`
*   `ui != vi`
*   `p != q`
*   `1 <= disi, limit <= 109`
*   At most `104` calls will be made to `query`.
Number Of Rectangles That Can Form The Largest Square

You are given an array `rectangles` where `rectangles[i] = [li, wi]` represents the `ith` rectangle of length `li` and width `wi`.

You can cut the `ith` rectangle to form a square with a side length of `k` if both `k <= li` and `k <= wi`. For example, if you have a rectangle `[4,6]`, you can cut it to get a square with a side length of at most `4`.

Let `maxLen` be the side length of the **largest** square you can obtain from any of the given rectangles.

Return _the **number** of rectangles that can make a square with a side length of_ `maxLen`.

**Example 1:**

**Input:** rectangles = \[\[5,8\],\[3,9\],\[5,12\],\[16,5\]\]
**Output:** 3
**Explanation:** The largest squares you can get from each rectangle are of lengths \[5,3,5,5\].
The largest possible square is of length 5, and you can get it out of 3 rectangles.

**Example 2:**

**Input:** rectangles = \[\[2,3\],\[3,7\],\[4,3\],\[3,7\]\]
**Output:** 3

**Constraints:**

*   `1 <= rectangles.length <= 1000`
*   `rectangles[i].length == 2`
*   `1 <= li, wi <= 109`
*   `li != wi`
Tuple with Same Product

Given an array `nums` of **distinct** positive integers, return _the number of tuples_ `(a, b, c, d)` _such that_ `a * b = c * d` _where_ `a`_,_ `b`_,_ `c`_, and_ `d` _are elements of_ `nums`_, and_ `a != b != c != d`_._

**Example 1:**

**Input:** nums = \[2,3,4,6\]
**Output:** 8
**Explanation:** There are 8 valid tuples:
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

**Example 2:**

**Input:** nums = \[1,2,4,5,10\]
**Output:** 16
**Explanation:** There are 16 valid tuples:
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= 104`
*   All elements in `nums` are **distinct**.
Largest Submatrix With Rearrangements

You are given a binary matrix `matrix` of size `m x n`, and you are allowed to rearrange the **columns** of the `matrix` in any order.

Return _the area of the largest submatrix within_ `matrix` _where **every** element of the submatrix is_ `1` _after reordering the columns optimally._

**Example 1:**

**Input:** matrix = \[\[0,0,1\],\[1,1,1\],\[1,0,1\]\]
**Output:** 4
**Explanation:** You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.

**Example 2:**

**Input:** matrix = \[\[1,0,1,0,1\]\]
**Output:** 3
**Explanation:** You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.

**Example 3:**

**Input:** matrix = \[\[1,1,0\],\[1,0,1\]\]
**Output:** 2
**Explanation:** Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m * n <= 105`
*   `matrix[i][j]` is either `0` or `1`.
Cat and Mouse II

A game is played by a cat and a mouse named Cat and Mouse.

The environment is represented by a `grid` of size `rows x cols`, where each element is a wall, floor, player (Cat, Mouse), or food.

*   Players are represented by the characters `'C'`(Cat)`,'M'`(Mouse).
*   Floors are represented by the character `'.'` and can be walked on.
*   Walls are represented by the character `'#'` and cannot be walked on.
*   Food is represented by the character `'F'` and can be walked on.
*   There is only one of each character `'C'`, `'M'`, and `'F'` in `grid`.

Mouse and Cat play according to the following rules:

*   Mouse **moves first**, then they take turns to move.
*   During each turn, Cat and Mouse can jump in one of the four directions (left, right, up, down). They cannot jump over the wall nor outside of the `grid`.
*   `catJump, mouseJump` are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.
*   Staying in the same position is allowed.
*   Mouse can jump over Cat.

The game can end in 4 ways:

*   If Cat occupies the same position as Mouse, Cat wins.
*   If Cat reaches the food first, Cat wins.
*   If Mouse reaches the food first, Mouse wins.
*   If Mouse cannot get to the food within 1000 turns, Cat wins.

Given a `rows x cols` matrix `grid` and two integers `catJump` and `mouseJump`, return `true` _if Mouse can win the game if both Cat and Mouse play optimally, otherwise return_ `false`.

**Example 1:**

**Input:** grid = \[ "####F ", "#C... ", "M.... "\], catJump = 1, mouseJump = 2
**Output:** true
**Explanation:** Cat cannot catch Mouse on its turn nor can it get the food before Mouse.

**Example 2:**

**Input:** grid = \[ "M.C...F "\], catJump = 1, mouseJump = 4
**Output:** true

**Example 3:**

**Input:** grid = \[ "M.C...F "\], catJump = 1, mouseJump = 3
**Output:** false

**Constraints:**

*   `rows == grid.length`
*   `cols = grid[i].length`
*   `1 <= rows, cols <= 8`
*   `grid[i][j]` consist only of characters `'C'`, `'M'`, `'F'`, `'.'`, and `'#'`.
*   There is only one of each character `'C'`, `'M'`, and `'F'` in `grid`.
*   `1 <= catJump, mouseJump <= 8`
Shortest Path to Get Food

You are starving and you want to eat food as quickly as possible. You want to find the shortest path to arrive at any food cell.

You are given an `m x n` character matrix, `grid`, of these different types of cells:

*   `'*'` is your location. There is **exactly one** `'*'` cell.
*   `'#'` is a food cell. There may be **multiple** food cells.
*   `'O'` is free space, and you can travel through these cells.
*   `'X'` is an obstacle, and you cannot travel through these cells.

You can travel to any adjacent cell north, east, south, or west of your current location if there is not an obstacle.

Return _the **length** of the shortest path for you to reach **any** food cell_. If there is no path for you to reach food, return `-1`.

**Example 1:**

**Input:** grid = \[\[ "X ", "X ", "X ", "X ", "X ", "X "\],\[ "X ", "\* ", "O ", "O ", "O ", "X "\],\[ "X ", "O ", "O ", "# ", "O ", "X "\],\[ "X ", "X ", "X ", "X ", "X ", "X "\]\]
**Output:** 3
**Explanation:** It takes 3 steps to reach the food.

**Example 2:**

**Input:** grid = \[\[ "X ", "X ", "X ", "X ", "X "\],\[ "X ", "\* ", "X ", "O ", "X "\],\[ "X ", "O ", "X ", "# ", "X "\],\[ "X ", "X ", "X ", "X ", "X "\]\]
**Output:** -1
**Explanation:** It is not possible to reach the food.

**Example 3:**

**Input:** grid = \[\[ "X ", "X ", "X ", "X ", "X ", "X ", "X ", "X "\],\[ "X ", "\* ", "O ", "X ", "O ", "# ", "O ", "X "\],\[ "X ", "O ", "O ", "X ", "O ", "O ", "X ", "X "\],\[ "X ", "O ", "O ", "O ", "O ", "# ", "O ", "X "\],\[ "X ", "X ", "X ", "X ", "X ", "X ", "X ", "X "\]\]
**Output:** 6
**Explanation:** There can be multiple food cells. It only takes 6 steps to reach the bottom food.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 200`
*   `grid[row][col]` is `'*'`, `'X'`, `'O'`, or `'#'`.
*   The `grid` contains **exactly one** `'*'`.
Find the Highest Altitude

There is a biker going on a road trip. The road trip consists of `n + 1` points at different altitudes. The biker starts his trip on point `0` with altitude equal `0`.

You are given an integer array `gain` of length `n` where `gain[i]` is the **net gain in altitude** between points `i`​​​​​​ and `i + 1` for all (`0 <= i < n)`. Return _the **highest altitude** of a point._

**Example 1:**

**Input:** gain = \[-5,1,5,0,-7\]
**Output:** 1
**Explanation:** The altitudes are \[0,-5,-4,1,1,-6\]. The highest is 1.

**Example 2:**

**Input:** gain = \[-4,-3,-2,-1,4,3,2\]
**Output:** 0
**Explanation:** The altitudes are \[0,-4,-7,-9,-10,-6,-3,-1\]. The highest is 0.

**Constraints:**

*   `n == gain.length`
*   `1 <= n <= 100`
*   `-100 <= gain[i] <= 100`
Minimum Number of People to Teach

On a social network consisting of `m` users and some friendships between users, two users can communicate with each other if they know a common language.

You are given an integer `n`, an array `languages`, and an array `friendships` where:

*   There are `n` languages numbered `1` through `n`,
*   `languages[i]` is the set of languages the `i​​​​​​th`​​​​ user knows, and
*   `friendships[i] = [u​​​​​​i​​​, v​​​​​​i]` denotes a friendship between the users `u​​​​​​​​​​​i`​​​​​ and `vi`.

You can choose **one** language and teach it to some users so that all friends can communicate with each other. Return _the_ _**minimum**_ _number of users you need to teach._

Note that friendships are not transitive, meaning if `x` is a friend of `y` and `y` is a friend of `z`, this doesn't guarantee that `x` is a friend of `z`.

**Example 1:**

**Input:** n = 2, languages = \[\[1\],\[2\],\[1,2\]\], friendships = \[\[1,2\],\[1,3\],\[2,3\]\]
**Output:** 1
**Explanation:** You can either teach user 1 the second language or user 2 the first language.

**Example 2:**

**Input:** n = 3, languages = \[\[2\],\[1,3\],\[1,2\],\[3\]\], friendships = \[\[1,4\],\[1,2\],\[3,4\],\[2,3\]\]
**Output:** 2
**Explanation:** Teach the third language to users 1 and 3, yielding two users to teach.

**Constraints:**

*   `2 <= n <= 500`
*   `languages.length == m`
*   `1 <= m <= 500`
*   `1 <= languages[i].length <= n`
*   `1 <= languages[i][j] <= n`
*   `1 <= u​​​​​​i < v​​​​​​i <= languages.length`
*   `1 <= friendships.length <= 500`
*   All tuples `(u​​​​​i, v​​​​​​i)` are unique
*   `languages[i]` contains only unique values