MAY-27 2020 Challenge

Possible Bipartition

Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.

Return true if and only if it is possible to split everyone into two groups in this way.

Example 1:

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Example 2:

Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Example 3:

Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Note:

1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].

Solution in C++:

class Solution {

public:

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

g_ = vector<vector<int>>(N);

for (const auto& d : dislikes) {

g_[d[0] - 1].push_back(d[1] - 1);

g_[d[1] - 1].push_back(d[0] - 1);

}

colors_ = vector<int>(N, 0); // 0: unknown, 1: red, -1: blue

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

if (colors_[i] == 0 && !dfs(i, 1)) return false;

return true;

}

private:

vector<vector<int>> g_;

vector<int> colors_;

bool dfs(int cur, int color) {

colors_[cur] = color;

for (int nxt : g_[cur]) {

if (colors_[nxt] == color) return false;

if (colors_[nxt] == 0 && !dfs(nxt, -color)) return false;

}

return true;

}

};

Comments

Leetcode 371. Sum of Two Integers. C++ / Java

371 . Sum of Two Integers Given two integers a and b , return the sum of the two integers without using the operators + and - . Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5 Constraints: -1000 <= a, b <= 1000 Solution : C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java : class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :

Leetcode 338. Counting Bits. Python (Bubble Sort)

Given an integer n , return an array ans of length n + 1 such that for each i ( 0 <= i <= n ) , ans[i] is the number of 1 's in the binary representation of i . Example 1: Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10 Example 2: Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101 Constraints: 0 <= n <= 10 5 Follow up: It is very easy to come up with a solution with a runtime of O(n log n) . Can you do it in linear time O(n) and possibly in a single pass? Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)? Solution : class Solution: def countBits(self, n: int) -> List[int]: dp = [0] * (n+1) c = 1 ...

Leetcode 347. Top K Frequent Elements. Python (Bubble Sort)

Top K Frequent Elements Given an integer array nums and an integer k , return the k most frequent elements . You may return the answer in any order . Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1] Constraints: 1 <= nums.length <= 10 5 -10 4 <= nums[i] <= 10 4 k is in the range [1, the number of unique elements in the array] . It is guaranteed that the answer is unique . Follow up: Your algorithm's time complexity must be better than O(n log n) , where n is the array's size. Solution : class Solution: def topKFrequent(self, n: List[int], k: int) -> List[int]: # [1,1,1,2,2,3] & k = 2 f = [[] for i in range(len(n) + 1)] # f = [...

LEETCODE SOLUTIONS

Search This Blog