Posts published in “Binary Search”

花花酱 LeetCode 2070. Most Beautiful Item for Each Query

By zxi on November 14, 2021

You are given a 2D integer array items where items[i] = [price_i, beauty_i] denotes the price and beauty of an item respectively.

You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0.

Return an array answer of the same length as queries where answer[j] is the answer to the j^th query.

Example 1:

Input: items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
Output: [2,4,5,5,6,6]
Explanation:
- For queries[0]=1, [1,2] is the only item which has price <= 1. Hence, the answer for this query is 2.
- For queries[1]=2, the items which can be considered are [1,2] and [2,4]. 
  The maximum beauty among them is 4.
- For queries[2]=3 and queries[3]=4, the items which can be considered are [1,2], [3,2], [2,4], and [3,5].
  The maximum beauty among them is 5.
- For queries[4]=5 and queries[5]=6, all items can be considered.
  Hence, the answer for them is the maximum beauty of all items, i.e., 6.

Example 2:

Input: items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
Output: [4]
Explanation: 
The price of every item is equal to 1, so we choose the item with the maximum beauty 4. 
Note that multiple items can have the same price and/or beauty.

Example 3:

Input: items = [[10,1000]], queries = [5]
Output: [0]
Explanation:
No item has a price less than or equal to 5, so no item can be chosen.
Hence, the answer to the query is 0.

Constraints:

1 <= items.length, queries.length <= 10⁵
items[i].length == 2
1 <= price_i, beauty_i, queries[j] <= 10⁹

Solution: Prefix Max + Binary Search

Sort items by price. For each price, use a treemap to store the max beauty of an item whose prices is <= p. Then use binary search to find the max beauty whose price is <= p.

Time complexity: Pre-processing O(nlogn) + query: O(qlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {

sort(begin(items), end(items));

map<int, int> m;

int best = 0;

for (const auto& item : items) {

best = max(best, item[1]);

m[item[0]] = best;

}

vector<int> ans;

for (const int q: queries) {

auto it = m.upper_bound(q);

if (it == begin(m))

ans.push_back(0);

else

ans.push_back(prev(it)->second);

}

return ans;

}

};

花花酱 LeetCode 2064. Minimized Maximum of Products Distributed to Any Store

By zxi on November 7, 2021

You are given an integer n indicating there are n specialty retail stores. There are m product types of varying amounts, which are given as a 0-indexed integer array quantities, where quantities[i] represents the number of products of the i^th product type.

You need to distribute all products to the retail stores following these rules:

A store can only be given at most one product type but can be given any amount of it.
After distribution, each store will be given some number of products (possibly 0). Let x represent the maximum number of products given to any store. You want x to be as small as possible, i.e., you want to minimize the maximum number of products that are given to any store.

Return the minimum possible x.

Example 1:

Input: n = 6, quantities = [11,6]
Output: 3
Explanation: One optimal way is:
- The 11 products of type 0 are distributed to the first four stores in these amounts: 2, 3, 3, 3
- The 6 products of type 1 are distributed to the other two stores in these amounts: 3, 3
The maximum number of products given to any store is max(2, 3, 3, 3, 3, 3) = 3.

Example 2:

Input: n = 7, quantities = [15,10,10]
Output: 5
Explanation: One optimal way is:
- The 15 products of type 0 are distributed to the first three stores in these amounts: 5, 5, 5
- The 10 products of type 1 are distributed to the next two stores in these amounts: 5, 5
- The 10 products of type 2 are distributed to the last two stores in these amounts: 5, 5
The maximum number of products given to any store is max(5, 5, 5, 5, 5, 5, 5) = 5.

Example 3:

Input: n = 1, quantities = [100000]
Output: 100000
Explanation: The only optimal way is:
- The 100000 products of type 0 are distributed to the only store.
The maximum number of products given to any store is max(100000) = 100000.

Constraints:

m == quantities.length
1 <= m <= n <= 10⁵
1 <= quantities[i] <= 10⁵

Solution: Binary Search

Find the smallest max product s.t. all products can be distribute to <= n stores.

Time complexity: O(nlog(max(q)))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minimizedMaximum(int n, vector<int>& quantities) {

int l = 1;

int r = *max_element(begin(quantities), end(quantities)) + 1;

while (l < r) {

int cur = 0;

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

for (int q : quantities)

cur += (q + (m - 1)) / m;

if (cur <= n)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 2055. Plates Between Candles

By zxi on November 3, 2021

There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters '*' and '|' only, where a '*' represents a plate and a '|' represents a candle.

You are also given a 0-indexed 2D integer array queries where queries[i] = [left_i, right_i] denotes the substring s[left_i...right_i] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.

For example, s = "||**||**|*", and a query [3, 8] denotes the substring "*||**|". The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.

Return an integer array answer where answer[i] is the answer to the i^th query.

Example 1:

Input: s = "**|**|***|", queries = [[2,5],[5,9]]
Output: [2,3]
Explanation:
- queries[0] has two plates between candles.
- queries[1] has three plates between candles.

Example 2:

Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
Output: [9,0,0,0,0]
Explanation:
- queries[0] has nine plates between candles.
- The other queries have zero plates between candles.

Constraints:

3 <= s.length <= 10⁵
s consists of '*' and '|' characters.
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= left_i <= right_i < s.length

Solution: Binary Search

Store the indices of all candles into an array idx.

For each query q:
1. Find the left most candle whose index is greater or equal to left as l.
2. Find the left most candle whose index is greater than right, choose the previous candle as r.

[idx[l], idx[r]] is the range that are elements between two candles , there are (idx[r] – idx[l] + 1) elements in total and there are (r – l + 1) candles in the range. So the number of plates is (idx[r] – idx[l] + 1) – (r – l + 1) or (idx[r] – idx[l]) – (r – l)

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

C++

// Author: huahua

class Solution {

public:

vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {

vector<int> idx;

for (size_t i = 0; i < s.size(); ++i)

if (s[i] == '|') idx.push_back(i);

vector<int> ans;

for (const auto& q : queries) {

const int l = lower_bound(begin(idx), end(idx), q[0]) - begin(idx);

const int r = upper_bound(begin(idx), end(idx), q[1]) - begin(idx) - 1;

ans.push_back(l >= r ? 0 : (idx[r] - idx[l]) - (r - l));

}

return ans;

}

};

花花酱 LeetCode 1906. Minimum Absolute Difference Queries

By zxi on August 15, 2021

The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.

For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different.

You are given an integer array nums and the array queries where queries[i] = [l_i, r_i]. For each query i, compute the minimum absolute difference of the subarray nums[l_i...r_i] containing the elements of nums between the 0-based indices l_i and r_i (inclusive).

Return an array ans where ans[i] is the answer to the i^th query.

A subarray is a contiguous sequence of elements in an array.

The value of |x| is defined as:

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

Example 1:

Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
Output: [2,1,4,1]
Explanation: The queries are processed as follows:
- queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.
- queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.
- queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.
- queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.

Example 2:

Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
Output: [-1,1,1,3]
Explanation: The queries are processed as follows:
- queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the
  elements are the same.
- queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.
- queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.
- queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.

Constraints:

2 <= nums.length <= 10⁵
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 10⁴
0 <= l_i < r_i < nums.length

Solution: Binary Search

Since the value range of num is quiet small [1~100], we can store the indices for each value.
[2, 1, 2, 2, 3] => {1: [1], 2: [0, 2, 3]: 3: [4]}.

For each query, we try all possible value b. Check whether b is the query range using binary search, we also keep tracking the previous available value a, ans will be min{b – a}.

Time complexity: O(n + q * 100 * log(n))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {

constexpr int kMax = 100;

const int n = nums.size();

vector<vector<int>> idx(kMax + 1);

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

idx[nums[i]].push_back(i);

vector<int> ans;

for (const auto& q: queries) {

int diff = INT_MAX;

for (int a = 0, b = 1; b <= kMax; ++b) {

auto it = lower_bound(begin(idx[b]), end(idx[b]), q[0]);

if (it == end(idx[b]) || *it > q[1]) continue;

if (a) diff = min(diff, b - a);

a = b;

}

ans.push_back(diff == INT_MAX ? -1 : diff);

}

return ans;

}

};

花花酱 LeetCode 1898. Maximum Number of Removable Characters

By zxi on August 11, 2021

You are given two strings s and p where p is a subsequence of s. You are also given a distinct 0-indexed integer array removable containing a subset of indices of s (s is also 0-indexed).

You want to choose an integer k (0 <= k <= removable.length) such that, after removing k characters from s using the first k indices in removable, p is still a subsequence of s. More formally, you will mark the character at s[removable[i]] for each 0 <= i < k, then remove all marked characters and check if p is still a subsequence.

Return the maximum k you can choose such that p is still a subsequence of s after the removals.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example 1:

Input: s = "abcacb", p = "ab", removable = [3,1,0]
Output: 2
Explanation: After removing the characters at indices 3 and 1, "abcacb" becomes "accb".
"ab" is a subsequence of "accb".
If we remove the characters at indices 3, 1, and 0, "abcacb" becomes "ccb", and "ab" is no longer a subsequence.
Hence, the maximum k is 2.

Example 2:

Input: s = "abcbddddd", p = "abcd", removable = [3,2,1,4,5,6]
Output: 1
Explanation: After removing the character at index 3, "abcbddddd" becomes "abcddddd".
"abcd" is a subsequence of "abcddddd".

Example 3:

Input: s = "abcab", p = "abc", removable = [0,1,2,3,4]
Output: 0
Explanation: If you remove the first index in the array removable, "abc" is no longer a subsequence.

Constraints:

1 <= p.length <= s.length <= 10⁵
0 <= removable.length < s.length
0 <= removable[i] < s.length
p is a subsequence of s.
s and p both consist of lowercase English letters.
The elements in removable are distinct.

Solution: Binary Search + Two Pointers

If we don’t remove any thing, p is a subseq of s, as we keep removing, at some point L, p is no longer a subseq of s. e.g [0:True, 1: True, …, L – 1: True, L: False, L+1: False, …, m:False], this array is monotonic. We can use binary search to find the smallest L such that p is no long a subseq of s. Ans = L – 1.

For each guess, we can use two pointers to check whether p is subseq of removed(s) in O(n).

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

C++

// Author: Huahua

class Solution {

public:

int maximumRemovals(string s, string p, vector<int>& removable) {

const int n = s.length();

const int t = p.length();

const int m = removable.size();

int l = 0;

int r = m + 1;

vector<int> idx(n, INT_MAX);

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

idx[removable[i]] = i;

while (l < r) {

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

int j = 0;

for (int i = 0; i < n && j < t; ++i)

if (idx[i] >= mid && s[i] == p[j]) ++j;

if (j != t)

r = mid;

else

l = mid + 1;

}

// l is the smallest number s.t. p is no longer a subseq of s.

return l - 1;

}

};