bowang0911/leetcode huggingface dataset:
XOR Queries of a Subarray

You are given an array `arr` of positive integers. You are also given the array `queries` where `queries[i] = [lefti, righti]`.

For each query `i` compute the **XOR** of elements from `lefti` to `righti` (that is, `arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti]` ).

Return an array `answer` where `answer[i]` is the answer to the `ith` query.

**Example 1:**

**Input:** arr = \[1,3,4,8\], queries = \[\[0,1\],\[1,2\],\[0,3\],\[3,3\]\]
**Output:** \[2,7,14,8\] 
**Explanation:** 
The binary representation of the elements in the array are:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
The XOR values for queries are:
\[0,1\] = 1 xor 3 = 2 
\[1,2\] = 3 xor 4 = 7 
\[0,3\] = 1 xor 3 xor 4 xor 8 = 14 
\[3,3\] = 8

**Example 2:**

**Input:** arr = \[4,8,2,10\], queries = \[\[2,3\],\[1,3\],\[0,0\],\[0,3\]\]
**Output:** \[8,0,4,4\]

**Constraints:**

*   `1 <= arr.length, queries.length <= 3 * 104`
*   `1 <= arr[i] <= 109`
*   `queries[i].length == 2`
*   `0 <= lefti <= righti < arr.length`
Get Watched Videos by Your Friends

There are `n` people, each person has a unique _id_ between `0` and `n-1`. Given the arrays `watchedVideos` and `friends`, where `watchedVideos[i]` and `friends[i]` contain the list of watched videos and the list of friends respectively for the person with `id = i`.

Level **1** of videos are all watched videos by your friends, level **2** of videos are all watched videos by the friends of your friends and so on. In general, the level `k` of videos are all watched videos by people with the shortest path **exactly** equal to `k` with you. Given your `id` and the `level` of videos, return the list of videos ordered by their frequencies (increasing). For videos with the same frequency order them alphabetically from least to greatest.

**Example 1:**

**Input:** watchedVideos = \[\[ "A ", "B "\],\[ "C "\],\[ "B ", "C "\],\[ "D "\]\], friends = \[\[1,2\],\[0,3\],\[0,3\],\[1,2\]\], id = 0, level = 1
**Output:** \[ "B ", "C "\] 
**Explanation:** 
You have id = 0 (green color in the figure) and your friends are (yellow color in the figure):
Person with id = 1 -> watchedVideos = \[ "C "\] 
Person with id = 2 -> watchedVideos = \[ "B ", "C "\] 
The frequencies of watchedVideos by your friends are: 
B -> 1 
C -> 2

**Example 2:**

**Input:** watchedVideos = \[\[ "A ", "B "\],\[ "C "\],\[ "B ", "C "\],\[ "D "\]\], friends = \[\[1,2\],\[0,3\],\[0,3\],\[1,2\]\], id = 0, level = 2
**Output:** \[ "D "\]
**Explanation:** 
You have id = 0 (green color in the figure) and the only friend of your friends is the person with id = 3 (yellow color in the figure).

**Constraints:**

*   `n == watchedVideos.length == friends.length`
*   `2 <= n <= 100`
*   `1 <= watchedVideos[i].length <= 100`
*   `1 <= watchedVideos[i][j].length <= 8`
*   `0 <= friends[i].length < n`
*   `0 <= friends[i][j] < n`
*   `0 <= id < n`
*   `1 <= level < n`
*   if `friends[i]` contains `j`, then `friends[j]` contains `i`
Minimum Insertion Steps to Make a String Palindrome

Given a string `s`. In one step you can insert any character at any index of the string.

Return _the minimum number of steps_ to make `s` palindrome.

A **Palindrome String** is one that reads the same backward as well as forward.

**Example 1:**

**Input:** s =  "zzazz "
**Output:** 0
**Explanation:** The string  "zzazz " is already palindrome we do not need any insertions.

**Example 2:**

**Input:** s =  "mbadm "
**Output:** 2
**Explanation:** String can be  "mbdadbm " or  "mdbabdm ".

**Example 3:**

**Input:** s =  "leetcode "
**Output:** 5
**Explanation:** Inserting 5 characters the string becomes  "leetcodocteel ".

**Constraints:**

*   `1 <= s.length <= 500`
*   `s` consists of lowercase English letters.
Decompress Run-Length Encoded List

We are given a list `nums` of integers representing a list compressed with run-length encoding.

Consider each adjacent pair of elements `[freq, val] = [nums[2*i], nums[2*i+1]]` (with `i >= 0`). For each such pair, there are `freq` elements with value `val` concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list.

Return the decompressed list.

**Example 1:**

**Input:** nums = \[1,2,3,4\]
**Output:** \[2,4,4,4\]
**Explanation:** The first pair \[1,2\] means we have freq = 1 and val = 2 so we generate the array \[2\].
The second pair \[3,4\] means we have freq = 3 and val = 4 so we generate \[4,4,4\].
At the end the concatenation \[2\] + \[4,4,4\] is \[2,4,4,4\].

**Example 2:**

**Input:** nums = \[1,1,2,3\]
**Output:** \[1,3,3\]

**Constraints:**

*   `2 <= nums.length <= 100`
*   `nums.length % 2 == 0`
*   `1 <= nums[i] <= 100`
Matrix Block Sum

Given a `m x n` matrix `mat` and an integer `k`, return _a matrix_ `answer` _where each_ `answer[i][j]` _is the sum of all elements_ `mat[r][c]` _for_:

*   `i - k <= r <= i + k,`
*   `j - k <= c <= j + k`, and
*   `(r, c)` is a valid position in the matrix.

**Example 1:**

**Input:** mat = \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\], k = 1
**Output:** \[\[12,21,16\],\[27,45,33\],\[24,39,28\]\]

**Example 2:**

**Input:** mat = \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\], k = 2
**Output:** \[\[45,45,45\],\[45,45,45\],\[45,45,45\]\]

**Constraints:**

*   `m == mat.length`
*   `n == mat[i].length`
*   `1 <= m, n, k <= 100`
*   `1 <= mat[i][j] <= 100`
Sum of Nodes with Even-Valued Grandparent

Given the `root` of a binary tree, return _the sum of values of nodes with an **even-valued grandparent**_. If there are no nodes with an **even-valued grandparent**, return `0`.

A **grandparent** of a node is the parent of its parent if it exists.

**Example 1:**

**Input:** root = \[6,7,8,2,7,1,3,9,null,1,4,null,null,null,5\]
**Output:** 18
**Explanation:** The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

**Example 2:**

**Input:** root = \[1\]
**Output:** 0

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `1 <= Node.val <= 100`
Convert Integer to the Sum of Two No-Zero Integers

**No-Zero integer** is a positive integer that **does not contain any `0`** in its decimal representation.

Given an integer `n`, return _a list of two integers_ `[a, b]` _where_:

*   `a` and `b` are **No-Zero integers**.
*   `a + b = n`

The test cases are generated so that there is at least one valid solution. If there are many valid solutions, you can return any of them.

**Example 1:**

**Input:** n = 2
**Output:** \[1,1\]
**Explanation:** Let a = 1 and b = 1.
Both a and b are no-zero integers, and a + b = 2 = n.

**Example 2:**

**Input:** n = 11
**Output:** \[2,9\]
**Explanation:** Let a = 2 and b = 9.
Both a and b are no-zero integers, and a + b = 9 = n.
Note that there are other valid answers as \[8, 3\] that can be accepted.

**Constraints:**

*   `2 <= n <= 104`
Minimum Flips to Make a OR b Equal to c

Given 3 positives numbers `a`, `b` and `c`. Return the minimum flips required in some bits of `a` and `b` to make ( `a` OR `b` == `c` ). (bitwise OR operation).  
Flip operation consists of change **any** single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

**Example 1:**

**Input:** a = 2, b = 6, c = 5
**Output:** 3
**Explanation:** After flips a = 1 , b = 4 , c = 5 such that (`a` OR `b` == `c`)

**Example 2:**

**Input:** a = 4, b = 2, c = 7
**Output:** 1

**Example 3:**

**Input:** a = 1, b = 2, c = 3
**Output:** 0

**Constraints:**

*   `1 <= a <= 10^9`
*   `1 <= b <= 10^9`
*   `1 <= c <= 10^9`
Number of Operations to Make Network Connected

There are `n` computers numbered from `0` to `n - 1` connected by ethernet cables `connections` forming a network where `connections[i] = [ai, bi]` represents a connection between computers `ai` and `bi`. Any computer can reach any other computer directly or indirectly through the network.

You are given an initial computer network `connections`. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected.

Return _the minimum number of times you need to do this in order to make all the computers connected_. If it is not possible, return `-1`.

**Example 1:**

**Input:** n = 4, connections = \[\[0,1\],\[0,2\],\[1,2\]\]
**Output:** 1
**Explanation:** Remove cable between computer 1 and 2 and place between computers 1 and 3.

**Example 2:**

**Input:** n = 6, connections = \[\[0,1\],\[0,2\],\[0,3\],\[1,2\],\[1,3\]\]
**Output:** 2

**Example 3:**

**Input:** n = 6, connections = \[\[0,1\],\[0,2\],\[0,3\],\[1,2\]\]
**Output:** -1
**Explanation:** There are not enough cables.

**Constraints:**

*   `1 <= n <= 105`
*   `1 <= connections.length <= min(n * (n - 1) / 2, 105)`
*   `connections[i].length == 2`
*   `0 <= ai, bi < n`
*   `ai != bi`
*   There are no repeated connections.
*   No two computers are connected by more than one cable.
Minimum Distance to Type a Word Using Two Fingers

You have a keyboard layout as shown above in the **X-Y** plane, where each English uppercase letter is located at some coordinate.

*   For example, the letter `'A'` is located at coordinate `(0, 0)`, the letter `'B'` is located at coordinate `(0, 1)`, the letter `'P'` is located at coordinate `(2, 3)` and the letter `'Z'` is located at coordinate `(4, 1)`.

Given the string `word`, return _the minimum total **distance** to type such string using only two fingers_.

The **distance** between coordinates `(x1, y1)` and `(x2, y2)` is `|x1 - x2| + |y1 - y2|`.

**Note** that the initial positions of your two fingers are considered free so do not count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.

**Example 1:**

**Input:** word =  "CAKE "
**Output:** 3
**Explanation:** Using two fingers, one optimal way to type  "CAKE " is: 
Finger 1 on letter 'C' -> cost = 0 
Finger 1 on letter 'A' -> cost = Distance from letter 'C' to letter 'A' = 2 
Finger 2 on letter 'K' -> cost = 0 
Finger 2 on letter 'E' -> cost = Distance from letter 'K' to letter 'E' = 1 
Total distance = 3

**Example 2:**

**Input:** word =  "HAPPY "
**Output:** 6
**Explanation:** Using two fingers, one optimal way to type  "HAPPY " is:
Finger 1 on letter 'H' -> cost = 0
Finger 1 on letter 'A' -> cost = Distance from letter 'H' to letter 'A' = 2
Finger 2 on letter 'P' -> cost = 0
Finger 2 on letter 'P' -> cost = Distance from letter 'P' to letter 'P' = 0
Finger 1 on letter 'Y' -> cost = Distance from letter 'A' to letter 'Y' = 4
Total distance = 6

**Constraints:**

*   `2 <= word.length <= 300`
*   `word` consists of uppercase English letters.
Maximum 69 Number

You are given a positive integer `num` consisting only of digits `6` and `9`.

Return _the maximum number you can get by changing **at most** one digit (_`6` _becomes_ `9`_, and_ `9` _becomes_ `6`_)_.

**Example 1:**

**Input:** num = 9669
**Output:** 9969
**Explanation:** 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.

**Example 2:**

**Input:** num = 9996
**Output:** 9999
**Explanation:** Changing the last digit 6 to 9 results in the maximum number.

**Example 3:**

**Input:** num = 9999
**Output:** 9999
**Explanation:** It is better not to apply any change.

**Constraints:**

*   `1 <= num <= 104`
*   `num` consists of only `6` and `9` digits.
Print Words Vertically

Given a string `s`. Return all the words vertically in the same order in which they appear in `s`.  
Words are returned as a list of strings, complete with spaces when is necessary. (Trailing spaces are not allowed).  
Each word would be put on only one column and that in one column there will be only one word.

**Example 1:**

**Input:** s =  "HOW ARE YOU "
**Output:** \[ "HAY ", "ORO ", "WEU "\]
**Explanation:** Each word is printed vertically. 
  "HAY "
  "ORO "
  "WEU "

