Minimum Courier Distance — Problem Statement & Solution Guide

GraphsMediumMixed

TimeO(S·(m log n) + k) // S = number of unique sources, k = packages

SpaceO(n + m) // adjacency list + distance array

Problem Description

You are given a weighted graph with n nodes representing towns, and a list of packages, each with a source node and a destination node. The graph is represented as a list of edges, where each edge is a tuple of (source node, destination node, weight). The packages are represented as a list of tuples, where each tuple contains the source node and the destination node of a package. Find the minimum total distance to deliver all packages.

DSA Pattern Breakdown

"Minimum Courier Distance"

medium

WHY DOES IT MATTER?

Shortest‑path query batching is a classic example of the "preprocess‑then‑query" pattern. It teaches candidates how to trade extra preprocessing time and memory for dramatically faster query responses, a skill essential for scaling services that serve millions of requests.

OPTIMIZATION CHALLENGE

The key insight is recognizing overlapping sub‑problems: many packages share the same source node. By collapsing those sub‑problems into a single Dijkstra run, we cut the factor of k (total packages) out of the time complexity.

REAL-WORLD CONNECTION

Think of a logistics platform that needs to estimate delivery times for thousands of orders each day. Instead of recomputing routes from scratch for every order, the system precomputes distances from each warehouse (source) to all possible destinations, then looks up the needed distance instantly—mirroring the Dijkstra‑per‑source strategy.

During an interview, first ask clarifying questions about graph density and query distribution. If the number of distinct sources is small, immediately propose Dijkstra per source; otherwise, suggest Floyd‑Warshall or Johnson’s algorithm for dense or negative‑weight scenarios.

COMPLEXITY AT A GLANCE

⏱ Time:O(S·(m log n) + k) // S = number of unique sources, k = packages

💾 Space:O(n + m) // adjacency list + distance array

Core Theory — Why This Approach?

The problem reduces to answering many shortest‑path queries on a weighted, undirected (or directed) graph. The naive way—running a breadth‑first search or Dijkstra for each package independently—blows up when the number of packages (k) and the graph size (n, m) are large, because each run costs O((n+m) log n) time. The optimal paradigm is to exploit the fact that many packages share the same source (or destination) node. By grouping queries by their source, we can run Dijkstra once per distinct source and reuse the distance array for all packages that start there. If the graph is dense and n is modest (≤400), the Floyd‑Warshall algorithm gives O(n³) all‑pairs distances, turning each query into O(1) look‑ups. This preprocessing trade‑off dramatically reduces the total runtime from O(k·(n+m) log n) to O(S·(n+m) log n) where S is the number of unique sources, or to O(n³) when using Floyd‑Warshall, making the solution scalable for the typical constraints of medium‑difficulty interview problems.

Interview Questions on This Problem

Q1How would you efficiently answer thousands of shortest‑path queries on a sparse graph where many queries share the same start node?

Group queries by their start node, run Dijkstra once per distinct start, store the distance array, and answer each query in O(1) by looking up the distance to its destination. This reduces total time to O(S·(m log n) + k) where S is the number of unique start nodes.

Q2When is Floyd‑Warshall preferable over repeated Dijkstra runs for answering all‑pairs shortest‑path queries?

Floyd‑Warshall runs in O(n³) regardless of edge count, so it is preferable when the graph is dense (m ≈ n²) or when n ≤ ~400, making the cubic term acceptable and avoiding the overhead of a priority queue for each Dijkstra.

Q3Explain how you would modify the solution if edge weights could be negative but there are no negative cycles.

With negative weights, Dijkstra is invalid. Use the Bellman‑Ford algorithm from each distinct source (O(S·n·m)) or run the Johnson’s algorithm: reweight edges using a single Bellman‑Ford pass, then run Dijkstra from each source on the reweighted graph, achieving O(n·m log n) overall.

Examples

Example 1

Input

[[(0, 1, 10), (1, 2, 20)], [(0, 2)]]

Output

Explanation: Step-by-step: with input graph [(0, 1, 10), (1, 2, 20)] and package (0, 2), we find the shortest path from 0 to 2 which is 0->1->2 with total weight 10+20=30

Example 2

Input

[[(0, 1, 5), (1, 2, 5)], [(0, 2)]]

Output

Explanation: Step-by-step: with input graph [(0, 1, 5), (1, 2, 5)] and package (0, 2), we find the shortest path from 0 to 2 which is 0->1->2 with total weight 5+5=10

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Optimal Approach & Strategy

Group packages by source, run Dijkstra once per distinct source, and answer all packages from that source using the precomputed distance array; or use Floyd‑Warshall for dense graphs.

Brute Force Approach

Run Dijkstra (or BFS for unweighted) separately for every package, computing its shortest path from scratch.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(S·(m log n) + k) // S = number of unique sources, k = packages

function solution(edges, packages) {
       const graph = {};
       for (const [u, v, weight] of edges) {
           if (!graph[u]) graph[u] = {};
           if (!graph[v]) graph[v] = {};
           graph[u][v] = weight;
           graph[v][u] = weight; // Assuming undirected graph
       }
       const distances = {};
       for (const [source, destination] of packages) {
           const queue = [[source, 0]];
           const visited = new Set();
           while (queue.length) {
               const [node, distance] = queue.shift();
               if (node === destination) {
                   distances[`${source},${destination}`] = distance;
                   break;
               }
               if (visited.has(node)) continue;
               visited.add(node);
               for (const neighbor in graph[node]) {
                   queue.push([neighbor, distance + graph[node][neighbor]]);
               }
               queue.sort((a, b) => a[1] - b[1]);
           }
       }
       return Math.min(...Object.values(distances));
   }

class Solution {
public:
    int solution(vector<vector<int>>& edges, vector<vector<int>>& packages) {
        unordered_map<int, unordered_map<int, int>> graph;
        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            graph[u][v] = weight;
            graph[v][u] = weight; // Assuming undirected graph
        }
        unordered_map<string, int> distances;
        for (const auto& pkg : packages) {
            int source = pkg[0], destination = pkg[1];
            priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> queue;
            queue.push({0, source});
            unordered_set<int> visited;
            while (!queue.empty()) {
                auto arr = queue.top(); queue.pop();
                int distance = arr[0], node = arr[1];
                if (node == destination) {
                    distances[to_string(source) + "," + to_string(destination)] = distance;
                    break;
                }
                if (visited.find(node) != visited.end()) continue;
                visited.insert(node);
                for (const auto& neighbor : graph[node]) {
                    if (visited.find(neighbor.first) == visited.end()) {
                        queue.push({distance + neighbor.second, neighbor.first});
                    }
                }
            }
        }
        int minDistance = INT_MAX;
        for (const auto& dist : distances) {
            minDistance = min(minDistance, dist.second);
        }
        return minDistance;
    }
}

import java.util.*;
public class Solution {
    public int solution(int[][] edges, int[][] packages) {
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            graph.computeIfAbsent(u, k -> new HashMap<>()).put(v, weight);
            graph.computeIfAbsent(v, k -> new HashMap<>()).put(u, weight); // Assuming undirected graph
        }
        Map<String, Integer> distances = new HashMap<>();
        for (int[] pkg : packages) {
            int source = pkg[0], destination = pkg[1];
            PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
            queue.offer(new int[] {0, source});
            Set<Integer> visited = new HashSet<>();
            while (!queue.isEmpty()) {
                int[] arr = queue.poll();
                int distance = arr[0], node = arr[1];
                if (node == destination) {
                    distances.put(source + "," + destination, distance);
                    break;
                }
                if (visited.contains(node)) continue;
                visited.add(node);
                for (Map.Entry<Integer, Integer> entry : graph.getOrDefault(node, new HashMap<>()).entrySet()) {
                    int neighbor = entry.getKey(), weight = entry.getValue();
                    if (!visited.contains(neighbor)) {
                        queue.offer(new int[] {distance + weight, neighbor});
                    }
                }
            }
        }
        return Collections.min(distances.values());
    }
}

import sys, heapq

def solution(edges, packages):
    graph = {}
    for u, v, weight in edges:
        if u not in graph: graph[u] = {}
        if v not in graph: graph[v] = {}
        graph[u][v] = weight
        graph[v][u] = weight  # Assuming undirected graph
    distances = {}
    for source, destination in packages:
        queue = [(0, source)]
        visited = set()
        while queue:
            distance, node = heapq.heappop(queue)
            if node == destination:
                distances[(source, destination)] = distance
                break
            if node in visited: continue
            visited.add(node)
            for neighbor, weight in graph.get(node, {}).items():
                if neighbor not in visited:
                    heapq.heappush(queue, (distance + weight, neighbor))
    return min(distances.values())

function solution(edges, packages) {
       const graph = {};
       for (const [u, v, weight] of edges) {
           if (!graph[u]) graph[u] = {};
           if (!graph[v]) graph[v] = {};
           graph[u][v] = weight;
           graph[v][u] = weight; // Assuming undirected graph
       }
       const distances = {};
       for (const [source, destination] of packages) {
           const queue = [[source, 0]];
           const visited = new Set();
           while (queue.length) {
               const [node, distance] = queue.shift();
               if (node === destination) {
                   distances[`${source},${destination}`] = distance;
                   break;
               }
               if (visited.has(node)) continue;
               visited.add(node);
               for (const neighbor in graph[node]) {
                   queue.push([neighbor, distance + graph[node][neighbor]]);
               }
               queue.sort((a, b) => a[1] - b[1]);
           }
       }
       return Math.min(...Object.values(distances));
   }

Asked in Top Tech Interviews

uncategorizedmediumgeneric

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Minimum Courier Distance Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Graphs

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Minimum Courier Distance — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor