Posts tagged as “medium”

花花酱 LeetCode 2070. Most Beautiful Item for Each Query

By zxi on November 14, 2021

You are given a 2D integer array items where items[i] = [price_i, beauty_i] denotes the price and beauty of an item respectively.

You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0.

Return an array answer of the same length as queries where answer[j] is the answer to the j^th query.

Example 1:

Input: items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
Output: [2,4,5,5,6,6]
Explanation:
- For queries[0]=1, [1,2] is the only item which has price <= 1. Hence, the answer for this query is 2.
- For queries[1]=2, the items which can be considered are [1,2] and [2,4]. 
  The maximum beauty among them is 4.
- For queries[2]=3 and queries[3]=4, the items which can be considered are [1,2], [3,2], [2,4], and [3,5].
  The maximum beauty among them is 5.
- For queries[4]=5 and queries[5]=6, all items can be considered.
  Hence, the answer for them is the maximum beauty of all items, i.e., 6.

Example 2:

Input: items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
Output: [4]
Explanation: 
The price of every item is equal to 1, so we choose the item with the maximum beauty 4. 
Note that multiple items can have the same price and/or beauty.

Example 3:

Input: items = [[10,1000]], queries = [5]
Output: [0]
Explanation:
No item has a price less than or equal to 5, so no item can be chosen.
Hence, the answer to the query is 0.

Constraints:

1 <= items.length, queries.length <= 10⁵
items[i].length == 2
1 <= price_i, beauty_i, queries[j] <= 10⁹

Solution: Prefix Max + Binary Search

Sort items by price. For each price, use a treemap to store the max beauty of an item whose prices is <= p. Then use binary search to find the max beauty whose price is <= p.

Time complexity: Pre-processing O(nlogn) + query: O(qlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {

sort(begin(items), end(items));

map<int, int> m;

int best = 0;

for (const auto& item : items) {

best = max(best, item[1]);

m[item[0]] = best;

}

vector<int> ans;

for (const int q: queries) {

auto it = m.upper_bound(q);

if (it == begin(m))

ans.push_back(0);

else

ans.push_back(prev(it)->second);

}

return ans;

}

};

花花酱 LeetCode 2069. Walking Robot Simulation II

By zxi on November 13, 2021

A width x height grid is on an XY-plane with the bottom-left cell at (0, 0) and the top-right cell at (width - 1, height - 1). The grid is aligned with the four cardinal directions ("North", "East", "South", and "West"). A robot is initially at cell (0, 0) facing direction "East".

The robot can be instructed to move for a specific number of steps. For each step, it does the following.

Attempts to move forward one cell in the direction it is facing.
If the cell the robot is moving to is out of bounds, the robot instead turns 90 degrees counterclockwise and retries the step.

After the robot finishes moving the number of steps required, it stops and awaits the next instruction.

Implement the Robot class:

Robot(int width, int height) Initializes the width x height grid with the robot at (0, 0) facing "East".
void move(int num) Instructs the robot to move forward num steps.
int[] getPos() Returns the current cell the robot is at, as an array of length 2, [x, y].
String getDir() Returns the current direction of the robot, "North", "East", "South", or "West".

Example 1:

