leetcode 323 - Number of Connected Components in an Undirected Graph

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/discuss/516491/Java-Union-Find-DFS-BFS-Solutions-Complexity-Explain-Clean-code

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

Example 1:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1

Constraints:

1 <= n <= 2000
1 <= edges.length <= 5000
edges[i].length == 2
0 <= ai <= bi < n
ai != bi
There are no repeated edges.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
int countComponents(int n, vector<vector<int>>& edges) {
parent.resize(n);

for (int i = 0; i < n; i++)
parent[i] = i;

for (auto &e : edges)
Union(e[0], e[1]);

unordered_set<int> ids;
for (int i = 0; i < n; i++)
ids.insert(Find(i));

return ids.size();
}

private:
vector<int> parent;

void Union(int i, int j) {
parent[Find(i)] = Find(j);
}

int Find(int i) {
if (parent[i] != i)
parent[i] = Find(parent[i]);
return parent[i];
}
};

//DFS, Time O(V+E)
class Solution {
public:
int countComponents(int n, vector<vector<int>>& edges) {
unordered_map<int, vector<int>> graph;

for (auto &e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}

unordered_set<int> seen;

int ans = 0;
for (int i = 0; i < n; i++) {
if (seen.count(i)) continue;

dfs(graph, seen, i);
ans++;
}

return ans;
}

private:
void dfs(unordered_map<int, vector<int>> &graph, unordered_set<int> &seen, int i) {
if (seen.count(i)) return;

seen.insert(i);
for (auto j : graph[i])
dfs(graph, seen, j);
}
};

leetcode 364 - Nested List Weight Sum II

https://leetcode.com/problems/nested-list-weight-sum-ii/
https://leetcode.com/problems/nested-list-weight-sum-ii/discuss/83655/JAVA-AC-BFS-solution

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1:

Input: [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1’s at depth 1, one 2 at depth 2.
Example 2:

Input: [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 13 + 42 + 6*1 = 17.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Constructor initializes an empty nested list.
* NestedInteger();
*
* // Constructor initializes a single integer.
* NestedInteger(int value);
*
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Set this NestedInteger to hold a single integer.
* void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* void add(const NestedInteger &ni);
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
//Two passes
class Solution {
public:
int depthSumInverse(vector<NestedInteger>& nestedList) {
int depth = getDepth(nestedList);

int sum = dfs(nestedList, depth);
return sum;
}

private:
int dfs(vector<NestedInteger>& nestedList, int depth) {
int sum = 0;

for (auto &nest : nestedList) {
if (!nest.isInteger())
sum += dfs(nest.getList(), depth-1);
else
sum += depth * nest.getInteger();
}

return sum;
}

int getDepth(vector<NestedInteger>& nestedList) {
int depth = 1;
for (auto &nest : nestedList) {
if (!nest.isInteger())
depth = max(depth, getDepth(nest.getList()) + 1);
}

return depth;
}
};

//One pass BFS
class Solution {
public:
int depthSumInverse(vector<NestedInteger>& nestedList) {
queue<NestedInteger> q;
int total_sum = 0;
int prev = 0;

for (auto &nested : nestedList)
q.push(nested);

while (!q.empty()) {
int size = q.size();
int level_sum = 0;

for (int i = 0; i < size; i++) {
auto nested = q.front(); q.pop();
if (nested.isInteger())
level_sum += nested.getInteger();
else {
for (auto n : nested.getList())
q.push(n);
}
}

prev += level_sum;
total_sum += prev;
}

return total_sum;
}
};

//One pass DFS
class Solution {
public:
int depthSumInverse(vector<NestedInteger>& nestedList) {
max_depth = 0;
flat_sum = 0;

int sum = depth_sum(nestedList, 1);
return (max_depth+1)*flat_sum - sum;
}

int depth_sum(vector<NestedInteger>& nestedList, int depth) {
int sum = 0;

max_depth = max(max_depth, depth);

for (auto &nested : nestedList) {
if (nested.isInteger()) {
sum += depth * nested.getInteger();
flat_sum += nested.getInteger();
} else
sum += depth_sum(nested.getList(), depth+1);
}

return sum;
}

private:
int max_depth;
int flat_sum;
};

leetcode 48 - Rotate Image

https://leetcode.com/problems/rotate-image/
https://leetcode.com/problems/rotate-image/discuss/18872/A-common-method-to-rotate-the-image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Example 3:

Input: matrix = [[1]]
Output: [[1]]
Example 4:

Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]

Constraints:

matrix.length == n
matrix[i].length == n
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();

reverse(matrix.begin(), matrix.end());

for (int r = 0; r < n; r++)
for (int c = r + 1; c < n; c++)
swap(matrix[r][c], matrix[c][r]);
}
};

