Posts tagged as “medium”

花花酱 LeetCode 1333. Filter Restaurants by Vegan-Friendly, Price and Distance

By zxi on January 26, 2020

Given the array restaurants where restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]. You have to filter the restaurants using three filters.

The veganFriendly filter will be either true (meaning you should only include restaurants with veganFriendly_i 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 veganFriendly_i 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 <= id_i, rating_i, price_i, distance_i<= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendly_i and veganFriendly are 0 or 1.
All id_i are distinct.

Solution

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

C++

// Author: Huahua

class Solution {

public:

vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {

vector<pair<int, int>> rs; // <rating, id>

for (auto& r : restaurants)

if ((!veganFriendly || veganFriendly && r[2]) && r[3] <= maxPrice && r[4] <= maxDistance)

rs.emplace_back(r[1], r[0]);

sort(rbegin(rs), rend(rs));

vector<int> ans;

for (const auto& r : rs) ans.push_back(r.second);

return ans;

}

};

花花酱 LeetCode 1329. Sort the Matrix Diagonally

By zxi on January 26, 2020

Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

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]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100

Solution: HashTable

Collect each diagonal’s (keyed by i – j) elements into an array and sort it separately.
If we offset the key by n, e.g. i – j + n, we can use an array instead of a hashtable.

Time complexity: O(m*n + (m+n) * (m+n) * log(m + n))) = (n^2*logn)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {

const int m = mat.size();

const int n = mat[0].size();

vector<deque<int>> qs(m + n);

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

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

qs[i - j + n].push_back(mat[i][j]);

for (auto& q : qs)

sort(begin(q), end(q));

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

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

mat[i][j] = qs[i - j + n].front();

qs[i - j + n].pop_front();

}

return mat;

}

};

花花酱 LeetCode 1328. Break a Palindrome

By zxi on January 26, 2020

Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn’t a palindrome.

After doing so, return the final string. If there is no way to do so, return the empty string.

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"

Example 2:

Input: palindrome = "a"
Output: ""

Constraints:

1 <= palindrome.length <= 1000
palindrome consists of only lowercase English letters.

Solution: Greedy

For the first half of the string, replace the first non ‘a’ character to ‘a’.

e.g. abcdcba => aacdcba

If not found which means the the entire string is ‘a’ expect the middle one if the length is odd, like aa or aba, replace the last character to ‘b’.

aa => ab
aba => abb

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

C++

// Author: Huahua

class Solution {

public:

string breakPalindrome(string palindrome) {

const int n = palindrome.length();

if (n == 1) return "";

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

if (palindrome[i] != 'a') {

palindrome[i] = 'a';

return palindrome;

}

palindrome.back() = 'b';

return palindrome;

}

};

花花酱 LeetCode 1325. Delete Leaves With a Given Value

By zxi on January 20, 2020

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 it’s parent node becomes a leaf node and has the value target, it should also be deleted (you need to continue doing that until you can’t).

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.

Example 4:

Input: root = [1,1,1], target = 1
Output: []

Example 5:

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

Constraints:

1 <= target <= 1000
Each tree has at most 3000 nodes.
Each node’s value is between [1, 1000].

Solution: Recursion

Post-order traversal

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* removeLeafNodes(TreeNode* root, int target) {

if (!root) return nullptr;

root->left = removeLeafNodes(root->left, target);

root->right = removeLeafNodes(root->right, target);

return root->left || root->right || root->val != target

? root : nullptr;

}

};

花花酱 LeetCode 1319. Number of Operations to Make Network Connected

By zxi on January 11, 2020

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

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’s 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.

Example 4:

Input: n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
Output: 0

Constraints:

1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
There are no repeated connections.
No two computers are connected by more than one cable.

Solution 1: Union-Find

Time complexity: O(V+E)
Space complexity: O(V)

C++

// Author: Huahua

class Solution {

public:

int makeConnected(int n, vector<vector<int>>& connections) {

if (connections.size() < n - 1) return -1;

vector<int> p(n);

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

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

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

};

for (const auto& c : connections)

p[find(c[0])] = find(c[1]);

unordered_set<int> s;

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

s.insert(find(i));

return s.size() - 1;

}

};

Solution 2: DFS

Time complexity: O(V+E)
Space complexity: O(V+E)

C++

// Author: Huahua

class Solution {

public:

int makeConnected(int n, vector<vector<int>>& connections) {

if (connections.size() < n - 1) return -1;

vector<vector<int>> g(n);

for (const auto& c : connections) {

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

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

}

vector<int> seen(n);

int count = 0;

function<void(int)> dfs = [&](int cur) {

for (int nxt : g[cur])

if (!seen[nxt]++) dfs(nxt);

};

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

if (!seen[i]++ && ++count)

dfs(i);

return count - 1;

}

};