Input
["Robot", "move", "move", "getPos", "getDir", "move", "move", "move", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
Output
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

Explanation
Robot robot = new Robot(6, 3); // Initialize the grid and the robot at (0, 0) facing East.
robot.move(2);  // It moves two steps East to (2, 0), and faces East.
robot.move(2);  // It moves two steps East to (4, 0), and faces East.
robot.getPos(); // return [4, 0]
robot.getDir(); // return "East"
robot.move(2);  // It moves one step East to (5, 0), and faces East.
                // Moving the next step East would be out of bounds, so it turns and faces North.
                // Then, it moves one step North to (5, 1), and faces North.
robot.move(1);  // It moves one step North to (5, 2), and faces North (not West).
robot.move(4);  // Moving the next step North would be out of bounds, so it turns and faces West.
                // Then, it moves four steps West to (1, 2), and faces West.
robot.getPos(); // return [1, 2]
robot.getDir(); // return "West"

Constraints:

2 <= width, height <= 100
1 <= num <= 10⁵
At most 10⁴ calls in total will be made to move, getPos, and getDir.

Solution: Simulation

Note num >> w + h, when we hit a wall, we will always follow the boundary afterwards. We can do num %= p to reduce steps, where p = ((w – 1) + (h – 1)) * 2

Time complexity: move: O(min(num, w+h))
Space complexity: O(1)

C++

// Author: Huahua

constexpr static int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

const static vector<string> kNames{"East", "North", "West", "South"};

class Robot {

public:

Robot(int width, int height): w_(width), h_(height) {

p_ = ((w_ - 1) + (h_ - 1)) * 2;

}

void move(int num) {

while (num) {

int tx = x_ + dirs[d_][0];

int ty = y_ + dirs[d_][1];

if (tx < 0 || tx >= w_ || ty < 0 || ty >= h_) {

if (num > p_) num %= p_;

if (num) d_ = (d_ + 1) % 4;

continue;

}

x_ = tx;

y_ = ty;

--num;

}

vector<int> getPos() { return {x_, y_}; }

string getDir() { return kNames[d_]; }

private:

int w_;

int h_;

int d_{0}; // 0: E, 1: N, 2: W, 3: S

int x_{0};

int y_{0};

int p_{0};

};

花花酱 LeetCode 2064. Minimized Maximum of Products Distributed to Any Store

By zxi on November 7, 2021

You are given an integer n indicating there are n specialty retail stores. There are m product types of varying amounts, which are given as a 0-indexed integer array quantities, where quantities[i] represents the number of products of the i^th product type.

You need to distribute all products to the retail stores following these rules:

A store can only be given at most one product type but can be given any amount of it.
After distribution, each store will be given some number of products (possibly 0). Let x represent the maximum number of products given to any store. You want x to be as small as possible, i.e., you want to minimize the maximum number of products that are given to any store.

Return the minimum possible x.

Example 1:

Input: n = 6, quantities = [11,6]
Output: 3
Explanation: One optimal way is:
- The 11 products of type 0 are distributed to the first four stores in these amounts: 2, 3, 3, 3
- The 6 products of type 1 are distributed to the other two stores in these amounts: 3, 3
The maximum number of products given to any store is max(2, 3, 3, 3, 3, 3) = 3.

Example 2:

Input: n = 7, quantities = [15,10,10]
Output: 5
Explanation: One optimal way is:
- The 15 products of type 0 are distributed to the first three stores in these amounts: 5, 5, 5
- The 10 products of type 1 are distributed to the next two stores in these amounts: 5, 5
- The 10 products of type 2 are distributed to the last two stores in these amounts: 5, 5
The maximum number of products given to any store is max(5, 5, 5, 5, 5, 5, 5) = 5.

Example 3:

Input: n = 1, quantities = [100000]
Output: 100000
Explanation: The only optimal way is:
- The 100000 products of type 0 are distributed to the only store.
The maximum number of products given to any store is max(100000) = 100000.

Constraints:

m == quantities.length
1 <= m <= n <= 10⁵
1 <= quantities[i] <= 10⁵

Solution: Binary Search

Find the smallest max product s.t. all products can be distribute to <= n stores.

Time complexity: O(nlog(max(q)))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minimizedMaximum(int n, vector<int>& quantities) {

int l = 1;

int r = *max_element(begin(quantities), end(quantities)) + 1;

while (l < r) {

int cur = 0;

int m = l + (r - l) / 2;

for (int q : quantities)

cur += (q + (m - 1)) / m;

if (cur <= n)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 2063. Vowels of All Substrings

By zxi on November 7, 2021

Given a string word, return the sum of the number of vowels ('a', 'e', 'i', 'o', and 'u') in every substring of word.

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

Note: Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.

Example 1:

Input: word = "aba"
Output: 6
Explanation: 
All possible substrings are: "a", "ab", "aba", "b", "ba", and "a".
- "b" has 0 vowels in it
- "a", "ab", "ba", and "a" have 1 vowel each
- "aba" has 2 vowels in it
Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6.

Example 2:

Input: word = "abc"
Output: 3
Explanation: 
All possible substrings are: "a", "ab", "abc", "b", "bc", and "c".
- "a", "ab", and "abc" have 1 vowel each
- "b", "bc", and "c" have 0 vowels each
Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3.

Example 3:

Input: word = "ltcd"
Output: 0
Explanation: There are no vowels in any substring of "ltcd".

Example 4:

Input: word = "noosabasboosa"
Output: 237
Explanation: There are a total of 237 vowels in all the substrings.

Constraints:

1 <= word.length <= 10⁵
word consists of lowercase English letters.

Solution: Math

For a vowel at index i,
we can choose 0, 1, … i as starting point
choose i, i+1, …, n -1 as end point.
There will be (i – 0 + 1) * (n – 1 – i + 1) possible substrings that contains word[i].

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

C++

class Solution {

public:

long long countVowels(string word) {

const long long n = word.size();

long long ans = 0;

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

switch (word[i]) {

case 'a':

case 'e':

case 'i':

case 'o':

case 'u':

ans += (i + 1) * (n - 1 - i + 1);

break;

}

return ans;

}

};

花花酱 LeetCode 2059. Minimum Operations to Convert Number

By zxi on November 4, 2021

You are given a 0-indexed integer array nums containing distinct numbers, an integer start, and an integer goal. There is an integer x that is initially set to start, and you want to perform operations on x such that it is converted to goal. You can perform the following operation repeatedly on the number x:

If 0 <= x <= 1000, then for any index i in the array (0 <= i < nums.length), you can set x to any of the following:

x + nums[i]
x - nums[i]
x ^ nums[i] (bitwise-XOR)

Note that you can use each nums[i] any number of times in any order. Operations that set x to be out of the range 0 <= x <= 1000 are valid, but no more operations can be done afterward.

Return the minimum number of operations needed to convert x = start into goal, and -1 if it is not possible.

Example 1:

Input: nums = [1,3], start = 6, goal = 4
Output: 2
Explanation:
We can go from 6 → 7 → 4 with the following 2 operations.
- 6 ^ 1 = 7
- 7 ^ 3 = 4

Example 2:

Input: nums = [2,4,12], start = 2, goal = 12
Output: 2
Explanation:
We can go from 2 → 14 → 12 with the following 2 operations.
- 2 + 12 = 14
- 14 - 2 = 12

Example 3:

Input: nums = [3,5,7], start = 0, goal = -4
Output: 2
Explanation:
We can go from 0 → 3 → -4 with the following 2 operations. 
- 0 + 3 = 3
- 3 - 7 = -4
Note that the last operation sets x out of the range 0 <= x <= 1000, which is valid.

Example 4:

Input: nums = [2,8,16], start = 0, goal = 1
Output: -1
Explanation:
There is no way to convert 0 into 1.

Example 5:

Input: nums = [1], start = 0, goal = 3

Output: 3

Explanation:

We can go from 0 → 1 → 2 → 3 with the following 3 operations.

- 0 + 1 = 1

- 1 + 1 = 2

- 2 + 1 = 3

Constraints:

1 <= nums.length <= 1000
-10⁹ <= nums[i], goal <= 10⁹
0 <= start <= 1000
start != goal
All the integers in nums are distinct.

Solution: BFS

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

C++

// Author: Huahua

class Solution {

public:

int minimumOperations(vector<int>& nums, int start, int goal) {

vector<int> seen(1001);

queue<int> q{{start}};

for (int ans = 1, s = 1; !q.empty(); ++ans, s = q.size()) {

while (s--) {

int x = q.front(); q.pop();

for (int n : nums)

for (int t : {x + n, x - n, x ^ n})

if (t == goal)

return ans;

else if (t < 0 || t > 1000 || seen[t]++)

continue;

else

q.push(t);

}

return -1;

}

};