Problems

Master cycle detection algorithms by solving these carefully selected problems. Each problem demonstrates different cycle detection techniques and helps build expertise in graph and linked list algorithms.

Problem List

1. Linked List Cycle

Difficulty: Easy

Brief: Determine if a linked list has a cycle in it.
Why this pattern?: Use the Fast & Slow pointers (Floyd’s Algorithm) to detect a loop in O(N) time and O(1) space.
Key Insight: If there is a cycle, the fast runner will eventually lap the slow runner.

  graph LR
    head(("3")) --> n2(("2"))
    n2 --> n0(("0"))
    n0 --> n4(("-4"))
    n4 --> n2
    style n2 fill:#f9f,stroke:#333,stroke-width:2px

var hasCycle = function(head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
};

def hasCycle(self, head: Optional[ListNode]) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

def hasCycle(head)
    slow = fast = head
    while fast && fast.next
        slow = slow.next
        fast = fast.next.next
        return true if slow == fast
    end
    return false
end

2. Find if Path Exists in Graph

Difficulty: Easy

Brief: Determine if there is a valid path between source and destination vertices.
Why this pattern?: While BFS/DFS is standard, this is a fundamental connectivity check that underpins cycle detection logic.
Key Insight: Use BFS/DFS or Union-Find. If start and end are in the same component, a path exists.

  graph LR
    A((0)) --- B((1))
    B --- C((2))
    A --- C

var validPath = function(n, edges, source, destination) {
    const parent = Array.from({length: n}, (_, i) => i);
    function find(x) {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }
    function union(x, y) {
        parent[find(x)] = find(y);
    }
    for (const [u, v] of edges) union(u, v);
    return find(source) === find(destination);
};

def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
    parent = list(range(n))
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    for u, v in edges:
        parent[find(u)] = find(v)

    return find(source) == find(destination)

public boolean validPath(int n, int[][] edges, int source, int destination) {
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;

    for (int[] edge : edges) {
        int rootU = find(parent, edge[0]);
        int rootV = find(parent, edge[1]);
        if (rootU != rootV) parent[rootU] = rootV;
    }
    return find(parent, source) == find(parent, destination);
}

private int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);
    return parent[x];
}

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    vector<int> parent(n);
    iota(parent.begin(), parent.end(), 0);
    function<int(int)> find = [&](int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    };

    for (auto& e : edges) {
        int rootU = find(e[0]), rootV = find(e[1]);
        if (rootU != rootV) parent[rootU] = rootV;
    }
    return find(source) == find(destination);
}

func validPath(n int, edges [][]int, source int, destination int) bool {
    parent := make([]int, n)
    for i := range parent { parent[i] = i }
    var find func(int) int
    find = func(x int) int {
        if parent[x] != x { parent[x] = find(parent[x]) }
        return parent[x]
    }

    for _, edge := range edges {
        rootU, rootV := find(edge[0]), find(edge[1])
        if rootU != rootV { parent[rootU] = rootV }
    }
    return find(source) == find(destination)
}

def valid_path(n, edges, source, destination)
    parent = (0...n).to_a
    find = ->(x) {
        parent[x] = find.call(parent[x]) if parent[x] != x
        parent[x]
    }

    edges.each do |u, v|
        root_u = find.call(u)
        root_v = find.call(v)
        parent[root_u] = root_v if root_u != root_v
    end
    find.call(source) == find.call(destination)
end

3. Linked List Cycle II

Difficulty: Medium

Brief: Return the node where the cycle begins in a linked list.
Why this pattern?: Extends Floyd’s algorithm. Once a cycle is detected, resetting one pointer allows finding the entrance.
Key Insight: The distance from start to cycle entry is equal to the distance from the meeting point to cycle entry.

  graph LR
    S[Start] --> A((A))
    A --> B((B))
    B --> C((C))
    C --> D((D))
    D --> E((E))
    E --> B
    style B fill:#f9f,stroke:#333

var detectCycle = function(head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            slow = head;
            while (slow !== fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
};

def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            slow = head
            for slow != fast {
                slow = slow.Next
                fast = fast.Next
            }
            return slow
        }
    }
    return nil
}

def detectCycle(head)
    slow = fast = head
    while fast && fast.next
        slow = slow.next
        fast = fast.next.next
        if slow == fast
            slow = head
            while slow != fast
                slow = slow.next
                fast = fast.next
            end
            return slow
        end
    end
    nil
end

4. Course Schedule

Difficulty: Medium

Brief: Determine if you can finish all courses given prerequisite dependencies.
Why this pattern?: Dependencies form a directed graph. A cycle means a deadlock (impossible to finish).
Key Insight: Use Kahn’s Algorithm (Topological Sort). If we can’t remove all nodes (indegree 0), there’s a cycle.

  graph TD
    A[Course 0] --> B[Course 1]
    B --> A
    style A fill:#ff9999
    style B fill:#ff9999