leetcode 49 - Group Anagrams

https://leetcode.com/problems/group-anagrams/

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
Example 2:

Input: strs = [“”]
Output: [[“”]]
Example 3:

Input: strs = [“a”]
Output: [[“a”]]

Constraints:

1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] consists of lower-case English letters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> result;

unordered_map<string,int> key_index_map;

for (auto &str : strs) {
string key = get_key(str);
if (key_index_map.count(key) == 0) {
result.push_back({str});
key_index_map[key] = result.size() - 1;
} else {
result[key_index_map[key]].push_back(str);
}
}

return result;
}

string get_key(string s) {
sort(s.begin(), s.end());
return s;
}

/*
string get_key(string &s) {
vector<int> count(26, 0);

for (char c : s)
count[c-'a']++;

string key;
for (int c : count)
key += "#" + to_string(c);

return key;
}
*/
};

leetcode 1573 - Number of Ways to Split a String

https://leetcode.com/problems/number-of-ways-to-split-a-string/

Given a binary string s (a string consisting only of ‘0’s and ‘1’s), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).

Return the number of ways s can be split such that the number of characters ‘1’ is the same in s1, s2, and s3.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = “10101”
Output: 4
Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters ‘1’.
“1|010|1”
“1|01|01”
“10|10|1”
“10|1|01”
Example 2:

Input: s = “1001”
Output: 0
Example 3:

Input: s = “0000”
Output: 3
Explanation: There are three ways to split s in 3 parts.
“0|0|00”
“0|00|0”
“00|0|0”
Example 4:

Input: s = “100100010100110”
Output: 12

Constraints:

3 <= s.length <= 10^5
s[i] is ‘0’ or ‘1’.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
int numWays(string s) {
int n = s.size();
int ones = 0;
for (char c : s)
ones += (c == '1');

const int mod = 1e9+7;
long n1, n2;

if (ones == 0) {
n1 = n - 2;
n2 = n - 1;
return (n1 * n2 / 2) % mod;
}

if (ones % 3) return 0;

int i = 0;
int count = 0;
while (i < n) {
count += (s[i] == '1');
if (count == ones/3)
break;
i++;
}

count = 0;
int j = n - 1;
while (j >= 0) {
count += (s[j] == '1');
if (count == ones/3)
break;
j--;
}

int p = i+1, q = j-1;
while (s[p] == '0')
p++;
while (s[q] == '0')
q--;

//cout << p-i << "," << j-q;
n1 = p - i;
n2 = j - q;
long ans = (n1*n2) % mod;
return ans;
}
};

leetcode 1329 - Sort the Matrix Diagonally

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix’s end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

Example 1:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]
Example 2:

Input: mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
Output: [[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
int rows = mat.size(), cols = mat[0].size();

for (int r = 0; r < rows; r++) {
int x = r, y = 0;

vector<int> nums;
while (x < rows && y < cols)
nums.push_back(mat[x++][y++]);
sort(nums.begin(), nums.end());

int i = 0;
x = r;
y = 0;
while (x < rows && y < cols)
mat[x++][y++] = nums[i++];
}

for (int c = 1; c < cols; c++) {
int x = 0, y = c;

vector<int> nums;
while (x < rows && y < cols)
nums.push_back(mat[x++][y++]);
sort(nums.begin(), nums.end());

int i = 0;
x = 0;
y = c;
while (x < rows && y < cols)
mat[x++][y++] = nums[i++];
}

return mat;
}
};

class Solution {
public:
vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
unordered_map<int, priority_queue<int, vector<int>, greater<int>>> maps;

int rows = mat.size(), cols = mat[0].size();
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
maps[r - c].push(mat[r][c]);

for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
mat[r][c] = maps[r - c].top();
maps[r - c].pop();
}
}

return mat;
}
};

leetcode 253

