Posts tagged as “binary search”

花花酱 LeetCode 1287. Element Appearing More Than 25% In Sorted Array

By zxi on December 14, 2019

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

Example 1:

1 2	<strong>Input:</strong> arr = [1,2,2,6,6,6,6,7,10] <strong>Output:</strong> 6

Constraints:

1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5

Solution 1: Linear Scan

if arr[i] == arr[i + len/4] => arr[i] is the special integer.

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

C++

// Author: Huahua

class Solution {

public:

int findSpecialInteger(vector<int>& arr) {

int s = arr.size() / 4;

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

if (arr[i] == arr[i + s]) return arr[i];

return -1;

}

};

Solution 2: Binary Search

The answer must be one of (s[0], s[l/4], s[l/2], s[l*3/4])
Using binary search to find the range of each number, the one has more than 1/4 of total elements is the answer.

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

C++

// Author: Huahua

class Solution {

public:

int findSpecialInteger(vector<int>& arr) {

const int s = arr.size() / 4;

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

const int x = arr[i * s];

const auto [it1, it2] = equal_range(begin(arr), end(arr), x);

if (it2 - it1 > s) return x;

}

return -1;

}

};

花花酱 LeetCode 1283. Find the Smallest Divisor Given a Threshold

By zxi on December 8, 2019

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

It is guaranteed that there will be an answer.

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

Example 2:

Input: nums = [2,3,5,7,11], threshold = 11
Output: 3

Example 3:

Input: nums = [19], threshold = 5
Output: 4

Solution: Binary Search

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

C++

// Author: Huahua

