leetcode 261 - Graph Valid Tree

https://leetcode.com/problems/graph-valid-tree/
https://leetcode.com/problems/graph-valid-tree/submissions/

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Example 1:

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

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

Constraints:

1 <= 2000 <= n
0 <= edges.length <= 5000
edges[i].length == 2
0 <= ai, bi < n
ai != bi
There are no self-loops or 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
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
class Solution {
public:
bool validTree(int n, vector<vector<int>>& edges) {
unordered_map<int, vector<int>> graph;
unordered_map<int, int> parent;

for (auto &edge : edges) {
int a = edge[0];
int b = edge[1];
graph[a].push_back(b);
graph[b].push_back(a);
}

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

unordered_set<int> seen;
bool ret = dfs(graph, 0, seen, parent);

return ret && seen.size() == n;
}

bool dfs(unordered_map<int, vector<int>> &graph, int i, unordered_set<int> &seen,
unordered_map<int, int> &parent) {
if (seen.count(i)) return false;

seen.insert(i);

for (int j : graph[i]) {
if (parent[i] == j) continue;

parent[j] = i;

if (dfs(graph, j, seen, parent) == false)
return false;
}

return true;
}
};

class Solution {
public:
bool validTree(int n, vector<vector<int>>& edges) {
if (edges.size() != n-1) return false;

unordered_map<int, vector<int>> graph;

for (auto &edge : edges) {
int a = edge[0];
int b = edge[1];
graph[a].push_back(b);
graph[b].push_back(a);
}

unordered_set<int> seen;
dfs(graph, 0, seen);

return seen.size() == n;
}

void dfs(unordered_map<int, vector<int>> &graph, int i, unordered_set<int> &seen) {
seen.insert(i);

for (int j : graph[i]) {
if (seen.count(j) == 0)
dfs(graph, j, seen);
}
}
};

//UnionFind, path compression and union by size
class Solution {
public:
bool validTree(int n, vector<vector<int>>& edges) {
if (edges.size() != n - 1) return false;

for (int i = 0; i < n; i++) {
parent.push_back(i);
size.push_back(1);
}

for (auto &edge : edges) {
int a = edge[0];
int b = edge[1];

if (Union(a, b) == false)
return false;
}

return true;
}

private:
vector<int> parent;
vector<int> size;

bool Union(int a, int b) {
int p_a = Find(a);
int p_b = Find(b);

if (p_a == p_b) return false;

if (size[p_a] > size[p_b]) {
parent[p_b] = p_a;
size[p_a] += size[p_b];
} else {
parent[p_a] = p_b;
size[p_b] += size[p_a];
}

return true;
}

int Find(int a) {
if (parent[a] != a)
parent[a] = Find(parent[a]);

return parent[a];
}
};

leetcode 150 - Evaluate Reverse Polish Notation

https://leetcode.com/problems/evaluate-reverse-polish-notation/

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Example 1:

Input: tokens = [“2”,”1”,”+”,”3”,”*”]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:

Input: tokens = [“4”,”13”,”5”,”/“,”+”]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:

Input: tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,”*”,”/“,”*”,”17”,”+”,”5”,”+”]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

1 <= tokens.length <= 10^4
tokens[i] is either an operator: “+”, “-“, “*”, or “/“, or an integer in the range [-200, 200].

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
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;

for (auto &token : tokens) {
char c = token[0];

if (isdigit(c) || token.size() > 1) {
stk.push(stoi(token));
continue;
}

int num2 = stk.top(); stk.pop();
int num1 = stk.top(); stk.pop();

if (c == '+')
stk.push(num1 + num2);
else if (c == '-')
stk.push(num1 - num2);
else if (c == '*')
stk.push(num1 * num2);
else
stk.push(num1 / num2);
}

return stk.top();
}
};

leetcode 69 - Sqrt(x)

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Example 1:

Input: x = 4
Output: 2
Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned.

Constraints:

0 <= x <= 2^31 - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int mySqrt(int x) {
if (x < 2) return x;

return binary_search(2, x/2, x);
}

int binary_search(int lo, int hi, int x) {
while (lo <= hi) {
long mid = lo + (hi - lo) / 2;

if (mid * mid > x)
hi = mid - 1;
else
lo = mid + 1;
}

return hi;
}
};

leetcode 1188 - Design Bounded Blocking Queue

https://leetcode.com/problems/design-bounded-blocking-queue/

Implement a thread-safe bounded blocking queue that has the following methods:

BoundedBlockingQueue(int capacity) The constructor initializes the queue with a maximum capacity.
void enqueue(int element) Adds an element to the front of the queue. If the queue is full, the calling thread is blocked until the queue is no longer full.
int dequeue() Returns the element at the rear of the queue and removes it. If the queue is empty, the calling thread is blocked until the queue is no longer empty.
int size() Returns the number of elements currently in the queue.
Your implementation will be tested using multiple threads at the same time. Each thread will either be a producer thread that only makes calls to the enqueue method or a consumer thread that only makes calls to the dequeue method. The size method will be called after every test case.

Please do not use built-in implementations of bounded blocking queue as this will not be accepted in an interview.

Example 1:

Input:
1
1
[“BoundedBlockingQueue”,”enqueue”,”dequeue”,”dequeue”,”enqueue”,”enqueue”,”enqueue”,”enqueue”,”dequeue”]
[[2],[1],[],[],[0],[2],[3],[4],[]]

Output:
[1,0,2,2]

Explanation:
Number of producer threads = 1
Number of consumer threads = 1

BoundedBlockingQueue queue = new BoundedBlockingQueue(2); // initialize the queue with capacity = 2.

queue.enqueue(1); // The producer thread enqueues 1 to the queue.
queue.dequeue(); // The consumer thread calls dequeue and returns 1 from the queue.
queue.dequeue(); // Since the queue is empty, the consumer thread is blocked.
queue.enqueue(0); // The producer thread enqueues 0 to the queue. The consumer thread is unblocked and returns 0 from the queue.
queue.enqueue(2); // The producer thread enqueues 2 to the queue.
queue.enqueue(3); // The producer thread enqueues 3 to the queue.
queue.enqueue(4); // The producer thread is blocked because the queue’s capacity (2) is reached.
queue.dequeue(); // The consumer thread returns 2 from the queue. The producer thread is unblocked and enqueues 4 to the queue.
queue.size(); // 2 elements remaining in the queue. size() is always called at the end of each test case.
Example 2:

Input:
3
4
[“BoundedBlockingQueue”,”enqueue”,”enqueue”,”enqueue”,”dequeue”,”dequeue”,”dequeue”,”enqueue”]
[[3],[1],[0],[2],[],[],[],[3]]
Output:
[1,0,2,1]

Explanation:
Number of producer threads = 3
Number of consumer threads = 4

BoundedBlockingQueue queue = new BoundedBlockingQueue(3); // initialize the queue with capacity = 3.

queue.enqueue(1); // Producer thread P1 enqueues 1 to the queue.
queue.enqueue(0); // Producer thread P2 enqueues 0 to the queue.
queue.enqueue(2); // Producer thread P3 enqueues 2 to the queue.
queue.dequeue(); // Consumer thread C1 calls dequeue.
queue.dequeue(); // Consumer thread C2 calls dequeue.
queue.dequeue(); // Consumer thread C3 calls dequeue.
queue.enqueue(3); // One of the producer threads enqueues 3 to the queue.
queue.size(); // 1 element remaining in the queue.

Since the number of threads for producer/consumer is greater than 1, we do not know how the threads will be scheduled in the operating system, even though the input seems to imply the ordering. Therefore, any of the output [1,0,2] or [1,2,0] or [0,1,2] or [0,2,1] or [2,0,1] or [2,1,0] will be accepted.

Constraints:

1 <= Number of Prdoucers <= 8
1 <= Number of Consumers <= 8
1 <= size <= 30
0 <= element <= 20
The number of calls to enqueue is greater than or equal to the number of calls to dequeue.
At most 40 calls will be made to enque, deque, and size.

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
class BoundedBlockingQueue {
public:
BoundedBlockingQueue(int capacity) {
this->capacity = capacity;
}

void enqueue(int element) {
unique_lock<mutex> lck(mtx);
while (q.size() == capacity)
cv.wait(lck);
q.push(element);
cv.notify_one();
}

int dequeue() {
unique_lock<mutex> lck(mtx);
int element;
while (q.size() == 0)
cv.wait(lck);
element = q.front();
q.pop();
cv.notify_one();
return element;
}

int size() {
unique_lock<mutex> lck(mtx);
return q.size();
}

private:
mutex mtx;
condition_variable cv;

queue<int> q;
int capacity;
};

leetcode 244 - Shortest Word Distance II

https://leetcode.com/problems/shortest-word-distance-ii/

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict.
int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

Example 1:

Input
[“WordDistance”, “shortest”, “shortest”]
[[[“practice”, “makes”, “perfect”, “coding”, “makes”]], [“coding”, “practice”], [“makes”, “coding”]]
Output
[null, 3, 1]

Explanation
WordDistance wordDistance = new WordDistance([“practice”, “makes”, “perfect”, “coding”, “makes”]);
wordDistance.shortest(“coding”, “practice”); // return 3
wordDistance.shortest(“makes”, “coding”); // return 1

Constraints:

1 <= wordsDict.length <= 3 * 10^4
1 <= wordsDict[i].length <= 10
wordsDict[i] consists of lowercase English letters.
word1 and word2 are in wordsDict.
word1 != word2
At most 5000 calls will be made to shortest.

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
class WordDistance {
public:
WordDistance(vector<string>& wordsDict) {
int n = wordsDict.size();

for (int i = 0; i < n; i++)
word_map[wordsDict[i]].push_back(i);
}

int shortest(string word1, string word2) {
auto &index1 = word_map[word1];
auto &index2 = word_map[word2];
int i = 0, j = 0;

int ans = INT_MAX;
while (i < index1.size() && j < index2.size()) {
if (index1[i] < index2[j]) {
ans = min(ans, index2[j] - index1[i]);
i++;
} else {
ans = min(ans, index1[i] - index2[j]);
j++;
}
}

return ans;
}

private:
unordered_map<string, vector<int>> word_map;
};

/**
* Your WordDistance object will be instantiated and called as such:
* WordDistance* obj = new WordDistance(wordsDict);
* int param_1 = obj->shortest(word1,word2);
*/

leetcode 671 - Second Minimum Node In a Binary Tree

https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/
https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/discuss/107159/C%2B%2B-DFS-recursion

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

Input: root = [2,2,5,null,null,5,7]
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
Example 2:

Input: root = [2,2,2]
Output: -1
Explanation: The smallest value is 2, but there isn’t any second smallest value.

Constraints:

The number of nodes in the tree is in the range [1, 25].
1 <= Node.val <= 2^31 - 1
root.val == min(root.left.val, root.right.val) for each internal node of the tree.

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int findSecondMinimumValue(TreeNode* root) {
TreeNode *node = helper(root, root->val);
return node ? node->val : -1;
}

TreeNode *helper(TreeNode *root, int val) {
if (!root) return NULL;

if (root->val != val) return root;

TreeNode *left = helper(root->left, val);
TreeNode *right = helper(root->right, val);
if (left && right) {
if (left->val < right->val)
return left;
else
return right;
} else if (left)
return left;
else
return right;
}
};

leetcode 24 - Swap Nodes in Pairs

https://leetcode.com/problems/swap-nodes-in-pairs/

Given a linked list, swap every two adjacent nodes and return its head.

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]
Example 2:

Input: head = []
Output: []
Example 3:

Input: head = [1]
Output: [1]

Constraints:

The number of nodes in the list is in the range [0, 100].
0 <= Node.val <= 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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *n1 = head;
if (!n1 || !n1->next)
return n1;

ListNode *n2 = n1->next;
ListNode *n3 = n2->next;

n1->next = swapPairs(n3);
n2->next = n1;
return n2;
}
};

leetcode 678 - Valid Parenthesis String

https://leetcode.com/problems/valid-parenthesis-string/
https://leetcode.com/problems/valid-parenthesis-string/discuss/543521/Java-Count-Open-Parenthesis-O(n)-time-O(1)-space-Picture-Explain

Given a string s containing only three types of characters: ‘(‘, ‘)’ and ‘*’, return true if s is valid.

The following rules define a valid string:

Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’.
Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.
Left parenthesis ‘(‘ must go before the corresponding right parenthesis ‘)’.
‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(‘ or an empty string “”.

Example 1:

Input: s = “()”
Output: true
Example 2:

Input: s = “(*)”
Output: true
Example 3:

Input: s = “(*))”
Output: true

Constraints:

1 <= s.length <= 100
s[i] is ‘(‘, ‘)’ or ‘*’.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
bool checkValidString(string s) {
int min_opening = 0, max_opening = 0;

for (char c : s) {
if (c == '(') {
min_opening++;
max_opening++;
} else if (c == ')') {
min_opening--;
max_opening--;
} else {
min_opening--;
max_opening++;
}

if (max_opening < 0) return false;
min_opening = max(min_opening, 0);
}

return min_opening == 0;
}
};