**Example 2:**

**Input:** s =  "TO BE OR NOT TO BE "
**Output:** \[ "TBONTB ", "OEROOE ", "   T "\]
**Explanation:** Trailing spaces is not allowed. 
 "TBONTB "
 "OEROOE "
 "   T "

**Example 3:**

**Input:** s =  "CONTEST IS COMING "
**Output:** \[ "CIC ", "OSO ", "N M ", "T I ", "E N ", "S G ", "T "\]

**Constraints:**

*   `1 <= s.length <= 200`
*   `s` contains only upper case English letters.
*   It's guaranteed that there is only one space between 2 words.
Delete Leaves With a Given Value

Given a binary tree `root` and an integer `target`, delete all the **leaf nodes** with value `target`.

Note that once you delete a leaf node with value `target`**,** if its parent node becomes a leaf node and has the value `target`, it should also be deleted (you need to continue doing that until you cannot).

**Example 1:**

**Input:** root = \[1,2,3,2,null,2,4\], target = 2
**Output:** \[1,null,3,null,4\]
**Explanation:** Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

**Example 2:**

**Input:** root = \[1,3,3,3,2\], target = 3
**Output:** \[1,3,null,null,2\]

**Example 3:**

**Input:** root = \[1,2,null,2,null,2\], target = 2
**Output:** \[1\]
**Explanation:** Leaf nodes in green with value (target = 2) are removed at each step.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 3000]`.
*   `1 <= Node.val, target <= 1000`
Minimum Number of Taps to Open to Water a Garden

There is a one-dimensional garden on the x-axis. The garden starts at the point `0` and ends at the point `n`. (i.e The length of the garden is `n`).

There are `n + 1` taps located at points `[0, 1, ..., n]` in the garden.

Given an integer `n` and an integer array `ranges` of length `n + 1` where `ranges[i]` (0-indexed) means the `i-th` tap can water the area `[i - ranges[i], i + ranges[i]]` if it was open.

Return _the minimum number of taps_ that should be open to water the whole garden, If the garden cannot be watered return **\-1**.

**Example 1:**

**Input:** n = 5, ranges = \[3,4,1,1,0,0\]
**Output:** 1
**Explanation:** The tap at point 0 can cover the interval \[-3,3\]
The tap at point 1 can cover the interval \[-3,5\]
The tap at point 2 can cover the interval \[1,3\]
The tap at point 3 can cover the interval \[2,4\]
The tap at point 4 can cover the interval \[4,4\]
The tap at point 5 can cover the interval \[5,5\]
Opening Only the second tap will water the whole garden \[0,5\]

**Example 2:**

**Input:** n = 3, ranges = \[0,0,0,0\]
**Output:** -1
**Explanation:** Even if you activate all the four taps you cannot water the whole garden.

**Constraints:**

*   `1 <= n <= 104`
*   `ranges.length == n + 1`
*   `0 <= ranges[i] <= 100`
Break a Palindrome

Given a palindromic string of lowercase English letters `palindrome`, replace **exactly one** character with any lowercase English letter so that the resulting string is **not** a palindrome and that it is the **lexicographically smallest** one possible.

Return _the resulting string. If there is no way to replace a character to make it not a palindrome, return an **empty string**._

A string `a` is lexicographically smaller than a string `b` (of the same length) if in the first position where `a` and `b` differ, `a` has a character strictly smaller than the corresponding character in `b`. For example, `"abcc "` is lexicographically smaller than `"abcd "` because the first position they differ is at the fourth character, and `'c'` is smaller than `'d'`.

**Example 1:**

**Input:** palindrome =  "abccba "
**Output:**  "aaccba "
**Explanation:** There are many ways to make  "abccba " not a palindrome, such as  "zbccba ",  "aaccba ", and  "abacba ".
Of all the ways,  "aaccba " is the lexicographically smallest.

**Example 2:**

**Input:** palindrome =  "a "
**Output:**  " "
**Explanation:** There is no way to replace a single character to make  "a " not a palindrome, so return an empty string.

**Constraints:**

*   `1 <= palindrome.length <= 1000`
*   `palindrome` consists of only lowercase English letters.
Sort the Matrix Diagonally

A **matrix diagonal** is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix's end. For example, the **matrix diagonal** starting from `mat[2][0]`, where `mat` is a `6 x 3` matrix, includes cells `mat[2][0]`, `mat[3][1]`, and `mat[4][2]`.

Given an `m x n` matrix `mat` of integers, sort each **matrix diagonal** in ascending order and return _the resulting matrix_.

**Example 1:**

**Input:** mat = \[\[3,3,1,1\],\[2,2,1,2\],\[1,1,1,2\]\]
**Output:** \[\[1,1,1,1\],\[1,2,2,2\],\[1,2,3,3\]\]

**Example 2:**

**Input:** mat = \[\[11,25,66,1,69,7\],\[23,55,17,45,15,52\],\[75,31,36,44,58,8\],\[22,27,33,25,68,4\],\[84,28,14,11,5,50\]\]
**Output:** \[\[5,17,4,1,52,7\],\[11,11,25,45,8,69\],\[14,23,25,44,58,15\],\[22,27,31,36,50,66\],\[84,28,75,33,55,68\]\]

**Constraints:**

*   `m == mat.length`
*   `n == mat[i].length`
*   `1 <= m, n <= 100`
*   `1 <= mat[i][j] <= 100`
Reverse Subarray To Maximize Array Value

You are given an integer array `nums`. The _value_ of this array is defined as the sum of `|nums[i] - nums[i + 1]|` for all `0 <= i < nums.length - 1`.

You are allowed to select any subarray of the given array and reverse it. You can perform this operation **only once**.

Find maximum possible value of the final array.

**Example 1:**

**Input:** nums = \[2,3,1,5,4\]
**Output:** 10
**Explanation:** By reversing the subarray \[3,1,5\] the array becomes \[2,5,1,3,4\] whose value is 10.

**Example 2:**

**Input:** nums = \[2,4,9,24,2,1,10\]
**Output:** 68

**Constraints:**

*   `1 <= nums.length <= 3 * 104`
*   `-105 <= nums[i] <= 105`
Rank Transform of an Array

Given an array of integers `arr`, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

*   Rank is an integer starting from 1.
*   The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
*   Rank should be as small as possible.

**Example 1:**

**Input:** arr = \[40,10,20,30\]
**Output:** \[4,1,2,3\]
**Explanation**: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

**Example 2:**

**Input:** arr = \[100,100,100\]
**Output:** \[1,1,1\]
**Explanation**: Same elements share the same rank.

**Example 3:**

**Input:** arr = \[37,12,28,9,100,56,80,5,12\]
**Output:** \[5,3,4,2,8,6,7,1,3\]

**Constraints:**

*   `0 <= arr.length <= 105`
*   `-109 <= arr[i] <= 109`

\- Every time you are in a cell you will collect all the gold in that cell. - From your position, you can walk one step to the left, right, up, or down. - You can't visit the same cell more than once. - Never visit a cell with 0 gold. - You can start and stop collecting gold from any position in the grid that has some gold.
Remove Palindromic Subsequences

You are given a string `s` consisting **only** of letters `'a'` and `'b'`. In a single step you can remove one **palindromic subsequence** from `s`.

Return _the **minimum** number of steps to make the given string empty_.

A string is a **subsequence** of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does **not** necessarily need to be contiguous.

A string is called **palindrome** if is one that reads the same backward as well as forward.

**Example 1:**

**Input:** s =  "ababa "
**Output:** 1
**Explanation:** s is already a palindrome, so its entirety can be removed in a single step.

**Example 2:**

**Input:** s =  "abb "
**Output:** 2
**Explanation:**  "abb " ->  "bb " ->  " ". 
Remove palindromic subsequence  "a " then  "bb ".

**Example 3:**

**Input:** s =  "baabb "
**Output:** 2
**Explanation:**  "baabb " ->  "b " ->  " ". 
Remove palindromic subsequence  "baab " then  "b ".

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s[i]` is either `'a'` or `'b'`.
Filter Restaurants by Vegan-Friendly, Price and Distance

