3244. Shortest Distance After Road Addition Queries II

Problem Description

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.

Intuition

To solve this problem, define an array nxt where nxt[i] denotes the next city that can be reached directly from city i. Initially, this array reflects the straight path from city 0 to city n-1, meaning nxt[i] = i + 1 for each city.

The key to this solution lies in efficiently finding out the shortest path using the updates provided in the queries. We are essentially asked to maintain a dynamic "shortcut" system and calculate the shortest path each time a new shortcut is added.

For each query [u, v], if the newly added connection could create a shorter path than the current path, we register this connection by updating our nxt array from the position u to v - 1, thus potentially shortening the path. A counter variable cnt maintains the length of this shortest path. Initially, cnt is set to n - 1 because that's the direct distance from one end to the other when there are no additional connections.

By reducing the connection length optimally, the nxt array helps in identifying how many direct connections have been "bypassed," which subsequently reduces cnt. Each query modifies this path and updates the shortest distance accordingly.

The approach takes advantage of "skipping" cities in between u and v, effectively creating a dynamic segment of connections that ensure the smallest travel count to the end city. This method is mindful of the constraint that no two queries will overlap in a way that requires re-evaluation, allowing each query to be processed in sequence efficiently.

Learn more about Greedy and Graph patterns.

Solution Approach

The solution employs a greedy strategy combined with maintaining an array to quickly navigate between cities, optimizing the shortest path calculation based on the queries:

Data Structure Initialization:
- Initialize an array nxt such that nxt[i] represents the next city accessible from city i. The array is filled as nxt[i] = i + 1, setting up the initial linear path between consecutive cities.
Path Length Tracking:
- Introduce a variable cnt to keep track of the length of the shortest path from city 0 to city n-1. Initially set cnt = n - 1, reflecting the direct path when no additional roads have been added.
Processing Queries:
- For each query [u, v], check if there's an opportunity to bypass some cities by adding the new road from u to v:
  - If the nxt[u] city lies between u and v, iterate from nxt[u] to v - 1.
  - Within this loop, continually decrease cnt by 1 for each city identified between these bounds, effectively reducing the total path length.
  - Each iteration updates nxt[i] of these intermediate cities to 0, marking them as "bypassed".
Updating Path:
- Set nxt[u] = v to record the new shortcut from u to v.
- Append the updated cnt value to the result list ans after processing each query, ensuring efficient update of the shortest path.

This approach efficiently manages the dynamic creation of shortcuts (new roads) by maintaining a focus on reducing unnecessary travel between cities, leveraging the direct updates made possible through the nxt array and the cnt variable.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a simple example to demonstrate the solution approach:

Example:

Suppose n = 5 and queries = [[1, 4], [2, 3]].

Initial Setup:
- Cities: 0 -> 1 -> 2 -> 3 -> 4
- nxt = [1, 2, 3, 4, 5] (where nxt[i] = i + 1)
- cnt = 4 (initially the path length from city 0 to city 4 is 4)
Processing Queries:
- First Query: [1, 4]
  - We try to create a shortcut from city 1 to city 4.
  - Check whether nxt[1] (currently 2) is between 1 and 4, since it is, update nxt from city 1 to city 4 - 1:
    - Starting at city 1, decrease cnt:
      - City 1: nxt[1] = 0, cnt = 3 (bypassing city 2)
      - City 2: nxt[2] = 0, cnt = 2 (bypassing city 3)
  - Update nxt[1] = 4, marking the bypass completion.
- Second Query: [2, 3]
  - Attempt to add a road from city 2 to city 3.
  - nxt[2] is currently 0, indicating 2 to 3 is bypassed due to the previous query.
  - No additional cities to bypass, and cnt remains 2.
Result Compilation:
- For the first query, the shortest path length is 2 (by taking route 0 -> 1 -> 4).
- For the second query, the path length is also 2 (still 0 -> 1 -> 4 or direct via 0 -> 1 -> 3), so both maintain a length of 2.

Result: [2, 2]

Solution Implementation

1from typing import List
2
3class Solution:
4    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
5        # Initialize the 'nxt' list where each element points to the next index
6        nxt = list(range(1, n))
7      
8        # Prepare a list to store the answer after each query
9        ans = []
10      
11        # Initialize the count of current connections
12        cnt = n - 1
13      
14        # Iterate over each query which contains nodes u and v
15        for u, v in queries:
16            # Check if there is a valid connection from u to v
17            if 0 < nxt[u] < v:
18                # Start from the next node after u
19                i = nxt[u]
20                # Traverse the nodes until we reach or exceed v
21                while i < v:
22                    cnt -= 1  # Decrease the count for each connection removed
23                    nxt[i], i = 0, nxt[i]  # Mark the current as visited and move to the next node
24                # Set the connection from u to v
25                nxt[u] = v
26            # Append the current count to the answer list
27            ans.append(cnt)
28      
29        # Return the list of counts after each query
30        return ans
31

