Posts published in “Algorithms”

花花酱 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 1846. Maximum Element After Decreasing and Rearranging

By zxi on May 1, 2021

You are given an array of positive integers arr. Perform some operations (possibly none) on arr so that it satisfies these conditions:

The value of the first element in arr must be 1.
The absolute difference between any 2 adjacent elements must be less than or equal to 1. In other words, abs(arr[i] - arr[i - 1]) <= 1 for each i where 1 <= i < arr.length (0-indexed). abs(x) is the absolute value of x.

There are 2 types of operations that you can perform any number of times:

Decrease the value of any element of arr to a smaller positive integer.
Rearrange the elements of arr to be in any order.

Return the maximum possible value of an element in arr after performing the operations to satisfy the conditions.

Example 1:

Input: arr = [2,2,1,2,1]
Output: 2
Explanation: 
We can satisfy the conditions by rearranging arr so it becomes [1,2,2,2,1].
The largest element in arr is 2.

Example 2:

Input: arr = [100,1,1000]
Output: 3
Explanation: 
One possible way to satisfy the conditions is by doing the following:
1. Rearrange arr so it becomes [1,100,1000].
2. Decrease the value of the second element to 2.
3. Decrease the value of the third element to 3.
Now arr = [1,2,3], which satisfies the conditions.
The largest element in arr is 3.

Example 3:

Input: arr = [1,2,3,4,5]
Output: 5
Explanation: The array already satisfies the conditions, and the largest element is 5.

Constraints:

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

Solution: Sort

arr[0] = 1,
arr[i] = min(arr[i], arr[i – 1] + 1)

ans = arr[n – 1]

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

C++

// Author: Huahua

class Solution {

public:

int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {

const int n = arr.size();

sort(begin(arr), end(arr));

arr[0] = 1;

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

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

return arr.back();

}

};

花花酱 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 1827. Minimum Operations to Make the Array Increasing

By zxi on April 17, 2021

You are given an integer array nums (0-indexed). In one operation, you can choose an element of the array and increment it by 1.

For example, if nums = [1,2,3], you can choose to increment nums[1] to make nums = [1,3,3].

Return the minimum number of operations needed to make nums strictly increasing.

An array nums is strictly increasing if nums[i] < nums[i+1] for all 0 <= i < nums.length - 1. An array of length 1 is trivially strictly increasing.

Example 1:

Input: nums = [1,1,1]
Output: 3
Explanation: You can do the following operations:
1) Increment nums[2], so nums becomes [1,1,2].
2) Increment nums[1], so nums becomes [1,2,2].
3) Increment nums[2], so nums becomes [1,2,3].

Example 2:

Input: nums = [1,5,2,4,1]
Output: 14

Example 3:

Input: nums = [8]
Output: 0

Constraints:

1 <= nums.length <= 5000
1 <= nums[i] <= 10⁴

Solution: Track Last

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

C++

class Solution {

public:

int minOperations(vector<int>& nums) {

int ans = 0, last = 0;

for (int x : nums)

if (x <= last)

ans += ++last - x;

else

last = x;

return ans;

}

};

花花酱 LeetCode 1822. Sign of the Product of an Array

By zxi on April 12, 2021

There is a function signFunc(x) that returns:

1 if x is positive.
-1 if x is negative.
0 if x is equal to 0.

You are given an integer array nums. Let product be the product of all values in the array nums.

Return signFunc(product).

Example 1:

Input: nums = [-1,-2,-3,-4,3,2,1]
Output: 1
Explanation: The product of all values in the array is 144, and signFunc(144) = 1

Example 2:

Input: nums = [1,5,0,2,-3]
Output: 0
Explanation: The product of all values in the array is 0, and signFunc(0) = 0

Example 3:

Input: nums = [-1,1,-1,1,-1]
Output: -1
Explanation: The product of all values in the array is -1, and signFunc(-1) = -1

Constraints:

1 <= nums.length <= 1000
-100 <= nums[i] <= 100

Solution: Sign Only

No need to compute the product, only track the sign changes. Flip the sign when encounter a negative number, return 0 if there is any 0 in the array.

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

C++

// Author: Huahua

class Solution {

public:

int arraySign(vector<int>& nums) {

int sign = 1;

for (int x : nums) {

if (x == 0) return 0;

else if (x < 0) sign = -sign;

}

return sign;

}

};