bowang0911/leetcode huggingface dataset:
Closest Dessert Cost

You would like to make dessert and are preparing to buy the ingredients. You have `n` ice cream base flavors and `m` types of toppings to choose from. You must follow these rules when making your dessert:

*   There must be **exactly one** ice cream base.
*   You can add **one or more** types of topping or have no toppings at all.
*   There are **at most two** of **each type** of topping.

You are given three inputs:

*   `baseCosts`, an integer array of length `n`, where each `baseCosts[i]` represents the price of the `ith` ice cream base flavor.
*   `toppingCosts`, an integer array of length `m`, where each `toppingCosts[i]` is the price of **one** of the `ith` topping.
*   `target`, an integer representing your target price for dessert.

You want to make a dessert with a total cost as close to `target` as possible.

Return _the closest possible cost of the dessert to_ `target`. If there are multiple, return _the **lower** one._

**Example 1:**

**Input:** baseCosts = \[1,7\], toppingCosts = \[3,4\], target = 10
**Output:** 10
**Explanation:** Consider the following combination (all 0-indexed):
- Choose base 1: cost 7
- Take 1 of topping 0: cost 1 x 3 = 3
- Take 0 of topping 1: cost 0 x 4 = 0
Total: 7 + 3 + 0 = 10.

**Example 2:**

**Input:** baseCosts = \[2,3\], toppingCosts = \[4,5,100\], target = 18
**Output:** 17
**Explanation:** Consider the following combination (all 0-indexed):
- Choose base 1: cost 3
- Take 1 of topping 0: cost 1 x 4 = 4
- Take 2 of topping 1: cost 2 x 5 = 10
- Take 0 of topping 2: cost 0 x 100 = 0
Total: 3 + 4 + 10 + 0 = 17. You cannot make a dessert with a total cost of 18.

**Example 3:**

**Input:** baseCosts = \[3,10\], toppingCosts = \[2,5\], target = 9
**Output:** 8
**Explanation:** It is possible to make desserts with cost 8 and 10. Return 8 as it is the lower cost.

**Constraints:**

*   `n == baseCosts.length`
*   `m == toppingCosts.length`
*   `1 <= n, m <= 10`
*   `1 <= baseCosts[i], toppingCosts[i] <= 104`
*   `1 <= target <= 104`
Equal Sum Arrays With Minimum Number of Operations

You are given two arrays of integers `nums1` and `nums2`, possibly of different lengths. The values in the arrays are between `1` and `6`, inclusive.

In one operation, you can change any integer's value in **any** of the arrays to **any** value between `1` and `6`, inclusive.

Return _the minimum number of operations required to make the sum of values in_ `nums1` _equal to the sum of values in_ `nums2`_._ Return `-1`​​​​​ if it is not possible to make the sum of the two arrays equal.

**Example 1:**

**Input:** nums1 = \[1,2,3,4,5,6\], nums2 = \[1,1,2,2,2,2\]
**Output:** 3
**Explanation:** You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed.
- Change nums2\[0\] to 6. nums1 = \[1,2,3,4,5,6\], nums2 = \[**6**,1,2,2,2,2\].
- Change nums1\[5\] to 1. nums1 = \[1,2,3,4,5,**1**\], nums2 = \[6,1,2,2,2,2\].
- Change nums1\[2\] to 2. nums1 = \[1,2,**2**,4,5,1\], nums2 = \[6,1,2,2,2,2\].

**Example 2:**

**Input:** nums1 = \[1,1,1,1,1,1,1\], nums2 = \[6\]
**Output:** -1
**Explanation:** There is no way to decrease the sum of nums1 or to increase the sum of nums2 to make them equal.

**Example 3:**

**Input:** nums1 = \[6,6\], nums2 = \[1\]
**Output:** 3
**Explanation:** You can make the sums of nums1 and nums2 equal with 3 operations. All indices are 0-indexed. 
- Change nums1\[0\] to 2. nums1 = \[**2**,6\], nums2 = \[1\].
- Change nums1\[1\] to 2. nums1 = \[2,**2**\], nums2 = \[1\].
- Change nums2\[0\] to 4. nums1 = \[2,2\], nums2 = \[**4**\].

**Constraints:**

*   `1 <= nums1.length, nums2.length <= 105`
*   `1 <= nums1[i], nums2[i] <= 6`
Car Fleet II

There are `n` cars traveling at different speeds in the same direction along a one-lane road. You are given an array `cars` of length `n`, where `cars[i] = [positioni, speedi]` represents:

*   `positioni` is the distance between the `ith` car and the beginning of the road in meters. It is guaranteed that `positioni < positioni+1`.
*   `speedi` is the initial speed of the `ith` car in meters per second.

For simplicity, cars can be considered as points moving along the number line. Two cars collide when they occupy the same position. Once a car collides with another car, they unite and form a single car fleet. The cars in the formed fleet will have the same position and the same speed, which is the initial speed of the **slowest** car in the fleet.

Return an array `answer`, where `answer[i]` is the time, in seconds, at which the `ith` car collides with the next car, or `-1` if the car does not collide with the next car. Answers within `10-5` of the actual answers are accepted.

**Example 1:**

**Input:** cars = \[\[1,2\],\[2,1\],\[4,3\],\[7,2\]\]
**Output:** \[1.00000,-1.00000,3.00000,-1.00000\]
**Explanation:** After exactly one second, the first car will collide with the second car, and form a car fleet with speed 1 m/s. After exactly 3 seconds, the third car will collide with the fourth car, and form a car fleet with speed 2 m/s.

**Example 2:**

**Input:** cars = \[\[3,4\],\[5,4\],\[6,3\],\[9,1\]\]
**Output:** \[2.00000,1.00000,1.50000,-1.00000\]

**Constraints:**

*   `1 <= cars.length <= 105`
*   `1 <= positioni, speedi <= 106`
*   `positioni < positioni+1`
Find Nearest Point That Has the Same X or Y Coordinate

You are given two integers, `x` and `y`, which represent your current location on a Cartesian grid: `(x, y)`. You are also given an array `points` where each `points[i] = [ai, bi]` represents that a point exists at `(ai, bi)`. A point is **valid** if it shares the same x-coordinate or the same y-coordinate as your location.

Return _the index **(0-indexed)** of the **valid** point with the smallest **Manhattan distance** from your current location_. If there are multiple, return _the valid point with the **smallest** index_. If there are no valid points, return `-1`.

The **Manhattan distance** between two points `(x1, y1)` and `(x2, y2)` is `abs(x1 - x2) + abs(y1 - y2)`.

**Example 1:**

**Input:** x = 3, y = 4, points = \[\[1,2\],\[3,1\],\[2,4\],\[2,3\],\[4,4\]\]
**Output:** 2
**Explanation:** Of all the points, only \[3,1\], \[2,4\] and \[4,4\] are valid. Of the valid points, \[2,4\] and \[4,4\] have the smallest Manhattan distance from your current location, with a distance of 1. \[2,4\] has the smallest index, so return 2.

**Example 2:**

**Input:** x = 3, y = 4, points = \[\[3,4\]\]
**Output:** 0
**Explanation:** The answer is allowed to be on the same location as your current location.

**Example 3:**

**Input:** x = 3, y = 4, points = \[\[2,3\]\]
**Output:** -1
**Explanation:** There are no valid points.

**Constraints:**

*   `1 <= points.length <= 104`
*   `points[i].length == 2`
*   `1 <= x, y, ai, bi <= 104`
Check if Number is a Sum of Powers of Three

Given an integer `n`, return `true` _if it is possible to represent_ `n` _as the sum of distinct powers of three._ Otherwise, return `false`.

An integer `y` is a power of three if there exists an integer `x` such that `y == 3x`.

**Example 1:**

**Input:** n = 12
**Output:** true
**Explanation:** 12 = 31 + 32

**Example 2:**

**Input:** n = 91
**Output:** true
**Explanation:** 91 = 30 + 32 + 34

**Example 3:**

**Input:** n = 21
**Output:** false

**Constraints:**

*   `1 <= n <= 107`
Sum of Beauty of All Substrings

The **beauty** of a string is the difference in frequencies between the most frequent and least frequent characters.

*   For example, the beauty of `"abaacc "` is `3 - 1 = 2`.

Given a string `s`, return _the sum of **beauty** of all of its substrings._

**Example 1:**

**Input:** s =  "aabcb "
**Output:** 5
**Explanation:** The substrings with non-zero beauty are \[ "aab ", "aabc ", "aabcb ", "abcb ", "bcb "\], each with beauty equal to 1.

**Example 2:**

**Input:** s =  "aabcbaa "
**Output:** 17

**Constraints:**

*   `1 <= s.length <= 500`
*   `s` consists of only lowercase English letters.
Count Pairs Of Nodes

You are given an undirected graph defined by an integer `n`, the number of nodes, and a 2D integer array `edges`, the edges in the graph, where `edges[i] = [ui, vi]` indicates that there is an **undirected** edge between `ui` and `vi`. You are also given an integer array `queries`.

Let `incident(a, b)` be defined as the **number of edges** that are connected to **either** node `a` or `b`.

The answer to the `jth` query is the **number of pairs** of nodes `(a, b)` that satisfy **both** of the following conditions:

*   `a < b`
*   `incident(a, b) > queries[j]`

Return _an array_ `answers` _such that_ `answers.length == queries.length` _and_ `answers[j]` _is the answer of the_ `jth` _query_.

Note that there can be **multiple edges** between the same two nodes.

**Example 1:**

**Input:** n = 4, edges = \[\[1,2\],\[2,4\],\[1,3\],\[2,3\],\[2,1\]\], queries = \[2,3\]
**Output:** \[6,5\]
**Explanation:** The calculations for incident(a, b) are shown in the table above.
The answers for each of the queries are as follows:
- answers\[0\] = 6. All the pairs have an incident(a, b) value greater than 2.
- answers\[1\] = 5. All the pairs except (3, 4) have an incident(a, b) value greater than 3.

**Example 2:**

**Input:** n = 5, edges = \[\[1,5\],\[1,5\],\[3,4\],\[2,5\],\[1,3\],\[5,1\],\[2,3\],\[2,5\]\], queries = \[1,2,3,4,5\]
**Output:** \[10,10,9,8,6\]

**Constraints:**

*   `2 <= n <= 2 * 104`
*   `1 <= edges.length <= 105`
*   `1 <= ui, vi <= n`
*   `ui != vi`
*   `1 <= queries.length <= 20`
*   `0 <= queries[j] < edges.length`
Check if Binary String Has at Most One Segment of Ones

Given a binary string `s` **​​​​​without leading zeros**, return `true`​​​ _if_ `s` _contains **at most one contiguous segment of ones**_. Otherwise, return `false`.

**Example 1:**

**Input:** s =  "1001 "
**Output:** false
**Explanation:** The ones do not form a contiguous segment.

**Example 2:**

**Input:** s =  "110 "
**Output:** true

**Constraints:**

*   `1 <= s.length <= 100`
*   `s[i]`​​​​ is either `'0'` or `'1'`.
*   `s[0]` is `'1'`.
Minimum Elements to Add to Form a Given Sum

You are given an integer array `nums` and two integers `limit` and `goal`. The array `nums` has an interesting property that `abs(nums[i]) <= limit`.

Return _the minimum number of elements you need to add to make the sum of the array equal to_ `goal`. The array must maintain its property that `abs(nums[i]) <= limit`.

Note that `abs(x)` equals `x` if `x >= 0`, and `-x` otherwise.

**Example 1:**

**Input:** nums = \[1,-1,1\], limit = 3, goal = -4
**Output:** 2
**Explanation:** You can add -2 and -3, then the sum of the array will be 1 - 1 + 1 - 2 - 3 = -4.

**Example 2:**