1class Solution {
2    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
3        // Array 'nxt' stores the next node for each position; initialized from 1 to n-1.
4        int[] next = new int[n - 1];
5        for (int i = 1; i < n; ++i) {
6            next[i - 1] = i;
7        }
8      
9        int queryCount = queries.length; // Total number of queries.
10        int remainingEdges = n - 1; // Count of remaining edges initially set to n-1.
11        int[] results = new int[queryCount]; // Array to store the result for each query.
12      
13        for (int i = 0; i < queryCount; ++i) {
14            int u = queries[i][0], v = queries[i][1]; // For each query, extract u and v.
15          
16            // Check if 'next[u]' points to a valid node and is less than 'v'.
17            if (next[u] > 0 && next[u] < v) {
18                int j = next[u];
19              
20                // Traverse from 'next[u]' to 'v', marking nodes and updating remaining edges count.
21                while (j < v) {
22                    --remainingEdges;
23                    int temp = next[j];
24                    next[j] = 0; // Mark the node as visited.
25                    j = temp; // Move to the next node.
26                }
27                next[u] = v; // Update 'next[u]' to point to 'v'.
28            }
29            results[i] = remainingEdges; // Store the number of remaining edges after this query.
30        }
31        return results; // Return results for all queries.
32    }
33}
34

1#include <vector>
2#include <numeric> // For std::iota
3
4class Solution {
5public:
6    std::vector<int> shortestDistanceAfterQueries(int n, std::vector<std::vector<int>>& queries) {
7        // Initialize a vector 'next' to store the next index for each element
8        std::vector<int> next(n - 1);
9
10        // Fill the vector 'next' such that next[i] == i + 1
11        std::iota(next.begin(), next.end(), 1);
12      
13        int remainingEdges = n - 1; // Counter for the remaining edges
14        std::vector<int> result;    // To store results for each query
15
16        // Process each query
17        for (const auto& query : queries) {
18            int start = query[0];
19            int end = query[1];
20
21            // If there's a valid path from 'start' and the next value is less than 'end'
22            if (next[start] && next[start] < end) {
23                int i = next[start];
24              
25                // Traverse and remove edges until reaching 'end'
26                while (i < end) {
27                    --remainingEdges;  // Reduce the number of remaining edges
28                    int temp = next[i];
29                    next[i] = 0;      // Mark the edge as removed
30                    i = temp;
31                }
32              
33                next[start] = end; // Link start directly to end
34            }
35          
36            result.push_back(remainingEdges); // Record the result for the query
37        }
38      
39        return result; // Return the results for all queries
40    }
41};
42

1/**
2 * Function to calculate the shortest distance after processing a series of queries.
3 * 
4 * @param n - The number of nodes.
5 * @param queries - An array where each element is a query represented as a two-element array [u, v].
6 * @returns An array representing the shortest distance after each query.
7 */
8function shortestDistanceAfterQueries(n: number, queries: number[][]): number[] {
9    // Array to store the next position for each node, initialized to the next node index.
10    const nxt: number[] = Array.from({ length: n - 1 }, (_, i) => i + 1);
11
12    // Array to store the result distances after each query.
13    const ans: number[] = [];
14
15    // Counter for the remaining distance, initially the number of edges (n - 1).
16    let cnt = n - 1;
17
18    // Process each query.
19    for (const [u, v] of queries) {
20        // Check if the current next node of 'u' is valid and less than 'v'.
21        if (nxt[u] && nxt[u] < v) {
22            // Start from the next node of 'u'.
23            let i = nxt[u];
24
25            // Loop to traverse and mark nodes until reaching 'v'.
26            while (i < v) {
27                --cnt; // Decrease the remaining distance counter.
28
29                // Update the next position of current node 'i' with 0 to mark it as visited,
30                // and proceed to the next node saved in 'nxt[i]'.
31                [nxt[i], i] = [0, nxt[i]];
32            }
33          
34            // Update the next position for 'u' to 'v'.
35            nxt[u] = v;
36        }
37
38        // Push the current remaining distance after processing the query.
39        ans.push(cnt);
40    }
41  
42    return ans;
43}
44

Time and Space Complexity

The time complexity of the code is O(n + q), where n is the number of cities, and q is the number of queries. This complexity arises from the initialization of the nxt list, which is O(n), and processing each query at most results in linear traversal operations, cumulative over all queries, thus O(q).

The space complexity of the code is O(n), due to the nxt list, which stores one value for each of the n cities.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know