Huahua’s Tech Road

花花酱 LeetCode 2126. Destroying Asteroids

By zxi on January 2, 2022

You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the i^th asteroid.

You can arrange for the planet to collide with the asteroids in any arbitrary order. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed.

Return true if all asteroids can be destroyed. Otherwise, return false.

Example 1:

Input: mass = 10, asteroids = [3,9,19,5,21]
Output: true
Explanation: One way to order the asteroids is [9,19,5,3,21]:
- The planet collides with the asteroid with a mass of 9. New planet mass: 10 + 9 = 19
- The planet collides with the asteroid with a mass of 19. New planet mass: 19 + 19 = 38
- The planet collides with the asteroid with a mass of 5. New planet mass: 38 + 5 = 43
- The planet collides with the asteroid with a mass of 3. New planet mass: 43 + 3 = 46
- The planet collides with the asteroid with a mass of 21. New planet mass: 46 + 21 = 67
All asteroids are destroyed.

Example 2:

Input: mass = 5, asteroids = [4,9,23,4]
Output: false
Explanation: 
The planet cannot ever gain enough mass to destroy the asteroid with a mass of 23.
After the planet destroys the other asteroids, it will have a mass of 5 + 4 + 9 + 4 = 22.
This is less than 23, so a collision would not destroy the last asteroid.

Constraints:

1 <= mass <= 10⁵
1 <= asteroids.length <= 10⁵
1 <= asteroids[i] <= 10⁵

Solution: Greedy

Sort asteroids by weight. Note, mass can be very big (10⁵*10⁵), for C++/Java, use long instead of int.

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

C++

// Author: Huahua

class Solution {

public:

bool asteroidsDestroyed(int mass, vector<int>& asteroids) {

long long curr = mass;

sort(begin(asteroids), end(asteroids));

for (int a : asteroids) {

if (curr < a) return false;

curr += a;

}

return true;

}

};

花花酱 LeetCode 2125. Number of Laser Beams in a Bank

By zxi on January 2, 2022

Anti-theft security devices are activated inside a bank. You are given a 0-indexed binary string array bank representing the floor plan of the bank, which is an m x n 2D matrix. bank[i] represents the i^th row, consisting of '0's and '1's. '0' means the cell is empty, while'1' means the cell has a security device.

There is one laser beam between any two security devices if both conditions are met:

The two devices are located on two different rows: r₁ and r₂, where r₁ < r₂.
For each row i where r₁ < i < r₂, there are no security devices in the i^th row.

Laser beams are independent, i.e., one beam does not interfere nor join with another.

Return the total number of laser beams in the bank.

Example 1:

Input: bank = ["011001","000000","010100","001000"]
Output: 8
Explanation: Between each of the following device pairs, there is one beam. In total, there are 8 beams:
 * bank[0][1] -- bank[2][1]
 * bank[0][1] -- bank[2][3]
 * bank[0][2] -- bank[2][1]
 * bank[0][2] -- bank[2][3]
 * bank[0][5] -- bank[2][1]
 * bank[0][5] -- bank[2][3]
 * bank[2][1] -- bank[3][2]
 * bank[2][3] -- bank[3][2]
Note that there is no beam between any device on the 0^th row with any on the 3^rd row.
This is because the 2^nd row contains security devices, which breaks the second condition.

Example 2:

Input: bank = ["000","111","000"]
Output: 0
Explanation: There does not exist two devices located on two different rows.

Constraints:

m == bank.length
n == bank[i].length
1 <= m, n <= 500
bank[i][j] is either '0' or '1'.

Solution: Rule of product

Just need to remember the # of devices of prev non-empty row.
# of beams between two non-empty row equals to row[i] * row[j]
ans += prev * curr

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

C++

// Author: Huahua

class Solution {

public:

int numberOfBeams(vector<string>& bank) {

int ans = 0;

int prev = 0;

for (const string& row : bank)

if (int curr = count(begin(row), end(row), '1')) {

ans += prev * curr;

prev = curr;

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def numberOfBeams(self, bank: List[str]) -> int:

ans = prev = 0

for row in bank:

if curr := row.count('1'):

ans += prev * curr

prev = curr

return ans

花花酱 LeetCode 2124. Check if All A’s Appears Before All B’s

By zxi on January 2, 2022

Given a string s consisting of only the characters 'a' and 'b', return true if every 'a' appears before every 'b' in the string. Otherwise, return false.

Example 1:

Input: s = "aaabbb"
Output: true
Explanation:
The 'a's are at indices 0, 1, and 2, while the 'b's are at indices 3, 4, and 5.
Hence, every 'a' appears before every 'b' and we return true.

Example 2:

Input: s = "abab"
Output: false
Explanation:
There is an 'a' at index 2 and a 'b' at index 1.
Hence, not every 'a' appears before every 'b' and we return false.

Example 3:

Input: s = "bbb"
Output: true
Explanation:
There are no 'a's, hence, every 'a' appears before every 'b' and we return true.

Constraints:

`1 <= s.length <= 100`

`s[i]` is either `'a'` or `'b'`.

Solution: Count bs

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

C++

// Author: Huahua

class Solution {

public:

bool checkString(string s) {

int b = 0;

for (char ch : s) {

b += ch == 'b';

if (ch == 'a' && b) return false;

}

return true;

}

};

花花酱 LeetCode 1912. Design Movie Rental System

By zxi on January 1, 2022

You have a movie renting company consisting of n shops. You want to implement a renting system that supports searching for, booking, and returning movies. The system should also support generating a report of the currently rented movies.

Each movie is given as a 2D integer array entries where entries[i] = [shop_i, movie_i, price_i] indicates that there is a copy of movie movie_i at shop shop_i with a rental price of price_i. Each shop carries at most one copy of a movie movie_i.

The system should support the following functions:

Search: Finds the cheapest 5 shops that have an unrented copy of a given movie. The shops should be sorted by price in ascending order, and in case of a tie, the one with the smaller shop_i should appear first. If there are less than 5 matching shops, then all of them should be returned. If no shop has an unrented copy, then an empty list should be returned.
Rent: Rents an unrented copy of a given movie from a given shop.
Drop: Drops off a previously rented copy of a given movie at a given shop.
Report: Returns the cheapest 5 rented movies (possibly of the same movie ID) as a 2D list res where res[j] = [shop_j, movie_j] describes that the j^th cheapest rented movie movie_j was rented from the shop shop_j. The movies in res should be sorted by price in ascending order, and in case of a tie, the one with the smaller shop_j should appear first, and if there is still tie, the one with the smaller movie_j should appear first. If there are fewer than 5 rented movies, then all of them should be returned. If no movies are currently being rented, then an empty list should be returned.

Implement the MovieRentingSystem class:

MovieRentingSystem(int n, int[][] entries) Initializes the MovieRentingSystem object with n shops and the movies in entries.
List<Integer> search(int movie) Returns a list of shops that have an unrented copy of the given movie as described above.
void rent(int shop, int movie) Rents the given movie from the given shop.
void drop(int shop, int movie) Drops off a previously rented movie at the given shop.
List<List<Integer>> report() Returns a list of cheapest rented movies as described above.

Note: The test cases will be generated such that rent will only be called if the shop has an unrented copy of the movie, and drop will only be called if the shop had previously rented out the movie.

Example 1:

Input
["MovieRentingSystem", "search", "rent", "rent", "report", "drop", "search"]
[[3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]], [1], [0, 1], [1, 2], [], [1, 2], [2]]
Output
[null, [1, 0, 2], null, null, [[0, 1], [1, 2]], null, [0, 1]]

Explanation
MovieRentingSystem movieRentingSystem = new MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]]);
movieRentingSystem.search(1);  // return [1, 0, 2], Movies of ID 1 are unrented at shops 1, 0, and 2. Shop 1 is cheapest; shop 0 and 2 are the same price, so order by shop number.
movieRentingSystem.rent(0, 1); // Rent movie 1 from shop 0. Unrented movies at shop 0 are now [2,3].
movieRentingSystem.rent(1, 2); // Rent movie 2 from shop 1. Unrented movies at shop 1 are now [1].
movieRentingSystem.report();   // return [[0, 1], [1, 2]]. Movie 1 from shop 0 is cheapest, followed by movie 2 from shop 1.
movieRentingSystem.drop(1, 2); // Drop off movie 2 at shop 1. Unrented movies at shop 1 are now [1,2].
movieRentingSystem.search(2);  // return [0, 1]. Movies of ID 2 are unrented at shops 0 and 1. Shop 0 is cheapest, followed by shop 1.

Constraints:

1 <= n <= 3 * 10⁵
1 <= entries.length <= 10⁵
0 <= shop_i < n
1 <= movie_i, price_i <= 10⁴
Each shop carries at most one copy of a movie movie_i.
At most 10⁵ calls in total will be made to search, rent, drop and report.

Solution: Hashtable + TreeSet

We need three containers:
1. movies tracks the {movie -> price} of each shop. This is readonly to get the price of a movie for generating keys for treesets.
2. unrented tracks unrented movies keyed by movie id, value is a treeset ordered by {price, shop}.
3. rented tracks rented movies, a treeset ordered by {price, shop, movie}

Note: By using array<int, 3> we can unpack values like below:
array<int, 3> entries; // {price, shop, movie}
for (const auto [price, shop, moive] : entries)
…

Time complexity:
Init: O(nlogn)
rent / drop: O(logn)
search / report: O(1)

Space complexity: O(n)

C++

// Author: Huahua

class MovieRentingSystem {

public:

MovieRentingSystem(int n, vector<vector<int>>& entries): movies(n) {

for (const auto& e : entries) {

const int shop = e[0];

const int movie = e[1];

const int price = e[2];

movies[shop].emplace(movie, price);

unrented[movie].emplace(price, shop);

}

vector<int> search(int movie) {

vector<int> shops;

for (const auto [price, shop] : unrented[movie]) {

shops.push_back(shop);

if (shops.size() == 5) break;

}

return shops;

}

void rent(int shop, int movie) {

const int price = movies[shop][movie];

unrented[movie].erase({price, shop});

rented.insert({price, shop, movie});

}

void drop(int shop, int movie) {

const int price = movies[shop][movie];

rented.erase({price, shop, movie});

unrented[movie].emplace(price, shop);

}

vector<vector<int>> report() {

vector<vector<int>> ans;

for (const auto& [price, shop, movie] : rented) {

ans.push_back({shop, movie});

if (ans.size() == 5) break;

}

return ans;

}

private:

vector<unordered_map<int, int>> movies; // shop -> {movie -> price}

unordered_map<int, set<pair<int, int>>> unrented; // movie -> {price, shop}

set<array<int, 3>> rented; // {price, shop, movie}

};

花花酱 LeetCode 1998. GCD Sort of an Array

By zxi on December 31, 2021

You are given an integer array nums, and you can perform the following operation any number of times on nums:

Swap the positions of two elements nums[i] and nums[j] if gcd(nums[i], nums[j]) > 1 where gcd(nums[i], nums[j]) is the greatest common divisor of nums[i] and nums[j].

Return true if it is possible to sort nums in non-decreasing order using the above swap method, or false otherwise.

Example 1:

Input: nums = [7,21,3]
Output: true
Explanation: We can sort [7,21,3] by performing the following operations:
- Swap 7 and 21 because gcd(7,21) = 7. nums = [21,7,3]
- Swap 21 and 3 because gcd(21,3) = 3. nums = [3,7,21]

Example 2:

Input: nums = [5,2,6,2]
Output: false
Explanation: It is impossible to sort the array because 5 cannot be swapped with any other element.

Example 3:

Input: nums = [10,5,9,3,15]
Output: true
We can sort [10,5,9,3,15] by performing the following operations:
- Swap 10 and 15 because gcd(10,15) = 5. nums = [15,5,9,3,10]
- Swap 15 and 3 because gcd(15,3) = 3. nums = [3,5,9,15,10]
- Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,10,15]

Constraints:

1 <= nums.length <= 3 * 10⁴
2 <= nums[i] <= 10⁵

Solution: Union-Find

Let nums[j]’s target position be i. In order to put nums[j] to pos i by swapping. nums[i] and nums[j] must be in the same connected component. There is an edge between two numbers if they have gcd > 1.

We union two numbers if their have gcd > 1. However, it will be TLE if we do all pairs . Thus, for each number, we union it with its divisors instead.

Time complexity: O(n²) TLE -> O(sum(sqrt(nums[i]))) <= O(n*sqrt(m))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool gcdSort(vector<int>& nums) {

const int m = *max_element(begin(nums), end(nums));

const int n = nums.size();

vector<int> p(m + 1);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return p[x] == x ? x : (p[x] = find(p[x]));

};

for (int x : nums)

for (int d = 2; d <= sqrt(x); ++d)

if (x % d == 0)

p[find(x)] = p[find(x / d)] = find(d);

vector<int> sorted(nums);

sort(begin(sorted), end(sorted));

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

if (find(sorted[i]) != find(nums[i]))

return false;

return true;

}

};

Huahua's Tech Road

花花酱 LeetCode 2126. Destroying Asteroids

Solution: Greedy

C++

花花酱 LeetCode 2125. Number of Laser Beams in a Bank

Solution: Rule of product

C++

Python3

花花酱 LeetCode 2124. Check if All A’s Appears Before All B’s

1 <= s.length <= 100

s[i] is either 'a' or 'b'.Solution: Count bs

C++

花花酱 LeetCode 1912. Design Movie Rental System

Solution: Hashtable + TreeSet

C++

花花酱 LeetCode 1998. GCD Sort of an Array

Solution: Union-Find

C++

`1 <= s.length <= 100`

`s[i]` is either `'a'` or `'b'`.

Solution: Count bs