Shortest Distance After Road Addition Queries I

Shortest Distance After Road Addition Queries I - Problem

You are given an integer n and a 2D integer array queries. There are n cities numbered from 0 to n - 1.

Initially, there is a unidirectional road from city i to city i + 1 for all 0 <= i < n - 1.

queries[i] = [u_i, v_i] represents the addition of a new unidirectional road from city u_i to city v_i.

After each query, you need to find the length of the shortest path from city 0 to city n - 1.

Return an array answer where for each i in the range [0, queries.length - 1], answer[i] is the length of the shortest path from city 0 to city n - 1 after processing the first i + 1 queries.

Input & Output

Example 1 — Basic Case

$ Input: n = 5, queries = [[2,4],[0,3],[0,4]]

› Output: [3,2,1]

💡 Note: Initially: 0→1→2→3→4 (distance 4). After [2,4]: 0→1→2→4 (distance 3). After [0,3]: 0→3→4 (distance 2). After [0,4]: 0→4 (distance 1).

Example 2 — Single Query

$ Input: n = 4, queries = [[0,3]]

› Output: [1]

💡 Note: Initially: 0→1→2→3 (distance 3). After [0,3]: direct path 0→3 (distance 1).

Example 3 — No Improvement

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

› Output: [2,2]

💡 Note: Initially: 0→1→2→3 (distance 3). After [1,3]: 0→1→3 (distance 2). After [2,0]: still shortest is 0→1→3 (distance 2).

Constraints

3 ≤ n ≤ 500
1 ≤ queries.length ≤ 500
queries[i].length == 2
0 ≤ u_i < v_i < n
1 < v_i - u_i

Visualization

Tap to expand

Understanding the Visualization

Initial State

Cities connected sequentially: 0→1→2→3→4

Add Roads

New roads create shortcuts between cities

Find Shortest

BFS finds shortest path after each addition

Key Takeaway

🎯 Key Insight: Each new road can potentially create a shorter path, so we need to recalculate the shortest distance using BFS after each addition

Asked in

G Google 15 f Meta 12 a Amazon 10 M Microsoft 8

The key insight is to use BFS after each road addition to find the shortest path in this unweighted graph. Best approach uses efficient adjacency list representation with BFS traversal. Time: O(q × (n + m)), Space: O(n + m)

Common Approaches

Approach	Time	Space	Notes
✓ BFS After Each Query	O(q × (n + m))	O(n + m)	Run BFS from scratch after adding each new road
Efficient BFS with Graph Updates	O(q × (n + m))	O(n + m)	Use adjacency list and optimized BFS for each query

BFS After Each Query — Algorithm Steps

Step 1: Build adjacency list with initial roads
Step 2: For each query, add new road to graph
Step 3: Run BFS to find shortest path from 0 to n-1

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Graph

Cities 0→1→2→3→4 with sequential roads

Add Road

Add shortcut road from query

BFS Search

Find shortest path using breadth-first search

Code -

solution.c — C

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

#define MAX_N 1000
#define MAX_QUERIES 1000

int* solution(int n, int queries[][2], int queriesSize, int* returnSize) {
    // Build initial adjacency list
    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 - 1; i++) {
        graph[i][graphSize[i]++] = i + 1;
    }
    
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int q = 0; q < queriesSize; q++) {
        int u = queries[q][0], v = queries[q][1];
        // Add new road
        graph[u][graphSize[u]++] = v;
        
        // BFS to find shortest path from 0 to n-1
        int queue[MAX_N];
        int visited[MAX_N] = {0};
        int front = 0, rear = 0;
        
        queue[rear++] = 0;
        visited[0] = 1;
        int distance = 0;
        
        while (front < rear) {
            int size = rear - front;
            for (int i = 0; i < size; i++) {
                int city = queue[front++];
                if (city == n - 1) {
                    result[q] = distance;
                    goto next_query;
                }
                
                for (int j = 0; j < graphSize[city]; j++) {
                    int neighbor = graph[city][j];
                    if (!visited[neighbor]) {
                        visited[neighbor] = 1;
                        queue[rear++] = neighbor;
                    }
                }
            }
            distance++;
        }
        next_query:;
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char buffer[10000];
    scanf(" %s", buffer);
    
    // Parse queries - simplified parsing
    int queries[MAX_QUERIES][2];
    int queriesSize = 0;
    
    char* ptr = buffer + 1; // Skip '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            queries[queriesSize][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip ','
            queries[queriesSize][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ']'
            queriesSize++;
        } else {
            ptr++;
        }
    }
    
    int returnSize;
    int* result = solution(n, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × (n + m))

For q queries, each BFS takes O(n + m) where m is number of edges

✓ Linear Growth

Space Complexity

O(n + m)

Adjacency list stores all edges plus BFS queue space

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

287 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

BFS After Each Query — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler