LeetCode 3244: Shortest Distance After Road Addition Queries II Solution

Master LeetCode problem 3244 (Shortest Distance After Road Addition Queries II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3244. Shortest Distance After Road Addition Queries II

Hard

Array Greedy Graph Ordered Set

Problem Explanation

Explanation

To solve this problem, we can use Dijkstra's algorithm to find the shortest path from city 0 to city n-1 after each query. We will maintain a priority queue to process the queries in increasing order of the road additions.

Initialize an adjacency list representing the initial roads.
Initialize an array dist to store the shortest distance from city 0 to each city.
Initialize a priority queue to store the queries sorted by the road addition order.
Iterate through the queries in the priority queue:
- Add the new road to the adjacency list.
- Run Dijkstra's algorithm to update the shortest path from city 0 to city n-1.
- Store the updated shortest path in the dist array.
Return the dist array as the answer.

Time Complexity:

Building the initial adjacency list: O(n)
Processing each query using Dijkstra's algorithm: O(m log m), where m is the number of queries
Overall time complexity: O(n + m log m)

Space Complexity:

Adjacency list: O(n + m)
Array to store shortest distances: O(n)
Priority queue: O(m)
Overall space complexity: O(n + m)

Solution Code

import java.util.*;

class Solution {
    public int[] shortestDistance(int n, int[][] queries) {
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
            if (i < n - 1) {
                adjList.get(i).add(i + 1);
            }
        }

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (int[] query : queries) {
            pq.offer(query);
        }

        List<Integer> answer = new ArrayList<>();
        for (int i = 0; i < queries.length; i++) {
            int[] query = pq.poll();
            int u = query[0];
            int v = query[1];

            adjList.get(u).add(v);

            dijkstra(adjList, dist, n);

            answer.add(dist[n - 1]);
        }

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }

    private void dijkstra(List<List<Integer>> adjList, int[] dist, int n) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> dist[a] - dist[b]);
        pq.offer(0);

        while (!pq.isEmpty()) {
            int u = pq.poll();

            for (int v : adjList.get(u)) {
                if (dist[u] + 1 < dist[v]) {
                    dist[v] = dist[u] + 1;
                    pq.offer(v);
                }
            }
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3244 (Shortest Distance After Road Addition Queries II)?

This page provides optimized solutions for LeetCode problem 3244 (Shortest Distance After Road Addition Queries II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3244 (Shortest Distance After Road Addition Queries II)?

The time complexity for LeetCode 3244 (Shortest Distance After Road Addition Queries II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3244 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3244 in Java, C++, or Python.

Back to LeetCode Solutions