https://leetcode.com/problems/meeting-rooms-ii/

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

Constraints:

1 <= intervals.length <= 10^4
0 <= starti < endi <= 10^6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
struct comp {
bool operator()(const vector<int> &itv1, const vector<int> &itv2) {
return itv1[1] > itv2[1];
}
};

int minMeetingRooms(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());

priority_queue<vector<int>, vector<vector<int>>, comp> pq;

int n = intervals.size();

pq.push(intervals[0]);
for (int i = 1; i < n; i++) {
if (intervals[i][0] >= pq.top()[1])
pq.pop();
pq.push(intervals[i]);
}

return pq.size();
}
};

leetcode 54 - Spiral Matrix

https://leetcode.com/problems/spiral-matrix/
https://leetcode.com/problems/spiral-matrix/solution/

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty()) return {};

int r1 = 0, c1 = 0;
int r2 = matrix.size() - 1, c2 = matrix[0].size() - 1;

vector<int> result;

while (r1 <= r2 && c1 <= c2) {
for (int c = c1; c <= c2; c++)
result.push_back(matrix[r1][c]);
for (int r = r1+1; r <= r2; r++)
result.push_back(matrix[r][c2]);

if (r1 < r2 && c1 < c2) {
for (int c = c2-1; c > c1; c--)
result.push_back(matrix[r2][c]);
for (int r = r2; r > r1; r--)
result.push_back(matrix[r][c1]);
}

r1++;
c1++;
r2--;
c2--;
}

return result;
}
};

leetcode 50 - Pow(x, n)

https://leetcode.com/problems/powx-n/
https://leetcode.com/problems/powx-n/solution/

Implement pow(x, n), which calculates x raised to the power n (i.e. xn).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Constraints:

-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-10^4 <= x^n <= 10^4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//Time O(logN), Space O(logN)
class Solution {
public:
double myPow(double x, int n) {
if (n == 0) return 1;
long nn = abs(n);
double res = helper(x, nn);
if (n < 0)
res = 1.0/res;

return res;
}

double helper(double x, long n) {
if (n == 1)
return x;

double res = helper(x, n/2);
res *= res;
if (n % 2 == 1)
res *= x;

return res;
}
};

//Time O(logN), Space O(1)
class Solution {
public:
double myPow(double x, int n) {
if (n == 0) return 1;

long nn = n;

if (nn < 0) {
x = 1.0/x;
nn = -nn;
}

double pow = x;
double result = 1;

while (nn) {//101
if (nn & 1)
result *= pow;
nn = nn >> 1;
pow = pow * pow;
}

return result;
}
};

leetcode 953 - Verifying an Alien Dictionary

https://leetcode.com/problems/verifying-an-alien-dictionary/

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Example 1:

Input: words = [“hello”,”leetcode”], order = “hlabcdefgijkmnopqrstuvwxyz”
Output: true
Explanation: As ‘h’ comes before ‘l’ in this language, then the sequence is sorted.
Example 2:

Input: words = [“word”,”world”,”row”], order = “worldabcefghijkmnpqstuvxyz”
Output: false
Explanation: As ‘d’ comes after ‘l’ in this language, then words[0] > words[1], hence the sequence is unsorted.
Example 3:

Input: words = [“apple”,”app”], order = “abcdefghijklmnopqrstuvwxyz”
Output: false
Explanation: The first three characters “app” match, and the second string is shorter (in size.) According to lexicographical rules “apple” > “app”, because ‘l’ > ‘∅’, where ‘∅’ is defined as the blank character which is less than any other character (More info).

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are English lowercase letters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
unordered_map<char,int> order_map; //letter ==> value
int n = order.size();
for (int i = 0; i < n; i++)
order_map[order[i]] = i;

n = words.size();
for (int i = 0; i < n-1; i++) {
if (less_than(words[i], words[i+1], order_map) == false)
return false;
}

return true;
}

bool less_than(string &word1, string &word2, unordered_map<char,int> &order_map) {
int len1 = word1.size(), len2 = word2.size();

int i = 0, j = 0;
while (i < len1 && j < len2) {
if (order_map[word1[i]] < order_map[word2[j]])
return true;
if (order_map[word1[i]] > order_map[word2[j]])
return false;
i++;
j++;
}

return len1 <= len2;
}
};