bowang0911/leetcode huggingface dataset:
Smallest Missing Non-negative Integer After Operations

You are given a **0-indexed** integer array `nums` and an integer `value`.

In one operation, you can add or subtract `value` from any element of `nums`.

*   For example, if `nums = [1,2,3]` and `value = 2`, you can choose to subtract `value` from `nums[0]` to make `nums = [-1,2,3]`.

The MEX (minimum excluded) of an array is the smallest missing **non-negative** integer in it.

*   For example, the MEX of `[-1,2,3]` is `0` while the MEX of `[1,0,3]` is `2`.

Return _the maximum MEX of_ `nums` _after applying the mentioned operation **any number of times**_.

**Example 1:**

**Input:** nums = \[1,-10,7,13,6,8\], value = 5
**Output:** 4
**Explanation:** One can achieve this result by applying the following operations:
- Add value to nums\[1\] twice to make nums = \[1,**0**,7,13,6,8\]
- Subtract value from nums\[2\] once to make nums = \[1,0,**2**,13,6,8\]
- Subtract value from nums\[3\] twice to make nums = \[1,0,2,**3**,6,8\]
The MEX of nums is 4. It can be shown that 4 is the maximum MEX we can achieve.

**Example 2:**

**Input:** nums = \[1,-10,7,13,6,8\], value = 7
**Output:** 2
**Explanation:** One can achieve this result by applying the following operation:
- subtract value from nums\[2\] once to make nums = \[1,-10,**0**,13,6,8\]
The MEX of nums is 2. It can be shown that 2 is the maximum MEX we can achieve.

**Constraints:**

*   `1 <= nums.length, value <= 105`
*   `-109 <= nums[i] <= 109`
Make the Prefix Sum Non-negative

You are given a **0-indexed** integer array `nums`. You can apply the following operation any number of times:

*   Pick any element from `nums` and put it at the end of `nums`.

The prefix sum array of `nums` is an array `prefix` of the same length as `nums` such that `prefix[i]` is the sum of all the integers `nums[j]` where `j` is in the inclusive range `[0, i]`.

Return _the minimum number of operations such that the prefix sum array does not contain negative integers_. The test cases are generated such that it is always possible to make the prefix sum array non-negative.

**Example 1:**

**Input:** nums = \[2,3,-5,4\]
**Output:** 0
**Explanation:** we do not need to do any operations.
The array is \[2,3,-5,4\]. The prefix sum array is \[2, 5, 0, 4\].

**Example 2:**

**Input:** nums = \[3,-5,-2,6\]
**Output:** 1
**Explanation:** we can do one operation on index 1.
The array after the operation is \[3,-2,6,-5\]. The prefix sum array is \[3, 1, 7, 2\].

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-109 <= nums[i] <= 109`
K Items With the Maximum Sum

There is a bag that consists of items, each item has a number `1`, `0`, or `-1` written on it.

You are given four **non-negative** integers `numOnes`, `numZeros`, `numNegOnes`, and `k`.

The bag initially contains:

*   `numOnes` items with `1`s written on them.
*   `numZeroes` items with `0`s written on them.
*   `numNegOnes` items with `-1`s written on them.

We want to pick exactly `k` items among the available items. Return _the **maximum** possible sum of numbers written on the items_.

**Example 1:**

**Input:** numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
**Output:** 2
**Explanation:** We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 2 items with 1 written on them and get a sum in a total of 2.
It can be proven that 2 is the maximum possible sum.

**Example 2:**

**Input:** numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
**Output:** 3
**Explanation:** We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 3 items with 1 written on them, and 1 item with 0 written on it, and get a sum in a total of 3.
It can be proven that 3 is the maximum possible sum.

**Constraints:**

*   `0 <= numOnes, numZeros, numNegOnes <= 50`
*   `0 <= k <= numOnes + numZeros + numNegOnes`
Prime Subtraction Operation

You are given a **0-indexed** integer array `nums` of length `n`.

You can perform the following operation as many times as you want:

*   Pick an index `i` that you haven't picked before, and pick a prime `p` **strictly less than** `nums[i]`, then subtract `p` from `nums[i]`.

Return _true if you can make `nums` a strictly increasing array using the above operation and false otherwise._

A **strictly increasing array** is an array whose each element is strictly greater than its preceding element.

**Example 1:**

**Input:** nums = \[4,9,6,10\]
**Output:** true
**Explanation:** In the first operation: Pick i = 0 and p = 3, and then subtract 3 from nums\[0\], so that nums becomes \[1,9,6,10\].
In the second operation: i = 1, p = 7, subtract 7 from nums\[1\], so nums becomes equal to \[1,2,6,10\].
After the second operation, nums is sorted in strictly increasing order, so the answer is true.

**Example 2:**

**Input:** nums = \[6,8,11,12\]
**Output:** true
**Explanation:** Initially nums is sorted in strictly increasing order, so we don't need to make any operations.

**Example 3:**

**Input:** nums = \[5,8,3\]
**Output:** false
**Explanation:** It can be proven that there is no way to perform operations to make nums sorted in strictly increasing order, so the answer is false.

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= nums[i] <= 1000`
*   `nums.length == n`
Minimum Operations to Make All Array Elements Equal

