bowang0911/leetcode huggingface dataset:
Two Furthest Houses With Different Colors

There are `n` houses evenly lined up on the street, and each house is beautifully painted. You are given a **0-indexed** integer array `colors` of length `n`, where `colors[i]` represents the color of the `ith` house.

Return _the **maximum** distance between **two** houses with **different** colors_.

The distance between the `ith` and `jth` houses is `abs(i - j)`, where `abs(x)` is the **absolute value** of `x`.

**Example 1:**

**Input:** colors = \[**1**,1,1,**6**,1,1,1\]
**Output:** 3
**Explanation:** In the above image, color 1 is blue, and color 6 is red.
The furthest two houses with different colors are house 0 and house 3.
House 0 has color 1, and house 3 has color 6. The distance between them is abs(0 - 3) = 3.
Note that houses 3 and 6 can also produce the optimal answer.

**Example 2:**

**Input:** colors = \[**1**,8,3,8,**3**\]
**Output:** 4
**Explanation:** In the above image, color 1 is blue, color 8 is yellow, and color 3 is green.
The furthest two houses with different colors are house 0 and house 4.
House 0 has color 1, and house 4 has color 3. The distance between them is abs(0 - 4) = 4.

**Example 3:**

**Input:** colors = \[**0**,**1**\]
**Output:** 1
**Explanation:** The furthest two houses with different colors are house 0 and house 1.
House 0 has color 0, and house 1 has color 1. The distance between them is abs(0 - 1) = 1.

**Constraints:**

*   `n == colors.length`
*   `2 <= n <= 100`
*   `0 <= colors[i] <= 100`
*   Test data are generated such that **at least** two houses have different colors.
Watering Plants

You want to water `n` plants in your garden with a watering can. The plants are arranged in a row and are labeled from `0` to `n - 1` from left to right where the `ith` plant is located at `x = i`. There is a river at `x = -1` that you can refill your watering can at.

Each plant needs a specific amount of water. You will water the plants in the following way:

*   Water the plants in order from left to right.
*   After watering the current plant, if you do not have enough water to **completely** water the next plant, return to the river to fully refill the watering can.
*   You **cannot** refill the watering can early.

You are initially at the river (i.e., `x = -1`). It takes **one step** to move **one unit** on the x-axis.

Given a **0-indexed** integer array `plants` of `n` integers, where `plants[i]` is the amount of water the `ith` plant needs, and an integer `capacity` representing the watering can capacity, return _the **number of steps** needed to water all the plants_.

**Example 1:**

**Input:** plants = \[2,2,3,3\], capacity = 5
**Output:** 14
**Explanation:** Start at the river with a full watering can:
- Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.
- Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.
- Since you cannot completely water plant 2, walk back to the river to refill (2 steps).
- Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.
- Since you cannot completely water plant 3, walk back to the river to refill (3 steps).
- Walk to plant 3 (4 steps) and water it.
Steps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14.

**Example 2:**

**Input:** plants = \[1,1,1,4,2,3\], capacity = 4
**Output:** 30
**Explanation:** Start at the river with a full watering can:
- Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).
- Water plant 3 (4 steps). Return to river (4 steps).
- Water plant 4 (5 steps). Return to river (5 steps).
- Water plant 5 (6 steps).
Steps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30.

**Example 3:**

**Input:** plants = \[7,7,7,7,7,7,7\], capacity = 8
**Output:** 49
**Explanation:** You have to refill before watering each plant.
Steps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49.

**Constraints:**

*   `n == plants.length`
*   `1 <= n <= 1000`
*   `1 <= plants[i] <= 106`
*   `max(plants[i]) <= capacity <= 109`
Range Frequency Queries

Design a data structure to find the **frequency** of a given value in a given subarray.

The **frequency** of a value in a subarray is the number of occurrences of that value in the subarray.

Implement the `RangeFreqQuery` class:

*   `RangeFreqQuery(int[] arr)` Constructs an instance of the class with the given **0-indexed** integer array `arr`.
*   `int query(int left, int right, int value)` Returns the **frequency** of `value` in the subarray `arr[left...right]`.

A **subarray** is a contiguous sequence of elements within an array. `arr[left...right]` denotes the subarray that contains the elements of `nums` between indices `left` and `right` (**inclusive**).

**Example 1:**

**Input**
\[ "RangeFreqQuery ",  "query ",  "query "\]
\[\[\[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56\]\], \[1, 2, 4\], \[0, 11, 33\]\]
**Output**
\[null, 1, 2\]

