bowang0911/leetcode huggingface dataset:
Partition Array Into Two Arrays to Minimize Sum Difference

You are given an integer array `nums` of `2 * n` integers. You need to partition `nums` into **two** arrays of length `n` to **minimize the absolute difference** of the **sums** of the arrays. To partition `nums`, put each element of `nums` into **one** of the two arrays.

Return _the **minimum** possible absolute difference_.

**Example 1:**

**Input:** nums = \[3,9,7,3\]
**Output:** 2
**Explanation:** One optimal partition is: \[3,9\] and \[7,3\].
The absolute difference between the sums of the arrays is abs((3 + 9) - (7 + 3)) = 2.

**Example 2:**

**Input:** nums = \[-36,36\]
**Output:** 72
**Explanation:** One optimal partition is: \[-36\] and \[36\].
The absolute difference between the sums of the arrays is abs((-36) - (36)) = 72.

**Example 3:**

**Input:** nums = \[2,-1,0,4,-2,-9\]
**Output:** 0
**Explanation:** One optimal partition is: \[2,4,-9\] and \[-1,0,-2\].
The absolute difference between the sums of the arrays is abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0.

**Constraints:**

*   `1 <= n <= 15`
*   `nums.length == 2 * n`
*   `-107 <= nums[i] <= 107`
Maximum Alternating Subarray Sum

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

The **alternating subarray sum** of a subarray that ranges from index `i` to `j` (**inclusive**, `0 <= i <= j < nums.length`) is `nums[i] - nums[i+1] + nums[i+2] - ... +/- nums[j]`.

Given a **0-indexed** integer array `nums`, return _the **maximum alternating subarray sum** of any subarray of_ `nums`.

**Example 1:**

**Input:** nums = \[3,-1,1,2\]
**Output:** 5
**Explanation:**
The subarray \[3,-1,1\] has the largest alternating subarray sum.
The alternating subarray sum is 3 - (-1) + 1 = 5.

**Example 2:**

**Input:** nums = \[2,2,2,2,2\]
**Output:** 2
**Explanation:**
The subarrays \[2\], \[2,2,2\], and \[2,2,2,2,2\] have the largest alternating subarray sum.
The alternating subarray sum of \[2\] is 2.
The alternating subarray sum of \[2,2,2\] is 2 - 2 + 2 = 2.
The alternating subarray sum of \[2,2,2,2,2\] is 2 - 2 + 2 - 2 + 2 = 2.

**Example 3:**