**Input:** nums = \[1,-10,9,1\], limit = 100, goal = 0
**Output:** 1

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= limit <= 106`
*   `-limit <= nums[i] <= limit`
*   `-109 <= goal <= 109`
Number of Restricted Paths From First to Last Node

There is an undirected weighted connected graph. You are given a positive integer `n` which denotes that the graph has `n` nodes labeled from `1` to `n`, and an array `edges` where each `edges[i] = [ui, vi, weighti]` denotes that there is an edge between nodes `ui` and `vi` with weight equal to `weighti`.

A path from node `start` to node `end` is a sequence of nodes `[z0, z1, z2, ..., zk]` such that `z0 = start` and `zk = end` and there is an edge between `zi` and `zi+1` where `0 <= i <= k-1`.

The distance of a path is the sum of the weights on the edges of the path. Let `distanceToLastNode(x)` denote the shortest distance of a path between node `n` and node `x`. A **restricted path** is a path that also satisfies that `distanceToLastNode(zi) > distanceToLastNode(zi+1)` where `0 <= i <= k-1`.

Return _the number of restricted paths from node_ `1` _to node_ `n`. Since that number may be too large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** n = 5, edges = \[\[1,2,3\],\[1,3,3\],\[2,3,1\],\[1,4,2\],\[5,2,2\],\[3,5,1\],\[5,4,10\]\]
**Output:** 3
**Explanation:** Each circle contains the node number in black and its `distanceToLastNode value in blue.` The three restricted paths are:
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5

**Example 2:**

**Input:** n = 7, edges = \[\[1,3,1\],\[4,1,2\],\[7,3,4\],\[2,5,3\],\[5,6,1\],\[6,7,2\],\[7,5,3\],\[2,6,4\]\]
**Output:** 1
**Explanation:** Each circle contains the node number in black and its `distanceToLastNode value in blue.` The only restricted path is 1 --> 3 --> 7.

**Constraints:**

*   `1 <= n <= 2 * 104`
*   `n - 1 <= edges.length <= 4 * 104`
*   `edges[i].length == 3`
*   `1 <= ui, vi <= n`
*   `ui != vi`
*   `1 <= weighti <= 105`
*   There is at most one edge between any two nodes.
*   There is at least one path between any two nodes.
Make the XOR of All Segments Equal to Zero

You are given an array `nums`​​​ and an integer `k`​​​​​. The XOR of a segment `[left, right]` where `left <= right` is the `XOR` of all the elements with indices between `left` and `right`, inclusive: `nums[left] XOR nums[left+1] XOR ... XOR nums[right]`.

Return _the minimum number of elements to change in the array_ such that the `XOR` of all segments of size `k`​​​​​​ is equal to zero.

**Example 1:**

**Input:** nums = \[1,2,0,3,0\], k = 1
**Output:** 3
**Explanation:** Modify the array from \[**1**,**2**,0,**3**,0\] to from \[**0**,**0**,0,**0**,0\].

**Example 2:**

**Input:** nums = \[3,4,5,2,1,7,3,4,7\], k = 3
**Output:** 3
**Explanation:** Modify the array from \[3,4,**5**,**2**,**1**,7,3,4,7\] to \[3,4,**7**,**3**,**4**,7,3,4,7\].

**Example 3:**

**Input:** nums = \[1,2,4,1,2,5,1,2,6\], k = 3
**Output:** 3
**Explanation:** Modify the array from \[1,2,**4,**1,2,**5**,1,2,**6**\] to \[1,2,**3**,1,2,**3**,1,2,**3**\].

**Constraints:**

*   `1 <= k <= nums.length <= 2000`
*   `​​​​​​0 <= nums[i] < 210`
Maximize the Beauty of the Garden

There is a garden of `n` flowers, and each flower has an integer beauty value. The flowers are arranged in a line. You are given an integer array `flowers` of size `n` and each `flowers[i]` represents the beauty of the `ith` flower.

A garden is **valid** if it meets these conditions:

*   The garden has at least two flowers.
*   The first and the last flower of the garden have the same beauty value.

As the appointed gardener, you have the ability to **remove** any (possibly none) flowers from the garden. You want to remove flowers in a way that makes the remaining garden **valid**. The beauty of the garden is the sum of the beauty of all the remaining flowers.

Return the maximum possible beauty of some **valid** garden after you have removed any (possibly none) flowers.

**Example 1:**

**Input:** flowers = \[1,2,3,1,2\]
**Output:** 8
**Explanation:** You can produce the valid garden \[2,3,1,2\] to have a total beauty of 2 + 3 + 1 + 2 = 8.

**Example 2:**

**Input:** flowers = \[100,1,1,-3,1\]
**Output:** 3
**Explanation:** You can produce the valid garden \[1,1,1\] to have a total beauty of 1 + 1 + 1 = 3.

**Example 3:**

**Input:** flowers = \[-1,-2,0,-1\]
**Output:** -2
**Explanation:** You can produce the valid garden \[-1,-1\] to have a total beauty of -1 + -1 = -2.

**Constraints:**

*   `2 <= flowers.length <= 105`
*   `-104 <= flowers[i] <= 104`
*   It is possible to create a valid garden by removing some (possibly none) flowers.
Check if One String Swap Can Make Strings Equal

You are given two strings `s1` and `s2` of equal length. A **string swap** is an operation where you choose two indices in a string (not necessarily different) and swap the characters at these indices.

Return `true` _if it is possible to make both strings equal by performing **at most one string swap** on **exactly one** of the strings._ Otherwise, return `false`.

**Example 1:**

**Input:** s1 =  "bank ", s2 =  "kanb "
**Output:** true
**Explanation:** For example, swap the first character with the last character of s2 to make  "bank ".

**Example 2:**

**Input:** s1 =  "attack ", s2 =  "defend "
**Output:** false
**Explanation:** It is impossible to make them equal with one string swap.

**Example 3:**

**Input:** s1 =  "kelb ", s2 =  "kelb "
**Output:** true
**Explanation:** The two strings are already equal, so no string swap operation is required.

**Constraints:**

*   `1 <= s1.length, s2.length <= 100`
*   `s1.length == s2.length`
*   `s1` and `s2` consist of only lowercase English letters.
Find Center of Star Graph

There is an undirected **star** graph consisting of `n` nodes labeled from `1` to `n`. A star graph is a graph where there is one **center** node and **exactly** `n - 1` edges that connect the center node with every other node.

You are given a 2D integer array `edges` where each `edges[i] = [ui, vi]` indicates that there is an edge between the nodes `ui` and `vi`. Return the center of the given star graph.

**Example 1:**

**Input:** edges = \[\[1,2\],\[2,3\],\[4,2\]\]
**Output:** 2
**Explanation:** As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

**Example 2:**

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

**Constraints:**

*   `3 <= n <= 105`
*   `edges.length == n - 1`
*   `edges[i].length == 2`
*   `1 <= ui, vi <= n`
*   `ui != vi`
*   The given `edges` represent a valid star graph.
Maximum Average Pass Ratio

There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array `classes`, where `classes[i] = [passi, totali]`. You know beforehand that in the `ith` class, there are `totali` total students, but only `passi` number of students will pass the exam.

You are also given an integer `extraStudents`. There are another `extraStudents` brilliant students that are **guaranteed** to pass the exam of any class they are assigned to. You want to assign each of the `extraStudents` students to a class in a way that **maximizes** the **average** pass ratio across **all** the classes.

The **pass ratio** of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The **average pass ratio** is the sum of pass ratios of all the classes divided by the number of the classes.

Return _the **maximum** possible average pass ratio after assigning the_ `extraStudents` _students._ Answers within `10-5` of the actual answer will be accepted.

**Example 1:**

**Input:** classes = \[\[1,2\],\[3,5\],\[2,2\]\], `extraStudents` = 2
**Output:** 0.78333
**Explanation:** You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.

**Example 2:**

**Input:** classes = \[\[2,4\],\[3,9\],\[4,5\],\[2,10\]\], `extraStudents` = 4
**Output:** 0.53485

**Constraints:**

*   `1 <= classes.length <= 105`
*   `classes[i].length == 2`
*   `1 <= passi <= totali <= 105`
*   `1 <= extraStudents <= 105`
Maximum Score of a Good Subarray

You are given an array of integers `nums` **(0-indexed)** and an integer `k`.

The **score** of a subarray `(i, j)` is defined as `min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)`. A **good** subarray is a subarray where `i <= k <= j`.

Return _the maximum possible **score** of a **good** subarray._

**Example 1:**

**Input:** nums = \[1,4,3,7,4,5\], k = 3
**Output:** 15
**Explanation:** The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) \* (5-1+1) = 3 \* 5 = 15. 

**Example 2:**

**Input:** nums = \[5,5,4,5,4,1,1,1\], k = 0
**Output:** 20
**Explanation:** The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) \* (4-0+1) = 4 \* 5 = 20.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 2 * 104`
*   `0 <= k < nums.length`
Count Pairs of Equal Substrings With Minimum Difference

