What is the brute force approach and complexity for Network Delay Time?

Relax every link n − 1 times, keeping the earliest time per node with time complexity O(N · E) and space complexity O(N).

What is the optimal approach and complexity for Network Delay Time?

Pop the earliest pending arrival; the largest final time is the answer with optimal time complexity O((N + E) log N) and space complexity O(N + E).

Network Delay Time

Q: How do you identify the pattern for Network Delay Time?

Look for key signals in the prompt: "time for the signal to reach all the nodes" indicates One source and a time to every node: Dijkstra from k.; "travel time on each link" indicates Weighted edges, so BFS by link count is wrong. Use a heap ordered by time.; "time when the last node receives it" indicates The answer is the largest final distance, not one target and not the sum.; "-1 if some node never receives it" indicates A distance still at the INT_MAX sentinel means unreachable..

Medium·LeetCode #743 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

A network has n nodes numbered 1 to n. You are given times, a list of one-way links [u, v, w]: a signal sent from u reaches v after w time.

A signal starts at node k at time 0 and spreads along the links. Return the time when the last node receives it. If some node never receives it, return -1.

Write int networkDelayTime(vector<vector<int>>& times, int n, int k) inside class Solution.

Input

times, the one-way links. n, the number of nodes. k, the start node.

Output

The time at which the last node gets the signal, or -1 if some node never gets it.

Example 1

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

Output: 2

Node 2 starts at time 0. Nodes 1 and 3 hear it at time 1, and node 4 hears it through node 3 at time 2. The last node hears it at time 2.

Example 2

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

Output: 1

Node 2 hears the signal at time 1.

Example 3

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

Output: -1

There is no link out of node 2, so node 1 never hears the signal.

Constraints

• 1 ≤ k ≤ n ≤ 100
• 1 ≤ times.length ≤ 6000
• times[i].length == 3
• 1 ≤ u_i, v_i ≤ n
• u_i ≠ v_i
• 0 ≤ w_i ≤ 100
• All the pairs (u_i, v_i) are unique.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“time for the signal to reach all the nodes”

→ One source and a time to every node: Dijkstra from k.

“travel time on each link”

→ Weighted edges, so BFS by link count is wrong. Use a heap ordered by time.

“time when the last node receives it”

→ The answer is the largest final distance, not one target and not the sum.

“-1 if some node never receives it”

→ A distance still at the INT_MAX sentinel means unreachable.

Approach Complexity Ladder

Brute Force — Bellman-Ford roundsO(N · E)O(N)

Relax every link n − 1 times, keeping the earliest time per node

Optimal — min-heap DijkstraO((N + E) log N)O(N + E)

Pop the earliest pending arrival; the largest final time is the answer

Brute Force Intuition

Start with time 0 at node k and INT_MAX everywhere else. Go through every link and, whenever a node can hear sooner through that link, lower its time. Do this for n − 1 full rounds. Then take the largest time, or -1 if a node is still unreached.

Recognition rule for this sub-pattern:

Min-heap of (distance, node). Skip stale entries; relax neighbours.

Remember this · Shortest Paths (Weighted)

Trigger

Weighted edges, "minimum cost / time / effort", at most K stops, negative weights, all-pairs distances.

Think

Are edge weights non-negative (Dijkstra), limited by stops (Bellman-Ford), or do I need every pair (Floyd)?

Key question

What is a node's "distance", and when is it final?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Shortest Paths (Weighted) translate into production architectures and low-level memory mechanics.

LLD Architecture