commit d10cb4dc4b88678c5b802ad76b083c08e1bcd61f
parent 69e20a4474ef66c9db5778893a9c162ef40e98c6
Author: Andrew Laack <andrew@laack.co>
Date: Thu, 10 Sep 2026 10:38:40 -0500
Completed some union find problems
Diffstat:
6 files changed, 324 insertions(+), 0 deletions(-)
diff --git a/longest-consecutive-sequence/longest-consecutive-sequence-v2.py b/longest-consecutive-sequence/longest-consecutive-sequence-v2.py
@@ -0,0 +1,50 @@
+class Node():
+ def __init__(self,parent,num):
+ self.parent = parent
+ self.num = num
+ # only accurate for root of tree
+ self.size = 1
+
+def find(a):
+ if a.parent is None:
+ return a
+ return find(a.parent)
+
+def union(a,b):
+ if b is None:
+ return a.size
+ a_rep = find(a)
+ b_rep = find(b)
+ b_rep.parent = a_rep
+ a_rep.size += b_rep.size
+ return a_rep.size
+
+class Solution:
+ def search(self, current, count):
+ if not current in self.num_set:
+ return count
+ return self.search(current + 1, count + 1)
+
+ def longestConsecutive(self, nums: List[int]) -> int:
+ # idea:
+ # this must be in linear time
+ # this means we can't sort
+ # we can use union find which has amortized constant time union and find ops
+
+ # how?
+ # make the set of our numbers into k disjoint trees
+ # try to union each number with num + 1
+ # return largest sized union
+
+ nodes = {x : Node(None,x) for x in nums}
+
+ # do unions
+ max_size = 0
+
+ for nd_num in nodes:
+ a = nodes.get(nd_num)
+ b = nodes.get(nd_num + 1)
+ un_size = union(a,b)
+ max_size = max(max_size, un_size)
+
+ return max_size
diff --git a/longest-consecutive-sequence/longest-consecutive-sequence-v3.py b/longest-consecutive-sequence/longest-consecutive-sequence-v3.py
@@ -0,0 +1,58 @@
+class Node():
+ def __init__(self,parent,num):
+ self.parent = parent
+ self.num = num
+ # only accurate for root of tree
+ self.size = 1
+
+def find(a):
+ if a.parent is None:
+ return a
+ rep = find(a.parent)
+ a.parent = rep
+ return rep
+
+def union(a,b):
+ if b is None:
+ return a.size
+ a_rep = find(a)
+ b_rep = find(b)
+
+ if a_rep.size > b_rep.size:
+ b_rep.parent = a_rep
+ a_rep.size += b_rep.size
+ return a_rep.size
+ else:
+ a_rep.parent = b_rep
+ b_rep.size += a_rep.size
+ return b_rep.size
+
+class Solution:
+ def search(self, current, count):
+ if not current in self.num_set:
+ return count
+ return self.search(current + 1, count + 1)
+
+ def longestConsecutive(self, nums: List[int]) -> int:
+ # idea:
+ # this must be in linear time
+ # this means we can't sort
+ # we can use union find which has amortized constant time union and find ops
+
+ # how?
+ # make the set of our numbers into k disjoint trees
+ # try to union each number with num + 1
+ # return largest sized union
+
+ nodes = {x : Node(None,x) for x in nums}
+
+ # do unions
+ max_size = 0
+
+ for nd_num in nodes:
+ a = nodes.get(nd_num)
+ b = nodes.get(nd_num + 1)
+ un_size = union(a,b)
+ max_size = max(max_size, un_size)
+
+ return max_size
diff --git a/longest-consecutive-sequence/longest-consecutive-sequence.py b/longest-consecutive-sequence/longest-consecutive-sequence.py
@@ -0,0 +1,24 @@
+class Solution:
+
+ def search(self, current, count):
+ if not current in self.num_set:
+ return count
+ return self.search(current + 1, count + 1)
+
+ def longestConsecutive(self, nums: List[int]) -> int:
+ # idea:
+ # this must be in linear time
+ # this means we can't sort
+ # we can use hashmaps though
+ # with this we could do some sort of key based increment checking, sorta like open addressing
+ # we'd evict elements as we go so we could achieve O(n)
+
+ max_val = 0
+ self.num_set = set(nums)
+
+ for ele in self.num_set:
+ if ele - 1 in self.num_set:
+ continue
+ current = self.search(ele, 0)
+ max_val = max(current,max_val)
+ return max_val
diff --git a/number-of-provinces/number-of-provinces-v2.cpp b/number-of-provinces/number-of-provinces-v2.cpp
@@ -0,0 +1,59 @@
+class Node {
+ public:
+ Node* parent = nullptr;
+ int size = 1;
+};
+
+Node* find(Node& a){
+ if(a.parent == nullptr) {
+ return &a;
+ }
+ auto found = find(*a.parent);
+ a.parent = found;
+ return found;
+}
+
+void union_nodes(Node& a, Node& b) {
+ auto p_a = find(a);
+ auto p_b = find(b);
+ if(p_a != p_b) {
+ if(p_a->size > p_b->size) {
+ p_b->parent = p_a;
+ p_a->size += p_b->size;
+ } else {
+ p_a->parent = p_b;
+ p_b->size += p_a->size;
+ }
+ }
+}
+
+class Solution {
+public:
+ int findCircleNum(vector<vector<int>>& isConnected) {
+
+ unordered_map<int, Node*> provinces {};
+
+ for(int i = 0; i < isConnected.size(); ++i) {
+ Node* node = new Node();
+ provinces[i] = node;
+ }
+
+ for(auto pair: provinces) {
+ vector<int>& adj = isConnected[pair.first];
+ for(int i = 0; i < adj.size(); ++i) {
+ if(adj[i]) {
+ union_nodes(*provinces[i], *pair.second);
+ }
+ }
+ }
+
+ unordered_set<Node*> reps {};
+
+ for(auto pair: provinces) {
+ auto rep = find(*pair.second);
+ reps.insert(rep);
+ }
+
+ return reps.size();
+ }
+};
diff --git a/number-of-provinces/number-of-provinces.cpp b/number-of-provinces/number-of-provinces.cpp
@@ -0,0 +1,51 @@
+class Node {
+ public:
+ Node* parent = nullptr;
+};
+
+
+Node* find(Node& a){
+ if(a.parent == nullptr) {
+ return &a;
+ }
+ return find(*a.parent);
+}
+
+void union_nodes(Node& a, Node& b) {
+ auto p_a = find(a);
+ auto p_b = find(b);
+ if(p_a != p_b) {
+ p_b->parent = p_a;
+ }
+}
+
+class Solution {
+public:
+ int findCircleNum(vector<vector<int>>& isConnected) {
+
+ unordered_map<int, Node*> provinces {};
+
+ for(int i = 0; i < isConnected.size(); ++i) {
+ Node* node = new Node();
+ provinces[i] = node;
+ }
+
+ for(auto pair: provinces) {
+ vector<int>& adj = isConnected[pair.first];
+ for(int i = 0; i < adj.size(); ++i) {
+ if(adj[i]) {
+ union_nodes(*provinces[i], *pair.second);
+ }
+ }
+ }
+
+ unordered_set<Node*> reps {};
+
+ for(auto pair: provinces) {
+ auto rep = find(*pair.second);
+ reps.insert(rep);
+ }
+
+ return reps.size();
+ }
+};
diff --git a/redundant-connection/redundant-connection.cpp b/redundant-connection/redundant-connection.cpp
@@ -0,0 +1,82 @@
+class Node {
+ public:
+ Node* parent = nullptr;
+ int identifier;
+ int size = 1;
+};
+
+Node* find(Node* a) {
+ if(a->parent == nullptr) {
+ return a;
+ }
+ else {
+ auto* rep = find(a->parent);
+ a->parent = rep;
+ return rep;
+ }
+}
+
+// return true if union must be done, false if both have same rep.
+bool union_sets(Node* n1,Node* n2) {
+ auto p_1 = find(n1);
+ auto p_2 = find(n2);
+
+ if(p_1->identifier == p_2->identifier) {
+ return false;
+ }
+
+ if(p_2->size < p_1->size) {
+ p_2->parent = p_1;
+ p_1->size += p_2->size;
+ } else {
+ p_1->parent = p_2;
+ p_2->size += p_1->size;
+ }
+ return true;
+}
+
+class Solution {
+public:
+ vector<int> findRedundantConnection(vector<vector<int>>& edges) {
+ // idea:
+ // - mst where edges are weighted based on position in edges list
+ // - union find where we join on edges in order of inputs
+ // - iff union(a,b) is non-changing, put edge a,b in list of un-necessary eles
+ // - return final element of un-necessary list
+
+ vector<vector<int>> unnecessaryEdges {};
+
+ // key = index of node
+ unordered_map<int, Node*> nodes {};
+
+ for(auto edge: edges) {
+ if(nodes[edge[0]] == nullptr) {
+ nodes[edge[0]] = new Node();
+ nodes[edge[0]]->identifier = edge[0];
+ }
+ if(nodes[edge[1]] == nullptr) {
+ nodes[edge[1]] = new Node();
+ nodes[edge[1]]->identifier = edge[1];
+ }
+ }
+
+ for(auto edge: edges) {
+
+ auto n1 = nodes[edge[0]];
+ auto n2 = nodes[edge[1]];
+
+ bool joined = union_sets(n1,n2);
+ if(not joined) {
+ unnecessaryEdges.push_back(edge);
+ }
+ }
+
+ if(unnecessaryEdges.size() > 0) {
+ return unnecessaryEdges[unnecessaryEdges.size() - 1];
+ }
+ else {
+ return vector<int>{};
+ }
+
+ }
+};
