Posts published in “Binary Search”

花花酱 LeetCode 1889. Minimum Space Wasted From Packaging

By zxi on August 9, 2021

You have n packages that you are trying to place in boxes, one package in each box. There are m suppliers that each produce boxes of different sizes (with infinite supply). A package can be placed in a box if the size of the package is less than or equal to the size of the box.

The package sizes are given as an integer array packages, where packages[i] is the size of the i^th package. The suppliers are given as a 2D integer array boxes, where boxes[j] is an array of box sizes that the j^th supplier produces.

You want to choose a single supplier and use boxes from them such that the total wasted space is minimized. For each package in a box, we define the space wasted to be size of the box - size of the package. The total wasted space is the sum of the space wasted in all the boxes.

For example, if you have to fit packages with sizes [2,3,5] and the supplier offers boxes of sizes [4,8], you can fit the packages of size-2 and size-3 into two boxes of size-4 and the package with size-5 into a box of size-8. This would result in a waste of (4-2) + (4-3) + (8-5) = 6.

Return the minimum total wasted space by choosing the box supplier optimally, or -1 if it is impossible to fit all the packages inside boxes. Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: packages = [2,3,5], boxes = [[4,8],[2,8]]
Output: 6
Explanation: It is optimal to choose the first supplier, using two size-4 boxes and one size-8 box.
The total waste is (4-2) + (4-3) + (8-5) = 6.

Example 2:

Input: packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
Output: -1
Explanation: There is no box that the package of size 5 can fit in.

Example 3:

Input: packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
Output: 9
Explanation: It is optimal to choose the third supplier, using two size-5 boxes, two size-10 boxes, and two size-14 boxes.
The total waste is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9.

Constraints:

n == packages.length
m == boxes.length
1 <= n <= 10⁵
1 <= m <= 10⁵
1 <= packages[i] <= 10⁵
1 <= boxes[j].length <= 10⁵
1 <= boxes[j][k] <= 10⁵
sum(boxes[j].length) <= 10⁵
The elements in boxes[j] are distinct.

Solution: Greedy + Binary Search

sort packages and boxes
for each box find all (unpacked) packages that are smaller or equal to itself.

Time complexity: O(nlogn) + O(mlogm) + O(mlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {

constexpr int kMod = 1e9 + 7;

const int n = packages.size();

sort(begin(packages), end(packages));

const auto bit = begin(packages);

const auto eit = end(packages);

long sum = accumulate(bit, eit, 0L);

long ans = LLONG_MAX;

for (auto& box : boxes) {

sort(begin(box), end(box));

int l = 0;

long cur = 0;

for (long b : box) {

int r = upper_bound(bit + l, eit, b) - bit;

cur += b * (r - l);

if (r == n) {

ans = min(ans, cur - sum);

break;

}

l = r;

}

return ans == LLONG_MAX ? -1 : ans % kMod;

}

};

花花酱 LeetCode 1871. Jump Game VII

By zxi on August 5, 2021

You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:

i + minJump <= j <= min(i + maxJump, s.length - 1), and
s[j] == '0'.

Return true if you can reach index s.length - 1 in s, or false otherwise.

Example 1:

Input: s = "011010", minJump = 2, maxJump = 3
Output: true
Explanation:
In the first step, move from index 0 to index 3. 
In the second step, move from index 3 to index 5.

Example 2:

Input: s = "01101110", minJump = 2, maxJump = 3
Output: false

Constraints:

2 <= s.length <= 10⁵
s[i] is either '0' or '1'.
s[0] == '0'
1 <= minJump <= maxJump < s.length

Solution 1: TreeSet /Dequq + Binary Search

Maintain a set of reachable indices so far, for each ‘0’ index check whether it can be reached from any of the elements in the set.

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

C++/set

// Author: Huahua, 296 ms, 59.7MB

class Solution {

public:

bool canReach(string s, int minJump, int maxJump) {

if (s.back() != '0') return false;

const int n = s.length();

set<int> seen{0};

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

if (s[i] != '0') continue;

while (!seen.empty() && (*seen.begin()) + maxJump < i)

seen.erase(seen.begin());

auto it = seen.upper_bound(i - minJump);

if (it != seen.begin() && *prev(it) + minJump <= i)

seen.insert(i);

}

return seen.count(n - 1);

}

};

C++/deque

// Author: Huahua, 280 ms, 19MB

class Solution {

public:

bool canReach(string s, int minJump, int maxJump) {

if (s.back() != '0') return false;

const int n = s.length();

deque<int> seen{0};

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

if (s[i] != '0') continue;

while (!seen.empty() && (seen.front()) + maxJump < i)

seen.pop_front();

auto it = upper_bound(begin(seen), end(seen), i - minJump);

if (it != seen.begin() && *prev(it) + minJump <= i)

seen.push_back(i);

}

return seen.back() == n - 1;

}

};

Solution 2: Queue

Same idea, we can replace the deque in sol1 with a queue, and only check the smallest element in the queue.

C++/set

// Author: Huahua, 56ms, 19.2MB

