bowang0911/leetcode huggingface dataset:
Minimum Number of Swaps to Make the String Balanced

You are given a **0-indexed** string `s` of **even** length `n`. The string consists of **exactly** `n / 2` opening brackets `'['` and `n / 2` closing brackets `']'`.

A string is called **balanced** if and only if:

*   It is the empty string, or
*   It can be written as `AB`, where both `A` and `B` are **balanced** strings, or
*   It can be written as `[C]`, where `C` is a **balanced** string.

You may swap the brackets at **any** two indices **any** number of times.

Return _the **minimum** number of swaps to make_ `s` _**balanced**_.

**Example 1:**

**Input:** s =  "\]\[\]\[ "
**Output:** 1
**Explanation:** You can make the string balanced by swapping index 0 with index 3.
The resulting string is  "\[\[\]\] ".

**Example 2:**

**Input:** s =  "\]\]\]\[\[\[ "
**Output:** 2
**Explanation:** You can do the following to make the string balanced:
- Swap index 0 with index 4. s =  "\[\]\]\[\]\[ ".
- Swap index 1 with index 5. s =  "\[\[\]\[\]\] ".
The resulting string is  "\[\[\]\[\]\] ".

**Example 3:**

**Input:** s =  "\[\] "
**Output:** 0
**Explanation:** The string is already balanced.

**Constraints:**

*   `n == s.length`
*   `2 <= n <= 106`
*   `n` is even.
*   `s[i]` is either `'['` or `']'`.
*   The number of opening brackets `'['` equals `n / 2`, and the number of closing brackets `']'` equals `n / 2`.
Find the Longest Valid Obstacle Course at Each Position

You want to build some obstacle courses. You are given a **0-indexed** integer array `obstacles` of length `n`, where `obstacles[i]` describes the height of the `ith` obstacle.

For every index `i` between `0` and `n - 1` (**inclusive**), find the length of the **longest obstacle course** in `obstacles` such that:

*   You choose any number of obstacles between `0` and `i` **inclusive**.
*   You must include the `ith` obstacle in the course.
*   You must put the chosen obstacles in the **same order** as they appear in `obstacles`.
*   Every obstacle (except the first) is **taller** than or the **same height** as the obstacle immediately before it.

Return _an array_ `ans` _of length_ `n`, _where_ `ans[i]` _is the length of the **longest obstacle course** for index_ `i` _as described above_.

**Example 1:**

**Input:** obstacles = \[1,2,3,2\]
**Output:** \[1,2,3,3\]
**Explanation:** The longest valid obstacle course at each position is:
- i = 0: \[1\], \[1\] has length 1.
- i = 1: \[1,2\], \[1,2\] has length 2.
- i = 2: \[1,2,3\], \[1,2,3\] has length 3.
- i = 3: \[1,2,3,2\], \[1,2,2\] has length 3.

**Example 2:**

**Input:** obstacles = \[2,2,1\]
**Output:** \[1,2,1\]
**Explanation:** The longest valid obstacle course at each position is:
- i = 0: \[2\], \[2\] has length 1.
- i = 1: \[2,2\], \[2,2\] has length 2.
- i = 2: \[2,2,1\], \[1\] has length 1.

**Example 3:**

**Input:** obstacles = \[3,1,5,6,4,2\]
**Output:** \[1,1,2,3,2,2\]
**Explanation:** The longest valid obstacle course at each position is:
- i = 0: \[3\], \[3\] has length 1.
- i = 1: \[3,1\], \[1\] has length 1.
- i = 2: \[3,1,5\], \[3,5\] has length 2. \[1,5\] is also valid.
- i = 3: \[3,1,5,6\], \[3,5,6\] has length 3. \[1,5,6\] is also valid.
- i = 4: \[3,1,5,6,4\], \[3,4\] has length 2. \[1,4\] is also valid.
- i = 5: \[3,1,5,6,4,2\], \[1,2\] has length 2.

**Constraints:**

*   `n == obstacles.length`
*   `1 <= n <= 105`
*   `1 <= obstacles[i] <= 107`
Binary Searchable Numbers in an Unsorted Array

