Posts published in “Binary Search”

花花酱 LeetCode 69. Sqrt(x)

By zxi on November 26, 2021

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

0 <= x <= 2³¹ - 1

Solution 1: Binary Search

Find the smallest l such that l * l > x, sqrt(x) = l – 1.

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

C++

// Author: Huahua

class Solution {

public:

int mySqrt(int x) {

unsigned l = 1;

unsigned r = 1u + x;

while (l < r) {

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

if (m > x / m) {

r = m;

} else {

l = m + 1;

}

return l - 1;

}

};

花花酱 LeetCode 34. Find First and Last Position of Element in Sorted Array

By zxi on November 26, 2021

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
nums is a non-decreasing array.
-10⁹ <= target <= 10⁹

Solution: Binary Search

Use lower_bound to find first
Use upper_bound to find last + 1

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

C++

// Author: Huahua

class Solution {

public:

vector<int> searchRange(vector<int>& nums, int target) {

auto it = lower_bound(begin(nums), end(nums), target);

int l = (it == end(nums) || *it != target) ? -1 : it - begin(nums);

auto it2 = upper_bound(begin(nums), end(nums), target);

int r = (it2 == begin(nums) || *prev(it2) != target) ? -1 : prev(it2) - begin(nums);

return {l, r};

}

};

花花酱 LeetCode 33. Search in Rotated Sorted Array

By zxi on November 26, 2021

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10⁴ <= target <= 10⁴

Solution: Binary Search

If the current range [l, r] is ordered, reduce to normal binary search. Otherwise, determine the range to search next by comparing target and nums[0].

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

C++

// Author: Huahua

class Solution {

public:

int search(vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

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

int x = (nums[m] < nums[0]) == (target < nums[0])

? nums[m]

: target < nums[0] ? INT_MIN : INT_MAX;

if (x < target)

l = m + 1;

else if (x > target)

r = m;

else

return m;

}

return -1;

}

};

花花酱 LeetCode 2080. Range Frequency Queries

By zxi on November 21, 2021

Design a data structure to find the frequency of a given value in a given subarray.

The frequency of a value in a subarray is the number of occurrences of that value in the subarray.

Implement the RangeFreqQuery class:

RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer array arr.
int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left...right].

A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

Example 1:

Input
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
Output

[null, 1, 2]

Explanation RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]); rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4] rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.

Constraints:

1 <= arr.length <= 10⁵
1 <= arr[i], value <= 10⁴
0 <= left <= right < arr.length
At most 10⁵ calls will be made to query

Solution: Hashtable + Binary Search

Time complexity: Init: O(max(arr) + n), query: O(logn)
Space complexity: O(max(arr) + n)

C++

// Author: Huahua

class RangeFreqQuery {

public:

RangeFreqQuery(vector<int>& arr) : s_(10001) {

for (int i = 0; i < arr.size(); ++i)

s_[arr[i]].push_back(i);

}

int query(int left, int right, int value) {

const auto& m = s_[value];

if (m.empty()) return 0;

auto r = prev(upper_bound(begin(m), end(m), right));

auto l = lower_bound(begin(m), end(m), left);

return r - l + 1;

}

private:

vector<vector<int>> s_;

};

/**

* Your RangeFreqQuery object will be instantiated and called as such:

* RangeFreqQuery* obj = new RangeFreqQuery(arr);

* int param_1 = obj->query(left,right,value);

花花酱 LeetCode 2071. Maximum Number of Tasks You Can Assign

By zxi on November 14, 2021

You have n tasks and m workers. Each task has a strength requirement stored in a 0-indexed integer array tasks, with the i^th task requiring tasks[i] strength to complete. The strength of each worker is stored in a 0-indexed integer array workers, with the j^th worker having workers[j] strength. Each worker can only be assigned to a single task and must have a strength greater than or equal to the task’s strength requirement (i.e., workers[j] >= tasks[i]).

Additionally, you have pills magical pills that will increase a worker’s strength by strength. You can decide which workers receive the magical pills, however, you may only give each worker at most one magical pill.

Given the 0-indexed integer arrays tasks and workers and the integers pills and strength, return the maximum number of tasks that can be completed.

Example 1:

Input: tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
Output: 3
Explanation:
We can assign the magical pill and tasks as follows:
- Give the magical pill to worker 0.
- Assign worker 0 to task 2 (0 + 1 >= 1)
- Assign worker 1 to task 1 (3 >= 2)
- Assign worker 2 to task 0 (3 >= 3)

Example 2:

Input: tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
Output: 1
Explanation:
We can assign the magical pill and tasks as follows:
- Give the magical pill to worker 0.
- Assign worker 0 to task 0 (0 + 5 >= 5)

Example 3:

Input: tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
Output: 2
Explanation:
We can assign the magical pills and tasks as follows:
- Give the magical pill to worker 0 and worker 1.
- Assign worker 0 to task 0 (0 + 10 >= 10)
- Assign worker 1 to task 1 (10 + 10 >= 15)

Example 4:

Input: tasks = [5,9,8,5,9], workers = [1,6,4,2,6], pills = 1, strength = 5
Output: 3
Explanation:
We can assign the magical pill and tasks as follows:
- Give the magical pill to worker 2.
- Assign worker 1 to task 0 (6 >= 5)
- Assign worker 2 to task 2 (4 + 5 >= 8)
- Assign worker 4 to task 3 (6 >= 5)

Constraints:

n == tasks.length
m == workers.length
1 <= n, m <= 5 * 10⁴
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 10⁹

Solution: Greedy + Binary Search in Binary Search.

Find the smallest k, s.t. we are NOT able to assign. Then answer is k- 1.

The key is to verify whether we can assign k tasks or not.

Greedy: We want k smallest tasks and k strongest workers.

Start with the hardest tasks among (smallest) k:
1. assign task[i] to the weakest worker without a pill (if he can handle the hardest work so far, then the stronger workers can handle any simpler tasks left)
2. If 1) is not possible, we find a weakest worker + pill that can handle task[i] (otherwise we are wasting workers)
3. If 2) is not possible, impossible to finish k tasks.

Let k = min(n, m)
Time complexity: O((logk)² * k)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {

const int n = tasks.size();

sort(begin(tasks), end(tasks));

sort(begin(workers), end(workers));

auto check = [&](int k) {

multiset<int> ws(rbegin(workers), rbegin(workers) + k);

for (int i = k - 1, p = 0; i >= 0; --i) {

auto it = ws.lower_bound(tasks[i]);

if (it != end(ws)) {

ws.erase(it);

} else if ((it = ws.lower_bound(tasks[i] - strength)) != end(ws)) {

if (++p > pills) return false;

ws.erase(it);

} else {

return false;

}

return true;

};

int l = 0;

int r = min(tasks.size(), workers.size()) + 1;

while (l < r) {

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

if (!check(m)) {

r = m;

} else {

l = m + 1;

}

return l - 1;

}

};