bowang0911/leetcode huggingface dataset:
Check if There is a Valid Partition For The Array

You are given a **0-indexed** integer array `nums`. You have to partition the array into one or more **contiguous** subarrays.

We call a partition of the array **valid** if each of the obtained subarrays satisfies **one** of the following conditions:

1.  The subarray consists of **exactly** `2` equal elements. For example, the subarray `[2,2]` is good.
2.  The subarray consists of **exactly** `3` equal elements. For example, the subarray `[4,4,4]` is good.
3.  The subarray consists of **exactly** `3` consecutive increasing elements, that is, the difference between adjacent elements is `1`. For example, the subarray `[3,4,5]` is good, but the subarray `[1,3,5]` is not.

Return `true` _if the array has **at least** one valid partition_. Otherwise, return `false`.

**Example 1:**

**Input:** nums = \[4,4,4,5,6\]
**Output:** true
**Explanation:** The array can be partitioned into the subarrays \[4,4\] and \[4,5,6\].
This partition is valid, so we return true.

**Example 2:**

**Input:** nums = \[1,1,1,2\]
**Output:** false
**Explanation:** There is no valid partition for this array.

**Constraints:**

*   `2 <= nums.length <= 105`
*   `1 <= nums[i] <= 106`
Longest Ideal Subsequence

You are given a string `s` consisting of lowercase letters and an integer `k`. We call a string `t` **ideal** if the following conditions are satisfied:

*   `t` is a **subsequence** of the string `s`.
*   The absolute difference in the alphabet order of every two **adjacent** letters in `t` is less than or equal to `k`.

Return _the length of the **longest** ideal string_.

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

**Note** that the alphabet order is not cyclic. For example, the absolute difference in the alphabet order of `'a'` and `'z'` is `25`, not `1`.

**Example 1:**

**Input:** s =  "acfgbd ", k = 2
**Output:** 4
**Explanation:** The longest ideal string is  "acbd ". The length of this string is 4, so 4 is returned.
Note that  "acfgbd " is not ideal because 'c' and 'f' have a difference of 3 in alphabet order.

**Example 2:**

**Input:** s =  "abcd ", k = 3
**Output:** 4
**Explanation:** The longest ideal string is  "abcd ". The length of this string is 4, so 4 is returned.

**Constraints:**

*   `1 <= s.length <= 105`
*   `0 <= k <= 25`
*   `s` consists of lowercase English letters.
Minimize Maximum Value in a Grid

You are given an `m x n` integer matrix `grid` containing **distinct** positive integers.

You have to replace each integer in the matrix with a positive integer satisfying the following conditions:

*   The **relative** order of every two elements that are in the same row or column should stay the **same** after the replacements.
*   The **maximum** number in the matrix after the replacements should be as **small** as possible.

The relative order stays the same if for all pairs of elements in the original matrix such that `grid[r1][c1] > grid[r2][c2]` where either `r1 == r2` or `c1 == c2`, then it must be true that `grid[r1][c1] > grid[r2][c2]` after the replacements.

For example, if `grid = [[2, 4, 5], [7, 3, 9]]` then a good replacement could be either `grid = [[1, 2, 3], [2, 1, 4]]` or `grid = [[1, 2, 3], [3, 1, 4]]`.

Return _the **resulting** matrix._ If there are multiple answers, return **any** of them.

**Example 1:**

**Input:** grid = \[\[3,1\],\[2,5\]\]
**Output:** \[\[2,1\],\[1,2\]\]
**Explanation:** The above diagram shows a valid replacement.
The maximum number in the matrix is 2. It can be shown that no smaller value can be obtained.

**Example 2:**

**Input:** grid = \[\[10\]\]
**Output:** \[\[1\]\]
**Explanation:** We replace the only number in the matrix with 1.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 1000`
*   `1 <= m * n <= 105`
*   `1 <= grid[i][j] <= 109`
*   `grid` consists of distinct integers.
Largest Local Values in a Matrix

You are given an `n x n` integer matrix `grid`.

Generate an integer matrix `maxLocal` of size `(n - 2) x (n - 2)` such that:

*   `maxLocal[i][j]` is equal to the **largest** value of the `3 x 3` matrix in `grid` centered around row `i + 1` and column `j + 1`.

In other words, we want to find the largest value in every contiguous `3 x 3` matrix in `grid`.

Return _the generated matrix_.

**Example 1:**

**Input:** grid = \[\[9,9,8,1\],\[5,6,2,6\],\[8,2,6,4\],\[6,2,2,2\]\]
**Output:** \[\[9,9\],\[8,6\]\]
**Explanation:** The diagram above shows the original matrix and the generated matrix.
Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in grid.

**Example 2:**

**Input:** grid = \[\[1,1,1,1,1\],\[1,1,1,1,1\],\[1,1,2,1,1\],\[1,1,1,1,1\],\[1,1,1,1,1\]\]
**Output:** \[\[2,2,2\],\[2,2,2\],\[2,2,2\]\]
**Explanation:** Notice that the 2 is contained within every contiguous 3 x 3 matrix in grid.

**Constraints:**

*   `n == grid.length == grid[i].length`
*   `3 <= n <= 100`
*   `1 <= grid[i][j] <= 100`
Node With Highest Edge Score

You are given a directed graph with `n` nodes labeled from `0` to `n - 1`, where each node has **exactly one** outgoing edge.

The graph is represented by a given **0-indexed** integer array `edges` of length `n`, where `edges[i]` indicates that there is a **directed** edge from node `i` to node `edges[i]`.

The **edge score** of a node `i` is defined as the sum of the **labels** of all the nodes that have an edge pointing to `i`.

Return _the node with the highest **edge score**_. If multiple nodes have the same **edge score**, return the node with the **smallest** index.

**Example 1:**

**Input:** edges = \[1,0,0,0,0,7,7,5\]
**Output:** 7
**Explanation:**
- The nodes 1, 2, 3 and 4 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 + 3 + 4 = 10.
- The node 0 has an edge pointing to node 1. The edge score of node 1 is 0.
- The node 7 has an edge pointing to node 5. The edge score of node 5 is 7.
- The nodes 5 and 6 have an edge pointing to node 7. The edge score of node 7 is 5 + 6 = 11.
Node 7 has the highest edge score so return 7.

**Example 2:**

**Input:** edges = \[2,0,0,2\]
**Output:** 0
**Explanation:**
- The nodes 1 and 2 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 = 3.
- The nodes 0 and 3 have an edge pointing to node 2. The edge score of node 2 is 0 + 3 = 3.
Nodes 0 and 2 both have an edge score of 3. Since node 0 has a smaller index, we return 0.

**Constraints:**

*   `n == edges.length`
*   `2 <= n <= 105`
*   `0 <= edges[i] < n`
*   `edges[i] != i`
Construct Smallest Number From DI String

You are given a **0-indexed** string `pattern` of length `n` consisting of the characters `'I'` meaning **increasing** and `'D'` meaning **decreasing**.

A **0-indexed** string `num` of length `n + 1` is created using the following conditions:

*   `num` consists of the digits `'1'` to `'9'`, where each digit is used **at most** once.
*   If `pattern[i] == 'I'`, then `num[i] < num[i + 1]`.
*   If `pattern[i] == 'D'`, then `num[i] > num[i + 1]`.

Return _the lexicographically **smallest** possible string_ `num` _that meets the conditions._

**Example 1:**

**Input:** pattern =  "IIIDIDDD "
**Output:**  "123549876 "
**Explanation:**
At indices 0, 1, 2, and 4 we must have that num\[i\] < num\[i+1\].
At indices 3, 5, 6, and 7 we must have that num\[i\] > num\[i+1\].
Some possible values of num are  "245639871 ",  "135749862 ", and  "123849765 ".
It can be proven that  "123549876 " is the smallest possible num that meets the conditions.
Note that  "123414321 " is not possible because the digit '1' is used more than once.

**Example 2:**

**Input:** pattern =  "DDD "
**Output:**  "4321 "
**Explanation:**
Some possible values of num are  "9876 ",  "7321 ", and  "8742 ".
It can be proven that  "4321 " is the smallest possible num that meets the conditions.

**Constraints:**

*   `1 <= pattern.length <= 8`
*   `pattern` consists of only the letters `'I'` and `'D'`.
Count Special Integers

We call a positive integer **special** if all of its digits are **distinct**.

Given a **positive** integer `n`, return _the number of special integers that belong to the interval_ `[1, n]`.

**Example 1:**

**Input:** n = 20
**Output:** 19
**Explanation:** All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.

**Example 2:**

**Input:** n = 5
**Output:** 5
**Explanation:** All the integers from 1 to 5 are special.

**Example 3:**

**Input:** n = 135
**Output:** 110
**Explanation:** There are 110 integers from 1 to 135 that are special.
Some of the integers that are not special are: 22, 114, and 131.

**Constraints:**

*   `1 <= n <= 2 * 109`
Choose Edges to Maximize Score in a Tree

You are given a **weighted** tree consisting of `n` nodes numbered from `0` to `n - 1`.

The tree is **rooted** at node `0` and represented with a **2D** array `edges` of size `n` where `edges[i] = [pari, weighti]` indicates that node `pari` is the **parent** of node `i`, and the edge between them has a weight equal to `weighti`. Since the root does **not** have a parent, you have `edges[0] = [-1, -1]`.

Choose some edges from the tree such that no two chosen edges are **adjacent** and the **sum** of the weights of the chosen edges is maximized.

Return _the **maximum** sum of the chosen edges_.

**Note**:

*   You are allowed to **not** choose any edges in the tree, the sum of weights in this case will be `0`.
*   Two edges `Edge1` and `Edge2` in the tree are **adjacent** if they have a **common** node.
    *   In other words, they are adjacent if `Edge1` connects nodes `a` and `b` and `Edge2` connects nodes `b` and `c`.

**Example 1:**

**Input:** edges = \[\[-1,-1\],\[0,5\],\[0,10\],\[2,6\],\[2,4\]\]
**Output:** 11
**Explanation:** The above diagram shows the edges that we have to choose colored in red.
The total score is 5 + 6 = 11.
It can be shown that no better score can be obtained.

**Example 2:**

**Input:** edges = \[\[-1,-1\],\[0,5\],\[0,-6\],\[0,7\]\]
**Output:** 7
**Explanation:** We choose the edge with weight 7.
Note that we cannot choose more than one edge because all edges are adjacent to each other.

**Constraints:**

*   `n == edges.length`
*   `1 <= n <= 105`
*   `edges[i].length == 2`
*   `par0 == weight0 == -1`
*   `0 <= pari <= n - 1` for all `i >= 1`.
*   `pari != i`
*   `-106 <= weighti <= 106` for all `i >= 1`.
*   `edges` represents a valid tree.
Minimum Recolors to Get K Consecutive Black Blocks

You are given a **0-indexed** string `blocks` of length `n`, where `blocks[i]` is either `'W'` or `'B'`, representing the color of the `ith` block. The characters `'W'` and `'B'` denote the colors white and black, respectively.

You are also given an integer `k`, which is the desired number of **consecutive** black blocks.

In one operation, you can **recolor** a white block such that it becomes a black block.

Return _the **minimum** number of operations needed such that there is at least **one** occurrence of_ `k` _consecutive black blocks._

**Example 1:**

**Input:** blocks =  "WBBWWBBWBW ", k = 7
**Output:** 3
**Explanation:**
One way to achieve 7 consecutive black blocks is to recolor the 0th, 3rd, and 4th blocks
so that blocks =  "BBBBBBBWBW ". 
It can be shown that there is no way to achieve 7 consecutive black blocks in less than 3 operations.
Therefore, we return 3.

**Example 2:**

**Input:** blocks =  "WBWBBBW ", k = 2
**Output:** 0
**Explanation:**
No changes need to be made, since 2 consecutive black blocks already exist.
Therefore, we return 0.

**Constraints:**

*   `n == blocks.length`
*   `1 <= n <= 100`
*   `blocks[i]` is either `'W'` or `'B'`.
*   `1 <= k <= n`
Time Needed to Rearrange a Binary String

You are given a binary string `s`. In one second, **all** occurrences of `"01 "` are **simultaneously** replaced with `"10 "`. This process **repeats** until no occurrences of `"01 "` exist.

Return _the number of seconds needed to complete this process._

**Example 1:**

**Input:** s =  "0110101 "
**Output:** 4
**Explanation:** 
After one second, s becomes  "1011010 ".
After another second, s becomes  "1101100 ".
After the third second, s becomes  "1110100 ".
After the fourth second, s becomes  "1111000 ".
No occurrence of  "01 " exists any longer, and the process needed 4 seconds to complete,
so we return 4.

**Example 2:**

**Input:** s =  "11100 "
**Output:** 0
**Explanation:**
No occurrence of  "01 " exists in s, and the processes needed 0 seconds to complete,
so we return 0.

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s[i]` is either `'0'` or `'1'`.

**Follow up:**

Can you solve this problem in O(n) time complexity?
Shifting Letters II

You are given a string `s` of lowercase English letters and a 2D integer array `shifts` where `shifts[i] = [starti, endi, directioni]`. For every `i`, **shift** the characters in `s` from the index `starti` to the index `endi` (**inclusive**) forward if `directioni = 1`, or shift the characters backward if `directioni = 0`.

Shifting a character **forward** means replacing it with the **next** letter in the alphabet (wrapping around so that `'z'` becomes `'a'`). Similarly, shifting a character **backward** means replacing it with the **previous** letter in the alphabet (wrapping around so that `'a'` becomes `'z'`).

Return _the final string after all such shifts to_ `s` _are applied_.

**Example 1:**

**Input:** s =  "abc ", shifts = \[\[0,1,0\],\[1,2,1\],\[0,2,1\]\]
**Output:**  "ace "
**Explanation:** Firstly, shift the characters from index 0 to index 1 backward. Now s =  "zac ".
Secondly, shift the characters from index 1 to index 2 forward. Now s =  "zbd ".
Finally, shift the characters from index 0 to index 2 forward. Now s =  "ace ".

**Example 2:**

**Input:** s =  "dztz ", shifts = \[\[0,0,0\],\[1,1,1\]\]
**Output:**  "catz "
**Explanation:** Firstly, shift the characters from index 0 to index 0 backward. Now s =  "cztz ".
Finally, shift the characters from index 1 to index 1 forward. Now s =  "catz ".

**Constraints:**

*   `1 <= s.length, shifts.length <= 5 * 104`
*   `shifts[i].length == 3`
*   `0 <= starti <= endi < s.length`
*   `0 <= directioni <= 1`
*   `s` consists of lowercase English letters.
Maximum Segment Sum After Removals

You are given two **0-indexed** integer arrays `nums` and `removeQueries`, both of length `n`. For the `ith` query, the element in `nums` at the index `removeQueries[i]` is removed, splitting `nums` into different segments.

A **segment** is a contiguous sequence of **positive** integers in `nums`. A **segment sum** is the sum of every element in a segment.

Return _an integer array_ `answer`_, of length_ `n`_, where_ `answer[i]` _is the **maximum** segment sum after applying the_ `ith` _removal._

**Note:** The same index will **not** be removed more than once.

**Example 1:**

**Input:** nums = \[1,2,5,6,1\], removeQueries = \[0,3,2,4,1\]
**Output:** \[14,7,2,2,0\]
**Explanation:** Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 0th element, nums becomes \[0,2,5,6,1\] and the maximum segment sum is 14 for segment \[2,5,6,1\].
Query 2: Remove the 3rd element, nums becomes \[0,2,5,0,1\] and the maximum segment sum is 7 for segment \[2,5\].
Query 3: Remove the 2nd element, nums becomes \[0,2,0,0,1\] and the maximum segment sum is 2 for segment \[2\]. 
Query 4: Remove the 4th element, nums becomes \[0,2,0,0,0\] and the maximum segment sum is 2 for segment \[2\]. 
Query 5: Remove the 1st element, nums becomes \[0,0,0,0,0\] and the maximum segment sum is 0, since there are no segments.
Finally, we return \[14,7,2,2,0\].

