Path Existence Queries in a Graph II - Practice Coding Problems

Path Existence Queries in a Graph II - Problem

Array Two Pointers Binary Search Dynamic Programming Greedy Bit Manipulation Graph Sorting Hard

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 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], find the minimum distance between nodes u_i and v_i. If no path exists between the two nodes, return -1 for that query.

Return an array answer, where answer[i] is the result of the ith query.

Note: The edges between the nodes are unweighted.

Input & Output

Example 1 — Basic Path Query

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

› Output: [3]

💡 Note: Nodes connected if |nums[i] - nums[j]| ≤ 2. Path: 0→1→2→3 (distance 3) since |1-3|≤2, |3-5|≤2, |5-7|≤2

Example 2 — No Path Exists

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

› Output: [-1]

💡 Note: No path from node 0 to node 2. Nodes 0,1 connect (|1-3|≤2) but no connection to nodes 2,3 (|3-10|>2)

Example 3 — Multiple Queries

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

› Output: [1,1,1]

💡 Note: All nodes connected: |2-4|≤3, |2-6|≤3, |4-6|≤3. Each query has direct path (distance 1)

Constraints

2 ≤ n ≤ 10⁴
nums.length == n
-10⁹ ≤ nums[i] ≤ 10⁹
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

n=4 nodes with nums=[1,3,5,7], maxDiff=2, query=[0,3]

Build Graph

Connect nodes where |nums[i]-nums[j]| ≤ 2

BFS Search

Find shortest path from node 0 to node 3

Key Takeaway

🎯 Key Insight: Model as graph connectivity problem - BFS guarantees shortest unweighted path

Asked in

G Google 35 M Meta 28 a Amazon 22

The key insight is to model this as a graph where edges exist between nodes with value differences ≤ maxDiff, then use BFS to find shortest paths. The optimized approach sorts nodes by values to reduce graph construction time from O(n²) to O(n log n + n×k). Time: O(n² + q×n), Space: O(n + e)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Graph Construction with Sorting	O(n log n + n × k + q × (n + e))	O(n + e)	Sort nodes by values to reduce edge checking complexity
Build Graph + BFS for Each Query	O(n² + q × (n + e))	O(n + e)	Build adjacency list, then run BFS from scratch for each query

Optimized Graph Construction with Sorting — Algorithm Steps

Create index array and sort by nums values
For each node, only check nearby nodes within maxDiff
Build graph with reduced comparisons
Run BFS for each query

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Values

Sort node indices by their nums values

Check Nearby

Only check adjacent nodes in sorted order within maxDiff

BFS Query

Use BFS on the efficiently constructed graph

Code -

solution.c — C

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

#define MAX_N 1000
#define MAX_QUEUE 10000

typedef struct {
    int data[MAX_QUEUE][2];
    int front, rear;
} Queue;

void initQueue(Queue* q) {
    q->front = q->rear = 0;
}

bool isEmpty(Queue* q) {
    return q->front == q->rear;
}

void enqueue(Queue* q, int node, int dist) {
    q->data[q->rear][0] = node;
    q->data[q->rear][1] = dist;
    q->rear++;
}

void dequeue(Queue* q, int* node, int* dist) {
    *node = q->data[q->front][0];
    *dist = q->data[q->front][1];
    q->front++;
}

int compare(const void* a, const void* b, void* nums) {
    int* numsArray = (int*)nums;
    int idxA = *(int*)a;
    int idxB = *(int*)b;
    return numsArray[idxA] - numsArray[idxB];
}

int* solution(int n, int* nums, int maxDiff, int** queries, int queriesSize, int* returnSize) {
    // Create sorted indices
    int indices[MAX_N];
    for (int i = 0; i < n; i++) {
        indices[i] = i;
    }
    qsort_r(indices, n, sizeof(int), compare, nums);
    
    // Build adjacency list efficiently
    int graph[MAX_N][MAX_N];
    int graphSize[MAX_N];
    
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
    }
    
    for (int i = 0; i < n; i++) {
        int idx = indices[i];
        // Check only nearby nodes in sorted order
        int j = i + 1;
        while (j < n && nums[indices[j]] - nums[idx] <= maxDiff) {
            graph[idx][graphSize[idx]++] = indices[j];
            graph[indices[j]][graphSize[indices[j]]++] = idx;
            j++;
        }
    }
    
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int q = 0; q < queriesSize; q++) {
        int start = queries[q][0];
        int end = queries[q][1];
        
        if (start == end) {
            result[q] = 0;
            continue;
        }
        
        Queue queue;
        initQueue(&queue);
        bool visited[MAX_N] = {false};
        
        enqueue(&queue, start, 0);
        visited[start] = true;
        
        int found = -1;
        while (!isEmpty(&queue) && found == -1) {
            int node, dist;
            dequeue(&queue, &node, &dist);
            
            for (int i = 0; i < graphSize[node]; i++) {
                int neighbor = graph[node][i];
                if (neighbor == end) {
                    found = dist + 1;
                    break;
                }
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    enqueue(&queue, neighbor, dist + 1);
                }
            }
        }
        
        result[q] = found;
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int nums[MAX_N];
    char line[10000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    // Parse nums array
    char* token = strtok(line + 1, ",]");
    int numsSize = 0;
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int maxDiff;
    scanf("%d", &maxDiff);
    
    int queriesSize;
    scanf("%d", &queriesSize);
    
    int** queries = (int**)malloc(queriesSize * sizeof(int*));
    for (int i = 0; i < queriesSize; i++) {
        queries[i] = (int*)malloc(2 * sizeof(int));
        scanf("%d %d", &queries[i][0], &queries[i][1]);
    }
    
    int returnSize;
    int* result = solution(n, nums, maxDiff, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    for (int i = 0; i < queriesSize; i++) {
        free(queries[i]);
    }
    free(queries);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + n × k + q × (n + e))

O(n log n) for sorting, O(n × k) for graph construction where k is average neighbors, O(q × (n + e)) for BFS queries

⚡ Linearithmic

Space Complexity

O(n + e)

Adjacency list stores up to e edges, plus sorting array and BFS structures

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

890 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

Optimized Graph Construction with Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler