2024 June 8 Problems
47 views
Skip to first unread message
daryl...@gmail.com
Jun 8, 2024, 12:33:31 PMJun 8
to leetcode-meetup
Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.
Please post your solutions to this thread so others can use this as a reference.
637Average of Levels in Binary Tree72.8%Easy
2685Count the Number of Complete Components65.3%Medium
2850Minimum Moves to Spread Stones Over Grid43.9%Medium
Please download and import the following iCalendar (.ics) files to your calendar system.
Weekly: https://us04web.zoom.us/meeting/upIqc-6upj8sGt0O2fJXTw2gC4FxRMQ-iqAT/ics?icsToken=98tyKu6uqT8tHNyRthmOR7YAB4-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZJoin Zoom Meeting (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1
Meeting ID: 767 4768 4609
Passcode: 8wf3Qa
Aks
Jun 8, 2024, 12:34:42 PMJun 8
to leetcod...@googlegroups.com
Hi,
Which library are you meeting today ?
Sincerely,
Akshay A
--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/leetcode-meetup/656b79b9-96fe-4437-9dee-65a670c2dc4dn%40googlegroups.com.
daryl...@gmail.com
Jun 8, 2024, 1:40:53 PMJun 8
to leetcode-meetup
Hello Akshay:
The in person meetings are at the Northside Branch Library. Attendance has declined since COVID but we still have a few people there. Everyone else working on problems remotely will join the Zoom call at 11:30.
Vivek H
Jun 8, 2024, 2:08:33 PMJun 8
to leetcod...@googlegroups.com
**************************************************************************************
*************************************************************************************
class Solution {
public:
map<vector<int>, int> edgeMap;
int component;
void bfs(map<int, vector<int>>& G, int start, vector<int>& visited) {
queue<int> Q;
Q.push(start);
vector<int> nodeVisited;
while(!Q.empty()) {
int front = Q.front();
Q.pop();
nodeVisited.push_back(front);
for(int i=0; i<G[front].size(); i++) {
if(!visited[G[front][i]]) {
visited[G[front][i]] = 1;
Q.push(G[front][i]);
}
}
}
bool isConnectedFound = true;
if(nodeVisited.size() == 1 || nodeVisited.size() == 2)
component++;
else {
for(int i=0; i<nodeVisited.size()-1; i++) {
for(int j=i+1; j<nodeVisited.size(); j++) {
if(edgeMap.count({nodeVisited[i], nodeVisited[j]}) == 0) {
isConnectedFound = false;
break;
}
}
}
if(isConnectedFound)
component++;
}
/*for(auto &a : nodeVisited) {
cout << a << " ";
}
cout << endl;*/
}
int countCompleteComponents(int n, vector<vector<int>>& edges) {
map<int, vector<int>> graph;
//intialize the map
for(int i=0; i<n; i++) {
graph[i] = vector<int>{};
}
for(int i=0; i<edges.size(); i++) {
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
edgeMap[{edges[i][0], edges[i][1]}]++;
edgeMap[{edges[i][1], edges[i][0]}]++;
}
vector<int> visited(n, 0);
component = 0;
for(int i=0; i<n; i++) {
if(!visited[i]) {
visited[i] = 1;
bfs(graph, i, visited);
}
}
//cout << "component:" << component << endl;
return component;
}
};
--
Carlos Green
Jun 8, 2024, 3:06:31 PMJun 8
to leetcode-meetup
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
Time & Space O(n)
*/
var averageOfLevels = function(root) {
const levels = {}
const averages = []
const queue = [[root, 0]]
while(queue.length !== 0) {
const [node, level] = queue.shift()
if (levels[level]) {
levels[level].push(node.val)
} else {
levels[level] = [node.val]
}
if (node.left) {queue.push([node.left, level + 1])}
if (node.right) {queue.push([node.right, level + 1])}
}
for (let key in levels) {
const len = levels[key].length
const val = levels[key].reduce((a,c) => a += c, 0)
averages.push(val / len)
}
return averages
};
vinay
Jun 15, 2024, 12:49:44 PMJun 15
to leetcod...@googlegroups.com
I took the union find approach to establish the parent nodes
Then for each vertex, I lookup parent and maintain a mapping of parent -> child nodes
Then for each edge, from -> to, lookup parent of "from" and maintain edge count for that parent
So in this graph if edges were defined as (a,b), (a,d), (b,c), (b,d), (c,d), (c,a)
we would have 'a' as parent node for all a,b,c,d
and the path count from 'a' to 'c' and 'b' to 'c' can be counted under 'a' since 'a' is parent of 'b' (to establish the path count for a complete connected component)
then we could check if path count for given node would be same as (nodeCount)*(nodeCount -1)/2 (Hint 3) and count as a complete component
time complexity: o(v+e)
class Solution {
public int countCompleteComponents(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
// Perform union operations for all edges
for (int[] edge : edges) {
uf.union(edge[0], edge[1]);
}
Map<Integer, Set<Integer>> componentNodes = new HashMap<>();
Map<Integer, Integer> componentEdges = new HashMap<>();
// Count nodes in each component
for (int i = 0; i < n; i++) {
int root = uf.find(i);
componentNodes.putIfAbsent(root, new HashSet<>());
componentNodes.get(root).add(i);
}
// Count edges in each component
for (int[] edge : edges) {
int root = uf.find(edge[0]);
componentEdges.put(root, componentEdges.getOrDefault(root, 0) + 1);
}
int completeComponentsCount = 0;
// Check for complete components
for (Map.Entry<Integer, Set<Integer>> entry : componentNodes.entrySet()) {
int nodeCount = entry.getValue().size();
int edgeCount = componentEdges.getOrDefault(entry.getKey(), 0);
if (edgeCount == nodeCount * (nodeCount - 1) / 2) {
completeComponentsCount += 1;
}
}
return completeComponentsCount;
}
class UnionFind{
int[] rank;
int[] root;
public UnionFind(int s){
rank = new int[s];
root = new int[s];
Arrays.fill(rank, 1);
for(int i = 0; i < s; i++){
root[i] = i;
}
}
public void union(int A, int B){
int rootA = find(A);
int rootB = find(B);
if(rank[rootA] > rank[rootB]){
root[rootB] = rootA;
}else if(rank[rootA] < rank[rootB]){
root[rootA] = rootB;
}else{
root[rootB] = rootA;
rank[rootA] += 1;
}
}
public int find(int node){
if(root[node] == node){
return node;
}else{
return root[node] = find(root[node]);
}
}
public int[] nodes(){
return root;
}
}
}
--
Reply all
Reply to author
Forward
0 new messages