Huahua’s Tech Road

花花酱 LeetCode 2115. Find All Possible Recipes from Given Supplies

By zxi on December 26, 2021

You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The i^th recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes.

You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.

Return a list of all the recipes that you can create. You may return the answer in any order.

Note that two recipes may contain each other in their ingredients.

Example 1:

Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output: ["bread"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".

Example 2:

Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

Example 3:

Input: recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich","burger"]
Explanation:
We can create "bread" since we have the ingredients "yeast" and "flour".
We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".
We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".

Constraints:

n == recipes.length == ingredients.length
1 <= n <= 100
1 <= ingredients[i].length, supplies.length <= 100
1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
recipes[i], ingredients[i][j], and supplies[k] consist only of lowercase English letters.
All the values of recipes and supplies combined are unique.
Each ingredients[i] does not contain any duplicate values.

Solution: Brute Force

C++

// Author: Huahua

class Solution {

public:

vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {

const int n = recipes.size();

unordered_set<string> s(begin(supplies), end(supplies));

vector<string> ans;

vector<int> seen(n);

while (true) {

bool newSupply = false;

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

if (seen[i]) continue;

bool hasAll = true;

for (const string& ingredient : ingredients[i])

if (!s.count(ingredient)) {

hasAll = false;

break;

}

if (!hasAll) continue;

ans.push_back(recipes[i]);

seen[i] = 1;

s.insert(recipes[i]);

newSupply = true;

}

if (!newSupply) break;

}

return ans;

}

};

花花酱 LeetCode 2114. Maximum Number of Words Found in Sentences

By zxi on December 26, 2021

A sentence is a list of words that are separated by a single space with no leading or trailing spaces.

You are given an array of strings sentences, where each sentences[i] represents a single sentence.

Return the maximum number of words that appear in a single sentence.

Example 1:

Input: sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
Output: 6
Explanation: 
- The first sentence, "alice and bob love leetcode", has 5 words in total.
- The second sentence, "i think so too", has 4 words in total.
- The third sentence, "this is great thanks very much", has 6 words in total.
Thus, the maximum number of words in a single sentence comes from the third sentence, which has 6 words.

Example 2:

Input: sentences = ["please wait", "continue to fight", "continue to win"]
Output: 3
Explanation: It is possible that multiple sentences contain the same number of words. 
In this example, the second and third sentences (underlined) have the same number of words.

Constraints:

1 <= sentences.length <= 100
1 <= sentences[i].length <= 100
sentences[i] consists only of lowercase English letters and ' ' only.
sentences[i] does not have leading or trailing spaces.
All the words in sentences[i] are separated by a single space.

Solution: Count spaces

Time complexity: O(sum(len(sentences[i]))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int mostWordsFound(vector<string>& sentences) {

int ans = 0;

for (const string& s : sentences)

ans = max(ans, 1 + static_cast<int>(count(begin(s), end(s), ' ')));

return ans;

}

};

花花酱 LeetCode 2122. Recover the Original Array

By zxi on December 26, 2021

Alice had a 0-indexed array arr consisting of n positive integers. She chose an arbitrary positive integer k and created two new 0-indexed integer arrays lower and higher in the following manner:

lower[i] = arr[i] - k, for every index i where 0 <= i < n
higher[i] = arr[i] + k, for every index i where 0 <= i < n

Unfortunately, Alice lost all three arrays. However, she remembers the integers that were present in the arrays lower and higher, but not the array each integer belonged to. Help Alice and recover the original array.

Given an array nums consisting of 2n integers, where exactly n of the integers were present in lower and the remaining in higher, return the original array arr. In case the answer is not unique, return any valid array.

Note: The test cases are generated such that there exists at least one valid array arr.

Example 1:

Input: nums = [2,10,6,4,8,12]
Output: [3,7,11]
Explanation:
If arr = [3,7,11] and k = 1, we get lower = [2,6,10] and higher = [4,8,12].
Combining lower and higher gives us [2,6,10,4,8,12], which is a permutation of nums.
Another valid possibility is that arr = [5,7,9] and k = 3. In that case, lower = [2,4,6] and higher = [8,10,12].