You are given two strings `firstString` and `secondString` that are **0-indexed** and consist only of lowercase English letters. Count the number of index quadruples `(i,j,a,b)` that satisfy the following conditions:

*   `0 <= i <= j < firstString.length`
*   `0 <= a <= b < secondString.length`
*   The substring of `firstString` that starts at the `ith` character and ends at the `jth` character (inclusive) is **equal** to the substring of `secondString` that starts at the `ath` character and ends at the `bth` character (inclusive).
*   `j - a` is the **minimum** possible value among all quadruples that satisfy the previous conditions.

Return _the **number** of such quadruples_.

**Example 1:**

**Input:** firstString =  "abcd ", secondString =  "bccda "
**Output:** 1
**Explanation:** The quadruple (0,0,4,4) is the only one that satisfies all the conditions and minimizes j - a.

**Example 2:**

**Input:** firstString =  "ab ", secondString =  "cd "
**Output:** 0
**Explanation:** There are no quadruples satisfying all the conditions.

**Constraints:**

*   `1 <= firstString.length, secondString.length <= 2 * 105`
*   Both strings consist only of lowercase English letters.
Second Largest Digit in a String

Given an alphanumeric string `s`, return _the **second largest** numerical digit that appears in_ `s`_, or_ `-1` _if it does not exist_.

An **alphanumeric** string is a string consisting of lowercase English letters and digits.

**Example 1:**

**Input:** s =  "dfa12321afd "
**Output:** 2
**Explanation:** The digits that appear in s are \[1, 2, 3\]. The second largest digit is 2.

**Example 2:**

**Input:** s =  "abc1111 "
**Output:** -1
**Explanation:** The digits that appear in s are \[1\]. There is no second largest digit. 

**Constraints:**

*   `1 <= s.length <= 500`
*   `s` consists of only lowercase English letters and/or digits.