Posts tagged as “hard”

花花酱 LeetCode 1847. Closest Room

By zxi on May 1, 2021

There is a hotel with n rooms. The rooms are represented by a 2D integer array rooms where rooms[i] = [roomId_i, size_i] denotes that there is a room with room number roomId_i and size equal to size_i. Each roomId_i is guaranteed to be unique.

You are also given k queries in a 2D array queries where queries[j] = [preferred_j, minSize_j]. The answer to the j^th query is the room number id of a room such that:

The room has a size of at least minSize_j, and
abs(id - preferred_j) is minimized, where abs(x) is the absolute value of x.

If there is a tie in the absolute difference, then use the room with the smallest such id. If there is no such room, the answer is -1.

Return an array answer of length k where answer[j] contains the answer to the j^th query.

Example 1:

Input: rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
Output: [3,-1,3]
Explanation: The answers to the queries are as follows:
Query = [3,1]: Room number 3 is the closest as abs(3 - 3) = 0, and its size of 2 is at least 1. The answer is 3.
Query = [3,3]: There are no rooms with a size of at least 3, so the answer is -1.
Query = [5,2]: Room number 3 is the closest as abs(3 - 5) = 2, and its size of 2 is at least 2. The answer is 3.

Example 2:

Input: rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
Output: [2,1,3]
Explanation: The answers to the queries are as follows:
Query = [2,3]: Room number 2 is the closest as abs(2 - 2) = 0, and its size of 3 is at least 3. The answer is 2.
Query = [2,4]: Room numbers 1 and 3 both have sizes of at least 4. The answer is 1 since it is smaller.
Query = [2,5]: Room number 3 is the only room with a size of at least 5. The answer is 3.

Constraints:

n == rooms.length
1 <= n <= 10⁵
k == queries.length
1 <= k <= 10⁴
1 <= roomId_i, preferred_j <= 10⁷
1 <= size_i, minSize_j <= 10⁷

Solution: Off Processing: Sort + Binary Search

Time complexity: O(nlogn + mlogm)
Space complexity: O(n + m)

Sort queries and rooms by size in descending order, only add valid rooms (size >= min_size) to the treeset for binary search.

C++

// Author: Huahua

class Solution {

public:

vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {

const int n = rooms.size();

const int m = queries.size();

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

queries[i].push_back(i);

// Sort queries by size DESC.

sort(begin(queries), end(queries), [](const auto& q1, const auto& q2){

return q1[1] > q2[1];

});

// Sort room by size DESC.

sort(begin(rooms), end(rooms), [](const auto& r1, const auto& r2) {

return r1[1] > r2[1];

});

vector<int> ans(m);

int j = 0;

set<int> ids;

for (const auto& q : queries) {

while (j < n && rooms[j][1] >= q[1])

ids.insert(rooms[j++][0]);

if (ids.empty()) {

ans[q[2]] = -1;

continue;

}

const int id = q[0];

auto it = ids.lower_bound(id);

int id1 = (it != end(ids)) ? *it : INT_MAX;

int id2 = id1;

if (it != begin(ids))

id2 = *prev(it);

ans[q[2]] = abs(id1 - id) < abs(id2 - id) ? id1 : id2;

}

return ans;

}

};

Solution 2: Fenwick Tree

Time complexity: O(nlogS + mlogSlogn)
Space complexity: O(nlogS)

C++

class Solution {

public:

vector<int> closestRoom(vector<vector<int>>& rooms,

vector<vector<int>>& queries) {

S = 0;

for (const auto& r : rooms) S = max(S, r[1]);

for (const auto& r : rooms) update(r[1], r[0]);

vector<int> ans;

for (const auto& q : queries)

ans.push_back(query(q[1], q[0]));

return ans;

}

private:

int S;

void update(int s, int id) {

for (s = S - s + 1; s <= S; s += s & (-s))

tree[s].insert(id);

}

int query(int s, int id) {

int ans = -1;

for (s = S - s + 1; s > 0; s -= s & (-s)) {

if (!tree.count(s)) continue;

int id1 = INT_MAX;

int id2 = INT_MAX;

auto it = tree[s].lower_bound(id);

if (it != end(tree[s])) id1 = *it;

if (it != begin(tree[s])) id2 = *prev(it);

int cid = (abs(id1 - id) < abs(id2 - id)) ? id1 : id2;

if (ans == -1 || abs(cid - id) < abs(ans - id))

ans = cid;

else if (abs(cid - id) == abs(ans - id))

ans = min(ans, cid);

}

return ans;

}

unordered_map<int, set<int>> tree;

};

花花酱 LeetCode 1840. Maximum Building Height

By zxi on April 25, 2021

You want to build n new buildings in a city. The new buildings will be built in a line and are labeled from 1 to n.

However, there are city restrictions on the heights of the new buildings:

The height of each building must be a non-negative integer.
The height of the first building must be 0.
The height difference between any two adjacent buildings cannot exceed 1.

Additionally, there are city restrictions on the maximum height of specific buildings. These restrictions are given as a 2D integer array restrictions where restrictions[i] = [id_i, maxHeight_i] indicates that building id_i must have a height less than or equal to maxHeight_i.

It is guaranteed that each building will appear at most once in restrictions, and building 1 will not be in restrictions.

Return the maximum possible height of the tallest building.

Example 1:

Input: n = 5, restrictions = [[2,1],[4,1]]
Output: 2
Explanation: The green area in the image indicates the maximum allowed height for each building.
We can build the buildings with heights [0,1,2,1,2], and the tallest building has a height of 2.

Example 2:

Input: n = 6, restrictions = []
Output: 5
Explanation: The green area in the image indicates the maximum allowed height for each building.
We can build the buildings with heights [0,1,2,3,4,5], and the tallest building has a height of 5.

Example 3:

Input: n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]

Output: 5

Explanation: The green area in the image indicates the maximum allowed height for each building.

We can build the buildings with heights [0,1,2,3,3,4,4,5,4,3], and the tallest building has a height of 5.

Constraints:

2 <= n <= 10⁹
0 <= restrictions.length <= min(n - 1, 10⁵)
2 <= id_i <= n
id_i is unique.
0 <= maxHeight_i <= 10⁹

Solution: Two Passes

Trim the max heights based on neighboring max heights.
Two passes: left to right, right to left.

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

C++

// Author: Huahua

class Solution {

public:

int maxBuilding(int n, vector<vector<int>>& rs) {

rs.push_back({1, 0});

sort(begin(rs), end(rs));

if (rs.back()[0] != n)

rs.push_back({n, n - 1});

const int m = rs.size();

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

rs[i][1] = min(rs[i][1], rs[i - 1][1] + rs[i][0] - rs[i - 1][0]);

for (int i = m - 2; i >= 0; --i)

rs[i][1] = min(rs[i][1], rs[i + 1][1] - rs[i][0] + rs[i + 1][0]);

int ans = 0;

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

const int l = rs[i - 1][1];

const int r = rs[i][1];

ans = max(ans, max(l, r) + (rs[i][0] - rs[i - 1][0] - abs(l - r)) / 2);

}

return ans;

}

};

花花酱 LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND

By zxi on April 18, 2021

The XOR sum of a list is the bitwise XOR of all its elements. If the list only contains one element, then its XOR sum will be equal to this element.

For example, the XOR sum of [1,2,3,4] is equal to 1 XOR 2 XOR 3 XOR 4 = 4, and the XOR sum of [3] is equal to 3.

You are given two 0-indexed arrays arr1 and arr2 that consist only of non-negative integers.

Consider the list containing the result of arr1[i] AND arr2[j] (bitwise AND) for every (i, j) pair where 0 <= i < arr1.length and 0 <= j < arr2.length.

Return the XOR sum of the aforementioned list.

Example 1:

Input: arr1 = [1,2,3], arr2 = [6,5]
Output: 0
Explanation: The list = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1].
The XOR sum = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0.

Example 2:

Input: arr1 = [12], arr2 = [4]
Output: 4
Explanation: The list = [12 AND 4] = [4]. The XOR sum = 4.

Constraints:

1 <= arr1.length, arr2.length <= 10⁵
0 <= arr1[i], arr2[j] <= 10⁹

Solution: Bit

(a[0] & b[i]) ^ (a[1] & b[i]) ^ … ^ (a[n-1] & b[i]) = (a[0] ^ a[1] ^ … ^ a[n-1]) & b[i]

We can pre compute that xor sum of array A.

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

C++

class Solution {

public:

int getXORSum(vector<int>& A, vector<int>& B) {

int ans = 0;

int xora = 0;

for (int a : A) xora ^= a;

for (int b : B) ans ^= (xora & b);

return ans;

}

};

花花酱 LeetCode 1830. Minimum Number of Operations to Make String Sorted

By zxi on April 18, 2021

You are given a string s (0-indexed). You are asked to perform the following operation on s until you get a sorted string:

Find the largest index i such that 1 <= i < s.length and s[i] < s[i - 1].
Find the largest index j such that i <= j < s.length and s[k] < s[i - 1] for all the possible values of k in the range [i, j] inclusive.
Swap the two characters at indices i - 1 and j.
Reverse the suffix starting at index i.

Return the number of operations needed to make the string sorted. Since the answer can be too large, return it modulo 10⁹ + 7.

Example 1:

Input: s = "cba"
Output: 5
Explanation: The simulation goes as follows:
Operation 1: i=2, j=2. Swap s[1] and s[2] to get s="cab", then reverse the suffix starting at 2. Now, s="cab".
Operation 2: i=1, j=2. Swap s[0] and s[2] to get s="bac", then reverse the suffix starting at 1. Now, s="bca".
Operation 3: i=2, j=2. Swap s[1] and s[2] to get s="bac", then reverse the suffix starting at 2. Now, s="bac".
Operation 4: i=1, j=1. Swap s[0] and s[1] to get s="abc", then reverse the suffix starting at 1. Now, s="acb".
Operation 5: i=2, j=2. Swap s[1] and s[2] to get s="abc", then reverse the suffix starting at 2. Now, s="abc".

Example 2:

Input: s = "aabaa"
Output: 2
Explanation: The simulation goes as follows:
Operation 1: i=3, j=4. Swap s[2] and s[4] to get s="aaaab", then reverse the substring starting at 3. Now, s="aaaba".
Operation 2: i=4, j=4. Swap s[3] and s[4] to get s="aaaab", then reverse the substring starting at 4. Now, s="aaaab".

Example 3:

Input: s = "cdbea"
Output: 63

Example 4:

Input: s = "leetcodeleetcodeleetcode"
Output: 982157772

Constraints:

1 <= s.length <= 3000
s consists only of lowercase English letters.

Solution: Math

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

C++

constexpr int kMod = 1e9 + 7;

int64_t powm(int64_t b, int64_t p) {

int64_t ans = 1;

while (p) {

if (p & 1) ans = (ans * b) % kMod;

b = (b * b) % kMod;

p >>= 1;

}

return ans;

}

class Solution {

public:

int makeStringSorted(string s) {

const int n = s.length();

vector<int64_t> fact(n + 1, 1);

vector<int64_t> inv(n + 1, 1);

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

fact[i] = (fact[i - 1] * i) % kMod;

inv[i] = powm(fact[i], kMod - 2);

}

int64_t ans = 0;

vector<int> freq(26);

for (int i = n - 1; i >= 0; --i) {

const int idx = s[i] - 'a';

++freq[idx];

int64_t cur = accumulate(begin(freq), begin(freq) + idx, 0ll) *

fact[n - i - 1] % kMod;

for (int f : freq)

cur = cur * inv[f] % kMod;

ans = (ans + cur) % kMod;

}

return ans;

}

};

花花酱 LeetCode 1825. Finding MK Average

By zxi on April 13, 2021

You are given two integers, m and k, and a stream of integers. You are tasked to implement a data structure that calculates the MKAverage for the stream.

The MKAverage can be calculated using these steps:

If the number of the elements in the stream is less than m you should consider the MKAverage to be -1. Otherwise, copy the last m elements of the stream to a separate container.
Remove the smallest k elements and the largest k elements from the container.
Calculate the average value for the rest of the elements rounded down to the nearest integer.

Implement the MKAverage class:

MKAverage(int m, int k) Initializes the MKAverage object with an empty stream and the two integers m and k.
void addElement(int num) Inserts a new element num into the stream.
int calculateMKAverage() Calculates and returns the MKAverage for the current stream rounded down to the nearest integer.

Example 1:

Input
["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]
[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]
Output
[null, null, null, -1, null, 3, null, null, null, 5]
Explanation MKAverage obj = new MKAverage(3, 1); obj.addElement(3); // current elements are [3] obj.addElement(1); // current elements are [3,1] obj.calculateMKAverage(); // return -1, because m = 3 and only 2 elements exist. obj.addElement(10); // current elements are [3,1,10] obj.calculateMKAverage(); // The last 3 elements are [3,1,10]. // After removing smallest and largest 1 element the container will be [3]. // The average of [3] equals 3/1 = 3, return 3 obj.addElement(5); // current elements are [3,1,10,5] obj.addElement(5); // current elements are [3,1,10,5,5] obj.addElement(5); // current elements are [3,1,10,5,5,5] obj.calculateMKAverage(); // The last 3 elements are [5,5,5]. // After removing smallest and largest 1 element the container will be [5]. // The average of [5] equals 5/1 = 5, return 5

Constraints:

3 <= m <= 10⁵
1 <= k*2 < m
1 <= num <= 10⁵
At most 10⁵ calls will be made to addElement and calculateMKAverage.

**Solution 1: Multiset * 3**

Use three multiset to track the left part (smallest k elements), right part (largest k elements) and mid (middle part of m – 2*k elements).

Time complexity: addElememt: O(logn), average: O(1)
Space complexity: O(n)

C++

class MKAverage {

public:

MKAverage(int m, int k):

sum(0), m(m), k(k), n(m - 2*k) {}

void addElement(int num) {

if (q.size() == m) {

remove(q.front());

q.pop();

}

q.push(num);

add(num);

}

int calculateMKAverage() {

return (q.size() < m) ? -1 : sum / n;

}

private:

void add(int x) {

left.insert(x);

if (left.size() > k) {

auto it = prev(end(left));

sum += *it;

mid.insert(*it);

left.erase(it);

}

if (mid.size() > n) {

auto it = prev(end(mid));

sum -= *it;

right.insert(*it);

mid.erase(it);

}

void remove(int x) {

if (x <= *rbegin(left)) {

left.erase(left.find(x));

} else if (x <= *rbegin(mid)) {

sum -= x;

mid.erase(mid.find(x));

} else {

right.erase(right.find(x));

}

if (left.size() < k) {

auto it = begin(mid);

sum -= *it;

left.insert(*it);

mid.erase(it);

}

if (mid.size() < n) {

auto it = begin(right);

sum += *it;

mid.insert(*it);

right.erase(it);

}

queue<int> q;

multiset<int> left, mid, right;

long sum;

const int m;

const int k;

const int n;

};