Example 2:

Input: nums = [1,1,3,3]
Output: [2,2]
Explanation:
If arr = [2,2] and k = 1, we get lower = [1,1] and higher = [3,3].
Combining lower and higher gives us [1,1,3,3], which is equal to nums.
Note that arr cannot be [1,3] because in that case, the only possible way to obtain [1,1,3,3] is with k = 0.
This is invalid since k must be positive.

Example 3:

Input: nums = [5,435]
Output: [220]
Explanation:
The only possible combination is arr = [220] and k = 215. Using them, we get lower = [5] and higher = [435].

Constraints:

2 * n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 10⁹
The test cases are generated such that there exists at least one valid array arr.

Solution: Try all possible k

Sort the array, we know that the smallest number nums[0] is org[0] – k, org[0] + k (nums[0] + 2k) must exist in nums. We try all possible ks. k = (nums[i] – nums[0]) / 2.

Then we iterate the sorted nums array as low, and see whether we can find low + 2k as high using a dynamic hashtable.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> recoverArray(vector<int>& nums) {

const int n = nums.size();

sort(begin(nums), end(nums));

unordered_map<int, int> m;

for (int x : nums) ++m[x];

auto check = [&](int k) -> vector<int> {

vector<int> ans;

unordered_map<int, int> cur(m);

for (int x : nums) {

if (cur[x] == 0) continue;

--cur[x];

if (--cur[x + 2 * k] < 0) return {};

ans.push_back(x + k);

}

return ans;

};

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

if (nums[i] == nums[0] || (nums[i] - nums[0]) & 1) continue;

const int k = (nums[i] - nums[0]) / 2;

vector<int> ans = check(k);

if (!ans.empty()) return ans;

}

return {};

}

};

花花酱 LeetCode 2121. Intervals Between Identical Elements

By zxi on December 26, 2021

You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

Example 1:

Input: arr = [2,1,3,1,2,3,3]
Output: [4,2,7,2,4,4,5]
Explanation:
- Index 0: Another 2 is found at index 4. |0 - 4| = 4
- Index 1: Another 1 is found at index 3. |1 - 3| = 2
- Index 2: Two more 3s are found at indices 5 and 6. |2 - 5| + |2 - 6| = 7
- Index 3: Another 1 is found at index 1. |3 - 1| = 2
- Index 4: Another 2 is found at index 0. |4 - 0| = 4
- Index 5: Two more 3s are found at indices 2 and 6. |5 - 2| + |5 - 6| = 4
- Index 6: Two more 3s are found at indices 2 and 5. |6 - 2| + |6 - 5| = 5

Example 2:

Input: arr = [10,5,10,10]
Output: [5,0,3,4]
Explanation:
- Index 0: Two more 10s are found at indices 2 and 3. |0 - 2| + |0 - 3| = 5
- Index 1: There is only one 5 in the array, so its sum of intervals to identical elements is 0.
- Index 2: Two more 10s are found at indices 0 and 3. |2 - 0| + |2 - 3| = 3
- Index 3: Two more 10s are found at indices 0 and 2. |3 - 0| + |3 - 2| = 4

Constraints:

n == arr.length
1 <= n <= 10⁵
1 <= arr[i] <= 10⁵

Solution: Math / Hashtable + Prefix Sum

For each arr[i], suppose it occurs in the array of total c times, among which k of them are in front of it and c – k – 1 of them are after it. Then the total sum intervals:
(i – j₁) + (i – j₂) + … + (i – j_k) + (j_k+1-i) + (j_k+2-i) + … + (j_c-i)
<=> k * i – sum(j₁~j_k) + sum(j_k+1~j_c) – (c – k – 1) * i

Use a hashtable to store the indies of each unique number in the array and compute the prefix sum for fast range sum query.

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

C++

// Author: Huahua