**Example 2:**

**Input:** nums = \[3,2,11,1\], removeQueries = \[3,2,1,0\]
**Output:** \[16,5,3,0\]
**Explanation:** Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 3rd element, nums becomes \[3,2,11,0\] and the maximum segment sum is 16 for segment \[3,2,11\].
Query 2: Remove the 2nd element, nums becomes \[3,2,0,0\] and the maximum segment sum is 5 for segment \[3,2\].
Query 3: Remove the 1st element, nums becomes \[3,0,0,0\] and the maximum segment sum is 3 for segment \[3\].
Query 4: Remove the 0th element, nums becomes \[0,0,0,0\] and the maximum segment sum is 0, since there are no segments.
Finally, we return \[16,5,3,0\].

**Constraints:**

*   `n == nums.length == removeQueries.length`
*   `1 <= n <= 105`
*   `1 <= nums[i] <= 109`
*   `0 <= removeQueries[i] < n`
*   All the values of `removeQueries` are **unique**.
Minimum Hours of Training to Win a Competition

You are entering a competition, and are given two **positive** integers `initialEnergy` and `initialExperience` denoting your initial energy and initial experience respectively.

You are also given two **0-indexed** integer arrays `energy` and `experience`, both of length `n`.

You will face `n` opponents **in order**. The energy and experience of the `ith` opponent is denoted by `energy[i]` and `experience[i]` respectively. When you face an opponent, you need to have both **strictly** greater experience and energy to defeat them and move to the next opponent if available.

Defeating the `ith` opponent **increases** your experience by `experience[i]`, but **decreases** your energy by `energy[i]`.

Before starting the competition, you can train for some number of hours. After each hour of training, you can **either** choose to increase your initial experience by one, or increase your initial energy by one.

Return _the **minimum** number of training hours required to defeat all_ `n` _opponents_.

**Example 1:**

**Input:** initialEnergy = 5, initialExperience = 3, energy = \[1,4,3,2\], experience = \[2,6,3,1\]
**Output:** 8
**Explanation:** You can increase your energy to 11 after 6 hours of training, and your experience to 5 after 2 hours of training.
You face the opponents in the following order:
- You have more energy and experience than the 0th opponent so you win.
  Your energy becomes 11 - 1 = 10, and your experience becomes 5 + 2 = 7.
- You have more energy and experience than the 1st opponent so you win.
  Your energy becomes 10 - 4 = 6, and your experience becomes 7 + 6 = 13.
- You have more energy and experience than the 2nd opponent so you win.
  Your energy becomes 6 - 3 = 3, and your experience becomes 13 + 3 = 16.
- You have more energy and experience than the 3rd opponent so you win.
  Your energy becomes 3 - 2 = 1, and your experience becomes 16 + 1 = 17.
You did a total of 6 + 2 = 8 hours of training before the competition, so we return 8.
It can be proven that no smaller answer exists.

**Example 2:**

**Input:** initialEnergy = 2, initialExperience = 4, energy = \[1\], experience = \[3\]
**Output:** 0
**Explanation:** You do not need any additional energy or experience to win the competition, so we return 0.

**Constraints:**

