Path Existence Queries in a Graph I - Practice Coding Problems

Path Existence Queries in a Graph I - Problem

You are given an integer n representing the number of nodes in a graph, labeled from 0 to n - 1. You are also given an integer array nums of length n sorted in non-decreasing order, and an integer maxDiff.

An undirected edge exists between nodes i and j if the absolute difference between nums[i] and nums[j] is at most maxDiff (i.e., |nums[i] - nums[j]| <= maxDiff).

You are also given a 2D integer array queries. For each queries[i] = [u_i, v_i], determine whether there exists a path between nodes u_i and v_i.

Return a boolean array answer, where answer[i] is true if there exists a path between u_i and v_i in the i-th query and false otherwise.

Input & Output

Example 1 — Basic Path Queries

$ Input: n = 4, nums = [4,4,2,3], maxDiff = 1, queries = [[2,3],[0,3]]

› Output: [true,false]

Example 2 — All Connected

$ Input: n = 3, nums = [1,2,3], maxDiff = 2, queries = [[0,1],[1,2],[0,2]]

› Output: [true,true,true]

💡 Note: All pairs have difference ≤ 2: |1-2|=1, |1-3|=2, |2-3|=1. All nodes are connected, so all queries return true.

Example 3 — No Connections

$ Input: n = 2, nums = [1,5], maxDiff = 3, queries = [[0,1]]

› Output: [false]

💡 Note: |1-5| = 4 > 3, so no edge exists between nodes 0 and 1. They are not connected.

Constraints

2 ≤ n ≤ 10⁴
nums.length == n
1 ≤ nums[i] ≤ 10⁹
nums is sorted in non-decreasing order
0 ≤ maxDiff ≤ 10⁹
1 ≤ queries.length ≤ 10⁴
queries[i].length == 2
0 ≤ u_i, v_i < n

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Nodes with values, edges where |nums[i] - nums[j]| ≤ maxDiff

Connected Components

Group nodes that can reach each other

Query Results

Check if query nodes are in same component

Key Takeaway

🎯 Key Insight: Precompute connected components using Union-Find for efficient query answering

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to recognize this as a graph connectivity problem. We build edges between nodes where |nums[i] - nums[j]| ≤ maxDiff, then check if query nodes are in the same connected component. Best approach is Union-Find for O(1) query answering after preprocessing. Time: O(n² × α(n) + q), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ DFS for Each Query	O(n² + q × (n + n²))	O(n²)	For each query, use DFS to check if nodes are connected
Union-Find (Disjoint Set)	O(n² × α(n) + q)	O(n)	Use Union-Find to precompute connected components, then answer queries in O(1)

DFS for Each Query — Algorithm Steps

Build adjacency list by checking all node pairs
For each query, run DFS from source node
Return true if target is reachable, false otherwise

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Connect nodes with |nums[i] - nums[j]| ≤ maxDiff

DFS Search

For each query, explore from source to find target

Result

Return true if path found, false otherwise

Code -

solution.c — C

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

bool dfs(int start, int target, int graph[][1000], int graphSize[], bool visited[]) {
    if (start == target) return true;
    visited[start] = true;
    for (int i = 0; i < graphSize[start]; i++) {
        int neighbor = graph[start][i];
        if (!visited[neighbor]) {
            if (dfs(neighbor, target, graph, graphSize, visited)) {
                return true;
            }
        }
    }
    return false;
}

bool* solution(int n, int* nums, int maxDiff, int queries[][2], int queriesSize, int* returnSize) {
    // Build adjacency list
    static int graph[1000][1000];
    static int graphSize[1000] = {0};
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (abs(nums[i] - nums[j]) <= maxDiff) {
                graph[i][graphSize[i]++] = j;
                graph[j][graphSize[j]++] = i;
            }
        }
    }
    
    bool* result = (bool*)malloc(queriesSize * sizeof(bool));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        bool visited[1000] = {false};
        result[i] = dfs(queries[i][0], queries[i][1], graph, graphSize, visited);
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int nums[1000];
    // Simple parsing assuming format [1,2,3]
    
    int maxDiff;
    scanf("%d", &maxDiff);
    
    int queries[1000][2];
    int queriesSize = 0;
    // Parse queries
    
    int returnSize;
    bool* result = solution(n, nums, maxDiff, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf(result[i] ? "true" : "false");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² + q × (n + n²))

O(n²) to build graph, O(n + n²) DFS for each of q queries

⚠ Quadratic Growth

Space Complexity

O(n²)

Adjacency list can store up to n² edges in worst case

⚠ Quadratic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 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

DFS for Each Query — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler