Introduction

In this blog post, we will explore how to solve the LeetCode problem "1971" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. You want to determine if there is a valid path that exists from vertex source to vertex destination. Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise. Example 1: Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 Output: true Explanation: There are two paths from vertex 0 to vertex 2: - 0 → 1 → 2 - 0 → 2 Example 2: Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 Output: false Explanation: There is no path from vertex 0 to vertex 5. Constraints: 1 <= n <= 2 105 0 <= edges.length <= 2 105 edges[i].length == 2 0 <= ui, vi <= n - 1 ui != vi 0 <= source, destination <= n - 1 There are no duplicate edges. There are no self edges.

Explanation

Here's a solution to determine if a path exists between two vertices in a graph:

• Core Idea: Use Breadth-First Search (BFS) or Depth-First Search (DFS) to traverse the graph starting from the source vertex.
• Graph Representation: Represent the graph using an adjacency list for efficient neighbor lookups.

• Path Existence: If the destination vertex is visited during the traversal, a path exists.

• Complexity: Time: O(V + E), where V is the number of vertices and E is the number of edges. Space: O(V + E) due to the adjacency list and queue (BFS) or recursion stack (DFS).

Code

    from collections import deque

def validPath(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    """
    Checks if a valid path exists between source and destination in a graph.

    Args:
        n: The number of vertices in the graph.
        edges: A list of edges, where each edge is a list of two vertices.
        source: The source vertex.
        destination: The destination vertex.

    Returns:
        True if a valid path exists, False otherwise.
    """

    adj_list = [[] for _ in range(n)]
    for u, v in edges:
        adj_list[u].append(v)
        adj_list[v].append(u)

    queue = deque([source])
    visited = [False] * n
    visited[source] = True

    while queue:
        curr = queue.popleft()

        if curr == destination:
            return True

        for neighbor in adj_list[curr]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

    return False