bowang0911/leetcode huggingface dataset:
Diet Plan Performance

A dieter consumes `calories[i]` calories on the `i`\-th day.

Given an integer `k`, for **every** consecutive sequence of `k` days (`calories[i], calories[i+1], ..., calories[i+k-1]` for all `0 <= i <= n-k`), they look at _T_, the total calories consumed during that sequence of `k` days (`calories[i] + calories[i+1] + ... + calories[i+k-1]`):

*   If `T < lower`, they performed poorly on their diet and lose 1 point;
*   If `T > upper`, they performed well on their diet and gain 1 point;
*   Otherwise, they performed normally and there is no change in points.

Initially, the dieter has zero points. Return the total number of points the dieter has after dieting for `calories.length` days.

Note that the total points can be negative.

**Example 1:**

**Input:** calories = \[1,2,3,4,5\], k = 1, lower = 3, upper = 3
**Output:** 0
**Explanation**: Since k = 1, we consider each element of the array separately and compare it to lower and upper.
calories\[0\] and calories\[1\] are less than lower so 2 points are lost.
calories\[3\] and calories\[4\] are greater than upper so 2 points are gained.

**Example 2:**

**Input:** calories = \[3,2\], k = 2, lower = 0, upper = 1
**Output:** 1
**Explanation**: Since k = 2, we consider subarrays of length 2.
calories\[0\] + calories\[1\] > upper so 1 point is gained.

**Example 3:**

**Input:** calories = \[6,5,0,0\], k = 2, lower = 1, upper = 5
**Output:** 0
**Explanation**:
calories\[0\] + calories\[1\] > upper so 1 point is gained.
lower <= calories\[1\] + calories\[2\] <= upper so no change in points.
calories\[2\] + calories\[3\] < lower so 1 point is lost.

**Constraints:**

*   `1 <= k <= calories.length <= 10^5`
*   `0 <= calories[i] <= 20000`
*   `0 <= lower <= upper`
Can Make Palindrome from Substring

You are given a string `s` and array `queries` where `queries[i] = [lefti, righti, ki]`. We may rearrange the substring `s[lefti...righti]` for each query and then choose up to `ki` of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is `true`. Otherwise, the result is `false`.

Return a boolean array `answer` where `answer[i]` is the result of the `ith` query `queries[i]`.

Note that each letter is counted individually for replacement, so if, for example `s[lefti...righti] = "aaa "`, and `ki = 2`, we can only replace two of the letters. Also, note that no query modifies the initial string `s`.

**Example :**

**Input:** s =  "abcda ", queries = \[\[3,3,0\],\[1,2,0\],\[0,3,1\],\[0,3,2\],\[0,4,1\]\]
**Output:** \[true,false,false,true,true\]
**Explanation:**
queries\[0\]: substring =  "d ", is palidrome.
queries\[1\]: substring =  "bc ", is not palidrome.
queries\[2\]: substring =  "abcd ", is not palidrome after replacing only 1 character.
queries\[3\]: substring =  "abcd ", could be changed to  "abba " which is palidrome. Also this can be changed to  "baab " first rearrange it  "bacd " then replace  "cd " with  "ab ".
queries\[4\]: substring =  "abcda ", could be changed to  "abcba " which is palidrome.

**Example 2:**

**Input:** s =  "lyb ", queries = \[\[0,1,0\],\[2,2,1\]\]
**Output:** \[false,true\]

**Constraints:**

*   `1 <= s.length, queries.length <= 105`
*   `0 <= lefti <= righti < s.length`
*   `0 <= ki <= s.length`
*   `s` consists of lowercase English letters.
Number of Valid Words for Each Puzzle

With respect to a given `puzzle` string, a `word` is _valid_ if both the following conditions are satisfied:

*   `word` contains the first letter of `puzzle`.
*   For each letter in `word`, that letter is in `puzzle`.
    *   For example, if the puzzle is `"abcdefg "`, then valid words are `"faced "`, `"cabbage "`, and `"baggage "`, while
    *   invalid words are `"beefed "` (does not include `'a'`) and `"based "` (includes `'s'` which is not in the puzzle).