Given the array `restaurants` where `restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]`. You have to filter the restaurants using three filters.

The `veganFriendly` filter will be either _true_ (meaning you should only include restaurants with `veganFriendlyi` set to true) or _false_ (meaning you can include any restaurant). In addition, you have the filters `maxPrice` and `maxDistance` which are the maximum value for price and distance of restaurants you should consider respectively.

Return the array of restaurant _**IDs**_ after filtering, ordered by **rating** from highest to lowest. For restaurants with the same rating, order them by _**id**_ from highest to lowest. For simplicity `veganFriendlyi` and `veganFriendly` take value _1_ when it is _true_, and _0_ when it is _false_.

**Example 1:**

**Input:** restaurants = \[\[1,4,1,40,10\],\[2,8,0,50,5\],\[3,8,1,30,4\],\[4,10,0,10,3\],\[5,1,1,15,1\]\], veganFriendly = 1, maxPrice = 50, maxDistance = 10
**Output:** \[3,1,5\] 
**Explanation:** 
The restaurants are:
Restaurant 1 \[id=1, rating=4, veganFriendly=1, price=40, distance=10\]
Restaurant 2 \[id=2, rating=8, veganFriendly=0, price=50, distance=5\]
Restaurant 3 \[id=3, rating=8, veganFriendly=1, price=30, distance=4\]
Restaurant 4 \[id=4, rating=10, veganFriendly=0, price=10, distance=3\]
Restaurant 5 \[id=5, rating=1, veganFriendly=1, price=15, distance=1\] 
After filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest). 

