Posts published in “Binary Search”

花花酱 LeetCode 911. Online Election

By zxi on September 25, 2018

Problem

n an election, the i-th vote was cast for persons[i] at time times[i].

Now, we would like to implement the following query function: TopVotedCandidate.q(int t) will return the number of the person that was leading the election at time t.

Votes cast at time t will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.

Example 1:

Input: ["TopVotedCandidate","q","q","q","q","q","q"], [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]
Output: [null,0,1,1,0,0,1]
Explanation: 
At time 3, the votes are [0], and 0 is leading.
At time 12, the votes are [0,1,1], and 1 is leading.
At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
This continues for 3 more queries at time 15, 24, and 8.

Note:

1 <= persons.length = times.length <= 5000
0 <= persons[i] <= persons.length
times is a strictly increasing array with all elements in [0, 10^9].
TopVotedCandidate.q is called at most 10000 times per test case.
TopVotedCandidate.q(int t) is always called with t >= times[0].

Solution: HashTable + Binary Search

Compute the leads for each t in times using a hash table.

binary search the upper bound of t, and return the lead of previous entry.

Time complexity: Constructor O(n), Query: O(logn)

Space complexity: O(n)

C++

// Author: Huahua

class TopVotedCandidate {

public:

TopVotedCandidate(vector<int> persons, vector<int> times) {

vector<int> votes(persons.size() + 1);

int last_lead = persons.front();

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

if (++votes[persons[i]] >= votes[last_lead])

last_lead = persons[i];

leads_[times[i]] = last_lead;

}

int q(int t) {

return prev(leads_.upper_bound(t))->second;

}

private:

map<int, int> leads_; // time -> lead

};

花花酱 LeetCode 18. 4Sum

By zxi on September 19, 2018

Problem

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solution 1: Sorting + Binary Search

Time complexity: O(n^3 log n + klogk)

Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> fourSum(vector<int> &num, int target) {

set<vector<int>> h;

sort(num.begin(), num.end());

int n = num.size();

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

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

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

int t = target - num[i] - num[j] - num[k];

if (t < num[k]) break;

if (!std::binary_search(num.begin() + k + 1, num.end(), t)) continue;

h.insert({num[i], num[j], num[k], t});

}

return vector<vector<int>>(begin(h), end(h));

}

};

C++ opt

// Author: Huahua

class Solution {

public:

vector<vector<int>> fourSum(vector<int> &num, int target) {

sort(num.begin(), num.end());

if (target > 0 && target > 4 * num.back()) return {};

if (target < 0 && target < 4 * num.front()) return {};

set<vector<int>> h;

int n = num.size();

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

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

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

int t = target - num[i] - num[j] - num[k];

if (t < num[k]) break;

if (!std::binary_search(num.begin() + k + 1, num.end(), t)) continue;

h.insert({num[i], num[j], num[k], t});

}

return vector<vector<int>>(begin(h), end(h));

}

};

Solution 2: Sorting + HashTable

Time complexity: O(n^3 + klogk)

Space complexity: O(n + k)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> fourSum(vector<int> &num, int target) {

sort(num.begin(), num.end());

if (target > 0 && target > 4 * num.back()) return {};

if (target < 0 && target < 4 * num.front()) return {};

unordered_map<int, int> index;

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

index[num[i]] = i;

set<vector<int>> h;

int n = num.size();

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

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

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

int t = target - num[i] - num[j] - num[k];

if (t < num[k]) break;

auto it = index.find(t);

if (it == index.end() || it->second <= k) continue;

h.insert({num[i], num[j], num[k], t});

}

return vector<vector<int>>(begin(h), end(h));

}

};

Problem

Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?

Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.

Example 1:

Input: m = 3, n = 3, k = 5
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6
3	6	9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Example 2:

Input: m = 2, n = 3, k = 6
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6

The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

Note:

The m and n will be in the range [1, 30000].
The k will be in the range [1, m * n]

Solution 1: Nth element (MLE)

Time complexity: O(mn)

Space complexity: O(mn)

C++

// 59 / 69 test cases passed.

class Solution {

public:

int findKthNumber(int m, int n, int k) {

vector<int> s(m * n);

auto it = begin(s);

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

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

*it++ = i * j;

nth_element(begin(s), begin(s) + k - 1, end(s));

return s[k - 1];

}

};

Solution2 : Binary Search

Find first x such that there are k elements less or equal to x in the table.

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

Space complexity: O(1)

C++

// Author: Huahua, 12 ms

class Solution {

public:

int findKthNumber(int m, int n, int k) {

int l = 1;

int r = m * n + 1;

while (l < r) {

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

if (LEX(m, n, x) >= k)

r = x;

else

l = x + 1;

}

return l;

}

private:

// Returns # of elements in the m*n table that are <= x

int LEX(int m, int n, int x) {

int count = 0;

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

count += min(n, x / i);

return count;

}

};

Java

// Author: Huahua, 16 ms

class Solution {

public int findKthNumber(int m, int n, int k) {

int l = 1;

int r = m * n + 1;

while (l < r) {

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

if (LEX(m, n, x) >= k)

r = x;

else

l = x + 1;

}

return l;

}

// Returns # of elements in the m*n table that are <= x

private int LEX(int m, int n, int x) {

int count = 0;

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

count += Math.min(n, x / i);

return count;

}

Python3

# Author: Huahua, 976 ms

class Solution:

def findKthNumber(self, m, n, k):

def LEX(m, n, x, k):

count = 0

for i in range(1, min(m + 1, x + 1)):

count += min(n, x // i)

if count >= k: return count

return count

l = 1

r = m * n + 1

while l < r:

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

if LEX(m, n, x, k) >= k:

r = x

else:

l = x + 1

return l

Mentioned Problems

花花酱 LeetCode 875. Koko Eating Bananas

By zxi on July 22, 2018

Problem

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

Example 1:

Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], H = 6
Output: 23

Note:

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

Solution: Binary Search

search for the smallest k [1, max_pile_height] such that eating time h <= H.

Time complexity: O(nlogh)

Space complexity: O(1)

// Author: Huahua

// Running time: 48 ms

class Solution {

public:

int minEatingSpeed(vector<int>& piles, int H) {

int l = 1;

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

while (l < r) {

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

int h = 0;

for (int p : piles)

h += (p + m - 1) / m;

if (h <= H)

r = m;

else

l = m + 1;

}

return l;

}

};

Posts published in “Binary Search”

花花酱 LeetCode 911. Online Election

Problem

Solution: HashTable + Binary Search

C++

花花酱 LeetCode 18. 4Sum

Problem

Solution 1: Sorting + Binary Search

C++

C++ opt

Solution 2: Sorting + HashTable

C++

Related Problems

花花酱 LeetCode 668. Kth Smallest Number in Multiplication Table

Problem

Solution 1: Nth element (MLE)

C++

Solution2 : Binary Search

C++

Java

Python3

Related Problems

花花酱 SP5 Binary Search

Mentioned Problems

花花酱 LeetCode 875. Koko Eating Bananas

Problem

Solution: Binary Search