You are given an array `nums` consisting of positive integers.

You are also given an integer array `queries` of size `m`. For the `ith` query, you want to make all of the elements of `nums` equal to `queries[i]`. You can perform the following operation on the array **any** number of times:

*   **Increase** or **decrease** an element of the array by `1`.

Return _an array_ `answer` _of size_ `m` _where_ `answer[i]` _is the **minimum** number of operations to make all elements of_ `nums` _equal to_ `queries[i]`.

**Note** that after each query the array is reset to its original state.

**Example 1:**

**Input:** nums = \[3,1,6,8\], queries = \[1,5\]
**Output:** \[14,10\]
**Explanation:** For the first query we can do the following operations:
- Decrease nums\[0\] 2 times, so that nums = \[1,1,6,8\].
- Decrease nums\[2\] 5 times, so that nums = \[1,1,1,8\].
- Decrease nums\[3\] 7 times, so that nums = \[1,1,1,1\].
So the total number of operations for the first query is 2 + 5 + 7 = 14.
For the second query we can do the following operations:
- Increase nums\[0\] 2 times, so that nums = \[5,1,6,8\].
- Increase nums\[1\] 4 times, so that nums = \[5,5,6,8\].
- Decrease nums\[2\] 1 time, so that nums = \[5,5,5,8\].
- Decrease nums\[3\] 3 times, so that nums = \[5,5,5,5\].
So the total number of operations for the second query is 2 + 4 + 1 + 3 = 10.

**Example 2:**

**Input:** nums = \[2,9,6,3\], queries = \[10\]
**Output:** \[20\]
**Explanation:** We can increase each value in the array to 10. The total number of operations will be 8 + 1 + 4 + 7 = 20.

**Constraints:**

*   `n == nums.length`
*   `m == queries.length`
*   `1 <= n, m <= 105`
*   `1 <= nums[i], queries[i] <= 109`
Collect Coins in a Tree

