Network Delay Time — Medium Coding Interview Question

Given times[i] = [ui, vi, wi] (source, target, travel time) for n nodes labeled 1 to n, and a starting node k. Return the minimum time for all nodes to receive the signal. If impossible, return -1.

Example

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Output: 2

Constraints

• 1 ≤ k ≤ n ≤ 100
• 1 ≤ times.length ≤ 6000

Topics & Companies

Topics: graphs

Asked by: Amazon, Google, Meta, Microsoft

Optimal Solution Complexity

Time complexity: O(E log V). Space complexity: O(V + E).

Practice more

• All DSA Problems
• DSA Patterns