We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Distance After Road Addition Queries II

Number: 3514

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

There are n cities numbered 0 to n–1. Initially the cities form a chain with a unidirectional road from city i to i+1 (for 0 ≤ i < n–1). We are given a list of queries, where each query adds a new unidirectional road from city u to city v (with u < v and the “jump” v–u is at least 2). After each query the task is to find the length (number of roads used) of the shortest path from city 0 to city n–1 taking into account both the original roads and all added roads so far. In addition, the queries are “non‑crossing” – no two queries (u₁,v₁) and (u₂,v₂) satisfy u₁ < u₂ < v₁ < v₂.

Key Insights

  • The baseline path is simply following the chain 0→1→…→n–1, so the cost initially is n–1.
  • A new road (u,v) provides a shortcut; if the best cost to reach u is known then cost[v] can potentially be updated to cost[u] + 1.
  • The original chain guarantees that after any update the recurrence dp[i+1] ≤ dp[i] + 1 holds.
  • Because roads are only added (not removed) and updates only lower the “dp” cost, each city’s best distance only decreases over time.
  • The “non‐crossing” property of queries implies that any two added shortcuts either do not interact or are nested. This lets us “propagate” improvements in an amortized efficient manner.

Space and Time Complexity

Time Complexity: O(n + q) in an amortized sense – each city’s distance is updated only when a shortcut strictly improves it. Space Complexity: O(n) – we use an array of size n to store the shortest distance from 0 to i.

Solution

We will maintain an array dp of length n where dp[i] represents the shortest distance from city 0 to city i. Initially dp[i] = i, corresponding to traveling along the chain. When a query (u,v) is added, we use the fact that a new road gives a candidate cost = dp[u] + 1 for reaching city v. If dp[v] improves (i.e. becomes lower than its current value), then the improved value might allow further “propagation” – namely we can update subsequent cities using the property dp[i+1] = min( dp[i+1], dp[i] + 1 ). Because queries only ever decrease dp-values and because of the non‐crossing property the propagation (performed via a simple while‑loop) has an amortized linear cost overall.

The main idea is:

  1. For each query (u,v), check if dp[v] > dp[u] + 1. If yes, update dp[v] and then “push” that improvement forward: for every city j > v, if dp[j] > dp[j–1] + 1 then update dp[j] to dp[j–1] + 1.
  2. Answer for the query is dp[n–1] after processing the query.
  3. Because of the amortized effect (each dp[j] is “lowered” only a limited number of times) the overall procedure is efficient.

We now provide implementations in Python, JavaScript, C++ and Java. Each version includes plentiful inline comments.

Code Solutions

# Python solution
def shortestDistance(n, queries):
    # initialize dp array: dp[i] is the shortest distance (number of roads) to reach city i
    dp = list(range(n))  # since initially city i is reached from 0 in i steps via chain
    answers = []
    
    # process each query (adding a new road u -> v)
    for u, v in queries:
        # Check if the new query offers a better way to reach city v.
        if dp[v] > dp[u] + 1:
            dp[v] = dp[u] + 1
            # Since the dp recurrence gives dp[i+1] <= dp[i] + 1,
            # propagate the improvement forward.
            j = v + 1
            while j < n and dp[j] > dp[j - 1] + 1:
                dp[j] = dp[j - 1] + 1
                j += 1
        # append the current shortest distance from city 0 to city n-1.
        answers.append(dp[n - 1])
    return answers

# Example usage:
n = 5
queries = [[2,4],[0,2],[0,4]]
print(shortestDistance(n, queries))  # Expected output: [3,2,1]
← Back to All Questions