var canFinish = function(numCourses, prerequisites) {
    const graph = Array.from({length: numCourses}, () => []);
    const indegree = new Array(numCourses).fill(0);

    for (const [course, pre] of prerequisites) {
        graph[pre].push(course);
        indegree[course]++;
    }

    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    let visited = 0;
    while (queue.length) {
        const node = queue.shift();
        visited++;
        for (const neighbor of graph[node]) {
            indegree[neighbor]--;
            if (indegree[neighbor] === 0) queue.push(neighbor);
        }
    }

    return visited === numCourses;
};

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses

    for course, pre in prerequisites:
        graph[pre].append(course)
        indegree[course] += 1

    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    visited = 0

    while queue:
        node = queue.popleft()
        visited += 1
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return visited == numCourses

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for(int i=0; i<numCourses; i++) graph.add(new ArrayList<>());
    int[] indegree = new int[numCourses];

    for(int[] edge : prerequisites) {
        graph.get(edge[1]).add(edge[0]);
        indegree[edge[0]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for(int i=0; i<numCourses; i++) {
        if(indegree[i] == 0) queue.offer(i);
    }

    int visited = 0;
    while(!queue.isEmpty()) {
        int node = queue.poll();
        visited++;
        for(int neighbor : graph.get(node)) {
            indegree[neighbor]--;
            if(indegree[neighbor] == 0) queue.offer(neighbor);
        }
    }

    return visited == numCourses;
}

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses);
    vector<int> indegree(numCourses, 0);

    for(auto& edge : prerequisites) {
        graph[edge[1]].push_back(edge[0]);
        indegree[edge[0]]++;
    }

    queue<int> q;
    for(int i=0; i<numCourses; i++) {
        if(indegree[i] == 0) q.push(i);
    }

    int visited = 0;
    while(!q.empty()) {
        int node = q.front(); q.pop();
        visited++;
        for(int neighbor : graph[node]) {
            indegree[neighbor]--;
            if(indegree[neighbor] == 0) q.push(neighbor);
        }
    }

    return visited == numCourses;
}

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := make([][]int, numCourses)
    indegree := make([]int, numCourses)

    for _, edge := range prerequisites {
        graph[edge[1]] = append(graph[edge[1]], edge[0])
        indegree[edge[0]]++
    }

    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    visited := 0
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        visited++

        for _, neighbor := range graph[node] {
            indegree[neighbor]--
            if indegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }

    return visited == numCourses
}

def can_finish(num_courses, prerequisites)
    graph = Array.new(num_courses) { [] }
    indegree = Array.new(num_courses, 0)

    prerequisites.each do |course, pre|
        graph[pre] << course
        indegree[course] += 1
    end

    queue = (0...num_courses).select { |i| indegree[i] == 0 }
    visited = 0

    while !queue.empty?
        node = queue.shift
        visited += 1
        graph[node].each do |neighbor|
            indegree[neighbor] -= 1
            queue.push(neighbor) if indegree[neighbor] == 0
        end
    end

    visited == num_courses
end

5. Graph Valid Tree

Difficulty: Medium

Brief: Check if undirected edges make up a valid tree.
Why this pattern?: A tree must be fully connected and contain NO cycles.
Key Insight: Use Union-Find. If we try to union two nodes that already have the same root, a cycle exists. Also check if edges = n - 1.

  graph TD
    A --- B
    A --- C
    B --- D
    D --- E
    style A fill:#bbf
    style E fill:#bbf

var validTree = function(n, edges) {
    if (edges.length !== n - 1) return false;
    const parent = Array.from({length: n}, (_, i) => i);
    function find(x) {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }
    for (const [u, v] of edges) {
        const rootU = find(u), rootV = find(v);
        if (rootU === rootV) return false;
        parent[rootU] = rootV;
    }
    return true;
};

def validTree(self, n: int, edges: List[List[int]]) -> bool:
    if len(edges) != n - 1: return False
    parent = list(range(n))
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    for u, v in edges:
        root_u, root_v = find(u), find(v)
        if root_u == root_v: return False
        parent[root_u] = root_v
    return True

public boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    for (int[] e : edges) {
        int rU = find(e[0]), rV = find(e[1]);
        if (rU == rV) return false;
        parent[rU] = rV;
    }
    return true;
}

bool validTree(int n, vector<vector<int>>& edges) {
    if (edges.size() != n - 1) return false;
    vector<int> parent(n);
    iota(parent.begin(), parent.end(), 0);
    function<int(int)> find = [&](int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); };

    for (auto& e : edges) {
        int rU = find(e[0]), rV = find(e[1]);
        if (rU == rV) return false;
        parent[rU] = rV;
    }
    return true;
}

func validTree(n int, edges [][]int) bool {
    if len(edges) != n-1 { return false }
    parent := make([]int, n)
    for i := range parent { parent[i] = i }
    var find func(int) int
    find = func(x int) int {
        if parent[x] != x { parent[x] = find(parent[x]) }
        return parent[x]
    }
    for _, e := range edges {
        rU, rV := find(e[0]), find(e[1])
        if rU == rV { return false }
        parent[rU] = rV
    }
    return true
}

def valid_tree(n, edges)
    return false if edges.length != n - 1
    parent = (0...n).to_a
    find = ->(x) {
        parent[x] = find.call(parent[x]) if parent[x] != x
        parent[x]
    }
    edges.each do |u, v|
        root_u = find.call(u)
        root_v = find.call(v)
        return false if root_u == root_v
        parent[root_u] = root_v
    end
    true
end

Recommended Study Order

Cycle Basics: Start with Linked List Cycle to master Floyd’s Algorithm.
Connectivity: Solve Find if Path Exists to understand basic graph traversal.
Graph Cycles: Move to Course Schedule to understand topological sort and DFS cycle detection.
Structure Validation: Solve Graph Valid Tree to apply Union-Find for cycle + connectivity checks.