Return _an array_ `answer`_, where_ `answer[i]` _is the number of words in the given word list_ `words` _that is valid with respect to the puzzle_ `puzzles[i]`.

**Example 1:**

**Input:** words = \[ "aaaa ", "asas ", "able ", "ability ", "actt ", "actor ", "access "\], puzzles = \[ "aboveyz ", "abrodyz ", "abslute ", "absoryz ", "actresz ", "gaswxyz "\]
**Output:** \[1,1,3,2,4,0\]
**Explanation:** 
1 valid word for  "aboveyz " :  "aaaa " 
1 valid word for  "abrodyz " :  "aaaa "
3 valid words for  "abslute " :  "aaaa ",  "asas ",  "able "
2 valid words for  "absoryz " :  "aaaa ",  "asas "
4 valid words for  "actresz " :  "aaaa ",  "asas ",  "actt ",  "access "
There are no valid words for  "gaswxyz " cause none of the words in the list contains letter 'g'.

**Example 2:**

**Input:** words = \[ "apple ", "pleas ", "please "\], puzzles = \[ "aelwxyz ", "aelpxyz ", "aelpsxy ", "saelpxy ", "xaelpsy "\]
**Output:** \[0,1,3,2,0\]

**Constraints:**

*   `1 <= words.length <= 105`
*   `4 <= words[i].length <= 50`
*   `1 <= puzzles.length <= 104`
*   `puzzles[i].length == 7`
*   `words[i]` and `puzzles[i]` consist of lowercase English letters.
*   Each `puzzles[i]` does not contain repeated characters.
Count Substrings with Only One Distinct Letter

Given a string `s`, return _the number of substrings that have only **one distinct** letter_.

**Example 1:**

**Input:** s =  "aaaba "
**Output:** 8
**Explanation:** The substrings with one distinct letter are  "aaa ",  "aa ",  "a ",  "b ".
 "aaa " occurs 1 time.
 "aa " occurs 2 times.
 "a " occurs 4 times.
 "b " occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

**Example 2:**

