Huahua’s Tech Road

花花酱 LeetCode 2523. Closest Prime Numbers in Range EP407

By zxi on December 31, 2022

Given two positive integers left and right, find the two integers num1 and num2 such that:

left <= nums1 < nums2 <= right .
nums1 and nums2 are both prime numbers.
nums2 - nums1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [nums1, nums2]. If there are multiple pairs satisfying these conditions, return the one with the minimum nums1 value or [-1, -1] if such numbers do not exist.

A number greater than 1 is called prime if it is only divisible by 1 and itself.

Example 1:

Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.

Example 2:

Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.

Constraints:

1 <= left <= right <= 10⁶

Solution: Sieve of Eratosthenes

Use Sieve of Eratosthenes to find all primes in range [0, right].

Check neighbor primes and find the best pair.

Time complexity: O(nloglogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> closestPrimes(int left, int right) {

vector<int> primes(right + 1, 1);

primes[0] = primes[1] = 0;

for (int i = 2; i <= sqrt(right); ++i) {

if (!primes[i]) continue;

for (int x = i * i; x <= right; x += i)

primes[x] = 0;

}

vector<int> ans{-1,-1};

for (int i = left, last = -1, best = INT_MAX; i <= right; ++i) {

if (!primes[i]) continue;

if (last > 0 && i - last < best) {

best = i - last;

ans = {last, i};

}

last = i;

}

return ans;

}

};

花花酱 LeetCode 2477. Minimum Fuel Cost to Report to the Capital

By zxi on November 26, 2022

There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads. The capital city is city 0. You are given a 2D integer array roads where roads[i] = [a_i, b_i] denotes that there exists a bidirectional road connecting cities a_i and b_i.

There is a meeting for the representatives of each city. The meeting is in the capital city.

There is a car in each city. You are given an integer seats that indicates the number of seats in each car.

A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.

Return the minimum number of liters of fuel to reach the capital city.

Example 1:

Input: roads = [[0,1],[0,2],[0,3]], seats = 5
Output: 3
Explanation: 
- Representative₁ goes directly to the capital with 1 liter of fuel.
- Representative₂ goes directly to the capital with 1 liter of fuel.
- Representative₃ goes directly to the capital with 1 liter of fuel.
It costs 3 liters of fuel at minimum. 
It can be proven that 3 is the minimum number of liters of fuel needed.

Example 2:

Input: roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
Output: 7
Explanation: 
- Representative₂ goes directly to city 3 with 1 liter of fuel.
- Representative₂ and representative₃ go together to city 1 with 1 liter of fuel.
- Representative₂ and representative₃ go together to the capital with 1 liter of fuel.
- Representative₁ goes directly to the capital with 1 liter of fuel.
- Representative₅ goes directly to the capital with 1 liter of fuel.
- Representative₆ goes directly to city 4 with 1 liter of fuel.
- Representative₄ and representative₆ go together to the capital with 1 liter of fuel.
It costs 7 liters of fuel at minimum. 
It can be proven that 7 is the minimum number of liters of fuel needed.

Example 3:

Input: roads = [], seats = 1
Output: 0
Explanation: No representatives need to travel to the capital city.

Constraints:

1 <= n <= 10⁵
roads.length == n - 1
roads[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
roads represents a valid tree.
1 <= seats <= 10⁵

Solution: Greedy + DFS

To reach the minimum cost, we must share cars if possible, say X reps from children nodes to an intermediate node u on the way towards capital 0. Then they all changes cars at node u, and we need (X + 1) // seats cars/fuel from u to 0.

We use DFS to count # of reps at each node u while accumulating the total cost.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

long long minimumFuelCost(vector<vector<int>>& roads, int seats) {

long long ans = 0;

vector<vector<int>> g(roads.size() + 1);

for (const vector<int>& r : roads) {

g[r[0]].push_back(r[1]);

g[r[1]].push_back(r[0]);

}

// Returns total # of children of u.

function<int(int, int)> dfs = [&](int u, int p, int rep = 1) {

for (int v : g[u])

if (v != p) rep += dfs(v, u);

if (u) ans += (rep + seats - 1) / seats;

return rep;

};

dfs(0, -1);

return ans;

}

};

花花酱 LeetCode 2469. Convert the Temperature

By zxi on November 22, 2022

You are given a non-negative floating point number rounded to two decimal places celsius, that denotes the temperature in Celsius.

You should convert Celsius into Kelvin and Fahrenheit and return it as an array ans = [kelvin, fahrenheit].

Return the array ans. Answers within 10^-5 of the actual answer will be accepted.

Note that:

Kelvin = Celsius + 273.15
Fahrenheit = Celsius * 1.80 + 32.00

Example 1:

Input: celsius = 36.50
Output: [309.65000,97.70000]
Explanation: Temperature at 36.50 Celsius converted in Kelvin is 309.65 and converted in Fahrenheit is 97.70.

Example 2:

Input: celsius = 122.11
Output: [395.26000,251.79800]
Explanation: Temperature at 122.11 Celsius converted in Kelvin is 395.26 and converted in Fahrenheit is 251.798.

Constraints:

0 <= celsius <= 1000