class Solution {

public:

int smallestDivisor(vector<int>& nums, int threshold) {

auto sums = [&](int d) {

int s = 0;

for (int n : nums)

s += (n + (d - 1)) / d;

return s;

};

int l = 1;

int r = 1e6;

while (l < r) {

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

if (sums(m) <= threshold)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 1268. Search Suggestions System

By zxi on November 24, 2019

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]

Example 2:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Example 3:

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:

Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]

Constraints:

1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
All characters of products[i] are lower-case English letters.
1 <= searchWord.length <= 1000
All characters of searchWord are lower-case English letters.

Solution 1: Binary Search

Sort the input array and do two binary searches.
One for prefix of the search word as lower bound, another for prefix + ‘~’ as upper bound.
‘~’ > ‘z’

Time complexity: O(nlogn + l * logn)
Space complexity: O(1)

C++

// Author: Huahua, 36ms, 35MB

class Solution {

public:

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {

vector<vector<string>> ans;

std::sort(begin(products), end(products));

string key;

for (char c : searchWord) {

key += c;

auto l = lower_bound(begin(products), end(products), key);

auto r = upper_bound(begin(products), end(products), key += '~');

if (l == r) break; // early return

key.pop_back();

ans.emplace_back(l, min(l + 3, r));

}

while (ans.size() != searchWord.length()) ans.push_back({});

return ans;

}

};

Solution 2: Trie

Initialization: Sum(len(products[i]))
Query: O(len(searchWord))

C++

// Author: Huahua, 148 ms, 98.8 MB

struct Trie {

Trie(): nodes(26) {}

~Trie() {

for (auto* node : nodes)

delete node;

}

vector<Trie*> nodes;

vector<const string*> words;

static void addWord(Trie* root, const string& word) {

for (char c : word) {

if (root->nodes[c - 'a'] == nullptr) root->nodes[c - 'a'] = new Trie();

root = root->nodes[c - 'a'];

if (root->words.size() < 3)

root->words.push_back(&word);

}

static vector<vector<string>> getWords(Trie* root, const string& prefix) {

vector<vector<string>> ans(prefix.size());

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

char c = prefix[i];

root = root->nodes[c - 'a'];

if (root == nullptr) break;

for (auto* word : root->words)

ans[i].push_back(*word);

}

return ans;

}

};

class Solution {

public:

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {

std::sort(begin(products), end(products));

Trie root;

for (const auto& product : products)

Trie::addWord(&root, product);

return Trie::getWords(&root, searchWord);

}

};

花花酱 LeetCode 1235. Maximum Profit in Job Scheduling

By zxi on October 24, 2019

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime , endTime and profit arrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:


Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

Solution: DP + binary search

Sort jobs by ending time.
dp[t] := max profit by end time t.

for a job = (s, e, p)
dp[e] = dp[u] + p, u <= s, and if dp[u] + p > last_element in dp.

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

C++

// Author: Huahua

class Solution {

public:

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {

const int n = startTime.size();

vector<vector<int>> jobs(n);

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

jobs[i] = {endTime[i], startTime[i], profit[i]};

sort(begin(jobs), end(jobs));

int ans = 0;

map<int, int> m{{0, 0}}; // {end_time -> max_profit}

for (const auto& job : jobs) {

int p = prev(m.upper_bound(job[1]))->second + job[2];

if (p > rbegin(m)->second) {

m[job[0]] = p;

}

return rbegin(m)->second;

}

};

花花酱 LeetCode 1222. Queens That Can Attack the King

By zxi on October 14, 2019

On an 8×8 chessboard, there can be multiple Black Queens and one White King.

Given an array of integer coordinates queens that represents the positions of the Black Queens, and a pair of coordinates king that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.

Example 1:

Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
Output: [[0,1],[1,0],[3,3]]
Explanation:  
The queen at [0,1] can attack the king cause they're in the same row. 
The queen at [1,0] can attack the king cause they're in the same column. 
The queen at [3,3] can attack the king cause they're in the same diagnal. 
The queen at [0,4] can't attack the king cause it's blocked by the queen at [0,1]. 
The queen at [4,0] can't attack the king cause it's blocked by the queen at [1,0]. 
The queen at [2,4] can't attack the king cause it's not in the same row/column/diagnal as the king.

Example 2:

Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
Output: [[2,2],[3,4],[4,4]]

Example 3:

Input: queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]
Output: [[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]

Constraints:

1 <= queens.length <= 63
queens[0].length == 2
0 <= queens[i][j] < 8
king.length == 2
0 <= king[0], king[1] < 8
At most one piece is allowed in a cell.

Solution2: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {

vector<vector<int>> b(8, vector<int>(8));

for (const auto& q : queens)

b[q[0]][q[1]] = 1;

vector<vector<int>> ans;

for (const auto& q : queens) {

for (int dx = -1; dx <= 1; ++dx)

for (int dy = -1; dy <= 1; ++dy) {

if (dx == 0 && dy == 0) continue;

int x = q[1] + dx;

int y = q[0] + dy;

while (x >= 0 && y >= 0 && x < 8 && y < 8 && !b[y][x]) {

if (x == king[1] && y == king[0])

ans.push_back(q);

x += dx;

y += dy;

}

return ans;

}

};

Solution 2: HashTable + Binary Search

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

Support arbitrarily large boards, e.g. 1e9 x 1e9 with 1e6 # of queens.

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {

unordered_map<int, map<int, vector<int>>> rows, cols, diag1, diag2;

for (const auto& q : queens) {

const int x = q[1];

const int y = q[0];

rows[y][x] = q;

cols[x][y] = q;

diag1[x + y][x] = q;

diag2[x - y][x] = q;

}

const int x = king[1];

const int y = king[0];

vector<vector<int>> ans;

find(rows, y, x, ans);

find(cols, x, y, ans);

find(diag1, x + y, x, ans);

find(diag2, x - y, x, ans);

return ans;

}

private:

void find(const unordered_map<int, map<int, vector<int>>>& m, int idx, int key, vector<vector<int>>& ans) {

if (!m.count(idx)) return;

const auto& d = m.at(idx);

auto it = d.upper_bound(key);

if (it != end(d))

ans.push_back(it->second);

if (it != begin(d))

ans.push_back(prev(it)->second);

}

};