algorithms

commit 07429cc6a3d3de2c89091e1281a683802c74b431
parent 657898d3beb19a305fb48a90cd8a637a7291975d
Author: Andrew Laack <andrew@laack.co>
Date:   Sun, 23 Aug 2026 11:15:29 -0500

Topological sort in c++

Diffstat:
A
course-schedule-ii/course-schedule-ii.cpp
 | 
71
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
course-schedule/course-schedule.cpp
 | 
69
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
valid-parenthesis/valid-parenthesis-v3.cpp
 | 
30
++++++++++++++++++++++++++++++

3 files changed, 170 insertions(+), 0 deletions(-)
diff --git a/course-schedule-ii/course-schedule-ii.cpp b/course-schedule-ii/course-schedule-ii.cpp
@@ -0,0 +1,71 @@
+class Solution {
+public:
+    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
+                unordered_map<int,unordered_set<int>> edges = {};
+
+        for(auto edge: prerequisites) {
+            if (edges.find(edge[1]) != edges.end()) {
+                edges[edge[1]].insert(edge[0]);
+            }
+            else {
+                edges[edge[1]] = unordered_set<int>{edge[0]};
+            }
+        }
+
+        unordered_set<int> visited = {};
+
+        vector<int> ordering =  {};
+
+        for(int i = 0; i < numCourses; ++i) {
+                        
+            // can't cause cycles if no out edges
+            if(edges.find(i) == edges.end()) {
+                if(visited.find(i) == visited.end()) {
+                    visited.insert(i);
+                    ordering.push_back(i);
+                }
+            }
+
+            if(visited.find(i) != visited.end()) {
+                continue;
+            }
+
+            unordered_set<int> traversedFromStart = {};
+            
+            if (!dfsAcyclic(visited, edges, traversedFromStart, i, ordering)) {
+                return vector<int> {};
+            }
+
+        }
+
+        std::reverse(ordering.begin(), ordering.end());
+        return ordering;
+
+        
+    }
+private:
+    bool dfsAcyclic(
+        unordered_set<int>& visited, 
+        unordered_map<int,unordered_set<int>>& edges, 
+        unordered_set<int>& traversedFromStart,
+        int current,
+        vector<int>& ordering) {
+
+            if(traversedFromStart.find(current) != traversedFromStart.end()) {
+                return false;
+            }
+
+            for(auto outEdge: edges[current]) {
+                if(visited.find(outEdge) == visited.end()) {
+                    traversedFromStart.insert(current);
+                    if (!dfsAcyclic(visited, edges, traversedFromStart, outEdge, ordering)) {
+                        return false;
+                    }
+                }
+            }
+
+            visited.insert(current);
+            ordering.push_back(current);
+            return true;
+        }
+};
diff --git a/course-schedule/course-schedule.cpp b/course-schedule/course-schedule.cpp
@@ -0,0 +1,69 @@
+class Solution {
+public:
+    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
+        // since we can take arbitrarily many courses, we simply have to find
+        // a cycle in the directed graph of prerequisites.
+
+        // representation of graph:
+        // [0,1] -> 1 must be completed to take 0. 
+        // e.g. e = (1,0)
+
+        // we know, based on this requirement:
+        // 0 <= ai, bi < numCourses
+        // that all courses are bounded ints in the interval [0,numCourses)
+
+        unordered_map<int,unordered_set<int>> edges = {};
+
+        for(auto edge: prerequisites) {
+            if (edges.find(edge[1]) != edges.end()) {
+                edges[edge[1]].insert(edge[0]);
+            }
+            else {
+                edges[edge[1]] = unordered_set<int>{edge[0]};
+            }
+        }
+
+        unordered_set<int> visited = {};
+
+        for(int i = 0; i < numCourses; ++i) {
+                        
+            if(edges.find(i) == edges.end() || visited.find(i) != visited.end()) {
+                continue;
+            }
+
+            unordered_set<int> traversedFromStart = {};
+            
+            if (!dfsAcyclic(visited, edges, traversedFromStart, i)) {
+                return false;
+            }
+
+        }
+
+        return true;
+
+        
+    }
+private:
+    bool dfsAcyclic(
+        unordered_set<int>& visited, 
+        unordered_map<int,unordered_set<int>>& edges, 
+        unordered_set<int>& traversedFromStart,
+        int current) {
+
+            if(traversedFromStart.find(current) != traversedFromStart.end()) {
+                return false;
+            }
+
+            for(auto outEdge: edges[current]) {
+                if(visited.find(outEdge) == visited.end()) {
+                    traversedFromStart.insert(current);
+                    if (!dfsAcyclic(visited, edges, traversedFromStart, outEdge)) {
+                        return false;
+                    }
+                }
+            }
+
+            visited.insert(current);
+            return true;
+        }
+};
diff --git a/valid-parenthesis/valid-parenthesis-v3.cpp b/valid-parenthesis/valid-parenthesis-v3.cpp
@@ -0,0 +1,30 @@
+class Solution {
+public:
+    bool isValid(string s) {
+        vector<char> stack = {};
+
+        unordered_map<char, char> mapping = {
+            {'(', ')'},
+            {'{', '}'},
+            {'[', ']'}
+        };
+
+        for (char value: s) {
+           if(mapping.find(value) != mapping.end()){
+            stack.push_back(value);
+           }
+           else {
+            
+            if (stack.size() == 0) return false;
+
+            char lastOpening = stack.back();
+            stack.pop_back();
+
+            if (mapping[lastOpening] != value) return false;
+
+           }
+        }
+
+        return stack.size() == 0;
+    }
+};