Posts published in “Binary Search”

花花酱 LeetCode 1201. Ugly Number III

By zxi on September 22, 2019

Write a program to find the n-th ugly number.

Ugly numbers are positive integers which are divisible by a or b or c.

Example 1:

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

Example 2:

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 12... The 4th is 6.

Example 3:

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

Example 4:

Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984

Constraints:

1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
It’s guaranteed that the result will be in range [1, 2 * 10^9]

Solution: Binary Search

Number of ugly numbers that are <= m are:

m / a + m / b + m / c – (m / LCM(a,b) + m / LCM(a, c) + m / LCM(b, c) + m / LCM(a, LCM(b, c))

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

C++

// Author: Huahua

class Solution {

public:

int nthUglyNumber(int n, long a, long b, long c) {

long l = 1;

long r = INT_MAX;

long ab = lcm(a, b);

long ac = lcm(a, c);

long bc = lcm(b, c);

long abc = lcm(a, bc);

while (l < r) {

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

long k = m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc;

if (k >= n) r = m;

else l = m + 1;

}

return l;

}

};

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

By zxi on August 20, 2019

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

Your algorithm’s runtime complexity must be in the order of O(log n).

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

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]

Solution: Binary Search

Basically this problem asks you to implement lower_bound and upper_bound using binary search.

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

C++

// Author: Huahua

class Solution {

public:

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

return {firstPos(nums, target), lastPos(nums, target)};

}

private:

int firstPos(const vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

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

if (nums[m] >= target) {

r = m;

} else {

l = m + 1;

}

if (l == nums.size() || nums[l] != target) return -1;

return l;

}

int lastPos(const vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

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

if (nums[m] > target) {

r = m;

} else {

l = m + 1;

}

// l points to the first element this is greater than target.

--l;

if (l < 0 || nums[l] != target) return -1;

return l;

}

};

花花酱 LeetCode 1011. Capacity To Ship Packages Within D Days

By zxi on March 16, 2019

A conveyor belt has packages that must be shipped from one port to another within D days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation: 
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = [3,2,2,4,1,4], D = 3
Output: 6
Explanation: 
A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], D = 4
Output: 3
Explanation: 
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Note:

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

Solution: Binary Search

Find the smallest capacity such that can finish in D days.

Time complexity: O(n * log(sum(weights))
Space complexity: O(1)

C++

// Author: Huahua, running time: 52 ms, 11.9 MB

class Solution {

public:

int shipWithinDays(vector<int>& weights, int D) {

int l = *max_element(begin(weights), end(weights));

int r = accumulate(begin(weights), end(weights), 0) + 1;

while (l < r) {

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

int d = 1;

int t = 0;

for (int w : weights)

if ((t += w) > m) {

t = w;

++d;

}

d > D ? l = m + 1 : r = m;

}

return l;

}

};

花花酱 LeetCode 74. Search a 2D Matrix

By zxi on February 13, 2019

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:

matrix = [

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 3

Output: true

Example 2:

Input:

matrix = [

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 13

Output: false

Solution: Binary Search

Treat the 2D array as a 1D array. matrix[index / cols][index % cols]

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

C++

class Solution {

public:

bool searchMatrix(vector<vector<int>>& matrix, int target) {

if (matrix.empty()) return false;

int l = 0;

int r = matrix.size() * matrix[0].size();

const int cols = matrix[0].size();

while (l < r) {

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

if (matrix[m / cols][m % cols] == target) {

return true;

} else if (matrix[m / cols][m % cols] > target) {

r = m;

} else {

l = m + 1;

}

return false;

}

};

花花酱 LeetCode 915. Partition Array into Disjoint Intervals

By zxi on September 30, 2018

Problem

Given an array A, partition it into two (contiguous) subarrays left and right so that:

Every element in left is less than or equal to every element in right.
left and right are non-empty.
left has the smallest possible size.

Return the length of left after such a partitioning. It is guaranteed that such a partitioning exists.

Example 1:

Input: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]

Example 2:

Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]

Note:

2 <= A.length <= 30000
0 <= A[i] <= 10^6
It is guaranteed there is at least one way to partition A as described.

Solution 1: BST

Time complexity: O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua, 100 ms

class Solution {

public:

int partitionDisjoint(vector<int>& A) {

multiset<int> s(begin(A) + 1, end(A));

int left_max = A[0];

for (int i = 1; i < A.size(); ++i) {

if (*begin(s) >= left_max) return i;

s.erase(s.equal_range(A[i]).first);

left_max = max(left_max, A[i]);

}

return -1;

}

};

Solution 2: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua, 28 ms

class Solution {

public:

int partitionDisjoint(vector<int>& A) {

int left_max = A[0];

int cur_max = A[0];

int left_len = 1;

for (int i = 1; i < A.size(); ++i) {

if (A[i] < left_max) {

left_max = cur_max;

left_len = i + 1;

} else {

cur_max = max(cur_max, A[i]);

}

return left_len;

}

};