Posts published in “Algorithms”

花花酱 SP5 Binary Search

By zxi on August 12, 2018

Template:

Time complexity: O(log(r-l)) * O(f(m) + g(m))

Space complexity: O(1)

"""

Returns the smallest number m such that g(m) is true.

"""

def binary_search(l, r):

while l < r:

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

if f(m): return m # if m is the answer

if g(m):

r = m # new range [l, m)

else

l = m + 1 # new range [m+1, r)

return l # or not found

Slides:

Lower Bound / Upper Bound

#include <iostream>

#include <vector>

using namespace std;

int upper_bound(const vector<int>& A, int val, int l, int r) {

while (l < r) {

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

if (A[m] > val)

r = m;

else

l = m + 1;

}

return l;

}

int lower_bound(const vector<int>& A, int val, int l, int r) {

while (l < r) {

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

if (A[m] >= val)

r = m;

else

l = m + 1;

}

return l;

}

int main() {

vector<int> A{1, 2, 2, 2, 4, 4, 5};

cout << lower_bound(A, 0, 0, A.size()) << endl; // 0

cout << lower_bound(A, 2, 0, A.size()) << endl; // 1

cout << lower_bound(A, 3, 0, A.size()) << endl; // 4

cout << upper_bound(A, 2, 0, A.size()) << endl; // 4

cout << upper_bound(A, 4, 0, A.size()) << endl; // 6

cout << upper_bound(A, 5, 0, A.size()) << endl; // 7

}

Mentioned Problems

花花酱 LeetCode 189. Rotate Array

By zxi on August 6, 2018

Problem

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3 
Output: [5,6,7,1,2,3,4]
Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] 
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input:[-1,-100,3,99] and k = 2 
Output: [3,99,-1,-100] 
Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

Solution 1: Simulate rotation with three reverses.

If k >= n, rotating k times has the same effect as rotating k % n times.

[1,2,3,4,5,6,7], K = 3

[5,6,7,1,2,3,4]

We can simulate the rotation with three reverses.

reverse the whole array O(n) [7,6,5,4,3,2,1]
reverse the left part 0 ~ k – 1 O(k) [5,6,7,4,3,2,1]
reverse the right part k ~ n – 1 O(n-k) [5,6,7,1,2,3,4]

Time complexity: O(n)

Space complexity: O(1) in-place

C++

class Solution {

public:

void rotate(vector<int>& nums, int k) {

if (nums.empty()) return;

k %= nums.size();

if (k == 0) return;

reverse(begin(nums), end(nums));

reverse(begin(nums), begin(nums) + k);

reverse(begin(nums) + k, end(nums));

}

};

花花酱 LeetCode 881. Random Flip Matrix

By zxi on July 31, 2018

Problem

You are given the number of rows n_rows and number of columns n_cols of a 2D binary matrix where all values are initially 0. Write a function flip which chooses a 0 value uniformly at random, changes it to 1, and then returns the position [row.id, col.id] of that value. Also, write a function reset which sets all values back to 0. Try to minimize the number of calls to system’s Math.random() and optimize the time and space complexity.

Note:

1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows and 0 <= col.id < n_cols
flip will not be called when the matrix has no 0 values left.
the total number of calls to flip and reset will not exceed 1000.

Example 1:

Input: 
["Solution","flip","flip","flip","flip"]
[[2,3],[],[],[],[]]
Output: [null,[0,1],[1,2],[1,0],[1,1]]

Example 2:

Input: 
["Solution","flip","flip","reset","flip"]
[[1,2],[],[],[],[]]
Output: [null,[0,0],[0,1],null,[0,0]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has two arguments, n_rows and n_cols. flip and reset have no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution 1: Hashtable + Resample

Time complexity: O(|flip|) = O(1000) = O(1)

Space complexity: O(|flip|) = O(1000) = O(1)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

Solution(int n_rows, int n_cols):

rows_(n_rows), cols_(n_cols), n_(rows_ * cols_) {}

vector<int> flip() {

int index = rand() % n_;

while (m_.count(index))

index = rand() % n_;

m_.insert(index);

return {index / cols_, index % cols_};

}

void reset() {

m_.clear();

n_ = rows_ * cols_;

}

private:

const int rows_;

const int cols_;

int n_;

unordered_set<int> m_;

};

Solution 2: Fisher–Yates shuffle

Generate a random shuffle of 0 to n – 1, one number at a time.

Time complexity: flip: O(1)

Space complexity: O(|flip|) = O(1000) = O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

Solution(int n_rows, int n_cols):

rows_(n_rows), cols_(n_cols), n_(rows_ * cols_) {}

vector<int> flip() {

int s = rand() % (n_--);

int index = s;

if (m_.count(s))

index = m_[s];

m_[s] = m_.count(n_) ? m_[n_] : n_;

return {index / cols_, index % cols_};

}

void reset() {

m_.clear();

n_ = rows_ * cols_;

}

private:

const int rows_;

const int cols_;

int n_;

unordered_map<int, int> m_;

};

花花酱 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;

}

};

花花酱 LeetCode 739. Daily Temperatures

By zxi on July 16, 2018

Problem

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Solution: Stack

Use a stack to track indices of future warmer days. From top to bottom: recent to far away.

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 148 ms

class Solution {

public:

vector<int> dailyTemperatures(vector<int>& temperatures) {

const int n = temperatures.size();

stack<int> s;

vector<int> ans(n);

for (int i = n - 1; i >= 0; --i) {

while (!s.empty() && temperatures[s.top()] <= temperatures[i]) s.pop();

ans[i] = s.empty() ? 0 : s.top() - i;

s.push(i);

}

return ans;

}

};