**Explanation**
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery(\[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56\]);
rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray \[33, 4\]
rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.

**Constraints:**

*   `1 <= arr.length <= 105`
*   `1 <= arr[i], value <= 104`
*   `0 <= left <= right < arr.length`
*   At most `105` calls will be made to `query`
Sum of k-Mirror Numbers

A **k-mirror number** is a **positive** integer **without leading zeros** that reads the same both forward and backward in base-10 **as well as** in base-k.

*   For example, `9` is a 2-mirror number. The representation of `9` in base-10 and base-2 are `9` and `1001` respectively, which read the same both forward and backward.
*   On the contrary, `4` is not a 2-mirror number. The representation of `4` in base-2 is `100`, which does not read the same both forward and backward.

Given the base `k` and the number `n`, return _the **sum** of the_ `n` _**smallest** k-mirror numbers_.

**Example 1:**

**Input:** k = 2, n = 5
**Output:** 25
**Explanation:**
The 5 smallest 2-mirror numbers and their representations in base-2 are listed as follows:
  base-10    base-2
    1          1
    3          11
    5          101
    7          111
    9          1001
Their sum = 1 + 3 + 5 + 7 + 9 = 25. 

**Example 2:**

**Input:** k = 3, n = 7
**Output:** 499
**Explanation:**
The 7 smallest 3-mirror numbers are and their representations in base-3 are listed as follows:
  base-10    base-3
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
Their sum = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499.

**Example 3:**

**Input:** k = 7, n = 17
**Output:** 20379000
**Explanation:** The 17 smallest 7-mirror numbers are:
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

**Constraints:**

*   `2 <= k <= 9`
*   `1 <= n <= 30`
Substrings That Begin and End With the Same Letter

You are given a **0-indexed** string `s` consisting of only lowercase English letters. Return _the number of **substrings** in_ `s` _that begin and end with the **same** character._

A **substring** is a contiguous non-empty sequence of characters within a string.

**Example 1:**

**Input:** s =  "abcba "
**Output:** 7
**Explanation:**
The substrings of length 1 that start and end with the same letter are:  "a ",  "b ",  "c ",  "b ", and  "a ".
The substring of length 3 that starts and ends with the same letter is:  "bcb ".
The substring of length 5 that starts and ends with the same letter is:  "abcba ".

**Example 2:**

**Input:** s =  "abacad "
**Output:** 9
**Explanation:**
The substrings of length 1 that start and end with the same letter are:  "a ",  "b ",  "a ",  "c ",  "a ", and  "d ".
The substrings of length 3 that start and end with the same letter are:  "aba " and  "aca ".
The substring of length 5 that starts and ends with the same letter is:  "abaca ".

**Example 3:**

**Input:** s =  "a "
**Output:** 1
**Explanation:**
The substring of length 1 that starts and ends with the same letter is:  "a ".

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists only of lowercase English letters.
Count Common Words With One Occurrence

Given two string arrays `words1` and `words2`, return _the number of strings that appear **exactly once** in **each** of the two arrays._

**Example 1:**

**Input:** words1 = \[ "leetcode ", "is ", "amazing ", "as ", "is "\], words2 = \[ "amazing ", "leetcode ", "is "\]
**Output:** 2
**Explanation:**
-  "leetcode " appears exactly once in each of the two arrays. We count this string.
-  "amazing " appears exactly once in each of the two arrays. We count this string.
-  "is " appears in each of the two arrays, but there are 2 occurrences of it in words1. We do not count this string.
-  "as " appears once in words1, but does not appear in words2. We do not count this string.
Thus, there are 2 strings that appear exactly once in each of the two arrays.

**Example 2:**

**Input:** words1 = \[ "b ", "bb ", "bbb "\], words2 = \[ "a ", "aa ", "aaa "\]
**Output:** 0
**Explanation:** There are no strings that appear in each of the two arrays.

**Example 3:**

**Input:** words1 = \[ "a ", "ab "\], words2 = \[ "a ", "a ", "a ", "ab "\]
**Output:** 1
**Explanation:** The only string that appears exactly once in each of the two arrays is  "ab ".

**Constraints:**

*   `1 <= words1.length, words2.length <= 1000`
*   `1 <= words1[i].length, words2[j].length <= 30`
*   `words1[i]` and `words2[j]` consists only of lowercase English letters.
Minimum Number of Food Buckets to Feed the Hamsters

You are given a **0-indexed** string `hamsters` where `hamsters[i]` is either:

*   `'H'` indicating that there is a hamster at index `i`, or
*   `'.'` indicating that index `i` is empty.

You will add some number of food buckets at the empty indices in order to feed the hamsters. A hamster can be fed if there is at least one food bucket to its left or to its right. More formally, a hamster at index `i` can be fed if you place a food bucket at index `i - 1` **and/or** at index `i + 1`.

Return _the minimum number of food buckets you should **place at empty indices** to feed all the hamsters or_ `-1` _if it is impossible to feed all of them_.

**Example 1:**

**Input:** hamsters =  "H..H "
**Output:** 2
**Explanation:** We place two food buckets at indices 1 and 2.
It can be shown that if we place only one food bucket, one of the hamsters will not be fed.

**Example 2:**

**Input:** hamsters =  ".H.H. "
**Output:** 1
**Explanation:** We place one food bucket at index 2.

**Example 3:**

**Input:** hamsters =  ".HHH. "
**Output:** -1
**Explanation:** If we place a food bucket at every empty index as shown, the hamster at index 2 will not be able to eat.

**Constraints:**

*   `1 <= hamsters.length <= 105`
*   `hamsters[i]` is either`'H'` or `'.'`.
Minimum Cost Homecoming of a Robot in a Grid

There is an `m x n` grid, where `(0, 0)` is the top-left cell and `(m - 1, n - 1)` is the bottom-right cell. You are given an integer array `startPos` where `startPos = [startrow, startcol]` indicates that **initially**, a **robot** is at the cell `(startrow, startcol)`. You are also given an integer array `homePos` where `homePos = [homerow, homecol]` indicates that its **home** is at the cell `(homerow, homecol)`.

The robot needs to go to its home. It can move one cell in four directions: **left**, **right**, **up**, or **down**, and it can not move outside the boundary. Every move incurs some cost. You are further given two **0-indexed** integer arrays: `rowCosts` of length `m` and `colCosts` of length `n`.

*   If the robot moves **up** or **down** into a cell whose **row** is `r`, then this move costs `rowCosts[r]`.
*   If the robot moves **left** or **right** into a cell whose **column** is `c`, then this move costs `colCosts[c]`.

Return _the **minimum total cost** for this robot to return home_.

**Example 1:**

**Input:** startPos = \[1, 0\], homePos = \[2, 3\], rowCosts = \[5, 4, 3\], colCosts = \[8, 2, 6, 7\]
**Output:** 18
**Explanation:** One optimal path is that:
Starting from (1, 0)
-> It goes down to (**2**, 0). This move costs rowCosts\[2\] = 3.
-> It goes right to (2, **1**). This move costs colCosts\[1\] = 2.
-> It goes right to (2, **2**). This move costs colCosts\[2\] = 6.
-> It goes right to (2, **3**). This move costs colCosts\[3\] = 7.
The total cost is 3 + 2 + 6 + 7 = 18

**Example 2:**

**Input:** startPos = \[0, 0\], homePos = \[0, 0\], rowCosts = \[5\], colCosts = \[26\]
**Output:** 0
**Explanation:** The robot is already at its home. Since no moves occur, the total cost is 0.

**Constraints:**

*   `m == rowCosts.length`
*   `n == colCosts.length`
*   `1 <= m, n <= 105`
*   `0 <= rowCosts[r], colCosts[c] <= 104`
*   `startPos.length == 2`
*   `homePos.length == 2`
*   `0 <= startrow, homerow < m`
*   `0 <= startcol, homecol < n`
Count Fertile Pyramids in a Land

A farmer has a **rectangular grid** of land with `m` rows and `n` columns that can be divided into unit cells. Each cell is either **fertile** (represented by a `1`) or **barren** (represented by a `0`). All cells outside the grid are considered barren.

A **pyramidal plot** of land can be defined as a set of cells with the following criteria:

1.  The number of cells in the set has to be **greater than** `1` and all cells must be **fertile**.
2.  The **apex** of a pyramid is the **topmost** cell of the pyramid. The **height** of a pyramid is the number of rows it covers. Let `(r, c)` be the apex of the pyramid, and its height be `h`. Then, the plot comprises of cells `(i, j)` where `r <= i <= r + h - 1` **and** `c - (i - r) <= j <= c + (i - r)`.

An **inverse pyramidal plot** of land can be defined as a set of cells with similar criteria:

1.  The number of cells in the set has to be **greater than** `1` and all cells must be **fertile**.
2.  The **apex** of an inverse pyramid is the **bottommost** cell of the inverse pyramid. The **height** of an inverse pyramid is the number of rows it covers. Let `(r, c)` be the apex of the pyramid, and its height be `h`. Then, the plot comprises of cells `(i, j)` where `r - h + 1 <= i <= r` **and** `c - (r - i) <= j <= c + (r - i)`.

Some examples of valid and invalid pyramidal (and inverse pyramidal) plots are shown below. Black cells indicate fertile cells.

Given a **0-indexed** `m x n` binary matrix `grid` representing the farmland, return _the **total number** of pyramidal and inverse pyramidal plots that can be found in_ `grid`.

**Example 1:**

**Input:** grid = \[\[0,1,1,0\],\[1,1,1,1\]\]
**Output:** 2
**Explanation:** The 2 possible pyramidal plots are shown in blue and red respectively.
There are no inverse pyramidal plots in this grid. 
Hence total number of pyramidal and inverse pyramidal plots is 2 + 0 = 2.

**Example 2:**

**Input:** grid = \[\[1,1,1\],\[1,1,1\]\]
**Output:** 2
**Explanation:** The pyramidal plot is shown in blue, and the inverse pyramidal plot is shown in red. 
Hence the total number of plots is 1 + 1 = 2.

**Example 3:**

**Input:** grid = \[\[1,1,1,1,0\],\[1,1,1,1,1\],\[1,1,1,1,1\],\[0,1,0,0,1\]\]
**Output:** 13
**Explanation:** There are 7 pyramidal plots, 3 of which are shown in the 2nd and 3rd figures.
There are 6 inverse pyramidal plots, 2 of which are shown in the last figure.
The total number of plots is 7 + 6 = 13.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 1000`
*   `1 <= m * n <= 105`
*   `grid[i][j]` is either `0` or `1`.
Find Target Indices After Sorting Array

You are given a **0-indexed** integer array `nums` and a target element `target`.

A **target index** is an index `i` such that `nums[i] == target`.

Return _a list of the target indices of_ `nums` after _sorting_ `nums` _in **non-decreasing** order_. If there are no target indices, return _an **empty** list_. The returned list must be sorted in **increasing** order.

**Example 1:**

**Input:** nums = \[1,2,5,2,3\], target = 2
**Output:** \[1,2\]
**Explanation:** After sorting, nums is \[1,**2**,**2**,3,5\].
The indices where nums\[i\] == 2 are 1 and 2.

**Example 2:**

**Input:** nums = \[1,2,5,2,3\], target = 3
**Output:** \[3\]
**Explanation:** After sorting, nums is \[1,2,2,**3**,5\].
The index where nums\[i\] == 3 is 3.

**Example 3:**

**Input:** nums = \[1,2,5,2,3\], target = 5
**Output:** \[4\]
**Explanation:** After sorting, nums is \[1,2,2,3,**5**\].
The index where nums\[i\] == 5 is 4.

**Constraints:**

*   `1 <= nums.length <= 100`
*   `1 <= nums[i], target <= 100`
K Radius Subarray Averages

You are given a **0-indexed** array `nums` of `n` integers, and an integer `k`.

The **k-radius average** for a subarray of `nums` **centered** at some index `i` with the **radius** `k` is the average of **all** elements in `nums` between the indices `i - k` and `i + k` (**inclusive**). If there are less than `k` elements before **or** after the index `i`, then the **k-radius average** is `-1`.

Build and return _an array_ `avgs` _of length_ `n` _where_ `avgs[i]` _is the **k-radius average** for the subarray centered at index_ `i`.

The **average** of `x` elements is the sum of the `x` elements divided by `x`, using **integer division**. The integer division truncates toward zero, which means losing its fractional part.

*   For example, the average of four elements `2`, `3`, `1`, and `5` is `(2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75`, which truncates to `2`.

**Example 1:**

**Input:** nums = \[7,4,3,9,1,8,5,2,6\], k = 3
**Output:** \[-1,-1,-1,5,4,4,-1,-1,-1\]
**Explanation:**
- avg\[0\], avg\[1\], and avg\[2\] are -1 because there are less than k elements **before** each index.
- The sum of the subarray centered at index 3 with radius 3 is: 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37.
  Using **integer division**, avg\[3\] = 37 / 7 = 5.
- For the subarray centered at index 4, avg\[4\] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4.
- For the subarray centered at index 5, avg\[5\] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4.
- avg\[6\], avg\[7\], and avg\[8\] are -1 because there are less than k elements **after** each index.

**Example 2:**

**Input:** nums = \[100000\], k = 0
**Output:** \[100000\]
**Explanation:**
- The sum of the subarray centered at index 0 with radius 0 is: 100000.
  avg\[0\] = 100000 / 1 = 100000.

**Example 3:**

**Input:** nums = \[8\], k = 100000
**Output:** \[-1\]
**Explanation:** 
- avg\[0\] is -1 because there are less than k elements before and after index 0.

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 105`
*   `0 <= nums[i], k <= 105`
Removing Minimum and Maximum From Array

You are given a **0-indexed** array of **distinct** integers `nums`.

There is an element in `nums` that has the **lowest** value and an element that has the **highest** value. We call them the **minimum** and **maximum** respectively. Your goal is to remove **both** these elements from the array.

A **deletion** is defined as either removing an element from the **front** of the array or removing an element from the **back** of the array.

Return _the **minimum** number of deletions it would take to remove **both** the minimum and maximum element from the array._

**Example 1:**

**Input:** nums = \[2,**10**,7,5,4,**1**,8,6\]
**Output:** 5
**Explanation:** 
The minimum element in the array is nums\[5\], which is 1.
The maximum element in the array is nums\[1\], which is 10.
We can remove both the minimum and maximum by removing 2 elements from the front and 3 elements from the back.
This results in 2 + 3 = 5 deletions, which is the minimum number possible.

**Example 2:**

**Input:** nums = \[0,**\-4**,**19**,1,8,-2,-3,5\]
**Output:** 3
**Explanation:** 
The minimum element in the array is nums\[1\], which is -4.
The maximum element in the array is nums\[2\], which is 19.
We can remove both the minimum and maximum by removing 3 elements from the front.
This results in only 3 deletions, which is the minimum number possible.

**Example 3:**

**Input:** nums = \[**101**\]
**Output:** 1
**Explanation:**  
There is only one element in the array, which makes it both the minimum and maximum element.
We can remove it with 1 deletion.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `-105 <= nums[i] <= 105`
*   The integers in `nums` are **distinct**.
Find All People With Secret

You are given an integer `n` indicating there are `n` people numbered from `0` to `n - 1`. You are also given a **0-indexed** 2D integer array `meetings` where `meetings[i] = [xi, yi, timei]` indicates that person `xi` and person `yi` have a meeting at `timei`. A person may attend **multiple meetings** at the same time. Finally, you are given an integer `firstPerson`.

Person `0` has a **secret** and initially shares the secret with a person `firstPerson` at time `0`. This secret is then shared every time a meeting takes place with a person that has the secret. More formally, for every meeting, if a person `xi` has the secret at `timei`, then they will share the secret with person `yi`, and vice versa.

The secrets are shared **instantaneously**. That is, a person may receive the secret and share it with people in other meetings within the same time frame.

Return _a list of all the people that have the secret after all the meetings have taken place._ You may return the answer in **any order**.

**Example 1:**

**Input:** n = 6, meetings = \[\[1,2,5\],\[2,3,8\],\[1,5,10\]\], firstPerson = 1
**Output:** \[0,1,2,3,5\]
**Explanation:**
At time 0, person 0 shares the secret with person 1.
At time 5, person 1 shares the secret with person 2.
At time 8, person 2 shares the secret with person 3.
At time 10, person 1 shares the secret with person 5.​​​​
Thus, people 0, 1, 2, 3, and 5 know the secret after all the meetings.

**Example 2:**

**Input:** n = 4, meetings = \[\[3,1,3\],\[1,2,2\],\[0,3,3\]\], firstPerson = 3
**Output:** \[0,1,3\]
**Explanation:**
At time 0, person 0 shares the secret with person 3.
At time 2, neither person 1 nor person 2 know the secret.
At time 3, person 3 shares the secret with person 0 and person 1.
Thus, people 0, 1, and 3 know the secret after all the meetings.

**Example 3:**

**Input:** n = 5, meetings = \[\[3,4,2\],\[1,2,1\],\[2,3,1\]\], firstPerson = 1
**Output:** \[0,1,2,3,4\]
**Explanation:**
At time 0, person 0 shares the secret with person 1.
At time 1, person 1 shares the secret with person 2, and person 2 shares the secret with person 3.
Note that person 2 can share the secret at the same time as receiving it.
At time 2, person 3 shares the secret with person 4.
Thus, people 0, 1, 2, 3, and 4 know the secret after all the meetings.

**Constraints:**

*   `2 <= n <= 105`
*   `1 <= meetings.length <= 105`
*   `meetings[i].length == 3`
*   `0 <= xi, yi <= n - 1`
*   `xi != yi`
*   `1 <= timei <= 105`
*   `1 <= firstPerson <= n - 1`