Find if Path Exists in Graph - Practice Coding Problems

Find if Path Exists in Graph - Problem

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.

Input & Output

Example 1 — Basic Connected Graph

$ Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2

› Output: true

💡 Note: There are two paths from vertex 0 to vertex 2: 0→1→2 and 0→2. Both are valid paths.

Example 2 — Disconnected Components

$ Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5

› Output: false

💡 Note: Vertex 0 is in component {0,1,2} while vertex 5 is in component {3,4,5}. No path exists between them.

Example 3 — Same Source and Destination

$ Input: n = 1, edges = [], source = 0, destination = 0

› Output: true

💡 Note: Source and destination are the same vertex. A path always exists from a vertex to itself.

Constraints

1 ≤ n ≤ 2 × 10⁵
0 ≤ edges.length ≤ 2 × 10⁵
edges[i].length == 2
0 ≤ u_i, v_i ≤ n - 1
u_i != v_i
0 ≤ source, destination ≤ n - 1

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Given edges [[0,1],[1,2],[2,0]], we want path from 0 to 2

Build Adjacency List

Create bidirectional connections between vertices

Search Algorithm

Use DFS/BFS to explore reachable nodes from source

Result

Return true if destination is reachable, false otherwise

Key Takeaway

🎯 Key Insight: Graph connectivity can be solved efficiently using DFS or BFS traversal in O(V + E) time

Asked in

F Facebook 15 a Amazon 12 G Google 10 M Microsoft 8

The key insight is that this is a graph connectivity problem - we need to determine if two nodes belong to the same connected component. The most efficient approaches are DFS or BFS traversal starting from the source. Both have optimal Time: O(V + E), Space: O(V) complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Paths	O(2^n)	O(n)	Recursively explore all possible paths from source to destination
Depth-First Search (DFS)	O(V + E)	O(V)	Use DFS with visited tracking to find path efficiently
Breadth-First Search (BFS)	O(V + E)	O(V)	Use BFS with queue to explore level by level until destination is found

Brute Force - Try All Paths — Algorithm Steps

Start from source vertex
Try all connected neighbors recursively
Return true if destination is found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at source node

Explore

Try each neighbor recursively

Backtrack

If path fails, backtrack and try next option

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_NODES 200000

int graph[MAX_NODES][MAX_NODES];
int graphSize[MAX_NODES];
bool visited[MAX_NODES];

bool dfsAllPaths(int current, int target, int n) {
    if (current == target) return true;
    
    if (visited[current]) return false;
    
    visited[current] = true;
    
    for (int i = 0; i < graphSize[current]; i++) {
        if (dfsAllPaths(graph[current][i], target, n)) {
            return true;
        }
    }
    
    visited[current] = false;
    return false;
}

bool solution(int n, int edges[][2], int edgesSize, int source, int destination) {
    if (source == destination) return true;
    
    // Initialize graph
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
        visited[i] = false;
    }
    
    // Build adjacency list
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        graph[u][graphSize[u]++] = v;
        graph[v][graphSize[v]++] = u;
    }
    
    return dfsAllPaths(source, destination, n);
}

int main() {
    int n;
    scanf("%d", &n);
    
    char edgesStr[100000];
    scanf("%s", edgesStr);
    
    int source, destination;
    scanf("%d %d", &source, &destination);
    
    // Parse edges (simplified for this example)
    int edges[1000][2];
    int edgesSize = 0;
    
    // Simple parsing - assumes format [[a,b],[c,d]...]
    char* ptr = edgesStr + 1; // Skip first '['
    while (*ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            edges[edgesSize][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            edges[edgesSize][1] = atoi(ptr);
            while (*ptr != ']') ptr++;
            ptr++;
            edgesSize++;
        }
        ptr++;
    }
    
    bool result = solution(n, edges, edgesSize, source, destination);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Without visited tracking, we might explore exponential number of paths

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack can go up to n levels deep

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Paths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler