Posts tagged as “binary search”

花花酱 1095. Find in Mountain Array – EP369

By zxi on November 13, 2020

(This problem is an interactive problem.)

You may recall that an array A is a mountain array if and only if:

A.length >= 3
There exists some i with 0 < i < A.length - 1 such that:
- A[0] < A[1] < ... A[i-1] < A[i]
- A[i] > A[i+1] > ... > A[A.length - 1]

Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index doesn’t exist, return -1.

You can’t access the mountain array directly. You may only access the array using a MountainArray interface:

MountainArray.get(k) returns the element of the array at index k (0-indexed).
MountainArray.length() returns the length of the array.

Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example 1:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

Example 2:

Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.

Constraints:

3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9

Solution: Binary Search

Find the peak index of the mountain array using binary search.
Perform two binary searches in two sorted subarrays (ascending one and descending one)

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

C++

class Solution {

public:

int findInMountainArray(int target, MountainArray &mountainArr) {

const int n = mountainArr.length();

auto binary_search = [&](int l, int r, function<bool(int)> cond) {

while (l < r) {

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

if (cond(m)) r = m;

else l = m + 1;

}

return l;

};

int p = binary_search(0, n - 1, [&](int i) -> bool {

return mountainArr.get(i) > mountainArr.get(i + 1);

});

// if (target > mountainArr.get(p)) return -1;

// if (target == mountainArr.get(p)) return p;

int l = binary_search(0, p, [&](int i) -> bool {

return mountainArr.get(i) >= target;

});

if (mountainArr.get(l) == target) return l;

int r = binary_search(p, n - 1, [&](int i) -> bool {

return mountainArr.get(i) <= target;

});

if (mountainArr.get(r) == target) return r;

return -1;

}

};

python3

class Solution:

def findInMountainArray(self, target: int, arr: 'MountainArray') -> int:

def binary_search(l, r, cond):

while l < r:

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

if cond(m): r = m

else: l = m + 1

return l

n = arr.length()

p = binary_search(0, n - 1, lambda i: arr.get(i) > arr.get(i + 1))

l = binary_search(0, p, lambda i: arr.get(i) >= target)

if arr.get(l) == target: return l

r = binary_search(p, n - 1, lambda i: arr.get(i) <= target)

if arr.get(r) == target: return r

return -1

花花酱 LeetCode 1642. Furthest Building You Can Reach

By zxi on November 1, 2020

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

If the current building’s height is greater than or equal to the next building’s height, you do not need a ladder or bricks.
If the current building’s height is less than the next building’s height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Example 1:

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

Example 2:

Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7

Example 3:

Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3

Constraints:

1 <= heights.length <= 10⁵
1 <= heights[i] <= 10⁶
0 <= bricks <= 10⁹
0 <= ladders <= heights.length

Solution 0: DFS

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

AC but should be TLE

Solution 1: Binary Search + Greedy

Guess we can reach to m, sort the height differences from 0~m. Use ladders for larger values and use bricks for smallest values left.

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

C++

// Author: Huahua, 300 ms

class Solution {

public:

int furthestBuilding(vector<int>& heights, int bricks, int ladders) {

const int n = heights.size();

if (ladders >= n - 1) return n - 1;

vector<int> diffs(n);

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

diffs[i - 1] = max(0, heights[i] - heights[i - 1]);

int l = ladders;

int r = n;

while (l < r) {

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

vector<int> d(begin(diffs), begin(diffs) + m);

nth_element(begin(d), end(d) - ladders, end(d));

if (accumulate(begin(d), end(d) - ladders, 0) > bricks)

r = m;

else

l = m + 1;

}

return l - 1;

}

};

Solution 2: Min heap

Use a min heap to store all the height differences ( > 0) so far, if heap size is greater than ladders, which means we have to use bricks, extract the smallest value and subtract the bricks.

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

C++

// Author: Huahua, 216 ms

class Solution {

public:

int furthestBuilding(vector<int>& heights, int bricks, int ladders) {

const int n = heights.size();

priority_queue<int, vector<int>, greater<int>> q;

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

const int d = heights[i] - heights[i - 1];

if (d <= 0) continue;

q.push(d);

if (q.size() <= ladders) continue;

bricks -= q.top(); q.pop();

if (bricks < 0) return i - 1;

}

return n - 1;

}

};

花花酱 LeetCode 1552. Magnetic Force Between Two Balls

By zxi on August 15, 2020

In universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the i^th basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.

Example 1:

Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.

Example 2:

Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: We can use baskets 1 and 1000000000.

Constraints:

n == position.length
2 <= n <= 10^5
1 <= position[i] <= 10^9
All integers in position are distinct.
2 <= m <= position.length

Solution: Binary Search

Find the max distance that we can put m balls.

Time complexity: O(n*log(distance))
Space complexity: O(1)

C++

class Solution {

public:

int maxDistance(vector<int>& position, int m) {

const int n = position.size();

sort(begin(position), end(position));

auto count = [&](int d) -> int {

int last = position[0];

int ans = 1;

for (int x : position) {

if (x - last >= d) {

last = x;

++ans;

}

return ans;

};

int l = 0;

int t = (position.back() - position.front()) + 1;

int r = t;

while (l < r) {

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

if (count(t - mid) >= m) // find min of l => max of t - l

r = mid;

else

l = mid + 1;

}

return t - l;

}

};

Java

class Solution {

public int maxDistance(int[] position, int m) {

Arrays.sort(position);

final int n = position.length;

int l = 0;

int r = position[n - 1] - position[0] + 1;

int t = r;

while (l < r) {

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

if (getCount(position, t - mid) >= m)

r = mid;

else

l = mid + 1;

}

return t - l;

}

private int getCount(int[] position, int d) {

int count = 1;

int last = position[0];

for (int x : position) {

if (x - last >= d) {

++count;

last = x;

}

return count;

}

Python3

class Solution:

def maxDistance(self, position: List[int], m: int) -> int:

position.sort()

def getCount(d: int) -> int:

last, count = position[0], 1

for x in position:

if x - last >= d:

last = x

count += 1

return count

l, r = 0, position[-1] - position[0] + 1

t = r

while l < r:

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

if getCount(t - mid) >= m:

r = mid

else:

l = mid + 1

return t - l

花花酱 LeetCode 1539. Kth Missing Positive Number

By zxi on August 9, 2020

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Find the k^th positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5^th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2^nd missing positive integer is 6.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Solution 1: HashTable

Store all the elements into a hashtable, and check from 1 to max(arr).

Time complexity: O(max(arr)) ~ O(1000)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int findKthPositive(vector<int>& arr, int k) {

unordered_set<int> s(begin(arr), end(arr));

for (int i = 1; i <= arr.back(); ++i) {

if (!s.count(i)) --k;

if (k == 0) return i;

}

return arr.back() + k;

}

};

Solution 2: Binary Search

We can find the smallest index l using binary search, s.t.
arr[l] – l + 1 >= k
which means we missed at least k numbers at index l.
And the answer will be l + k.

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

C++

// Author: Huahua

class Solution {

public:

int findKthPositive(vector<int>& arr, int k) {

int l = 0;

int r = arr.size();

while (l < r) {

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

if (arr[m] - (m + 1) >= k)

r = m;

else

l = m + 1;

}

return l + k;

}

};

Java

class Solution {

public int findKthPositive(int[] arr, int k) {

int l = 0;

int r = arr.length;

while (l < r) {

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

if (arr[m] - (m + 1) >= k)

r = m;

else

l = m + 1;

}

return l + k;

}

Python3

class Solution:

def findKthPositive(self, arr: List[int], k: int) -> int:

l, r = 0, len(arr)

while l < r:

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

if arr[m] - (m + 1) >= k:

r = m

else:

l = m + 1

return l + k

花花酱 LeetCode 1521. Find a Value of a Mysterious Function Closest to Target

By zxi on July 19, 2020

Winston was given the above mysterious function func. He has an integer array arr and an integer target and he wants to find the values l and r that make the value |func(arr, l, r) - target| minimum possible.

Return the minimum possible value of |func(arr, l, r) - target|.

Notice that func should be called with the values l and r where 0 <= l, r < arr.length.

Example 1:

Input: arr = [9,12,3,7,15], target = 5
Output: 2
Explanation: Calling func with all the pairs of [l,r] = [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]], Winston got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.

Example 2:

Input: arr = [1000000,1000000,1000000], target = 1
Output: 999999
Explanation: Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.

Example 3:

Input: arr = [1,2,4,8,16], target = 0
Output: 0

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
0 <= target <= 10^7

Solution: Brute Force w/ Optimization

Try all possible [l, r] range with pruning.
1. for a given l, we extend r, since s & x <= s, if s becomes less than target, we can stop the inner loop.
2. Case 1, s = arr[l] & … & arr[n-1], s > target,
Let s’ = arr[l+1] & … & arr[n-1], s’ >= s,
if s > target, then s’ > target, we can stop outer loop as well.
Case 2, inner loop stops at r, s = arr[l] & … & arr[r], s <= target, we continue with l+1.

Time complexity: O(n)? on average, O(n^2) in worst case.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int closestToTarget(vector<int>& arr, int target) {

const int n = arr.size();

int ans = INT_MAX;

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

int s = arr[i];

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

s &= arr[j];

ans = min(ans, abs(s - target));

if (ans == 0) return 0;

if (s <= target) break; // s is decreasing.

}

if (s > target) break; // s is increasing.

}

return ans;

}

};