class Solution {

public:

bool canReach(string s, int minJump, int maxJump) {

if (s.back() != '0') return false;

const int n = s.length();

queue<int> q{{0}};

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

if (s[i] != '0') continue;

while (!q.empty() && q.front() + maxJump < i)

q.pop();

if (!q.empty() && q.front() + minJump <= i)

q.push(i);

}

return q.back() == n - 1;

}

};

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

花花酱 LeetCode 1870. Minimum Speed to Arrive on Time

By zxi on August 5, 2021

You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take n trains in sequential order. You are also given an integer array dist of length n, where dist[i] describes the distance (in kilometers) of the i^th train ride.

Each train can only depart at an integer hour, so you may need to wait in between each train ride.

For example, if the 1^st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2^nd train ride at the 2 hour mark.

Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.

Tests are generated such that the answer will not exceed 10⁷ and hour will have at most two digits after the decimal point.

Example 1:

Input: dist = [1,3,2], hour = 6
Output: 1
Explanation: At speed 1:
- The first train ride takes 1/1 = 1 hour.
- Since we are already at an integer hour, we depart immediately at the 1 hour mark. The second train takes 3/1 = 3 hours.
- Since we are already at an integer hour, we depart immediately at the 4 hour mark. The third train takes 2/1 = 2 hours.
- You will arrive at exactly the 6 hour mark.

Example 2:

Input: dist = [1,3,2], hour = 2.7
Output: 3
Explanation: At speed 3:
- The first train ride takes 1/3 = 0.33333 hours.
- Since we are not at an integer hour, we wait until the 1 hour mark to depart. The second train ride takes 3/3 = 1 hour.
- Since we are already at an integer hour, we depart immediately at the 2 hour mark. The third train takes 2/3 = 0.66667 hours.
- You will arrive at the 2.66667 hour mark.

Example 3:

Input: dist = [1,3,2], hour = 1.9
Output: -1
Explanation: It is impossible because the earliest the third train can depart is at the 2 hour mark.

Constraints:

n == dist.length
1 <= n <= 10⁵
1 <= dist[i] <= 10⁵
1 <= hour <= 10⁹
There will be at most two digits after the decimal point in hour.

Solution: Binary Search

l = speed_min=1
r = speed_max+1 = 1e7 + 1

Find the min valid speed m such that t(m) <= hour.

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

C++

// Author: Huahua

class Solution {

public:

int minSpeedOnTime(vector<int>& dist, double hour) {

constexpr int kMax = 1e7 + 1;

const int n = dist.size();

int l = 1;

int r = kMax;

while (l < r) {

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

int t = 0;

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

t += (dist[i] + m - 1) / m;

if (t + dist.back() * 1.0 / m <= hour)

r = m;

else

l = m + 1;

}

return l == kMax ? -1 : l;

}

};

花花酱 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 1818. Minimum Absolute Sum Difference

By zxi on April 6, 2021

You are given two positive integer arrays nums1 and nums2, both of length n.

The absolute sum difference of arrays nums1 and nums2 is defined as the sum of |nums1[i] - nums2[i]| for each 0 <= i < n (0-indexed).

You can replace at most one element of nums1 with any other element in nums1 to minimize the absolute sum difference.

Return the minimum absolute sum difference after replacing at most oneelement in the array nums1. Since the answer may be large, return it modulo 10⁹ + 7.

|x| is defined as:

x if x >= 0, or
-x if x < 0.

Example 1:

Input: nums1 = [1,7,5], nums2 = [2,3,5]
Output: 3
Explanation: There are two possible optimal solutions:
- Replace the second element with the first: [1,7,5] => [1,1,5], or
- Replace the second element with the third: [1,7,5] => [1,5,5].
Both will yield an absolute sum difference of |1-2| + (|1-3| or |5-3|) + |5-5| = 3.

Example 2:

Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
Output: 0
Explanation: nums1 is equal to nums2 so no replacement is needed. This will result in an 
absolute sum difference of 0.

Example 3:

Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
Output: 20
Explanation: Replace the first element with the second: [1,10,4,4,2,7] => [10,10,4,4,2,7].
This yields an absolute sum difference of |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20

Constraints:

n == nums1.length
n == nums2.length
1 <= n <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁵

Solution: Binary Search

Greedy won’t work, e.g. finding the max diff pair and replace it. Counter example:
nums1 = [7, 5], nums2 = [1, -2]
pair1 = abs(7 – 1) = 6
pair2 = abs(5 – (-2)) = 7
If we replace 5 with 7, we got pair2′ = abs(7 – (-2)) = 9 > 7.

Every pair of numbers can be the candidate, we just need to find the closest number for each nums2[i].

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

C++

class Solution {

public:

int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {

constexpr int kMod = 1e9 + 7;

const int n = nums1.size();

long ans = 0;

int gain = 0;

set<int> s(begin(nums1), end(nums1));

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

const int diff = abs(nums1[i] - nums2[i]);

ans += diff;

if (diff <= gain) continue;

auto it = s.lower_bound(nums2[i]);

if (it != s.end())

gain = max(gain, diff - abs(*it - nums2[i]));

if (it != s.begin())

gain = max(gain, diff - abs(*prev(it) - nums2[i]));

}

return (ans - gain) % kMod;

}

};