**Example 2:**

**Input:** restaurants = \[\[1,4,1,40,10\],\[2,8,0,50,5\],\[3,8,1,30,4\],\[4,10,0,10,3\],\[5,1,1,15,1\]\], veganFriendly = 0, maxPrice = 50, maxDistance = 10
**Output:** \[4,3,2,1,5\]
**Explanation:** The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.

**Example 3:**

**Input:** restaurants = \[\[1,4,1,40,10\],\[2,8,0,50,5\],\[3,8,1,30,4\],\[4,10,0,10,3\],\[5,1,1,15,1\]\], veganFriendly = 0, maxPrice = 30, maxDistance = 3
**Output:** \[4,5\]

**Constraints:**

*   `1 <= restaurants.length <= 10^4`
*   `restaurants[i].length == 5`
*   `1 <= idi, ratingi, pricei, distancei <= 10^5`
*   `1 <= maxPrice, maxDistance <= 10^5`
*   `veganFriendlyi` and `veganFriendly` are 0 or 1.
*   All `idi` are distinct.
Find the City With the Smallest Number of Neighbors at a Threshold Distance

There are `n` cities numbered from `0` to `n-1`. Given the array `edges` where `edges[i] = [fromi, toi, weighti]` represents a bidirectional and weighted edge between cities `fromi` and `toi`, and given the integer `distanceThreshold`.

Return the city with the smallest number of cities that are reachable through some path and whose distance is **at most** `distanceThreshold`, If there are multiple such cities, return the city with the greatest number.

Notice that the distance of a path connecting cities _**i**_ and _**j**_ is equal to the sum of the edges' weights along that path.

**Example 1:**

**Input:** n = 4, edges = \[\[0,1,3\],\[1,2,1\],\[1,3,4\],\[2,3,1\]\], distanceThreshold = 4
**Output:** 3
**Explanation:** The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> \[City 1, City 2\] 
City 1 -> \[City 0, City 2, City 3\] 
City 2 -> \[City 0, City 1, City 3\] 
City 3 -> \[City 1, City 2\] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

**Example 2:**

**Input:** n = 5, edges = \[\[0,1,2\],\[0,4,8\],\[1,2,3\],\[1,4,2\],\[2,3,1\],\[3,4,1\]\], distanceThreshold = 2
**Output:** 0
**Explanation:** The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 2 for each city are:
City 0 -> \[City 1\] 
City 1 -> \[City 0, City 4\] 
City 2 -> \[City 3, City 4\] 
City 3 -> \[City 2, City 4\]
City 4 -> \[City 1, City 2, City 3\] 
The city 0 has 1 neighboring city at a distanceThreshold = 2.

**Constraints:**

*   `2 <= n <= 100`
*   `1 <= edges.length <= n * (n - 1) / 2`
*   `edges[i].length == 3`
*   `0 <= fromi < toi < n`
*   `1 <= weighti, distanceThreshold <= 10^4`
*   All pairs `(fromi, toi)` are distinct.