bowang0911/leetcode huggingface dataset:
Maximum Bags With Full Capacity of Rocks

You have `n` bags numbered from `0` to `n - 1`. You are given two **0-indexed** integer arrays `capacity` and `rocks`. The `ith` bag can hold a maximum of `capacity[i]` rocks and currently contains `rocks[i]` rocks. You are also given an integer `additionalRocks`, the number of additional rocks you can place in **any** of the bags.

Return _the **maximum** number of bags that could have full capacity after placing the additional rocks in some bags._

**Example 1:**

**Input:** capacity = \[2,3,4,5\], rocks = \[1,2,4,4\], additionalRocks = 2
**Output:** 3
**Explanation:**
Place 1 rock in bag 0 and 1 rock in bag 1.
The number of rocks in each bag are now \[2,3,4,4\].
Bags 0, 1, and 2 have full capacity.
There are 3 bags at full capacity, so we return 3.
It can be shown that it is not possible to have more than 3 bags at full capacity.
Note that there may be other ways of placing the rocks that result in an answer of 3.

**Example 2:**

**Input:** capacity = \[10,2,2\], rocks = \[2,2,0\], additionalRocks = 100
**Output:** 3
**Explanation:**
Place 8 rocks in bag 0 and 2 rocks in bag 2.
The number of rocks in each bag are now \[10,2,2\].
Bags 0, 1, and 2 have full capacity.
There are 3 bags at full capacity, so we return 3.
It can be shown that it is not possible to have more than 3 bags at full capacity.
Note that we did not use all of the additional rocks.

**Constraints:**

*   `n == capacity.length == rocks.length`
*   `1 <= n <= 5 * 104`
*   `1 <= capacity[i] <= 109`
*   `0 <= rocks[i] <= capacity[i]`
*   `1 <= additionalRocks <= 109`
Minimum Lines to Represent a Line Chart

You are given a 2D integer array `stockPrices` where `stockPrices[i] = [dayi, pricei]` indicates the price of the stock on day `dayi` is `pricei`. A **line chart** is created from the array by plotting the points on an XY plane with the X-axis representing the day and the Y-axis representing the price and connecting adjacent points. One such example is shown below:

Return _the **minimum number of lines** needed to represent the line chart_.

**Example 1:**

**Input:** stockPrices = \[\[1,7\],\[2,6\],\[3,5\],\[4,4\],\[5,4\],\[6,3\],\[7,2\],\[8,1\]\]
**Output:** 3
**Explanation:**
The diagram above represents the input, with the X-axis representing the day and Y-axis representing the price.
The following 3 lines can be drawn to represent the line chart:
- Line 1 (in red) from (1,7) to (4,4) passing through (1,7), (2,6), (3,5), and (4,4).
- Line 2 (in blue) from (4,4) to (5,4).
- Line 3 (in green) from (5,4) to (8,1) passing through (5,4), (6,3), (7,2), and (8,1).
It can be shown that it is not possible to represent the line chart using less than 3 lines.

**Example 2:**

**Input:** stockPrices = \[\[3,4\],\[1,2\],\[7,8\],\[2,3\]\]
**Output:** 1
**Explanation:**
As shown in the diagram above, the line chart can be represented with a single line.

**Constraints:**

*   `1 <= stockPrices.length <= 105`
*   `stockPrices[i].length == 2`
*   `1 <= dayi, pricei <= 109`
*   All `dayi` are **distinct**.
Sum of Total Strength of Wizards

As the ruler of a kingdom, you have an army of wizards at your command.

