Posts tagged as “binary search”

花花酱 LeetCode 1802. Maximum Value at a Given Index in a Bounded Array

By zxi on March 22, 2021

You are given three positive integers n, index and maxSum. You want to construct an array nums (0-indexed) that satisfies the following conditions:

nums.length == n
nums[i] is a positive integer where 0 <= i < n.
abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.
The sum of all the elements of nums does not exceed maxSum.
nums[index] is maximized.

Return nums[index] of the constructed array.

Note that abs(x) equals x if x >= 0, and -x otherwise.

Example 1:

Input: n = 4, index = 2,  maxSum = 6
Output: 2
Explanation: The arrays [1,1,2,1] and [1,2,2,1] satisfy all the conditions. There are no other valid arrays with a larger value at the given index.

Example 2:

Input: n = 6, index = 1,  maxSum = 10
Output: 3

Constraints:

1 <= n <= maxSum <= 10⁹
0 <= index < n

Solution: Binary Search

To maximize nums[index], we can construct an array like this:
[1, 1, 1, …, 1, 2, 3, …, k – 1, k, k – 1, …,3, 2, 1, …., 1, 1, 1]

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

C++

// Author: Huahua

class Solution {

public:

int maxValue(int n, int index, int maxSum) {

int l = 1;

int r = maxSum + 1;

while (l < r) {

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

int64_t t1 = m - index;

int64_t t2 = m - (n - 1 - index);

int64_t s1 = (t1 + m) * (index + 1) / 2;

int64_t s2 = (m + t2) * (n - index) / 2;

if (t1 <= 0) s1 = (1 + m) * m / 2 + (index - m + 1);

if (t2 <= 0) s2 = (1 + m) * m / 2 + (n - index - m);

if (s1 + s2 - m > maxSum)

r = m;

else

l = m + 1;

}

return l - 1;

}

};

花花酱 LeetCode 1760. Minimum Limit of Balls in a Bag

By zxi on February 13, 2021

You are given an integer array nums where the i^th bag contains nums[i] balls. You are also given an integer maxOperations.

You can perform the following operation at most maxOperations times:

Take any bag of balls and divide it into two new bags with a positive number of balls.
- For example, a bag of 5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls.

Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.

Return the minimum possible penalty after performing the operations.

Example 1:

Input: nums = [9], maxOperations = 2
Output: 3
Explanation: 
- Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3].
- Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3].
The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.

Example 2:

Input: nums = [2,4,8,2], maxOperations = 4
Output: 2
Explanation:
- Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
The bag with the most number of balls has 2 balls, so your penalty is 2 an you should return 2.

Example 3:

Input: nums = [7,17], maxOperations = 2
Output: 7

Constraints:

1 <= nums.length <= 10⁵
1 <= maxOperations, nums[i] <= 10⁹

Solution: Binary Search

Find the smallest penalty that requires less or equal ops than max_ops.

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

C++

// Author: Huahua

class Solution {

public:

int minimumSize(vector<int>& nums, int maxOperations) {

int l = 1, r = *max_element(begin(nums), end(nums));

while (l < r) {

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

int count = 0;

for (int x : nums)

count += (x - 1) / m;

if (count <= maxOperations)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 1755. Closest Subsequence Sum

By zxi on February 13, 2021

You are given an integer array nums and an integer goal.

You want to choose a subsequence of nums such that the sum of its elements is the closest possible to goal. That is, if the sum of the subsequence’s elements is sum, then you want to minimize the absolute difference abs(sum - goal).

Return the minimum possible value of abs(sum - goal).

Note that a subsequence of an array is an array formed by removing some elements (possibly all or none) of the original array.

Example 1:

Input: nums = [5,-7,3,5], goal = 6
Output: 0
Explanation: Choose the whole array as a subsequence, with a sum of 6.
This is equal to the goal, so the absolute difference is 0.

Example 2:

Input: nums = [7,-9,15,-2], goal = -5
Output: 1
Explanation: Choose the subsequence [7,-9,-2], with a sum of -4.
The absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum.

Example 3:

Input: nums = [1,2,3], goal = -7
Output: 7

Constraints:

1 <= nums.length <= 40
-10⁷ <= nums[i] <= 10⁷
-10⁹ <= goal <= 10⁹

Solution: Binary Search

Since n is too large to generate sums for all subsets O(2^n), we have to split the array into half, generate two sum sets. O(2^(n/2)).

Then the problem can be reduced to find the closet sum by picking one number (sum) each from two different arrays which can be solved in O(mlogm), where m = 2^(n/2).

So final time complexity is O(n * 2^(n/2))
Space complexity: O(2^(n/2))

C++

// Author: Huahua

class Solution {

public:

int minAbsDifference(vector<int>& nums, int goal) {

const int n = nums.size();

int ans = abs(goal);

vector<int> t1{0}, t2{0};

t1.reserve(1 << (n / 2 + 1));

t2.reserve(1 << (n / 2 + 1));

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

for (int j = t1.size() - 1; j >= 0; --j)

t1.push_back(t1[j] + nums[i]);

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

for (int j = t2.size() - 1; j >= 0; --j)

t2.push_back(t2[j] + nums[i]);

set<int> s2(begin(t2), end(t2));

for (int x : unordered_set<int>(begin(t1), end(t1))) {

auto it = s2.lower_bound(goal - x);

if (it != s2.end())

ans = min(ans, abs(goal - x - *it));

if (it != s2.begin())

ans = min(ans, abs(goal - x - *prev(it)));

}

return ans;

}

};

花花酱 LeetCode 1751. Maximum Number of Events That Can Be Attended II

By zxi on February 6, 2021

You are given an array of events where events[i] = [startDay_i, endDay_i, value_i]. The i^th event starts at startDay_iand ends at endDay_i, and if you attend this event, you will receive a value of value_i. You are also given an integer k which represents the maximum number of events you can attend.

You can only attend one event at a time. If you choose to attend an event, you must attend the entire event. Note that the end day is inclusive: that is, you cannot attend two events where one of them starts and the other ends on the same day.

Return the maximum sum of values that you can receive by attending events.

Example 1:

Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output: 7
Explanation: Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.

Example 2:

Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
Output: 10
Explanation: Choose event 2 for a total value of 10.
Notice that you cannot attend any other event as they overlap, and that you do not have to attend k events.

Example 3:

Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
Output: 9
Explanation: Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.

Constraints:

1 <= k <= events.length
1 <= k * events.length <= 10⁶
1 <= startDay_i <= endDay_i <= 10⁹
1 <= value_i <= 10⁶

Solution: DP + Binary Search

Sort events by ending time.
dp[i][j] := max value we can get by attending at most j events among events[0~i].
dp[i][j] = max(dp[i – 1][j], dp[p][j – 1] + value[i])
p is the first event that does not overlap with the current one.

Time complexity: O(nlogn + nk)
Space complexity: O(nk)

C++

// Author: Huahua

class Solution {

public:

int maxValue(vector<vector<int>>& events, int k) {

const int n = events.size();

vector<vector<int>> dp(n + 1, vector<int>(k + 1));

vector<int> e(n);

auto comp = [](const vector<int>& a, const vector<int>& b) {

return a[1] < b[1];

};

sort(begin(events), end(events), comp);

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

const int p = lower_bound(begin(events),

begin(events) + i,

vector<int>{0, events[i - 1][0], 0},

comp) - begin(events);

for (int j = 1; j <= k; ++j)

dp[i][j] = max(dp[i - 1][j],

dp[p][j - 1] + events[i - 1][2]);

}

return dp[n][k];

}

};

花花酱 LeetCode 1712. Ways to Split Array Into Three Subarrays

By zxi on January 3, 2021

A split of an integer array is good if:

The array is split into three non-empty contiguous subarrays – named left, mid, right respectively from left to right.
The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.

Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 10⁹+ 7.

Example 1:

Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].

Example 2:

Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.

Constraints:

3 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁴

Solution 1: Prefix Sum + Binary Search

We split the array into [0 … i] [i + 1… j] [j + 1 … n – 1]
we can use binary search to find the min and max of j for each i.
s.t. sum(0 ~ i) <= sums(i + 1 ~j) <= sums(j + 1 ~ n – 1)
min is lower_bound(2 * sums(0 ~ i))
max is upper_bound(sums(0 ~ i) + (total – sums(0 ~ i)) / 2)

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

C++

// Author: Huahua

class Solution {

public:

int waysToSplit(vector<int>& nums) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

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

nums[i] += nums[i - 1];

const int total = nums.back();

long ans = 0;

// [0 .. i] [i + 1 ... j] [j + 1 ... n - 1]

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

auto it1 = lower_bound(begin(nums) + i + 1, end(nums), 2 * nums[i]);

auto it2 = upper_bound(begin(nums), end(nums) - 1, nums[i] + (total - nums[i]) / 2);

if (it2 <= it1) continue;

ans += it2 - it1;

}

return ans % kMod;

}

};

Solution 2: Prefix Sum + Two Pointers

The right end of the middle array is in range [j, k – 1] and there are k – j choices.
Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int waysToSplit(vector<int>& nums) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

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

nums[i] += nums[i - 1];

const int total = nums.back();

long ans = 0;

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

j = max(j, i + 1);

while (j < n - 1 && nums[j] < 2 * nums[i]) ++j;

k = max(k, j);

while (k < n - 1 && 2 * nums[k] <= nums[i] + total) ++k;

ans += (k - j);

}

return ans % kMod;

}

};