**Input:** nums = \[1\]
**Output:** 1
**Explanation:**
There is only one non-empty subarray, which is \[1\].
The alternating subarray sum is 1.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-105 <= nums[i] <= 105`
Minimum Number of Moves to Seat Everyone

There are `n` seats and `n` students in a room. You are given an array `seats` of length `n`, where `seats[i]` is the position of the `ith` seat. You are also given the array `students` of length `n`, where `students[j]` is the position of the `jth` student.

You may perform the following move any number of times:

*   Increase or decrease the position of the `ith` student by `1` (i.e., moving the `ith` student from position `x` to `x + 1` or `x - 1`)

Return _the **minimum number of moves** required to move each student to a seat_ _such that no two students are in the same seat._

Note that there may be **multiple** seats or students in the **same** position at the beginning.

**Example 1:**

**Input:** seats = \[3,1,5\], students = \[2,7,4\]
**Output:** 4
**Explanation:** The students are moved as follows:
- The first student is moved from from position 2 to position 1 using 1 move.
- The second student is moved from from position 7 to position 5 using 2 moves.
- The third student is moved from from position 4 to position 3 using 1 move.
In total, 1 + 2 + 1 = 4 moves were used.

**Example 2:**

**Input:** seats = \[4,1,5,9\], students = \[1,3,2,6\]
**Output:** 7
**Explanation:** The students are moved as follows:
- The first student is not moved.
- The second student is moved from from position 3 to position 4 using 1 move.
- The third student is moved from from position 2 to position 5 using 3 moves.
- The fourth student is moved from from position 6 to position 9 using 3 moves.
In total, 0 + 1 + 3 + 3 = 7 moves were used.

**Example 3:**

**Input:** seats = \[2,2,6,6\], students = \[1,3,2,6\]
**Output:** 4
**Explanation:** Note that there are two seats at position 2 and two seats at position 6.
The students are moved as follows:
- The first student is moved from from position 1 to position 2 using 1 move.
- The second student is moved from from position 3 to position 6 using 3 moves.
- The third student is not moved.
- The fourth student is not moved.
In total, 1 + 3 + 0 + 0 = 4 moves were used.

**Constraints:**

*   `n == seats.length == students.length`
*   `1 <= n <= 100`
*   `1 <= seats[i], students[j] <= 100`
Remove Colored Pieces if Both Neighbors are the Same Color

There are `n` pieces arranged in a line, and each piece is colored either by `'A'` or by `'B'`. You are given a string `colors` of length `n` where `colors[i]` is the color of the `ith` piece.

Alice and Bob are playing a game where they take **alternating turns** removing pieces from the line. In this game, Alice moves **first**.

*   Alice is only allowed to remove a piece colored `'A'` if **both its neighbors** are also colored `'A'`. She is **not allowed** to remove pieces that are colored `'B'`.
*   Bob is only allowed to remove a piece colored `'B'` if **both its neighbors** are also colored `'B'`. He is **not allowed** to remove pieces that are colored `'A'`.
*   Alice and Bob **cannot** remove pieces from the edge of the line.
*   If a player cannot make a move on their turn, that player **loses** and the other player **wins**.

Assuming Alice and Bob play optimally, return `true` _if Alice wins, or return_ `false` _if Bob wins_.

**Example 1:**

**Input:** colors =  "AAABABB "
**Output:** true
**Explanation:**
AAABABB -> AABABB
Alice moves first.
She removes the second 'A' from the left since that is the only 'A' whose neighbors are both 'A'.

Now it's Bob's turn.
Bob cannot make a move on his turn since there are no 'B's whose neighbors are both 'B'.
Thus, Alice wins, so return true.

**Example 2:**

**Input:** colors =  "AA "
**Output:** false
**Explanation:**
Alice has her turn first.
There are only two 'A's and both are on the edge of the line, so she cannot move on her turn.
Thus, Bob wins, so return false.

**Example 3:**

**Input:** colors =  "ABBBBBBBAAA "
**Output:** false
**Explanation:**
ABBBBBBBAAA -> ABBBBBBBAA
Alice moves first.
Her only option is to remove the second to last 'A' from the right.

ABBBBBBBAA -> ABBBBBBAA
Next is Bob's turn.
He has many options for which 'B' piece to remove. He can pick any.

On Alice's second turn, she has no more pieces that she can remove.
Thus, Bob wins, so return false.

**Constraints:**

*   `1 <= colors.length <= 105`
*   `colors` consists of only the letters `'A'` and `'B'`
Kth Smallest Product of Two Sorted Arrays

Given two **sorted 0-indexed** integer arrays `nums1` and `nums2` as well as an integer `k`, return _the_ `kth` _(**1-based**) smallest product of_ `nums1[i] * nums2[j]` _where_ `0 <= i < nums1.length` _and_ `0 <= j < nums2.length`.

**Example 1:**

**Input:** nums1 = \[2,5\], nums2 = \[3,4\], k = 2
**Output:** 8
**Explanation:** The 2 smallest products are:
- nums1\[0\] \* nums2\[0\] = 2 \* 3 = 6
- nums1\[0\] \* nums2\[1\] = 2 \* 4 = 8
The 2nd smallest product is 8.

**Example 2:**

**Input:** nums1 = \[-4,-2,0,3\], nums2 = \[2,4\], k = 6
**Output:** 0
**Explanation:** The 6 smallest products are:
- nums1\[0\] \* nums2\[1\] = (-4) \* 4 = -16
- nums1\[0\] \* nums2\[0\] = (-4) \* 2 = -8
- nums1\[1\] \* nums2\[1\] = (-2) \* 4 = -8
- nums1\[1\] \* nums2\[0\] = (-2) \* 2 = -4
- nums1\[2\] \* nums2\[0\] = 0 \* 2 = 0
- nums1\[2\] \* nums2\[1\] = 0 \* 4 = 0
The 6th smallest product is 0.

**Example 3:**

**Input:** nums1 = \[-2,-1,0,1,2\], nums2 = \[-3,-1,2,4,5\], k = 3
**Output:** -6
**Explanation:** The 3 smallest products are:
- nums1\[0\] \* nums2\[4\] = (-2) \* 5 = -10
- nums1\[0\] \* nums2\[3\] = (-2) \* 4 = -8
- nums1\[4\] \* nums2\[0\] = 2 \* (-3) = -6
The 3rd smallest product is -6.

**Constraints:**

*   `1 <= nums1.length, nums2.length <= 5 * 104`
*   `-105 <= nums1[i], nums2[j] <= 105`
*   `1 <= k <= nums1.length * nums2.length`
*   `nums1` and `nums2` are sorted.
Check if Numbers Are Ascending in a Sentence

A sentence is a list of **tokens** separated by a **single** space with no leading or trailing spaces. Every token is either a **positive number** consisting of digits `0-9` with no leading zeros, or a **word** consisting of lowercase English letters.

*   For example, `"a puppy has 2 eyes 4 legs "` is a sentence with seven tokens: `"2 "` and `"4 "` are numbers and the other tokens such as `"puppy "` are words.

Given a string `s` representing a sentence, you need to check if **all** the numbers in `s` are **strictly increasing** from left to right (i.e., other than the last number, **each** number is **strictly smaller** than the number on its **right** in `s`).

Return `true` _if so, or_ `false` _otherwise_.

**Example 1:**

**Input:** s =  "1 box has 3 blue 4 red 6 green and 12 yellow marbles "
**Output:** true
**Explanation:** The numbers in s are: 1, 3, 4, 6, 12.
They are strictly increasing from left to right: 1 < 3 < 4 < 6 < 12.

**Example 2:**

**Input:** s =  "hello world 5 x 5 "
**Output:** false
**Explanation:** The numbers in s are: **5**, **5**. They are not strictly increasing.

**Example 3:**

**Input:** s =  "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s "
**Output:** false
**Explanation:** The numbers in s are: 7, **51**, **50**, 60. They are not strictly increasing.

**Constraints:**

*   `3 <= s.length <= 200`
*   `s` consists of lowercase English letters, spaces, and digits from `0` to `9`, inclusive.
*   The number of tokens in `s` is between `2` and `100`, inclusive.
*   The tokens in `s` are separated by a single space.
*   There are at least **two** numbers in `s`.
*   Each number in `s` is a **positive** number **less** than `100`, with no leading zeros.
*   `s` contains no leading or trailing spaces.
Simple Bank System

You have been tasked with writing a program for a popular bank that will automate all its incoming transactions (transfer, deposit, and withdraw). The bank has `n` accounts numbered from `1` to `n`. The initial balance of each account is stored in a **0-indexed** integer array `balance`, with the `(i + 1)th` account having an initial balance of `balance[i]`.

Execute all the **valid** transactions. A transaction is **valid** if:

*   The given account number(s) are between `1` and `n`, and
*   The amount of money withdrawn or transferred from is **less than or equal** to the balance of the account.

Implement the `Bank` class:

*   `Bank(long[] balance)` Initializes the object with the **0-indexed** integer array `balance`.
*   `boolean transfer(int account1, int account2, long money)` Transfers `money` dollars from the account numbered `account1` to the account numbered `account2`. Return `true` if the transaction was successful, `false` otherwise.
*   `boolean deposit(int account, long money)` Deposit `money` dollars into the account numbered `account`. Return `true` if the transaction was successful, `false` otherwise.
*   `boolean withdraw(int account, long money)` Withdraw `money` dollars from the account numbered `account`. Return `true` if the transaction was successful, `false` otherwise.

**Example 1:**

**Input**
\[ "Bank ",  "withdraw ",  "transfer ",  "deposit ",  "transfer ",  "withdraw "\]
\[\[\[10, 100, 20, 50, 30\]\], \[3, 10\], \[5, 1, 20\], \[5, 20\], \[3, 4, 15\], \[10, 50\]\]
**Output**
\[null, true, true, true, false, false\]

**Explanation**
Bank bank = new Bank(\[10, 100, 20, 50, 30\]);
bank.withdraw(3, 10);    // return true, account 3 has a balance of $20, so it is valid to withdraw $10.
                         // Account 3 has $20 - $10 = $10.
bank.transfer(5, 1, 20); // return true, account 5 has a balance of $30, so it is valid to transfer $20.
                         // Account 5 has $30 - $20 = $10, and account 1 has $10 + $20 = $30.
bank.deposit(5, 20);     // return true, it is valid to deposit $20 to account 5.
                         // Account 5 has $10 + $20 = $30.
bank.transfer(3, 4, 15); // return false, the current balance of account 3 is $10,
                         // so it is invalid to transfer $15 from it.
bank.withdraw(10, 50);   // return false, it is invalid because account 10 does not exist.

**Constraints:**

*   `n == balance.length`
*   `1 <= n, account, account1, account2 <= 105`
*   `0 <= balance[i], money <= 1012`
*   At most `104` calls will be made to **each** function `transfer`, `deposit`, `withdraw`.
Count Number of Maximum Bitwise-OR Subsets

Given an integer array `nums`, find the **maximum** possible **bitwise OR** of a subset of `nums` and return _the **number of different non-empty subsets** with the maximum bitwise OR_.

An array `a` is a **subset** of an array `b` if `a` can be obtained from `b` by deleting some (possibly zero) elements of `b`. Two subsets are considered **different** if the indices of the elements chosen are different.

The bitwise OR of an array `a` is equal to `a[0] **OR** a[1] **OR** ... **OR** a[a.length - 1]` (**0-indexed**).

**Example 1:**

**Input:** nums = \[3,1\]
**Output:** 2
**Explanation:** The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:
- \[3\]
- \[3,1\]

**Example 2:**

**Input:** nums = \[2,2,2\]
**Output:** 7
**Explanation:** All non-empty subsets of \[2,2,2\] have a bitwise OR of 2. There are 23 - 1 = 7 total subsets.

**Example 3:**

**Input:** nums = \[3,2,1,5\]
**Output:** 6
**Explanation:** The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:
- \[3,5\]
- \[3,1,5\]
- \[3,2,5\]
- \[3,2,1,5\]
- \[2,5\]
- \[2,1,5\]

**Constraints:**

*   `1 <= nums.length <= 16`
*   `1 <= nums[i] <= 105`
Second Minimum Time to Reach Destination

A city is represented as a **bi-directional connected** graph with `n` vertices where each vertex is labeled from `1` to `n` (**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. The time taken to traverse any edge is `time` minutes.

Each vertex has a traffic signal which changes its color from **green** to **red** and vice versa every `change` minutes. All signals change **at the same time**. You can enter a vertex at **any time**, but can leave a vertex **only when the signal is green**. You **cannot wait** at a vertex if the signal is **green**.

The **second minimum value** is defined as the smallest value **strictly larger** than the minimum value.

*   For example the second minimum value of `[2, 3, 4]` is `3`, and the second minimum value of `[2, 2, 4]` is `4`.

Given `n`, `edges`, `time`, and `change`, return _the **second minimum time** it will take to go from vertex_ `1` _to vertex_ `n`.

**Notes:**

*   You can go through any vertex **any** number of times, **including** `1` and `n`.
*   You can assume that when the journey **starts**, all signals have just turned **green**.

**Example 1:**

       

**Input:** n = 5, edges = \[\[1,2\],\[1,3\],\[1,4\],\[3,4\],\[4,5\]\], time = 3, change = 5
**Output:** 13
**Explanation:**
The figure on the left shows the given graph.
The blue path in the figure on the right is the minimum time path.
The time taken is:
- Start at 1, time elapsed=0
- 1 -> 4: 3 minutes, time elapsed=3
- 4 -> 5: 3 minutes, time elapsed=6
Hence the minimum time needed is 6 minutes.

The red path shows the path to get the second minimum time.
- Start at 1, time elapsed=0
- 1 -> 3: 3 minutes, time elapsed=3
- 3 -> 4: 3 minutes, time elapsed=6
- Wait at 4 for 4 minutes, time elapsed=10
- 4 -> 5: 3 minutes, time elapsed=13
Hence the second minimum time is 13 minutes.      

**Example 2:**

**Input:** n = 2, edges = \[\[1,2\]\], time = 3, change = 2
**Output:** 11
**Explanation:**
The minimum time path is 1 -> 2 with time = 3 minutes.
The second minimum time path is 1 -> 2 -> 1 -> 2 with time = 11 minutes.

**Constraints:**

*   `2 <= n <= 104`
*   `n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2)`
*   `edges[i].length == 2`
*   `1 <= ui, vi <= n`
*   `ui != vi`
*   There are no duplicate edges.
*   Each vertex can be reached directly or indirectly from every other vertex.
*   `1 <= time, change <= 103`
Sort Linked List Already Sorted Using Absolute Values

Given the `head` of a singly linked list that is sorted in **non-decreasing** order using the **absolute values** of its nodes, return _the list sorted in **non-decreasing** order using the **actual values** of its nodes_.

**Example 1:**

**Input:** head = \[0,2,-5,5,10,-10\]
**Output:** \[-10,-5,0,2,5,10\]
**Explanation:**
The list sorted in non-descending order using the absolute values of the nodes is \[0,2,-5,5,10,-10\].
The list sorted in non-descending order using the actual values is \[-10,-5,0,2,5,10\].

**Example 2:**

**Input:** head = \[0,1,2\]
**Output:** \[0,1,2\]
**Explanation:**
The linked list is already sorted in non-decreasing order.

**Example 3:**

**Input:** head = \[1\]
**Output:** \[1\]
**Explanation:**
The linked list is already sorted in non-decreasing order.

**Constraints:**

*   The number of nodes in the list is the range `[1, 105]`.
*   `-5000 <= Node.val <= 5000`
*   `head` is sorted in non-decreasing order using the absolute value of its nodes.

**Follow up:**

*   Can you think of a solution with `O(n)` time complexity?
Number of Valid Words in a Sentence

A sentence consists of lowercase letters (`'a'` to `'z'`), digits (`'0'` to `'9'`), hyphens (`'-'`), punctuation marks (`'!'`, `'.'`, and `','`), and spaces (`' '`) only. Each sentence can be broken down into **one or more tokens** separated by one or more spaces `' '`.

A token is a valid word if **all three** of the following are true:

*   It only contains lowercase letters, hyphens, and/or punctuation (**no** digits).
*   There is **at most one** hyphen `'-'`. If present, it **must** be surrounded by lowercase characters ( `"a-b "` is valid, but `"-ab "` and `"ab- "` are not valid).
*   There is **at most one** punctuation mark. If present, it **must** be at the **end** of the token ( `"ab, "`, `"cd! "`, and `". "` are valid, but `"a!b "` and `"c., "` are not valid).

Examples of valid words include `"a-b. "`, `"afad "`, `"ba-c "`, `"a! "`, and `"! "`.

Given a string `sentence`, return _the **number** of valid words in_ `sentence`.

**Example 1:**

**Input:** sentence =  "cat and  dog "
**Output:** 3
**Explanation:** The valid words in the sentence are  "cat ",  "and ", and  "dog ".

**Example 2:**

**Input:** sentence =  "!this  1-s b8d! "
**Output:** 0
**Explanation:** There are no valid words in the sentence.
 "!this " is invalid because it starts with a punctuation mark.
 "1-s " and  "b8d " are invalid because they contain digits.

**Example 3:**

**Input:** sentence =  "alice and  bob are playing stone-game10 "
**Output:** 5
**Explanation:** The valid words in the sentence are  "alice ",  "and ",  "bob ",  "are ", and  "playing ".
 "stone-game10 " is invalid because it contains digits.

**Constraints:**

*   `1 <= sentence.length <= 1000`
*   `sentence` only contains lowercase English letters, digits, `' '`, `'-'`, `'!'`, `'.'`, and `','`.
*   There will be at least `1` token.
Next Greater Numerically Balanced Number

An integer `x` is **numerically balanced** if for every digit `d` in the number `x`, there are **exactly** `d` occurrences of that digit in `x`.

Given an integer `n`, return _the **smallest numerically balanced** number **strictly greater** than_ `n`_._

**Example 1:**

**Input:** n = 1
**Output:** 22
**Explanation:** 
22 is numerically balanced since:
- The digit 2 occurs 2 times. 
It is also the smallest numerically balanced number strictly greater than 1.

**Example 2:**

**Input:** n = 1000
**Output:** 1333
**Explanation:** 
1333 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times. 
It is also the smallest numerically balanced number strictly greater than 1000.
Note that 1022 cannot be the answer because 0 appeared more than 0 times.

**Example 3:**

**Input:** n = 3000
**Output:** 3133
**Explanation:** 
3133 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times.
It is also the smallest numerically balanced number strictly greater than 3000.

**Constraints:**

*   `0 <= n <= 106`
Count Nodes With the Highest Score

There is a **binary** tree rooted at `0` consisting of `n` nodes. The nodes are labeled from `0` to `n - 1`. You are given a **0-indexed** integer array `parents` representing the tree, where `parents[i]` is the parent of node `i`. Since node `0` is the root, `parents[0] == -1`.

Each node has a **score**. To find the score of a node, consider if the node and the edges connected to it were **removed**. The tree would become one or more **non-empty** subtrees. The **size** of a subtree is the number of the nodes in it. The **score** of the node is the **product of the sizes** of all those subtrees.

Return _the **number** of nodes that have the **highest score**_.

**Example 1:**

**Input:** parents = \[-1,2,0,2,0\]
**Output:** 3
**Explanation:**
- The score of node 0 is: 3 \* 1 = 3
- The score of node 1 is: 4 = 4
- The score of node 2 is: 1 \* 1 \* 2 = 2
- The score of node 3 is: 4 = 4
- The score of node 4 is: 4 = 4
The highest score is 4, and three nodes (node 1, node 3, and node 4) have the highest score.

**Example 2:**

**Input:** parents = \[-1,2,0\]
**Output:** 2
**Explanation:**
- The score of node 0 is: 2 = 2
- The score of node 1 is: 2 = 2
- The score of node 2 is: 1 \* 1 = 1
The highest score is 2, and two nodes (node 0 and node 1) have the highest score.

**Constraints:**

*   `n == parents.length`
*   `2 <= n <= 105`
*   `parents[0] == -1`
*   `0 <= parents[i] <= n - 1` for `i != 0`
*   `parents` represents a valid binary tree.