There exists an undirected and unrooted tree with `n` nodes indexed from `0` to `n - 1`. You are given an integer `n` and a 2D integer array edges of length `n - 1`, where `edges[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the tree. You are also given an array `coins` of size `n` where `coins[i]` can be either `0` or `1`, where `1` indicates the presence of a coin in the vertex `i`.

Initially, you choose to start at any vertex in the tree. Then, you can perform the following operations any number of times:

*   Collect all the coins that are at a distance of at most `2` from the current vertex, or
*   Move to any adjacent vertex in the tree.

Find _the minimum number of edges you need to go through to collect all the coins and go back to the initial vertex_.

Note that if you pass an edge several times, you need to count it into the answer several times.

**Example 1:**

**Input:** coins = \[1,0,0,0,0,1\], edges = \[\[0,1\],\[1,2\],\[2,3\],\[3,4\],\[4,5\]\]
**Output:** 2
**Explanation:** Start at vertex 2, collect the coin at vertex 0, move to vertex 3, collect the coin at vertex 5 then move back to vertex 2.

**Example 2:**

**Input:** coins = \[0,0,0,1,1,0,0,1\], edges = \[\[0,1\],\[0,2\],\[1,3\],\[1,4\],\[2,5\],\[5,6\],\[5,7\]\]
**Output:** 2
**Explanation:** Start at vertex 0, collect the coins at vertices 4 and 3, move to vertex 2,  collect the coin at vertex 7, then move back to vertex 0.

**Constraints:**

*   `n == coins.length`
*   `1 <= n <= 3 * 104`
*   `0 <= coins[i] <= 1`
*   `edges.length == n - 1`
*   `edges[i].length == 2`
*   `0 <= ai, bi < n`
*   `ai != bi`
*   `edges` represents a valid tree.
Minimum Time to Eat All Grains

There are `n` hens and `m` grains on a line. You are given the initial positions of the hens and the grains in two integer arrays `hens` and `grains` of size `n` and `m` respectively.

Any hen can eat a grain if they are on the same position. The time taken for this is negligible. One hen can also eat multiple grains.

In `1` second, a hen can move right or left by `1` unit. The hens can move simultaneously and independently of each other.

Return _the **minimum** time to eat all grains if the hens act optimally._

**Example 1:**

**Input:** hens = \[3,6,7\], grains = \[2,4,7,9\]
**Output:** 2
**Explanation:** 
One of the ways hens eat all grains in 2 seconds is described below:
- The first hen eats the grain at position 2 in 1 second. 
- The second hen eats the grain at position 4 in 2 seconds. 
- The third hen eats the grains at positions 7 and 9 in 2 seconds. 
So, the maximum time needed is 2.
It can be proven that the hens cannot eat all grains before 2 seconds.

**Example 2:**

**Input:** hens = \[4,6,109,111,213,215\], grains = \[5,110,214\]
**Output:** 1
**Explanation:** 
One of the ways hens eat all grains in 1 second is described below:
- The first hen eats the grain at position 5 in 1 second. 
- The fourth hen eats the grain at position 110 in 1 second.
- The sixth hen eats the grain at position 214 in 1 second. 
- The other hens do not move. 
So, the maximum time needed is 1.

**Constraints:**

*   `1 <= hens.length, grains.length <= 2*104`
*   `0 <= hens[i], grains[j] <= 109`
Form Smallest Number From Two Digit Arrays

Given two arrays of **unique** digits `nums1` and `nums2`, return _the **smallest** number that contains **at least** one digit from each array_.

**Example 1:**

**Input:** nums1 = \[4,1,3\], nums2 = \[5,7\]
**Output:** 15
**Explanation:** The number 15 contains the digit 1 from nums1 and the digit 5 from nums2. It can be proven that 15 is the smallest number we can have.

**Example 2:**

**Input:** nums1 = \[3,5,2,6\], nums2 = \[3,1,7\]
**Output:** 3
**Explanation:** The number 3 contains the digit 3 which exists in both arrays.

**Constraints:**

*   `1 <= nums1.length, nums2.length <= 9`
*   `1 <= nums1[i], nums2[i] <= 9`
*   All digits in each array are **unique**.
Find the Substring With Maximum Cost

You are given a string `s`, a string `chars` of **distinct** characters and an integer array `vals` of the same length as `chars`.

The **cost of the substring** is the sum of the values of each character in the substring. The cost of an empty string is considered `0`.

The **value of the character** is defined in the following way:

*   If the character is not in the string `chars`, then its value is its corresponding position **(1-indexed)** in the alphabet.
    *   For example, the value of `'a'` is `1`, the value of `'b'` is `2`, and so on. The value of `'z'` is `26`.
*   Otherwise, assuming `i` is the index where the character occurs in the string `chars`, then its value is `vals[i]`.

Return _the maximum cost among all substrings of the string_ `s`.

**Example 1:**

**Input:** s =  "adaa ", chars =  "d ", vals = \[-1000\]
**Output:** 2
**Explanation:** The value of the characters  "a " and  "d " is 1 and -1000 respectively.
The substring with the maximum cost is  "aa " and its cost is 1 + 1 = 2.
It can be proven that 2 is the maximum cost.

**Example 2:**

**Input:** s =  "abc ", chars =  "abc ", vals = \[-1,-1,-1\]
**Output:** 0
**Explanation:** The value of the characters  "a ",  "b " and  "c " is -1, -1, and -1 respectively.
The substring with the maximum cost is the empty substring  " " and its cost is 0.
It can be proven that 0 is the maximum cost.

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consist of lowercase English letters.
*   `1 <= chars.length <= 26`
*   `chars` consist of **distinct** lowercase English letters.
*   `vals.length == chars.length`
*   `-1000 <= vals[i] <= 1000`
Make K-Subarray Sums Equal

You are given a **0-indexed** integer array `arr` and an integer `k`. The array `arr` is circular. In other words, the first element of the array is the next element of the last element, and the last element of the array is the previous element of the first element.

You can do the following operation any number of times:

*   Pick any element from `arr` and increase or decrease it by `1`.

Return _the minimum number of operations such that the sum of each **subarray** of length_ `k` _is equal_.

A **subarray** is a contiguous part of the array.

**Example 1:**

**Input:** arr = \[1,4,1,3\], k = 2
**Output:** 1
**Explanation:** we can do one operation on index 1 to make its value equal to 3.
The array after the operation is \[1,3,1,3\]
- Subarray starts at index 0 is \[1, 3\], and its sum is 4 
- Subarray starts at index 1 is \[3, 1\], and its sum is 4 
- Subarray starts at index 2 is \[1, 3\], and its sum is 4 
- Subarray starts at index 3 is \[3, 1\], and its sum is 4 

**Example 2:**

**Input:** arr = \[2,5,5,7\], k = 3
**Output:** 5
**Explanation:** we can do three operations on index 0 to make its value equal to 5 and two operations on index 3 to make its value equal to 5.
The array after the operations is \[5,5,5,5\]
- Subarray starts at index 0 is \[5, 5, 5\], and its sum is 15
- Subarray starts at index 1 is \[5, 5, 5\], and its sum is 15
- Subarray starts at index 2 is \[5, 5, 5\], and its sum is 15
- Subarray starts at index 3 is \[5, 5, 5\], and its sum is 15 

**Constraints:**

*   `1 <= k <= arr.length <= 105`
*   `1 <= arr[i] <= 109`
Shortest Cycle in a Graph

There is a **bi-directional** graph with `n` vertices, where each vertex is labeled from `0` to `n - 1`. The edges in the graph are represented by a given 2D integer array `edges`, where `edges[i] = [ui, vi]` denotes an 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.

Return _the length of the **shortest** cycle in the graph_. If no cycle exists, return `-1`.

A cycle is a path that starts and ends at the same node, and each edge in the path is used only once.

**Example 1:**

**Input:** n = 7, edges = \[\[0,1\],\[1,2\],\[2,0\],\[3,4\],\[4,5\],\[5,6\],\[6,3\]\]
**Output:** 3
**Explanation:** The cycle with the smallest length is : 0 -> 1 -> 2 -> 0 

**Example 2:**

**Input:** n = 4, edges = \[\[0,1\],\[0,2\]\]
**Output:** -1
**Explanation:** There are no cycles in this graph.

**Constraints:**

*   `2 <= n <= 1000`
*   `1 <= edges.length <= 1000`
*   `edges[i].length == 2`
*   `0 <= ui, vi < n`
*   `ui != vi`
*   There are no repeated edges.
Find the Longest Balanced Substring of a Binary String

You are given a binary string `s` consisting only of zeroes and ones.

A substring of `s` is considered balanced if **all zeroes are before ones** and the number of zeroes is equal to the number of ones inside the substring. Notice that the empty substring is considered a balanced substring.

Return _the length of the longest balanced substring of_ `s`.

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

**Example 1:**

**Input:** s =  "01000111 "
**Output:** 6
**Explanation:** The longest balanced substring is  "000111 ", which has length 6.

**Example 2:**

**Input:** s =  "00111 "
**Output:** 4
**Explanation:** The longest balanced substring is  "0011 ", which has length 4. 

**Example 3:**

**Input:** s =  "111 "
**Output:** 0
**Explanation:** There is no balanced substring except the empty substring, so the answer is 0.

**Constraints:**

*   `1 <= s.length <= 50`
*   `'0' <= s[i] <= '1'`
Convert an Array Into a 2D Array With Conditions

You are given an integer array `nums`. You need to create a 2D array from `nums` satisfying the following conditions:

*   The 2D array should contain **only** the elements of the array `nums`.
*   Each row in the 2D array contains **distinct** integers.
*   The number of rows in the 2D array should be **minimal**.

Return _the resulting array_. If there are multiple answers, return any of them.

**Note** that the 2D array can have a different number of elements on each row.

**Example 1:**

**Input:** nums = \[1,3,4,1,2,3,1\]
**Output:** \[\[1,3,4,2\],\[1,3\],\[1\]\]
**Explanation:** We can create a 2D array that contains the following rows:
- 1,3,4,2
- 1,3
- 1
All elements of nums were used, and each row of the 2D array contains distinct integers, so it is a valid answer.
It can be shown that we cannot have less than 3 rows in a valid array.

**Example 2:**

**Input:** nums = \[1,2,3,4\]
**Output:** \[\[4,3,2,1\]\]
**Explanation:** All elements of the array are distinct, so we can keep all of them in the first row of the 2D array.

**Constraints:**

*   `1 <= nums.length <= 200`
*   `1 <= nums[i] <= nums.length`
Mice and Cheese

There are two mice and `n` different types of cheese, each type of cheese should be eaten by exactly one mouse.

A point of the cheese with index `i` (**0-indexed**) is:

*   `reward1[i]` if the first mouse eats it.
*   `reward2[i]` if the second mouse eats it.

You are given a positive integer array `reward1`, a positive integer array `reward2`, and a non-negative integer `k`.

Return _**the maximum** points the mice can achieve if the first mouse eats exactly_ `k` _types of cheese._

**Example 1:**

**Input:** reward1 = \[1,1,3,4\], reward2 = \[4,4,1,1\], k = 2
**Output:** 15
**Explanation:** In this example, the first mouse eats the 2nd (0-indexed) and the 3rd types of cheese, and the second mouse eats the 0th and the 1st types of cheese.
The total points are 4 + 4 + 3 + 4 = 15.
It can be proven that 15 is the maximum total points that the mice can achieve.

**Example 2:**

**Input:** reward1 = \[1,1\], reward2 = \[1,1\], k = 2
**Output:** 2
**Explanation:** In this example, the first mouse eats the 0th (0-indexed) and 1st types of cheese, and the second mouse does not eat any cheese.
The total points are 1 + 1 = 2.
It can be proven that 2 is the maximum total points that the mice can achieve.

**Constraints:**

*   `1 <= n == reward1.length == reward2.length <= 105`
*   `1 <= reward1[i], reward2[i] <= 1000`
*   `0 <= k <= n`
Minimum Reverse Operations

You are given an integer `n` and an integer `p` in the range `[0, n - 1]`. Representing a **0-indexed** array `arr` of length `n` where all positions are set to `0`'s, except position `p` which is set to `1`.

You are also given an integer array `banned` containing some positions from the array. For the **i****th** position in `banned`, `arr[banned[i]] = 0`, and `banned[i] != p`.

You can perform **multiple** operations on `arr`. In an operation, you can choose a **subarray** with size `k` and **reverse** the subarray. However, the `1` in `arr` should never go to any of the positions in `banned`. In other words, after each operation `arr[banned[i]]` **remains** `0`.

_Return an array_ `ans` _where_ _for each_ `i` _from_ `[0, n - 1]`, `ans[i]` _is the **minimum** number of reverse operations needed to bring the_ `1` _to position_ `i` _in arr_, _or_ `-1` _if it is impossible_.

*   A **subarray** is a contiguous **non-empty** sequence of elements within an array.
*   The values of `ans[i]` are independent for all `i`'s.
*   The **reverse** of an array is an array containing the values in **reverse order**.

**Example 1:**

**Input:** n = 4, p = 0, banned = \[1,2\], k = 4
**Output:** \[0,-1,-1,1\]
**Explanation:** In this case `k = 4` so there is only one possible reverse operation we can perform, which is reversing the whole array. Initially, 1 is placed at position 0 so the amount of operations we need for position 0 is `0`. We can never place a 1 on the banned positions, so the answer for positions 1 and 2 is `-1`. Finally, with one reverse operation we can bring the 1 to index 3, so the answer for position 3 is `1`. 

**Example 2:**

**Input:** n = 5, p = 0, banned = \[2,4\], k = 3
**Output:** \[0,-1,-1,-1,-1\]
**Explanation:** In this case the 1 is initially at position 0, so the answer for that position is `0`. We can perform reverse operations of size 3. The 1 is currently located at position 0, so we need to reverse the subarray `[0, 2]` for it to leave that position, but reversing that subarray makes position 2 have a 1, which shouldn't happen. So, we can't move the 1 from position 0, making the result for all the other positions `-1`. 

**Example 3:**

**Input:** n = 4, p = 2, banned = \[0,1,3\], k = 1
**Output:** \[-1,-1,0,-1\]
**Explanation:** In this case we can only perform reverse operations of size 1. So the 1 never changes its position.

**Constraints:**

*   `1 <= n <= 105`
*   `0 <= p <= n - 1`
*   `0 <= banned.length <= n - 1`
*   `0 <= banned[i] <= n - 1`
*   `1 <= k <= n`
*   `banned[i] != p`
*   all values in `banned` are **unique**