You are given a **0-indexed** integer array `strength`, where `strength[i]` denotes the strength of the `ith` wizard. For a **contiguous** group of wizards (i.e. the wizards' strengths form a **subarray** of `strength`), the **total strength** is defined as the **product** of the following two values:

*   The strength of the **weakest** wizard in the group.
*   The **total** of all the individual strengths of the wizards in the group.

Return _the **sum** of the total strengths of **all** contiguous groups of wizards_. Since the answer may be very large, return it **modulo** `109 + 7`.

A **subarray** is a contiguous **non-empty** sequence of elements within an array.

**Example 1:**

**Input:** strength = \[1,3,1,2\]
**Output:** 44
**Explanation:** The following are all the contiguous groups of wizards:
- \[1\] from \[**1**,3,1,2\] has a total strength of min(\[1\]) \* sum(\[1\]) = 1 \* 1 = 1
- \[3\] from \[1,**3**,1,2\] has a total strength of min(\[3\]) \* sum(\[3\]) = 3 \* 3 = 9
- \[1\] from \[1,3,**1**,2\] has a total strength of min(\[1\]) \* sum(\[1\]) = 1 \* 1 = 1
- \[2\] from \[1,3,1,**2**\] has a total strength of min(\[2\]) \* sum(\[2\]) = 2 \* 2 = 4
- \[1,3\] from \[**1,3**,1,2\] has a total strength of min(\[1,3\]) \* sum(\[1,3\]) = 1 \* 4 = 4
- \[3,1\] from \[1,**3,1**,2\] has a total strength of min(\[3,1\]) \* sum(\[3,1\]) = 1 \* 4 = 4
- \[1,2\] from \[1,3,**1,2**\] has a total strength of min(\[1,2\]) \* sum(\[1,2\]) = 1 \* 3 = 3
- \[1,3,1\] from \[**1,3,1**,2\] has a total strength of min(\[1,3,1\]) \* sum(\[1,3,1\]) = 1 \* 5 = 5
- \[3,1,2\] from \[1,**3,1,2**\] has a total strength of min(\[3,1,2\]) \* sum(\[3,1,2\]) = 1 \* 6 = 6
- \[1,3,1,2\] from \[**1,3,1,2**\] has a total strength of min(\[1,3,1,2\]) \* sum(\[1,3,1,2\]) = 1 \* 7 = 7
The sum of all the total strengths is 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44.

**Example 2:**

**Input:** strength = \[5,4,6\]
**Output:** 213
**Explanation:** The following are all the contiguous groups of wizards: 
- \[5\] from \[**5**,4,6\] has a total strength of min(\[5\]) \* sum(\[5\]) = 5 \* 5 = 25
- \[4\] from \[5,**4**,6\] has a total strength of min(\[4\]) \* sum(\[4\]) = 4 \* 4 = 16
- \[6\] from \[5,4,**6**\] has a total strength of min(\[6\]) \* sum(\[6\]) = 6 \* 6 = 36
- \[5,4\] from \[**5,4**,6\] has a total strength of min(\[5,4\]) \* sum(\[5,4\]) = 4 \* 9 = 36
- \[4,6\] from \[5,**4,6**\] has a total strength of min(\[4,6\]) \* sum(\[4,6\]) = 4 \* 10 = 40
- \[5,4,6\] from \[**5,4,6**\] has a total strength of min(\[5,4,6\]) \* sum(\[5,4,6\]) = 4 \* 15 = 60
The sum of all the total strengths is 25 + 16 + 36 + 36 + 40 + 60 = 213.

**Constraints:**

*   `1 <= strength.length <= 105`
*   `1 <= strength[i] <= 109`
Number of People That Can Be Seen in a Grid

You are given an `m x n` **0-indexed** 2D array of positive integers `heights` where `heights[i][j]` is the height of the person standing at position `(i, j)`.

A person standing at position `(row1, col1)` can see a person standing at position `(row2, col2)` if:

*   The person at `(row2, col2)` is to the right **or** below the person at `(row1, col1)`. More formally, this means that either `row1 == row2` and `col1 < col2` **or** `row1 < row2` and `col1 == col2`.
*   Everyone in between them is shorter than **both** of them.

Return _an_ `m x n` _2D array of integers_ `answer` _where_ `answer[i][j]` _is the number of people that the person at position_ `(i, j)` _can see._

**Example 1:**

**Input:** heights = \[\[3,1,4,2,5\]\]
**Output:** \[\[2,1,2,1,0\]\]
**Explanation:**
- The person at (0, 0) can see the people at (0, 1) and (0, 2).
  Note that he cannot see the person at (0, 4) because the person at (0, 2) is taller than him.
- The person at (0, 1) can see the person at (0, 2).
- The person at (0, 2) can see the people at (0, 3) and (0, 4).
- The person at (0, 3) can see the person at (0, 4).
- The person at (0, 4) cannot see anybody.

**Example 2:**

**Input:** heights = \[\[5,1\],\[3,1\],\[4,1\]\]
**Output:** \[\[3,1\],\[2,1\],\[1,0\]\]
**Explanation:**
- The person at (0, 0) can see the people at (0, 1), (1, 0) and (2, 0).
- The person at (0, 1) can see the person at (1, 1).
- The person at (1, 0) can see the people at (1, 1) and (2, 0).
- The person at (1, 1) can see the person at (2, 1).
- The person at (2, 0) can see the person at (2, 1).
- The person at (2, 1) cannot see anybody.

**Constraints:**

*   `1 <= heights.length <= 400`
*   `1 <= heights[i].length <= 400`
*   `1 <= heights[i][j] <= 105`
Check if Number Has Equal Digit Count and Digit Value

You are given a **0-indexed** string `num` of length `n` consisting of digits.

Return `true` _if for **every** index_ `i` _in the range_ `0 <= i < n`_, the digit_ `i` _occurs_ `num[i]` _times in_ `num`_, otherwise return_ `false`.

**Example 1:**

**Input:** num =  "1210 "
**Output:** true
**Explanation:**
num\[0\] = '1'. The digit 0 occurs once in num.
num\[1\] = '2'. The digit 1 occurs twice in num.
num\[2\] = '1'. The digit 2 occurs once in num.
num\[3\] = '0'. The digit 3 occurs zero times in num.
The condition holds true for every index in  "1210 ", so return true.

**Example 2:**

**Input:** num =  "030 "
**Output:** false
**Explanation:**
num\[0\] = '0'. The digit 0 should occur zero times, but actually occurs twice in num.
num\[1\] = '3'. The digit 1 should occur three times, but actually occurs zero times in num.
num\[2\] = '0'. The digit 2 occurs zero times in num.
The indices 0 and 1 both violate the condition, so return false.

**Constraints:**

*   `n == num.length`
*   `1 <= n <= 10`
*   `num` consists of digits.
Sender With Largest Word Count

You have a chat log of `n` messages. You are given two string arrays `messages` and `senders` where `messages[i]` is a **message** sent by `senders[i]`.

A **message** is list of **words** that are separated by a single space with no leading or trailing spaces. The **word count** of a sender is the total number of **words** sent by the sender. Note that a sender may send more than one message.

Return _the sender with the **largest** word count_. If there is more than one sender with the largest word count, return _the one with the **lexicographically largest** name_.

**Note:**

*   Uppercase letters come before lowercase letters in lexicographical order.
*   `"Alice "` and `"alice "` are distinct.

**Example 1:**

**Input:** messages = \[ "Hello userTwooo ", "Hi userThree ", "Wonderful day Alice ", "Nice day userThree "\], senders = \[ "Alice ", "userTwo ", "userThree ", "Alice "\]
**Output:**  "Alice "
**Explanation:** Alice sends a total of 2 + 3 = 5 words.
userTwo sends a total of 2 words.
userThree sends a total of 3 words.
Since Alice has the largest word count, we return  "Alice ".

**Example 2:**

**Input:** messages = \[ "How is leetcode for everyone ", "Leetcode is useful for practice "\], senders = \[ "Bob ", "Charlie "\]
**Output:**  "Charlie "
**Explanation:** Bob sends a total of 5 words.
Charlie sends a total of 5 words.
Since there is a tie for the largest word count, we return the sender with the lexicographically larger name, Charlie.

**Constraints:**

*   `n == messages.length == senders.length`
*   `1 <= n <= 104`
*   `1 <= messages[i].length <= 100`
*   `1 <= senders[i].length <= 10`
*   `messages[i]` consists of uppercase and lowercase English letters and `' '`.
*   All the words in `messages[i]` are separated by **a single space**.
*   `messages[i]` does not have leading or trailing spaces.
*   `senders[i]` consists of uppercase and lowercase English letters only.
Maximum Total Importance of Roads

You are given an integer `n` denoting the number of cities in a country. The cities are numbered from `0` to `n - 1`.

You are also given a 2D integer array `roads` where `roads[i] = [ai, bi]` denotes that there exists a **bidirectional** road connecting cities `ai` and `bi`.

You need to assign each city with an integer value from `1` to `n`, where each value can only be used **once**. The **importance** of a road is then defined as the **sum** of the values of the two cities it connects.

Return _the **maximum total importance** of all roads possible after assigning the values optimally._

**Example 1:**

**Input:** n = 5, roads = \[\[0,1\],\[1,2\],\[2,3\],\[0,2\],\[1,3\],\[2,4\]\]
**Output:** 43
**Explanation:** The figure above shows the country and the assigned values of \[2,4,5,3,1\].
- The road (0,1) has an importance of 2 + 4 = 6.
- The road (1,2) has an importance of 4 + 5 = 9.
- The road (2,3) has an importance of 5 + 3 = 8.
- The road (0,2) has an importance of 2 + 5 = 7.
- The road (1,3) has an importance of 4 + 3 = 7.
- The road (2,4) has an importance of 5 + 1 = 6.
The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43.
It can be shown that we cannot obtain a greater total importance than 43.

**Example 2:**

**Input:** n = 5, roads = \[\[0,3\],\[2,4\],\[1,3\]\]
**Output:** 20
**Explanation:** The figure above shows the country and the assigned values of \[4,3,2,5,1\].
- The road (0,3) has an importance of 4 + 5 = 9.
- The road (2,4) has an importance of 2 + 1 = 3.
- The road (1,3) has an importance of 3 + 5 = 8.
The total importance of all roads is 9 + 3 + 8 = 20.
It can be shown that we cannot obtain a greater total importance than 20.

**Constraints:**

*   `2 <= n <= 5 * 104`
*   `1 <= roads.length <= 5 * 104`
*   `roads[i].length == 2`
*   `0 <= ai, bi <= n - 1`
*   `ai != bi`
*   There are no duplicate roads.
Rearrange Characters to Make Target String

You are given two **0-indexed** strings `s` and `target`. You can take some letters from `s` and rearrange them to form new strings.

Return _the **maximum** number of copies of_ `target` _that can be formed by taking letters from_ `s` _and rearranging them._

**Example 1:**

**Input:** s =  "ilovecodingonleetcode ", target =  "code "
**Output:** 2
**Explanation:**
For the first copy of  "code ", take the letters at indices 4, 5, 6, and 7.
For the second copy of  "code ", take the letters at indices 17, 18, 19, and 20.
The strings that are formed are  "ecod " and  "code " which can both be rearranged into  "code ".
We can make at most two copies of  "code ", so we return 2.

**Example 2:**

**Input:** s =  "abcba ", target =  "abc "
**Output:** 1
**Explanation:**
We can make one copy of  "abc " by taking the letters at indices 0, 1, and 2.
We can make at most one copy of  "abc ", so we return 1.
Note that while there is an extra 'a' and 'b' at indices 3 and 4, we cannot reuse the letter 'c' at index 2, so we cannot make a second copy of  "abc ".

**Example 3:**

**Input:** s =  "abbaccaddaeea ", target =  "aaaaa "
**Output:** 1
**Explanation:**
We can make one copy of  "aaaaa " by taking the letters at indices 0, 3, 6, 9, and 12.
We can make at most one copy of  "aaaaa ", so we return 1.

**Constraints:**

*   `1 <= s.length <= 100`
*   `1 <= target.length <= 10`
*   `s` and `target` consist of lowercase English letters.
Apply Discount to Prices

A **sentence** is a string of single-space separated words where each word can contain digits, lowercase letters, and the dollar sign `'$'`. A word represents a **price** if it is a sequence of digits preceded by a dollar sign.

*   For example, `"$100 "`, `"$23 "`, and `"$6 "` represent prices while `"100 "`, `"$ "`, and `"$1e5 "` do not.

You are given a string `sentence` representing a sentence and an integer `discount`. For each word representing a price, apply a discount of `discount%` on the price and **update** the word in the sentence. All updated prices should be represented with **exactly two** decimal places.

Return _a string representing the modified sentence_.

Note that all prices will contain **at most** `10` digits.

**Example 1:**

**Input:** sentence =  "there are $1 $2 and 5$ candies in the shop ", discount = 50
**Output:**  "there are $0.50 $1.00 and 5$ candies in the shop "
**Explanation:** 
The words which represent prices are  "$1 " and  "$2 ". 
- A 50% discount on  "$1 " yields  "$0.50 ", so  "$1 " is replaced by  "$0.50 ".
- A 50% discount on  "$2 " yields  "$1 ". Since we need to have exactly 2 decimal places after a price, we replace  "$2 " with  "$1.00 ".

**Example 2:**

**Input:** sentence =  "1 2 $3 4 $5 $6 7 8$ $9 $10$ ", discount = 100
**Output:**  "1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$ "
**Explanation:** 
Applying a 100% discount on any price will result in 0.
The words representing prices are  "$3 ",  "$5 ",  "$6 ", and  "$9 ".
Each of them is replaced by  "$0.00 ".

**Constraints:**

*   `1 <= sentence.length <= 105`
*   `sentence` consists of lowercase English letters, digits, `' '`, and `'$'`.
*   `sentence` does not have leading or trailing spaces.
*   All words in `sentence` are separated by a single space.
*   All prices will be **positive** numbers without leading zeros.
*   All prices will have **at most** `10` digits.
*   `0 <= discount <= 100`
Steps to Make Array Non-decreasing

You are given a **0-indexed** integer array `nums`. In one step, **remove** all elements `nums[i]` where `nums[i - 1] > nums[i]` for all `0 < i < nums.length`.

Return _the number of steps performed until_ `nums` _becomes a **non-decreasing** array_.

**Example 1:**

**Input:** nums = \[5,3,4,4,7,3,6,11,8,5,11\]
**Output:** 3
**Explanation:** The following are the steps performed:
- Step 1: \[5,**3**,4,4,7,**3**,6,11,**8**,**5**,11\] becomes \[5,4,4,7,6,11,11\]
- Step 2: \[5,**4**,4,7,**6**,11,11\] becomes \[5,4,7,11,11\]
- Step 3: \[5,**4**,7,11,11\] becomes \[5,7,11,11\]
\[5,7,11,11\] is a non-decreasing array. Therefore, we return 3.

**Example 2:**

**Input:** nums = \[4,5,7,7,13\]
**Output:** 0
**Explanation:** nums is already a non-decreasing array. Therefore, we return 0.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 109`
Minimum Obstacle Removal to Reach Corner

You are given a **0-indexed** 2D integer array `grid` of size `m x n`. Each cell has one of two values:

*   `0` represents an **empty** cell,
*   `1` represents an **obstacle** that may be removed.

You can move up, down, left, or right from and to an empty cell.

Return _the **minimum** number of **obstacles** to **remove** so you can move from the upper left corner_ `(0, 0)` _to the lower right corner_ `(m - 1, n - 1)`.

**Example 1:**

**Input:** grid = \[\[0,1,1\],\[1,1,0\],\[1,1,0\]\]
**Output:** 2
**Explanation:** We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2).
It can be shown that we need to remove at least 2 obstacles, so we return 2.
Note that there may be other ways to remove 2 obstacles to create a path.

**Example 2:**

**Input:** grid = \[\[0,1,0,0,0\],\[0,1,0,1,0\],\[0,0,0,1,0\]\]
**Output:** 0
**Explanation:** We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 105`
*   `2 <= m * n <= 105`
*   `grid[i][j]` is either `0` **or** `1`.
*   `grid[0][0] == grid[m - 1][n - 1] == 0`
Maximum Profit From Trading Stocks

You are given two **0-indexed** integer arrays of the same length `present` and `future` where `present[i]` is the current price of the `ith` stock and `future[i]` is the price of the `ith` stock a year in the future. You may buy each stock at most **once**. You are also given an integer `budget` representing the amount of money you currently have.

Return _the maximum amount of profit you can make._

**Example 1:**

**Input:** present = \[5,4,6,2,3\], future = \[8,5,4,3,5\], budget = 10
**Output:** 6
**Explanation:** One possible way to maximize your profit is to:
Buy the 0th, 3rd, and 4th stocks for a total of 5 + 2 + 3 = 10.
Next year, sell all three stocks for a total of 8 + 3 + 5 = 16.
The profit you made is 16 - 10 = 6.
It can be shown that the maximum profit you can make is 6.

**Example 2:**

**Input:** present = \[2,2,5\], future = \[3,4,10\], budget = 6
**Output:** 5
**Explanation:** The only possible way to maximize your profit is to:
Buy the 2nd stock, and make a profit of 10 - 5 = 5.
It can be shown that the maximum profit you can make is 5.

**Example 3:**

**Input:** present = \[3,3,12\], future = \[0,3,15\], budget = 10
**Output:** 0
**Explanation:** One possible way to maximize your profit is to:
Buy the 1st stock, and make a profit of 3 - 3 = 0.
It can be shown that the maximum profit you can make is 0.

**Constraints:**

*   `n == present.length == future.length`
*   `1 <= n <= 1000`
*   `0 <= present[i], future[i] <= 100`
*   `0 <= budget <= 1000`
Min Max Game

You are given a **0-indexed** integer array `nums` whose length is a power of `2`.

Apply the following algorithm on `nums`:

1.  Let `n` be the length of `nums`. If `n == 1`, **end** the process. Otherwise, **create** a new **0-indexed** integer array `newNums` of length `n / 2`.
2.  For every **even** index `i` where `0 <= i < n / 2`, **assign** the value of `newNums[i]` as `min(nums[2 * i], nums[2 * i + 1])`.
3.  For every **odd** index `i` where `0 <= i < n / 2`, **assign** the value of `newNums[i]` as `max(nums[2 * i], nums[2 * i + 1])`.
4.  **Replace** the array `nums` with `newNums`.
5.  **Repeat** the entire process starting from step 1.

Return _the last number that remains in_ `nums` _after applying the algorithm._

**Example 1:**

**Input:** nums = \[1,3,5,2,4,8,2,2\]
**Output:** 1
**Explanation:** The following arrays are the results of applying the algorithm repeatedly.
First: nums = \[1,5,4,2\]
Second: nums = \[1,4\]
Third: nums = \[1\]
1 is the last remaining number, so we return 1.

**Example 2:**

**Input:** nums = \[3\]
**Output:** 3
**Explanation:** 3 is already the last remaining number, so we return 3.

**Constraints:**

*   `1 <= nums.length <= 1024`
*   `1 <= nums[i] <= 109`
*   `nums.length` is a power of `2`.
Partition Array Such That Maximum Difference Is K

You are given an integer array `nums` and an integer `k`. You may partition `nums` into one or more **subsequences** such that each element in `nums` appears in **exactly** one of the subsequences.

Return _the **minimum** number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is **at most**_ `k`_._

A **subsequence** is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

**Example 1:**

**Input:** nums = \[3,6,1,2,5\], k = 2
**Output:** 2
**Explanation:**
We can partition nums into the two subsequences \[3,1,2\] and \[6,5\].
The difference between the maximum and minimum value in the first subsequence is 3 - 1 = 2.
The difference between the maximum and minimum value in the second subsequence is 6 - 5 = 1.
Since two subsequences were created, we return 2. It can be shown that 2 is the minimum number of subsequences needed.

**Example 2:**

**Input:** nums = \[1,2,3\], k = 1
**Output:** 2
**Explanation:**
We can partition nums into the two subsequences \[1,2\] and \[3\].
The difference between the maximum and minimum value in the first subsequence is 2 - 1 = 1.
The difference between the maximum and minimum value in the second subsequence is 3 - 3 = 0.
Since two subsequences were created, we return 2. Note that another optimal solution is to partition nums into the two subsequences \[1\] and \[2,3\].

**Example 3:**

**Input:** nums = \[2,2,4,5\], k = 0
**Output:** 3
**Explanation:**
We can partition nums into the three subsequences \[2,2\], \[4\], and \[5\].
The difference between the maximum and minimum value in the first subsequences is 2 - 2 = 0.
The difference between the maximum and minimum value in the second subsequences is 4 - 4 = 0.
The difference between the maximum and minimum value in the third subsequences is 5 - 5 = 0.
Since three subsequences were created, we return 3. It can be shown that 3 is the minimum number of subsequences needed.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `0 <= nums[i] <= 105`
*   `0 <= k <= 105`