**Input:** s =  "aaaaaaaaaa "
**Output:** 55

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s[i]` consists of only lowercase English letters.
Before and After Puzzle

Given a list of `phrases`, generate a list of Before and After puzzles.

A _phrase_ is a string that consists of lowercase English letters and spaces only. No space appears in the start or the end of a phrase. There are no consecutive spaces in a phrase.

_Before and After puzzles_ are phrases that are formed by merging two phrases where the **last word of the first phrase** is the same as the **first word of the second phrase**.

Return the Before and After puzzles that can be formed by every two phrases `phrases[i]` and `phrases[j]` where `i != j`. Note that the order of matching two phrases matters, we want to consider both orders.

You should return a list of **distinct** strings **sorted lexicographically**.

**Example 1:**

**Input:** phrases = \[ "writing code ", "code rocks "\]
**Output:** \[ "writing code rocks "\]

**Example 2:**

**Input:** phrases = \[ "mission statement ",
                   "a quick bite to eat ",
                   "a chip off the old block ",
                   "chocolate bar ",
                   "mission impossible ",
                   "a man on a mission ",
                   "block party ",
                   "eat my words ",
                   "bar of soap "\]
**Output:** \[ "a chip off the old block party ",
          "a man on a mission impossible ",
          "a man on a mission statement ",
          "a quick bite to eat my words ",
          "chocolate bar of soap "\]

**Example 3:**

**Input:** phrases = \[ "a ", "b ", "a "\]
**Output:** \[ "a "\]

**Constraints:**

*   `1 <= phrases.length <= 100`
*   `1 <= phrases[i].length <= 100`
Shortest Distance to Target Color

You are given an array `colors`, in which there are three colors: `1`, `2` and `3`.

You are also given some queries. Each query consists of two integers `i` and `c`, return the shortest distance between the given index `i` and the target color `c`. If there is no solution return `-1`.

**Example 1:**

**Input:** colors = \[1,1,2,1,3,2,2,3,3\], queries = \[\[1,3\],\[2,2\],\[6,1\]\]
**Output:** \[3,0,3\]
**Explanation:** 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

**Example 2:**

**Input:** colors = \[1,2\], queries = \[\[0,3\]\]
**Output:** \[-1\]
**Explanation:** There is no 3 in the array.

**Constraints:**

*   `1 <= colors.length <= 5*10^4`
*   `1 <= colors[i] <= 3`
*   `1 <= queries.length <= 5*10^4`
*   `queries[i].length == 2`
*   `0 <= queries[i][0] < colors.length`
*   `1 <= queries[i][1] <= 3`
Maximum Number of Ones

Consider a matrix `M` with dimensions `width * height`, such that every cell has value `0` or `1`, and any **square** sub-matrix of `M` of size `sideLength * sideLength` has at most `maxOnes` ones.

Return the maximum possible number of ones that the matrix `M` can have.

**Example 1:**

**Input:** width = 3, height = 3, sideLength = 2, maxOnes = 1
**Output:** 4
**Explanation:**
In a 3\*3 matrix, no 2\*2 sub-matrix can have more than 1 one.
The best solution that has 4 ones is:
\[1,0,1\]
\[0,0,0\]
\[1,0,1\]

**Example 2:**

**Input:** width = 3, height = 3, sideLength = 2, maxOnes = 2
**Output:** 6
**Explanation:**
\[1,0,1\]
\[1,0,1\]
\[1,0,1\]

**Constraints:**

*   `1 <= width, height <= 100`
*   `1 <= sideLength <= width, height`
*   `0 <= maxOnes <= sideLength * sideLength`
Distance Between Bus Stops

A bus has `n` stops numbered from `0` to `n - 1` that form a circle. We know the distance between all pairs of neighboring stops where `distance[i]` is the distance between the stops number `i` and `(i + 1) % n`.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given `start` and `destination` stops.

**Example 1:**

**Input:** distance = \[1,2,3,4\], start = 0, destination = 1
**Output:** 1
**Explanation:** Distance between 0 and 1 is 1 or 9, minimum is 1.

**Example 2:**

**Input:** distance = \[1,2,3,4\], start = 0, destination = 2
**Output:** 3
**Explanation:** Distance between 0 and 2 is 3 or 7, minimum is 3.

**Example 3:**

**Input:** distance = \[1,2,3,4\], start = 0, destination = 3
**Output:** 4
**Explanation:** Distance between 0 and 3 is 6 or 4, minimum is 4.

**Constraints:**

*   `1 <= n <= 10^4`
*   `distance.length == n`
*   `0 <= start, destination < n`
*   `0 <= distance[i] <= 10^4`
Day of the Week

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the `day`, `month` and `year` respectively.

Return the answer as one of the following values `{ "Sunday ", "Monday ", "Tuesday ", "Wednesday ", "Thursday ", "Friday ", "Saturday "}`.

**Example 1:**

**Input:** day = 31, month = 8, year = 2019
**Output:**  "Saturday "

**Example 2:**

**Input:** day = 18, month = 7, year = 1999
**Output:**  "Sunday "

**Example 3:**

**Input:** day = 15, month = 8, year = 1993
**Output:**  "Sunday "

**Constraints:**

*   The given dates are valid dates between the years `1971` and `2100`.
Maximum Subarray Sum with One Deletion

Given an array of integers, return the maximum sum for a **non-empty** subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be **non-empty** after deleting one element.

**Example 1:**

**Input:** arr = \[1,-2,0,3\]
**Output:** 4
**Explanation:** Because we can choose \[1, -2, 0, 3\] and drop -2, thus the subarray \[1, 0, 3\] becomes the maximum value.

**Example 2:**

**Input:** arr = \[1,-2,-2,3\]
**Output:** 3
**Explanation:** We just choose \[3\] and it's the maximum sum.

**Example 3:**

**Input:** arr = \[-1,-1,-1,-1\]
**Output:** -1
**Explanation:** The final subarray needs to be non-empty. You can't choose \[-1\] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

**Constraints:**

*   `1 <= arr.length <= 105`
*   `-104 <= arr[i] <= 104`
Make Array Strictly Increasing

Given two integer arrays `arr1` and `arr2`, return the minimum number of operations (possibly zero) needed to make `arr1` strictly increasing.

In one operation, you can choose two indices `0 <= i < arr1.length` and `0 <= j < arr2.length` and do the assignment `arr1[i] = arr2[j]`.

If there is no way to make `arr1` strictly increasing, return `-1`.

**Example 1:**

**Input:** arr1 = \[1,5,3,6,7\], arr2 = \[1,3,2,4\]
**Output:** 1
**Explanation:** Replace `5` with `2`, then `arr1 = [1, 2, 3, 6, 7]`.

**Example 2:**

**Input:** arr1 = \[1,5,3,6,7\], arr2 = \[4,3,1\]
**Output:** 2
**Explanation:** Replace `5` with `3` and then replace `3` with `4`. `arr1 = [1, 3, 4, 6, 7]`.

**Example 3:**

**Input:** arr1 = \[1,5,3,6,7\], arr2 = \[1,6,3,3\]
**Output:** -1
**Explanation:** You can't make `arr1` strictly increasing.

**Constraints:**

*   `1 <= arr1.length, arr2.length <= 2000`
*   `0 <= arr1[i], arr2[i] <= 10^9`
Maximum Number of Balloons

Given a string `text`, you want to use the characters of `text` to form as many instances of the word **"balloon "** as possible.

You can use each character in `text` **at most once**. Return the maximum number of instances that can be formed.

**Example 1:**

**Input:** text =  "nlaebolko "
**Output:** 1

**Example 2:**

**Input:** text =  "loonbalxballpoon "
**Output:** 2

**Example 3:**

**Input:** text =  "leetcode "
**Output:** 0

**Constraints:**

*   `1 <= text.length <= 104`
*   `text` consists of lower case English letters only.
Reverse Substrings Between Each Pair of Parentheses

You are given a string `s` that consists of lower case English letters and brackets.

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should **not** contain any brackets.

**Example 1:**

**Input:** s =  "(abcd) "
**Output:**  "dcba "

**Example 2:**

**Input:** s =  "(u(love)i) "
**Output:**  "iloveu "
**Explanation:** The substring  "love " is reversed first, then the whole string is reversed.

**Example 3:**

**Input:** s =  "(ed(et(oc))el) "
**Output:**  "leetcode "
**Explanation:** First, we reverse the substring  "oc ", then  "etco ", and finally, the whole string.

**Constraints:**

*   `1 <= s.length <= 2000`
*   `s` only contains lower case English characters and parentheses.
*   It is guaranteed that all parentheses are balanced.
K-Concatenation Maximum Sum

Given an integer array `arr` and an integer `k`, modify the array by repeating it `k` times.

For example, if `arr = [1, 2]` and `k = 3` then the modified array will be `[1, 2, 1, 2, 1, 2]`.

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be `0` and its sum in that case is `0`.

As the answer can be very large, return the answer **modulo** `109 + 7`.

**Example 1:**

**Input:** arr = \[1,2\], k = 3
**Output:** 9

**Example 2:**

**Input:** arr = \[1,-2,1\], k = 5
**Output:** 2

**Example 3:**

**Input:** arr = \[-1,-2\], k = 7
**Output:** 0

**Constraints:**

*   `1 <= arr.length <= 105`
*   `1 <= k <= 105`
*   `-104 <= arr[i] <= 104`
Critical Connections in a Network

There are `n` servers numbered from `0` to `n - 1` connected by undirected server-to-server `connections` forming a network where `connections[i] = [ai, bi]` represents a connection between servers `ai` and `bi`. Any server can reach other servers directly or indirectly through the network.

A _critical connection_ is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

**Example 1:**

**Input:** n = 4, connections = \[\[0,1\],\[1,2\],\[2,0\],\[1,3\]\]
**Output:** \[\[1,3\]\]
**Explanation:** \[\[3,1\]\] is also accepted.

**Example 2:**

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

**Constraints:**

*   `2 <= n <= 105`
*   `n - 1 <= connections.length <= 105`
*   `0 <= ai, bi <= n - 1`
*   `ai != bi`
*   There are no repeated connections.
How Many Apples Can You Put into the Basket

You have some apples and a basket that can carry up to `5000` units of weight.

Given an integer array `weight` where `weight[i]` is the weight of the `ith` apple, return _the maximum number of apples you can put in the basket_.

**Example 1:**

**Input:** weight = \[100,200,150,1000\]
**Output:** 4
**Explanation:** All 4 apples can be carried by the basket since their sum of weights is 1450.

**Example 2:**

**Input:** weight = \[900,950,800,1000,700,800\]
**Output:** 5
**Explanation:** The sum of weights of the 6 apples exceeds 5000 so we choose any 5 of them.

**Constraints:**

*   `1 <= weight.length <= 103`
*   `1 <= weight[i] <= 103`
Minimum Knight Moves

In an **infinite** chess board with coordinates from `-infinity` to `+infinity`, you have a **knight** at square `[0, 0]`.

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return _the minimum number of steps needed to move the knight to the square_ `[x, y]`. It is guaranteed the answer exists.

**Example 1:**

**Input:** x = 2, y = 1
**Output:** 1
**Explanation:** \[0, 0\] -> \[2, 1\]

**Example 2:**

**Input:** x = 5, y = 5
**Output:** 4
**Explanation:** \[0, 0\] -> \[2, 1\] -> \[4, 2\] -> \[3, 4\] -> \[5, 5\]

**Constraints:**

*   `-300 <= x, y <= 300`
*   `0 <= |x| + |y| <= 300`

"t", evaluating to True; "f", evaluating to False; "!(expression)", evaluating to the logical NOT of the expression inside the parentheses; "&(expression1,expression2,...)", evaluating to the logical AND of 2 or more expressions; "|(expression1,expression2,...)", evaluating to the logical OR of 2 or more expressions.
Find Smallest Common Element in All Rows

Given an `m x n` matrix `mat` where every row is sorted in **strictly** **increasing** order, return _the **smallest common element** in all rows_.

If there is no common element, return `-1`.

**Example 1:**

**Input:** mat = \[\[1,2,3,4,5\],\[2,4,5,8,10\],\[3,5,7,9,11\],\[1,3,5,7,9\]\]
**Output:** 5

**Example 2:**

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

**Constraints:**

*   `m == mat.length`
*   `n == mat[i].length`
*   `1 <= m, n <= 500`
*   `1 <= mat[i][j] <= 104`
*   `mat[i]` is sorted in strictly increasing order.
Minimum Time to Build Blocks

You are given a list of blocks, where `blocks[i] = t` means that the `i`\-th block needs `t` units of time to be built. A block can only be built by exactly one worker.

A worker can either split into two workers (number of workers increases by one) or build a block then go home. Both decisions cost some time.

The time cost of spliting one worker into two workers is given as an integer `split`. Note that if two workers split at the same time, they split in parallel so the cost would be `split`.

Output the minimum time needed to build all blocks.

Initially, there is only **one** worker.

**Example 1:**

**Input:** blocks = \[1\], split = 1
**Output:** 1
**Explanation:** We use 1 worker to build 1 block in 1 time unit.

**Example 2:**

**Input:** blocks = \[1,2\], split = 5
**Output:** 7
**Explanation:** We split the worker into 2 workers in 5 time units then assign each of them to a block so the cost is 5 + max(1, 2) = 7.

**Example 3:**

**Input:** blocks = \[1,2,3\], split = 1
**Output:** 4
**Explanation:** Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2.
Then, use the two unassigned workers to build the first two blocks.
The cost is 1 + max(3, 1 + max(1, 2)) = 4.

**Constraints:**

*   `1 <= blocks.length <= 1000`
*   `1 <= blocks[i] <= 10^5`
*   `1 <= split <= 100`
Minimum Absolute Difference

Given an array of **distinct** integers `arr`, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair `[a, b]` follows

*   `a, b` are from `arr`
*   `a < b`
*   `b - a` equals to the minimum absolute difference of any two elements in `arr`

**Example 1:**

**Input:** arr = \[4,2,1,3\]
**Output:** \[\[1,2\],\[2,3\],\[3,4\]\]
**Explanation:** The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

**Example 2:**

**Input:** arr = \[1,3,6,10,15\]
**Output:** \[\[1,3\]\]

**Example 3:**

**Input:** arr = \[3,8,-10,23,19,-4,-14,27\]
**Output:** \[\[-14,-10\],\[19,23\],\[23,27\]\]

**Constraints:**

*   `2 <= arr.length <= 105`
*   `-106 <= arr[i] <= 106`
Ugly Number III

An **ugly number** is a positive integer that is divisible by `a`, `b`, or `c`.

Given four integers `n`, `a`, `b`, and `c`, return the `nth` **ugly number**.

**Example 1:**

**Input:** n = 3, a = 2, b = 3, c = 5
**Output:** 4
**Explanation:** The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

**Example 2:**

**Input:** n = 4, a = 2, b = 3, c = 4
**Output:** 6
**Explanation:** The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.

**Example 3:**

**Input:** n = 5, a = 2, b = 11, c = 13
**Output:** 10
**Explanation:** The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

**Constraints:**

*   `1 <= n, a, b, c <= 109`
*   `1 <= a * b * c <= 1018`
*   It is guaranteed that the result will be in range `[1, 2 * 109]`.
Smallest String With Swaps

You are given a string `s`, and an array of pairs of indices in the string `pairs` where `pairs[i] = [a, b]` indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given `pairs` **any number of times**.

Return the lexicographically smallest string that `s` can be changed to after using the swaps.

**Example 1:**

**Input:** s =  "dcab ", pairs = \[\[0,3\],\[1,2\]\]
**Output:**  "bacd "
**Explaination:** 
Swap s\[0\] and s\[3\], s =  "bcad "
Swap s\[1\] and s\[2\], s =  "bacd "

**Example 2:**

**Input:** s =  "dcab ", pairs = \[\[0,3\],\[1,2\],\[0,2\]\]
**Output:**  "abcd "
**Explaination:** 
Swap s\[0\] and s\[3\], s =  "bcad "
Swap s\[0\] and s\[2\], s =  "acbd "
Swap s\[1\] and s\[2\], s =  "abcd "

**Example 3:**

**Input:** s =  "cba ", pairs = \[\[0,1\],\[1,2\]\]
**Output:**  "abc "
**Explaination:** 
Swap s\[0\] and s\[1\], s =  "bca "
Swap s\[1\] and s\[2\], s =  "bac "
Swap s\[0\] and s\[1\], s =  "abc "

**Constraints:**

*   `1 <= s.length <= 10^5`
*   `0 <= pairs.length <= 10^5`
*   `0 <= pairs[i][0], pairs[i][1] < s.length`
*   `s` only contains lower case English letters.
Sort Items by Groups Respecting Dependencies

There are `n` items each belonging to zero or one of `m` groups where `group[i]` is the group that the `i`\-th item belongs to and it's equal to `-1` if the `i`\-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.

Return a sorted list of the items such that:

*   The items that belong to the same group are next to each other in the sorted list.
*   There are some relations between these items where `beforeItems[i]` is a list containing all the items that should come before the `i`\-th item in the sorted array (to the left of the `i`\-th item).

Return any solution if there is more than one solution and return an **empty list** if there is no solution.

**Example 1:**

**Input:** n = 8, m = 2, group = \[-1,-1,1,0,0,1,0,-1\], beforeItems = \[\[\],\[6\],\[5\],\[6\],\[3,6\],\[\],\[\],\[\]\]
**Output:** \[6,3,4,1,5,2,0,7\]

**Example 2:**

**Input:** n = 8, m = 2, group = \[-1,-1,1,0,0,1,0,-1\], beforeItems = \[\[\],\[6\],\[5\],\[6\],\[3\],\[\],\[4\],\[\]\]
**Output:** \[\]
**Explanation:** This is the same as example 1 except that 4 needs to be before 6 in the sorted list.

**Constraints:**

*   `1 <= m <= n <= 3 * 104`
*   `group.length == beforeItems.length == n`
*   `-1 <= group[i] <= m - 1`
*   `0 <= beforeItems[i].length <= n - 1`
*   `0 <= beforeItems[i][j] <= n - 1`
*   `i != beforeItems[i][j]`
*   `beforeItems[i]` does not contain duplicates elements.