*   `n == energy.length == experience.length`
*   `1 <= n <= 100`
*   `1 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100`
Largest Palindromic Number

You are given a string `num` consisting of digits only.

Return _the **largest palindromic** integer (in the form of a string) that can be formed using digits taken from_ `num`. It should not contain **leading zeroes**.

**Notes:**

*   You do **not** need to use all the digits of `num`, but you must use **at least** one digit.
*   The digits can be reordered.

**Example 1:**

**Input:** num =  "444947137 "
**Output:**  "7449447 "
**Explanation:** 
Use the digits  "4449477 " from  "**44494****7**13**7** " to form the palindromic integer  "7449447 ".
It can be shown that  "7449447 " is the largest palindromic integer that can be formed.

**Example 2:**

**Input:** num =  "00009 "
**Output:**  "9 "
**Explanation:** 
It can be shown that  "9 " is the largest palindromic integer that can be formed.
Note that the integer returned should not contain leading zeroes.

**Constraints:**

*   `1 <= num.length <= 105`
*   `num` consists of digits.
Amount of Time for Binary Tree to Be Infected

You are given the `root` of a binary tree with **unique** values, and an integer `start`. At minute `0`, an **infection** starts from the node with value `start`.

Each minute, a node becomes infected if:

*   The node is currently uninfected.
*   The node is adjacent to an infected node.

Return _the number of minutes needed for the entire tree to be infected._

**Example 1:**

**Input:** root = \[1,5,3,null,4,10,6,9,2\], start = 3
**Output:** 4
**Explanation:** The following nodes are infected during:
- Minute 0: Node 3
- Minute 1: Nodes 1, 10 and 6
- Minute 2: Node 5
- Minute 3: Node 4
- Minute 4: Nodes 9 and 2
It takes 4 minutes for the whole tree to be infected so we return 4.

**Example 2:**

**Input:** root = \[1\], start = 1
**Output:** 0
**Explanation:** At minute 0, the only node in the tree is infected so we return 0.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 105]`.
*   `1 <= Node.val <= 105`
*   Each node has a **unique** value.
*   A node with a value of `start` exists in the tree.
Find the K-Sum of an Array

You are given an integer array `nums` and a **positive** integer `k`. You can choose any **subsequence** of the array and sum all of its elements together.

We define the **K-Sum** of the array as the `kth` **largest** subsequence sum that can be obtained (**not** necessarily distinct).

Return _the K-Sum of the array_.

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

**Note** that the empty subsequence is considered to have a sum of `0`.

**Example 1:**

**Input:** nums = \[2,4,-2\], k = 5
**Output:** 2
**Explanation:** All the possible subsequence sums that we can obtain are the following sorted in decreasing order:
- 6, 4, 4, 2, 2, 0, 0, -2.
The 5-Sum of the array is 2.

**Example 2:**

**Input:** nums = \[1,-2,3,4,-10,12\], k = 16
**Output:** 10
**Explanation:** The 16-Sum of the array is 10.

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 105`
*   `-109 <= nums[i] <= 109`
*   `1 <= k <= min(2000, 2n)`
Median of a Row Wise Sorted Matrix

Given an `m x n` matrix `grid` containing an **odd** number of integers where each row is sorted in **non-decreasing** order, return _the **median** of the matrix_.

You must solve the problem in less than `O(m * n)` time complexity.

**Example 1:**

**Input:** grid = \[\[1,1,2\],\[2,3,3\],\[1,3,4\]\]
**Output:** 2
**Explanation:** The elements of the matrix in sorted order are 1,1,1,2,2,3,3,3,4. The median is 2.

**Example 2:**

**Input:** grid = \[\[1,1,3,3,4\]\]
**Output:** 3
**Explanation:** The elements of the matrix in sorted order are 1,1,3,3,4. The median is 3.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 500`
*   `m` and `n` are both odd.
*   `1 <= grid[i][j] <= 106`
*   `grid[i]` is sorted in non-decreasing order.