class Solution {

public:

vector<long long> getDistances(vector<int>& arr) {

const int n = arr.size();

unordered_map<int, vector<long long>> m;

vector<int> pos(n);

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

m[arr[i]].push_back(i);

pos[i] = m[arr[i]].size() - 1;

}

for (auto& [k, idx] : m)

partial_sum(begin(idx), end(idx), begin(idx));

vector<long long> ans(n);

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

const auto& sums = m[arr[i]];

const long long k = pos[i];

const long long c = sums.size();

if (k > 0) ans[i] += k * i - sums[k - 1];

if (k + 1 < c) ans[i] += (sums[c - 1] - sums[k]) - (c - k - 1) * i;

}

return ans;

}

};

花花酱 LeetCode 2120. Execution of All Suffix Instructions Staying in a Grid

By zxi on December 26, 2021

There is an n x n grid, with the top-left cell at (0, 0) and the bottom-right cell at (n - 1, n - 1). You are given the integer n and an integer array startPos where startPos = [start_row, start_col] indicates that a robot is initially at cell (start_row, start_col).

You are also given a 0-indexed string s of length m where s[i] is the i^th instruction for the robot: 'L' (move left), 'R' (move right), 'U' (move up), and 'D' (move down).

The robot can begin executing from any i^th instruction in s. It executes the instructions one by one towards the end of s but it stops if either of these conditions is met:

The next instruction will move the robot off the grid.
There are no more instructions left to execute.

Return an array answer of length m where answer[i] is the number of instructions the robot can execute if the robot begins executing from the i^th instruction in s.

Example 1:

Input: n = 3, startPos = [0,1], s = "RRDDLU"
Output: [1,5,4,3,1,0]
Explanation: Starting from startPos and beginning execution from the i^th instruction:
- 0^th: "RRDDLU". Only one instruction "R" can be executed before it moves off the grid.
- 1^st:  "RDDLU". All five instructions can be executed while it stays in the grid and ends at (1, 1).
- 2^nd:   "DDLU". All four instructions can be executed while it stays in the grid and ends at (1, 0).
- 3^rd:    "DLU". All three instructions can be executed while it stays in the grid and ends at (0, 0).
- 4^th:     "LU". Only one instruction "L" can be executed before it moves off the grid.
- 5^th:      "U". If moving up, it would move off the grid.

Example 2:

Input: n = 2, startPos = [1,1], s = "LURD"
Output: [4,1,0,0]
Explanation:
- 0^th: "LURD".
- 1^st:  "URD".
- 2^nd:   "RD".
- 3^rd:    "D".

Example 3:

Input: n = 1, startPos = [0,0], s = "LRUD"
Output: [0,0,0,0]
Explanation: No matter which instruction the robot begins execution from, it would move off the grid.

Constraints:

m == s.length
1 <= n, m <= 500
startPos.length == 2
0 <= start_row, start_col < n
s consists of 'L', 'R', 'U', and 'D'.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<int> executeInstructions(int n, vector<int>& startPos, string s) {

const int m = s.length();

auto moves = [&](int k) -> int {

int x = startPos[1];

int y = startPos[0];

for (int i = k; i < m; ++i) {

switch (s[i]) {

case 'R': x += 1; break;

case 'D': y += 1; break;

case 'L': x -= 1; break;

case 'U': y -= 1; break;

}

if (x < 0 || x == n || y < 0 || y == n)

return i - k;

}

return m - k;

};

vector<int> ans(m);

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

ans[i] = moves(i);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2115. Find All Possible Recipes from Given Supplies

Solution: Brute Force

C++

花花酱 LeetCode 2114. Maximum Number of Words Found in Sentences

Solution: Count spaces

C++

花花酱 LeetCode 2122. Recover the Original Array

Solution: Try all possible k

C++

花花酱 LeetCode 2121. Intervals Between Identical Elements

Solution: Math / Hashtable + Prefix Sum

C++

花花酱 LeetCode 2120. Execution of All Suffix Instructions Staying in a Grid

Solution: Simulation

C++