Consider a function that implements an algorithm **similar** to [Binary Search](https://leetcode.com/explore/learn/card/binary-search/). The function has two input parameters: `sequence` is a sequence of integers, and `target` is an integer value. The purpose of the function is to find if the `target` exists in the `sequence`.

The pseudocode of the function is as follows:

func(sequence, target)
  while sequence is not empty
    **randomly** choose an element from sequence as the pivot
    if pivot = target, return **true**
    else if pivot < target, remove pivot and all elements to its left from the sequence
    else, remove pivot and all elements to its right from the sequence
  end while
  return **false**

When the `sequence` is sorted, the function works correctly for **all** values. When the `sequence` is not sorted, the function does not work for all values, but may still work for **some** values.

Given an integer array `nums`, representing the `sequence`, that contains **unique** numbers and **may or may not be sorted**, return _the number of values that are **guaranteed** to be found using the function, for **every possible** pivot selection_.

**Example 1:**

**Input:** nums = \[7\]
**Output:** 1
**Explanation**: 
Searching for value 7 is guaranteed to be found.
Since the sequence has only one element, 7 will be chosen as the pivot. Because the pivot equals the target, the function will return true.

**Example 2:**

**Input:** nums = \[-1,5,2\]
**Output:** 1
**Explanation**: 
Searching for value -1 is guaranteed to be found.
If -1 was chosen as the pivot, the function would return true.
If 5 was chosen as the pivot, 5 and 2 would be removed. In the next loop, the sequence would have only -1 and the function would return true.
If 2 was chosen as the pivot, 2 would be removed. In the next loop, the sequence would have -1 and 5. No matter which number was chosen as the next pivot, the function would find -1 and return true.

Searching for value 5 is NOT guaranteed to be found.
If 2 was chosen as the pivot, -1, 5 and 2 would be removed. The sequence would be empty and the function would return false.

Searching for value 2 is NOT guaranteed to be found.
If 5 was chosen as the pivot, 5 and 2 would be removed. In the next loop, the sequence would have only -1 and the function would return false.

Because only -1 is guaranteed to be found, you should return 1.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-105 <= nums[i] <= 105`
*   All the values of `nums` are **unique**.

**Follow-up:** If `nums` has **duplicates**, would you modify your algorithm? If so, how?
Number of Strings That Appear as Substrings in Word

Given an array of strings `patterns` and a string `word`, return _the **number** of strings in_ `patterns` _that exist as a **substring** in_ `word`.

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

**Example 1:**

**Input:** patterns = \[ "a ", "abc ", "bc ", "d "\], word =  "abc "
**Output:** 3
**Explanation:**
-  "a " appears as a substring in  "abc ".
-  "abc " appears as a substring in  "abc ".
-  "bc " appears as a substring in  "abc ".
-  "d " does not appear as a substring in  "abc ".
3 of the strings in patterns appear as a substring in word.

**Example 2:**

**Input:** patterns = \[ "a ", "b ", "c "\], word =  "aaaaabbbbb "
**Output:** 2
**Explanation:**
-  "a " appears as a substring in  "aaaaabbbbb ".
-  "b " appears as a substring in  "aaaaabbbbb ".
-  "c " does not appear as a substring in  "aaaaabbbbb ".
2 of the strings in patterns appear as a substring in word.

**Example 3:**

**Input:** patterns = \[ "a ", "a ", "a "\], word =  "ab "
**Output:** 3
**Explanation:** Each of the patterns appears as a substring in word  "ab ".

**Constraints:**

*   `1 <= patterns.length <= 100`
*   `1 <= patterns[i].length <= 100`
*   `1 <= word.length <= 100`
*   `patterns[i]` and `word` consist of lowercase English letters.
Array With Elements Not Equal to Average of Neighbors

You are given a **0-indexed** array `nums` of **distinct** integers. You want to rearrange the elements in the array such that every element in the rearranged array is **not** equal to the **average** of its neighbors.

More formally, the rearranged array should have the property such that for every `i` in the range `1 <= i < nums.length - 1`, `(nums[i-1] + nums[i+1]) / 2` is **not** equal to `nums[i]`.

Return _**any** rearrangement of_ `nums` _that meets the requirements_.

**Example 1:**

**Input:** nums = \[1,2,3,4,5\]
**Output:** \[1,2,4,5,3\]
**Explanation:**
When i=1, nums\[i\] = 2, and the average of its neighbors is (1+4) / 2 = 2.5.
When i=2, nums\[i\] = 4, and the average of its neighbors is (2+5) / 2 = 3.5.
When i=3, nums\[i\] = 5, and the average of its neighbors is (4+3) / 2 = 3.5.

**Example 2:**

**Input:** nums = \[6,2,0,9,7\]
**Output:** \[9,7,6,2,0\]
**Explanation:**
When i=1, nums\[i\] = 7, and the average of its neighbors is (9+6) / 2 = 7.5.
When i=2, nums\[i\] = 6, and the average of its neighbors is (7+2) / 2 = 4.5.
When i=3, nums\[i\] = 2, and the average of its neighbors is (6+0) / 2 = 3.

**Constraints:**

*   `3 <= nums.length <= 105`
*   `0 <= nums[i] <= 105`
Minimum Non-Zero Product of the Array Elements

You are given a positive integer `p`. Consider an array `nums` (**1-indexed**) that consists of the integers in the **inclusive** range `[1, 2p - 1]` in their binary representations. You are allowed to do the following operation **any** number of times:

*   Choose two elements `x` and `y` from `nums`.
*   Choose a bit in `x` and swap it with its corresponding bit in `y`. Corresponding bit refers to the bit that is in the **same position** in the other integer.

For example, if `x = 1101` and `y = 0011`, after swapping the `2nd` bit from the right, we have `x = 1111` and `y = 0001`.

Find the **minimum non-zero** product of `nums` after performing the above operation **any** number of times. Return _this product_ _**modulo**_ `109 + 7`.

**Note:** The answer should be the minimum product **before** the modulo operation is done.

**Example 1:**

**Input:** p = 1
**Output:** 1
**Explanation:** nums = \[1\].
There is only one element, so the product equals that element.

**Example 2:**

**Input:** p = 2
**Output:** 6
**Explanation:** nums = \[01, 10, 11\].
Any swap would either make the product 0 or stay the same.
Thus, the array product of 1 \* 2 \* 3 = 6 is already minimized.

**Example 3:**

**Input:** p = 3
**Output:** 1512
**Explanation:** nums = \[001, 010, 011, 100, 101, 110, 111\]
- In the first operation we can swap the leftmost bit of the second and fifth elements.
    - The resulting array is \[001, 110, 011, 100, 001, 110, 111\].
- In the second operation we can swap the middle bit of the third and fourth elements.
    - The resulting array is \[001, 110, 001, 110, 001, 110, 111\].
The array product is 1 \* 6 \* 1 \* 6 \* 1 \* 6 \* 7 = 1512, which is the minimum possible product.

**Constraints:**

*   `1 <= p <= 60`
Last Day Where You Can Still Cross

There is a **1-based** binary matrix where `0` represents land and `1` represents water. You are given integers `row` and `col` representing the number of rows and columns in the matrix, respectively.

Initially on day `0`, the **entire** matrix is **land**. However, each day a new cell becomes flooded with **water**. You are given a **1-based** 2D array `cells`, where `cells[i] = [ri, ci]` represents that on the `ith` day, the cell on the `rith` row and `cith` column (**1-based** coordinates) will be covered with **water** (i.e., changed to `1`).

You want to find the **last** day that it is possible to walk from the **top** to the **bottom** by only walking on land cells. You can start from **any** cell in the top row and end at **any** cell in the bottom row. You can only travel in the **four** cardinal directions (left, right, up, and down).

Return _the **last** day where it is possible to walk from the **top** to the **bottom** by only walking on land cells_.

**Example 1:**

**Input:** row = 2, col = 2, cells = \[\[1,1\],\[2,1\],\[1,2\],\[2,2\]\]
**Output:** 2
**Explanation:** The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 2.

**Example 2:**

**Input:** row = 2, col = 2, cells = \[\[1,1\],\[1,2\],\[2,1\],\[2,2\]\]
**Output:** 1
**Explanation:** The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 1.

**Example 3:**

**Input:** row = 3, col = 3, cells = \[\[1,2\],\[2,1\],\[3,3\],\[2,2\],\[1,1\],\[1,3\],\[2,3\],\[3,2\],\[3,1\]\]
**Output:** 3
**Explanation:** The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 3.

**Constraints:**

*   `2 <= row, col <= 2 * 104`
*   `4 <= row * col <= 2 * 104`
*   `cells.length == row * col`
*   `1 <= ri <= row`
*   `1 <= ci <= col`
*   All the values of `cells` are **unique**.
Find if Path Exists in Graph

There is a **bi-directional** graph with `n` vertices, where each vertex is labeled from `0` to `n - 1` (**inclusive**). The edges in the graph are represented as a 2D integer array `edges`, where each `edges[i] = [ui, vi]` denotes a bi-directional edge between vertex `ui` and vertex `vi`. Every vertex pair is connected by **at most one** edge, and no vertex has an edge to itself.

You want to determine if there is a **valid path** that exists from vertex `source` to vertex `destination`.

Given `edges` and the integers `n`, `source`, and `destination`, return `true` _if there is a **valid path** from_ `source` _to_ `destination`_, or_ `false` _otherwise__._

**Example 1:**

**Input:** n = 3, edges = \[\[0,1\],\[1,2\],\[2,0\]\], source = 0, destination = 2
**Output:** true
**Explanation:** There are two paths from vertex 0 to vertex 2:
- 0 -> 1 -> 2
- 0 -> 2

**Example 2:**

**Input:** n = 6, edges = \[\[0,1\],\[0,2\],\[3,5\],\[5,4\],\[4,3\]\], source = 0, destination = 5
**Output:** false
**Explanation:** There is no path from vertex 0 to vertex 5.

**Constraints:**

*   `1 <= n <= 2 * 105`
*   `0 <= edges.length <= 2 * 105`
*   `edges[i].length == 2`
*   `0 <= ui, vi <= n - 1`
*   `ui != vi`
*   `0 <= source, destination <= n - 1`
*   There are no duplicate edges.
*   There are no self edges.
Count Nodes Equal to Sum of Descendants

Given the `root` of a binary tree, return _the number of nodes where the value of the node is equal to the **sum** of the values of its descendants_.

A **descendant** of a node `x` is any node that is on the path from node `x` to some leaf node. The sum is considered to be `0` if the node has no descendants.

**Example 1:**

**Input:** root = \[10,3,4,2,1\]
**Output:** 2
**Explanation:**
For the node with value 10: The sum of its descendants is 3+4+2+1 = 10.
For the node with value 3: The sum of its descendants is 2+1 = 3.

**Example 2:**

**Input:** root = \[2,3,null,2,null\]
**Output:** 0
**Explanation:**
No node has a value that is equal to the sum of its descendants.

**Example 3:**

**Input:** root = \[0\]
**Output:** 1
For the node with value 0: The sum of its descendants is 0 since it has no descendants.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 105]`.
*   `0 <= Node.val <= 105`
Minimum Time to Type Word Using Special Typewriter

There is a special typewriter with lowercase English letters `'a'` to `'z'` arranged in a **circle** with a **pointer**. A character can **only** be typed if the pointer is pointing to that character. The pointer is **initially** pointing to the character `'a'`.

Each second, you may perform one of the following operations:

*   Move the pointer one character **counterclockwise** or **clockwise**.
*   Type the character the pointer is **currently** on.

Given a string `word`, return the **minimum** number of seconds to type out the characters in `word`.

**Example 1:**

**Input:** word =  "abc "
**Output:** 5
**Explanation:** 
The characters are printed as follows:
- Type the character 'a' in 1 second since the pointer is initially on 'a'.
- Move the pointer clockwise to 'b' in 1 second.
- Type the character 'b' in 1 second.
- Move the pointer clockwise to 'c' in 1 second.
- Type the character 'c' in 1 second.

**Example 2:**

**Input:** word =  "bza "
**Output:** 7
**Explanation:**
The characters are printed as follows:
- Move the pointer clockwise to 'b' in 1 second.
- Type the character 'b' in 1 second.
- Move the pointer counterclockwise to 'z' in 2 seconds.
- Type the character 'z' in 1 second.
- Move the pointer clockwise to 'a' in 1 second.
- Type the character 'a' in 1 second.

**Example 3:**

**Input:** word =  "zjpc "
**Output:** 34
**Explanation:**
The characters are printed as follows:
- Move the pointer counterclockwise to 'z' in 1 second.
- Type the character 'z' in 1 second.
- Move the pointer clockwise to 'j' in 10 seconds.
- Type the character 'j' in 1 second.
- Move the pointer clockwise to 'p' in 6 seconds.
- Type the character 'p' in 1 second.
- Move the pointer counterclockwise to 'c' in 13 seconds.
- Type the character 'c' in 1 second.

**Constraints:**

*   `1 <= word.length <= 100`
*   `word` consists of lowercase English letters.
Maximum Matrix Sum

You are given an `n x n` integer `matrix`. You can do the following operation **any** number of times:

*   Choose any two **adjacent** elements of `matrix` and **multiply** each of them by `-1`.

Two elements are considered **adjacent** if and only if they share a **border**.

Your goal is to **maximize** the summation of the matrix's elements. Return _the **maximum** sum of the matrix's elements using the operation mentioned above._

**Example 1:**

**Input:** matrix = \[\[1,-1\],\[-1,1\]\]
**Output:** 4
**Explanation:** We can follow the following steps to reach sum equals 4:
- Multiply the 2 elements in the first row by -1.
- Multiply the 2 elements in the first column by -1.

**Example 2:**

**Input:** matrix = \[\[1,2,3\],\[-1,-2,-3\],\[1,2,3\]\]
**Output:** 16
**Explanation:** We can follow the following step to reach sum equals 16:
- Multiply the 2 last elements in the second row by -1.

**Constraints:**

*   `n == matrix.length == matrix[i].length`
*   `2 <= n <= 250`
*   `-105 <= matrix[i][j] <= 105`
Number of Ways to Arrive at Destination

You are in a city that consists of `n` intersections numbered from `0` to `n - 1` with **bi-directional** roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.

You are given an integer `n` and a 2D integer array `roads` where `roads[i] = [ui, vi, timei]` means that there is a road between intersections `ui` and `vi` that takes `timei` minutes to travel. You want to know in how many ways you can travel from intersection `0` to intersection `n - 1` in the **shortest amount of time**.

Return _the **number of ways** you can arrive at your destination in the **shortest amount of time**_. Since the answer may be large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** n = 7, roads = \[\[0,6,7\],\[0,1,2\],\[1,2,3\],\[1,3,3\],\[6,3,3\],\[3,5,1\],\[6,5,1\],\[2,5,1\],\[0,4,5\],\[4,6,2\]\]
**Output:** 4
**Explanation:** The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6

**Example 2:**

**Input:** n = 2, roads = \[\[1,0,10\]\]
**Output:** 1
**Explanation:** There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.

**Constraints:**

*   `1 <= n <= 200`
*   `n - 1 <= roads.length <= n * (n - 1) / 2`
*   `roads[i].length == 3`
*   `0 <= ui, vi <= n - 1`
*   `1 <= timei <= 109`
*   `ui != vi`
*   There is at most one road connecting any two intersections.
*   You can reach any intersection from any other intersection.
Number of Ways to Separate Numbers

You wrote down many **positive** integers in a string called `num`. However, you realized that you forgot to add commas to seperate the different numbers. You remember that the list of integers was **non-decreasing** and that **no** integer had leading zeros.

Return _the **number of possible lists of integers** that you could have written down to get the string_ `num`. Since the answer may be large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** num =  "327 "
**Output:** 2
**Explanation:** You could have written down the numbers:
3, 27
327

**Example 2:**

**Input:** num =  "094 "
**Output:** 0
**Explanation:** No numbers can have leading zeros and all numbers must be positive.

**Example 3:**

**Input:** num =  "0 "
**Output:** 0
**Explanation:** No numbers can have leading zeros and all numbers must be positive.

**Constraints:**

*   `1 <= num.length <= 3500`
*   `num` consists of digits `'0'` through `'9'`.
Find Greatest Common Divisor of Array

Given an integer array `nums`, return _the **greatest common divisor** of the smallest number and largest number in_ `nums`.

The **greatest common divisor** of two numbers is the largest positive integer that evenly divides both numbers.

**Example 1:**

**Input:** nums = \[2,5,6,9,10\]
**Output:** 2
**Explanation:**
The smallest number in nums is 2.
The largest number in nums is 10.
The greatest common divisor of 2 and 10 is 2.

**Example 2:**

**Input:** nums = \[7,5,6,8,3\]
**Output:** 1
**Explanation:**
The smallest number in nums is 3.
The largest number in nums is 8.
The greatest common divisor of 3 and 8 is 1.

**Example 3:**

**Input:** nums = \[3,3\]
**Output:** 3
**Explanation:**
The smallest number in nums is 3.
The largest number in nums is 3.
The greatest common divisor of 3 and 3 is 3.

**Constraints:**

*   `2 <= nums.length <= 1000`
*   `1 <= nums[i] <= 1000`
Find Unique Binary String

Given an array of strings `nums` containing `n` **unique** binary strings each of length `n`, return _a binary string of length_ `n` _that **does not appear** in_ `nums`_. If there are multiple answers, you may return **any** of them_.

**Example 1:**

**Input:** nums = \[ "01 ", "10 "\]
**Output:**  "11 "
**Explanation:**  "11 " does not appear in nums.  "00 " would also be correct.

**Example 2:**

**Input:** nums = \[ "00 ", "01 "\]
**Output:**  "11 "
**Explanation:**  "11 " does not appear in nums.  "10 " would also be correct.

**Example 3:**

**Input:** nums = \[ "111 ", "011 ", "001 "\]
**Output:**  "101 "
**Explanation:**  "101 " does not appear in nums.  "000 ",  "010 ",  "100 ", and  "110 " would also be correct.

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 16`
*   `nums[i].length == n`
*   `nums[i]` is either `'0'` or `'1'`.
*   All the strings of `nums` are **unique**.
Minimize the Difference Between Target and Chosen Elements

You are given an `m x n` integer matrix `mat` and an integer `target`.

Choose one integer from **each row** in the matrix such that the **absolute difference** between `target` and the **sum** of the chosen elements is **minimized**.

Return _the **minimum absolute difference**_.

The **absolute difference** between two numbers `a` and `b` is the absolute value of `a - b`.

**Example 1:**

**Input:** mat = \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\], target = 13
**Output:** 0
**Explanation:** One possible choice is to:
- Choose 1 from the first row.
- Choose 5 from the second row.
- Choose 7 from the third row.
The sum of the chosen elements is 13, which equals the target, so the absolute difference is 0.

**Example 2:**

**Input:** mat = \[\[1\],\[2\],\[3\]\], target = 100
**Output:** 94
**Explanation:** The best possible choice is to:
- Choose 1 from the first row.
- Choose 2 from the second row.
- Choose 3 from the third row.
The sum of the chosen elements is 6, and the absolute difference is 94.

**Example 3:**

**Input:** mat = \[\[1,2,9,8,7\]\], target = 6
**Output:** 1
**Explanation:** The best choice is to choose 7 from the first row.
The absolute difference is 1.

**Constraints:**

*   `m == mat.length`
*   `n == mat[i].length`
*   `1 <= m, n <= 70`
*   `1 <= mat[i][j] <= 70`
*   `1 <= target <= 800`