Posts tagged as “medium”

花花酱 LeetCode 785. Is Graph Bipartite?

By zxi on July 24, 2018

Video is for 花花酱 LeetCode 886. Possible Bipartition, but the algorithm is exact the same.

Problem

https://leetcode.com/problems/is-graph-bipartite/

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.

Note:

graph will have length in range [1, 100].
graph[i] will contain integers in range [0, graph.length - 1].
graph[i] will not contain i or duplicate values.
The graph is undirected: if any element j is in graph[i], then i will be in graph[j].

Solution: Graph Coloring

For each node

If has not been colored, color it to RED(1).
Color its neighbors with a different color RED(1) to BLUE(-1) or BLUE(-1) to RED(-1).

If we can finish the coloring then the graph is bipartite. All red nodes on the left no connections between them and all blues nodes on the right, again no connections between them. red and blue nodes are neighbors.

Time complexity: O(V+E)

Space complexity: O(V)

C++ / DFS

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

bool isBipartite(vector<vector<int>>& graph) {

const int n = graph.size();

vector<int> colors(n);

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

if (!colors[i] && !coloring(graph, colors, 1, i))

return false;

return true;

}

private:

bool coloring(const vector<vector<int>>& graph, vector<int>& colors, int color, int node) {

if (colors[node]) return colors[node] == color;

colors[node] = color;

for (int nxt : graph[node])

if (!coloring(graph, colors, -color, nxt)) return false;

return true;

}

};

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 873. Length of Longest Fibonacci Subsequence

By zxi on July 22, 2018

Problem

A sequence X_1, X_2, ..., X_n is fibonacci-like if:

n >= 3
X_i + X_{i+1} = X_{i+2} for all i + 2 <= n

Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A. If one does not exist, return 0.

(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)

Example 1:

Input: [1,2,3,4,5,6,7,8]
Output: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18].

Note:

3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
(The time limit has been reduced by 50% for submissions in Java, C, and C++.)

Solution 1: DP

C++

// Author: Huahua

// Running time: 68 ms

// w/ Hashtable

// Time complexity: O(n^2)

// Space complexity: O(n^2)

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

unordered_map<int, int> m;

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

m[A[i]] = i;

vector<vector<int>> dp(n, vector<int>(n, 2));

int ans = 0;

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

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

int a_i = A[k] - A[j];

if (a_i >= A[j]) break; // pruning 168 ms -> 68 ms

auto it = m.find(a_i);

if (it == end(m)) continue;

int i = it->second;

dp[j][k] = dp[i][j] + 1;

ans = max(ans, dp[j][k]);

}

return ans;

}

};

C++ V2

// Author: Huahua

// Running time: 96 ms

// w / Binary Search

// Time complexity: O(n^2logn)

// Space complexity: O(n)

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

vector<vector<int>> dp(n, vector<int>(n, 2));

int ans = 0;

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

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

int a_i = A[k] - A[j];

if (a_i >= A[j]) break;

auto it = lower_bound(begin(A), begin(A) + j, a_i);

int i = it - begin(A);

if (A[i] != a_i) continue;

dp[j][k] = dp[i][j] + 1;

ans = max(ans, dp[j][k]);

}

return ans;

}

};

Solution 2: HashTable

Time complexity: O(n^3)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 172 ms

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

unordered_set<int> m(begin(A), end(A));

int ans = 0;

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

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

int a = A[i];

int b = A[j];

int c = a + b;

int l = 2;

while (m.count(c)) {

a = b;

b = c;

c = a + b;

ans = max(ans, ++l);

}

return ans;

}

};

花花酱 LeetCode 501. Find Mode in Binary Search Tree

By zxi on July 19, 2018

Problem

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Solution1: Recursion w/ extra space

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

vector<int> findMode(TreeNode* root) {

inorder(root);

return ans_;

}

private:

int val_ = 0;

int count_ = 0;

int max_count_ = 0;

vector<int> ans_;

void inorder(TreeNode* root) {

if (root == nullptr) return;

inorder(root->left);

visit(root->val);

inorder(root->right);

}

void visit(int val) {

if (count_ > 0 && val == val_) {

++count_;

} else {

val_ = val;

count_ = 1;

}

if (count_ > max_count_) {

max_count_ = count_;

ans_.clear();

}

if (count_ == max_count_)

ans_.push_back(val);

}

};

Solution2: Recursion w/o extra space

Two passes. First pass to find the count of the mode, second pass to collect all the modes.

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

vector<int> findMode(TreeNode* root) {

inorder(root);

mode_count_ = max_count_;

count_ = 0;

inorder(root);

return ans_;

}

private:

int val_ = 0;

int count_ = 0;

int mode_count_ = INT_MAX;

int max_count_ = 0;

vector<int> ans_;

void inorder(TreeNode* root) {

if (root == nullptr) return;

inorder(root->left);

visit(root->val);

inorder(root->right);

}

void visit(int val) {

if (count_ > 0 && val == val_) {

++count_;

} else {

val_ = val;

count_ = 1;

}

if (count_ > max_count_)

max_count_ = count_;

if (count_ == mode_count_)

ans_.push_back(val);

}

};

花花酱 LeetCode 491. Increasing Subsequences

By zxi on July 17, 2018

Problem

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

Note:

The length of the given array will not exceed 15.
The range of integer in the given array is [-100,100].
The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

Solution: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 140 ms (<99.88%)

class Solution {

public:

vector<vector<int>> findSubsequences(vector<int>& nums) {

vector<vector<int>> ans;

vector<int> cur;

dfs(nums, 0, cur, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int s, vector<int>& cur, vector<vector<int>>& ans) {

unordered_set<int> seen;

for (int i = s; i < nums.size(); ++i) {

if (!cur.empty() && nums[i] < cur.back()) continue;

// each number can be used only once at the same depth.

if (seen.count(nums[i])) continue;

seen.insert(nums[i]);

cur.push_back(nums[i]);

if (cur.size() > 1)

ans.push_back(cur);

dfs(nums, i + 1, cur, ans);

cur.pop_back();

}

};

Posts tagged as “medium”

花花酱 LeetCode 785. Is Graph Bipartite?

Problem

Solution: Graph Coloring

Related Problem

花花酱 LeetCode 875. Koko Eating Bananas

Problem

Solution: Binary Search

花花酱 LeetCode 873. Length of Longest Fibonacci Subsequence

Problem

Solution 1: DP

C++

C++ V2

Solution 2: HashTable

C++

花花酱 LeetCode 501. Find Mode in Binary Search Tree

Problem

Solution1: Recursion w/ extra space

Solution2: Recursion w/o extra space

花花酱 LeetCode 491. Increasing Subsequences

Problem

Solution: DFS