Solution: Follow the formulas

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<double> convertTemperature(double celsius) {

return {celsius + 273.15, celsius * 1.80 + 32.00};

}

};

花花酱 LeetCode 2476. Closest Nodes Queries in a Binary Search Tree

By zxi on November 21, 2022

You are given the root of a binary search tree and an array queries of size n consisting of positive integers.

Find a 2D array answer of size n where answer[i] = [min_i, max_i]:

min_i is the largest value in the tree that is smaller than or equal to queries[i]. If a such value does not exist, add -1 instead.
max_i is the smallest value in the tree that is greater than or equal to queries[i]. If a such value does not exist, add -1 instead.

Return the array answer.

Example 1:

Input: root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
Output: [[2,2],[4,6],[15,-1]]
Explanation: We answer the queries in the following way:
- The largest number that is smaller or equal than 2 in the tree is 2, and the smallest number that is greater or equal than 2 is still 2. So the answer for the first query is [2,2].
- The largest number that is smaller or equal than 5 in the tree is 4, and the smallest number that is greater or equal than 5 is 6. So the answer for the second query is [4,6].
- The largest number that is smaller or equal than 16 in the tree is 15, and the smallest number that is greater or equal than 16 does not exist. So the answer for the third query is [15,-1].

Example 2:

Input: root = [4,null,9], queries = [3]
Output: [[-1,4]]
Explanation: The largest number that is smaller or equal to 3 in the tree does not exist, and the smallest number that is greater or equal to 3 is 4. So the answer for the query is [-1,4].

Constraints:

The number of nodes in the tree is in the range [2, 10⁵].
1 <= Node.val <= 10⁶
n == queries.length
1 <= n <= 10⁵
1 <= queries[i] <= 10⁶

Solution: Convert to sorted array

Since we don’t know whether the tree is balanced or not, the safest and easiest way is to convert the tree into a sorted array using inorder traversal. Or just any traversal and sort the array later on.

Once we have a sorted array, we can use lower_bound / upper_bound to query.

Time complexity: O(qlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {

vector<int> vals;

function<void(TreeNode*)> inorder = [&](TreeNode* root) {

if (!root) return;

inorder(root->left);

vals.push_back(root->val);

inorder(root->right);

};

inorder(root);

vector<vector<int>> ans;

for (const int q : queries) {

vector<int> cur{-1, -1};

auto lit = upper_bound(begin(vals), end(vals), q);

if (lit != begin(vals))

cur[0] = *(prev(lit));

auto rit = lower_bound(begin(vals), end(vals), q);

if (rit != end(vals))

cur[1] = *rit;

ans.push_back(std::move(cur));

}

return ans;

}

};

One binary search per query.

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {

vector<int> vals;

function<void(TreeNode*)> inorder = [&](TreeNode* root) {

if (!root) return;

inorder(root->left);

if (vals.empty() || root->val > vals.back()) vals.push_back(root->val);

inorder(root->right);

};

inorder(root);

vector<vector<int>> ans;

for (const int q : queries) {

vector<int> cur{-1, -1};

auto it = lower_bound(begin(vals), end(vals), q);

if (it != end(vals) && *it == q)

cur[0] = cur[1] = q;

else {

if (it != begin(vals)) cur[0] = *prev(it);

if (it != end(vals)) cur[1] = *it;

}

ans.push_back(std::move(cur));

}

return ans;

}

};

花花酱 LeetCode 2475. Number of Unequal Triplets in Array

By zxi on November 21, 2022

You are given a 0-indexed array of positive integers nums. Find the number of triplets (i, j, k) that meet the following conditions:

0 <= i < j < k < nums.length
nums[i], nums[j], and nums[k] are pairwise distinct.
- In other words, nums[i] != nums[j], nums[i] != nums[k], and nums[j] != nums[k].

Return the number of triplets that meet the conditions.

Example 1:

Input: nums = [4,4,2,4,3]
Output: 3
Explanation: The following triplets meet the conditions:
- (0, 2, 4) because 4 != 2 != 3
- (1, 2, 4) because 4 != 2 != 3
- (2, 3, 4) because 2 != 4 != 3
Since there are 3 triplets, we return 3.
Note that (2, 0, 4) is not a valid triplet because 2 > 0.

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: No triplets meet the conditions so we return 0.

Constraints:

3 <= nums.length <= 100
1 <= nums[i] <= 1000

Solution 1: Brute Force

Enumerate i, j, k.

Time complexity: O(n³)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int unequalTriplets(vector<int>& nums) {

int ans = 0;

const int n = nums.size();

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

for (int k = j + 1; k < n; ++k)

if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k])

++ans;

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2523. Closest Prime Numbers in Range EP407

Solution: Sieve of Eratosthenes

C++

花花酱 LeetCode 2477. Minimum Fuel Cost to Report to the Capital

Solution: Greedy + DFS

C++

花花酱 LeetCode 2469. Convert the Temperature

Solution: Follow the formulas

C++

花花酱 LeetCode 2476. Closest Nodes Queries in a Binary Search Tree

Solution: Convert to sorted array

C++

C++

花花酱 LeetCode 2475. Number of Unequal Triplets in Array

Solution 1: Brute Force

C++