Shortest Distance After Road Addition Queries II

Shortest Distance After Road Addition Queries II - 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.

There are no two queries such that queries[i][0] < queries[j][0] < queries[i][1] < queries[j][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 Road Addition

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

› Output: [2]

💡 Note: Initially: 0→1→2→3→4 (distance 4). After adding road 0→3: shortest path becomes 0→3→4 (distance 2).

Example 2 — Multiple Queries

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

› Output: [2,1]

💡 Note: Initially: 0→1→2→3 (distance 3). After [0,2]: 0→2→3 (distance 2). After [1,3]: 0→2 and optimal becomes 0→2 then skip to 3 via any path giving distance 1.

Example 3 — No Improvement

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

› Output: [2]

💡 Note: Initially: 0→1→2 (distance 2). Adding road 1→2 doesn't create a shortcut from 0 to 2, so distance remains 2.

Constraints

3 ≤ n ≤ 10⁵
1 ≤ queries.length ≤ 10⁵
queries[i].length = 2
0 ≤ u_i < v_i < n
There are no repeated queries

Visualization

Tap to expand

Understanding the Visualization

Initial Network

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

Add Shortcuts

New roads create express routes skipping cities

Calculate Distance

Find shortest path length after each addition

Key Takeaway

🎯 Key Insight: New roads create express lanes that skip intermediate cities, reducing the shortest path distance by eliminating unnecessary stops.

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that new roads create shortcuts that skip intermediate cities. Instead of running BFS after each query, maintain a skip list of reachable cities and remove those that are bypassed by shortcuts. Best approach uses Skip List Optimization with Time: O(q × n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Skip List Optimization	O(q × n)	O(n)	Maintain reachable cities efficiently by tracking which segments can be skipped
BFS After Each Query	O(q × (n + q))	O(n + q)	Run BFS from city 0 to find shortest path after each road addition

Skip List Optimization — Algorithm Steps

Initialize reachable cities as ordered set
For each query, add shortcut and remove skipped cities
Count remaining reachable cities for distance

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

All cities [0,1,2,3,4] are reachable

Add Shortcut

Road [0,3] skips cities 1,2

Update Skip List

Remove skipped cities, count remaining

Code -

solution.c — C

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

int lowerBound(int* arr, int size, int target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = (left + right) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

int upperBound(int* arr, int size, int target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = (left + right) / 2;
        if (arr[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left;
}

int* solution(int n, int** queries, int queriesSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    // Maintain sorted array of reachable cities
    int* reachable = (int*)malloc(n * sizeof(int));
    int reachableSize = n;
    for (int i = 0; i < n; i++) {
        reachable[i] = i;
    }
    
    for (int i = 0; i < queriesSize; i++) {
        int u = queries[i][0];
        int v = queries[i][1];
        
        // Find cities that will be skipped by this shortcut
        int leftIdx = upperBound(reachable, reachableSize, u);
        int rightIdx = lowerBound(reachable, reachableSize, v);
        
        // Remove skipped cities
        if (leftIdx < rightIdx) {
            int removeCount = rightIdx - leftIdx;
            for (int j = leftIdx; j < reachableSize - removeCount; j++) {
                reachable[j] = reachable[j + removeCount];
            }
            reachableSize -= removeCount;
        }
        
        // Distance is number of reachable cities - 1
        result[i] = reachableSize - 1;
    }
    
    free(reachable);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Parse queries array
    int queriesSize = 0;
    int** queries = NULL;
    
    // Count queries by counting '[' after first one
    for (int i = 1; i < strlen(line); i++) {
        if (line[i] == '[') queriesSize++;
    }
    
    queries = (int**)malloc(queriesSize * sizeof(int*));
    for (int i = 0; i < queriesSize; i++) {
        queries[i] = (int*)malloc(2 * sizeof(int));
    }
    
    // Simple parsing
    char* ptr = line + 1; // Skip first '['
    for (int i = 0; i < queriesSize; i++) {
        while (*ptr != '[') ptr++;
        ptr++; // Skip '['
        queries[i][0] = atoi(ptr);
        while (*ptr != ',') ptr++;
        ptr++; // Skip ','
        queries[i][1] = atoi(ptr);
        while (*ptr != ']') ptr++;
        ptr++; // Skip ']'
    }
    
    int returnSize;
    int* result = solution(n, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    // Cleanup
    for (int i = 0; i < queriesSize; i++) {
        free(queries[i]);
    }
    free(queries);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n)

For each query, may need to remove up to n cities from the skip list

✓ Linear Growth

Space Complexity

O(n)

Skip list stores at most n cities

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 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

Skip List Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler