Network Delay Time (Dijkstra)

🎯

Network Delay Time (Dijkstra)

mediumGRAPHAmazonGoogleFacebook

Imagine you are managing a network of servers and want to know how long it takes for a signal to reach all servers starting from one source server.

💡 This problem is about finding the shortest time for a signal to propagate through a network. Beginners often struggle because it involves understanding graph traversal with weighted edges and why simple BFS doesn't work for weighted graphs.

📋

Problem Statement

You are given a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from u to v. There are n nodes labeled from 1 to n. Starting from node k, return the time it takes for all nodes to receive the signal. If it is impossible for all nodes to receive the signal, return -1.

1 ≤ n ≤ 10^51 ≤ times.length ≤ 10^5times[i].length == 31 ≤ u, v ≤ n1 ≤ w ≤ 100All edges are directed

💡

Example

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

Output2

Starting at node 2, signal reaches node 1 and 3 in 1 unit time, then node 4 in 2 units time.

• No edges in times → output -1 (nodes unreachable)
• Single node network (n=1) → output 0 (signal already at node)
• Graph with cycles → algorithm must avoid infinite loops
• Disconnected graph where some nodes can't be reached → output -1

⚠️

Common Mistakes

Using BFS instead of Dijkstra for weighted edges

Incorrect shortest path results because BFS assumes equal edge weights

✅ Use Dijkstra's algorithm with a priority queue for weighted graphs

Not skipping outdated heap entries in Dijkstra

Extra unnecessary processing, slowing down the algorithm

✅ Check if current distance is greater than recorded distance and skip if so

Not handling unreachable nodes correctly

Returning incorrect maximum distance instead of -1

✅ Check if any node distance remains infinity and return -1 accordingly

Using recursion for brute force on large graphs

Stack overflow or timeout due to deep recursion

✅ Avoid brute force recursion on large inputs; use iterative or optimized algorithms

Not building adjacency list properly

Incorrect graph traversal or missing edges

✅ Ensure all edges are added correctly to adjacency list before processing

🧠

Brute Force (DFS with path relaxation)

💡 This approach tries all possible paths recursively to find the shortest time to each node. It is very inefficient but helps understand the problem's nature and why optimization is needed.

Intuition

Try every path from the source to all nodes, updating the shortest time found so far. This brute force search explores all routes without pruning.

Algorithm

1. Build adjacency list from times for quick access to neighbors.
2. Initialize a distance array with infinity for all nodes except the source node set to 0.
3. Use DFS to explore all paths from the source, updating distances if a shorter path is found.
4. After exploring all paths, check the maximum distance; if any node is unreachable, return -1.

💡 The recursive DFS explores all paths, which is hard to visualize because it can revisit nodes multiple times and requires careful distance updates.

</>

Code

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    dist = [float('inf')] * (n + 1)
    dist[k] = 0
    def dfs(node):
        for nei, w in graph[node]:
            if dist[node] + w < dist[nei]:
                dist[nei] = dist[node] + w
                dfs(nei)
    dfs(k)
    ans = max(dist[1:])
    return ans if ans < float('inf') else -1

# Example usage
if __name__ == '__main__':
    times = [[2,1,1],[2,3,1],[3,4,1]]
    n = 4
    k = 2
    print(network_delay_time(times, n, k))

Line Notes

graph = defaultdict(list)Create adjacency list for efficient neighbor lookup to quickly find all outgoing edges from a node.

dist = [float('inf')] * (n + 1)Initialize distances as infinity to represent unknown shortest paths initially.

dist[k] = 0Set distance to source node as zero since signal starts here.

if dist[node] + w < dist[nei]Relax edge if a shorter path to neighbor is found, updating the distance.

dfs(nei)Recursively explore neighbors to propagate updated shortest distances.

import java.util.*;
public class NetworkDelayTime {
    static Map<Integer, List<int[]>> graph = new HashMap<>();
    static int[] dist;
    static int n;
    public static void dfs(int node) {
        for (int[] edge : graph.getOrDefault(node, new ArrayList<>())) {
            int nei = edge[0], w = edge[1];
            if (dist[node] + w < dist[nei]) {
                dist[nei] = dist[node] + w;
                dfs(nei);
            }
        }
    }
    public static int networkDelayTime(int[][] times, int N, int K) {
        n = N;
        dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[K] = 0;
        for (int[] time : times) {
            graph.computeIfAbsent(time[0], x -> new ArrayList<>()).add(new int[]{time[1], time[2]});
        }
        dfs(K);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }
    public static void main(String[] args) {
        int[][] times = {{2,1,1},{2,3,1},{3,4,1}};
        int n = 4, k = 2;
        System.out.println(networkDelayTime(times, n, k));
    }

Line Notes

Map<Integer, List<int[]>> graph = new HashMap<>()Adjacency list to store graph edges for quick neighbor lookup.

dist = new int[n + 1]Distance array to store shortest known times to each node.

Arrays.fill(dist, Integer.MAX_VALUE)Initialize distances to max value to represent unknown paths.

if (dist[node] + w < dist[nei])Relax edge if a shorter path to neighbor is found.

dfs(nei)Recursive DFS call to propagate updated distances to neighbors.

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, vector<pair<int,int>>> graph;
vector<int> dist;
int n;

void dfs(int node) {
    for (auto &edge : graph[node]) {
        int nei = edge.first, w = edge.second;
        if (dist[node] + w < dist[nei]) {
            dist[nei] = dist[node] + w;
            dfs(nei);
        }
    }
}

int networkDelayTime(vector<vector<int>>& times, int N, int K) {
    n = N;
    dist.assign(n + 1, INT_MAX);
    dist[K] = 0;
    for (auto &time : times) {
        graph[time[0]].push_back({time[1], time[2]});
    }
    dfs(K);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INT_MAX) return -1;
        ans = max(ans, dist[i]);
    }
    return ans;
}

int main() {
    vector<vector<int>> times = {{2,1,1},{2,3,1},{3,4,1}};
    int n = 4, k = 2;
    cout << networkDelayTime(times, n, k) << "\n";
    return 0;
}

Line Notes

unordered_map<int, vector<pair<int,int>>> graphAdjacency list to store graph edges for efficient neighbor access.

dist.assign(n + 1, INT_MAX)Initialize distances to max int to represent unknown shortest paths.

dist[K] = 0Distance to source node is zero since signal starts here.

if (dist[node] + w < dist[nei])Relax edge if a shorter path to neighbor is found.

dfs(nei)Recursive DFS call to update distances of neighbors.

function networkDelayTime(times, n, k) {
    const graph = new Map();
    for (const [u, v, w] of times) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u).push([v, w]);
    }
    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;
    function dfs(node) {
        if (!graph.has(node)) return;
        for (const [nei, w] of graph.get(node)) {
            if (dist[node] + w < dist[nei]) {
                dist[nei] = dist[node] + w;
                dfs(nei);
            }
        }
    }
    dfs(k);
    const ans = Math.max(...dist.slice(1));
    return ans === Infinity ? -1 : ans;
}

// Example usage
console.log(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2));

Line Notes

const graph = new Map()Create adjacency list for graph to quickly find neighbors.

const dist = new Array(n + 1).fill(Infinity)Initialize distances to infinity to represent unknown paths.

dist[k] = 0Distance to source node is zero as signal starts here.

if (dist[node] + w < dist[nei])Relax edge if a shorter path to neighbor is found.

dfs(nei)Recursive DFS call to propagate updated distances.

⏱

Complexity

TimeO(n * E) where E is number of edges, due to repeated DFS calls and no pruning

SpaceO(n + E) for graph and recursion stack

The DFS explores all edges multiple times without memoization, leading to exponential behavior in worst case.

💡 For n=10 and E=20, this could mean thousands of recursive calls, which is inefficient.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large graphs but helps understand the problem and why optimization is necessary.

🧠

Dijkstra's Algorithm with Min-Heap (Priority Queue)

💡 Dijkstra's algorithm efficiently finds shortest paths from a source to all nodes using a priority queue to always expand the closest node next.

Intuition

Use a min-heap to greedily pick the next node with the smallest known distance, updating neighbors' distances only if a shorter path is found.

Algorithm

1. Build adjacency list from times.
2. Initialize distance array with infinity, set source distance to 0.
3. Use a min-heap to store nodes prioritized by current shortest distance.
4. Pop the closest node from the heap, update distances of neighbors if shorter paths are found, and push updated neighbors into the heap.
5. After processing all reachable nodes, return the maximum distance or -1 if any node is unreachable.

💡 The priority queue ensures we always process the next closest node, avoiding unnecessary work and infinite loops.

</>

Code

import heapq
from collections import defaultdict
def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    dist = [float('inf')] * (n + 1)
    dist[k] = 0
    heap = [(0, k)]
    while heap:
        time, node = heapq.heappop(heap)
        if time > dist[node]:
            continue
        for nei, w in graph[node]:
            if dist[node] + w < dist[nei]:
                dist[nei] = dist[node] + w
                heapq.heappush(heap, (dist[nei], nei))
    ans = max(dist[1:])
    return ans if ans < float('inf') else -1

# Example usage
if __name__ == '__main__':
    times = [[2,1,1],[2,3,1],[3,4,1]]
    n = 4
    k = 2
    print(network_delay_time(times, n, k))

Line Notes

graph = defaultdict(list)Build adjacency list for quick neighbor access to efficiently find edges.

dist = [float('inf')] * (n + 1)Initialize distances as infinity to represent unknown shortest paths.

heap = [(0, k)]Min-heap initialized with source node and distance 0 to start processing.

if time > dist[node]Skip outdated heap entries to avoid redundant processing of stale distances.

heapq.heappush(heap, (dist[nei], nei))Push updated neighbor distances into heap to process next.

import java.util.*;
public class NetworkDelayTime {
    public static int networkDelayTime(int[][] times, int N, int K) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] time : times) {
            graph.computeIfAbsent(time[0], x -> new ArrayList<>()).add(new int[]{time[1], time[2]});
        }
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[K] = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        heap.offer(new int[]{0, K});
        while (!heap.isEmpty()) {
            int[] cur = heap.poll();
            int time = cur[0], node = cur[1];
            if (time > dist[node]) continue;
            for (int[] edge : graph.getOrDefault(node, new ArrayList<>())) {
                int nei = edge[0], w = edge[1];
                if (dist[node] + w < dist[nei]) {
                    dist[nei] = dist[node] + w;
                    heap.offer(new int[]{dist[nei], nei});
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }
    public static void main(String[] args) {
        int[][] times = {{2,1,1},{2,3,1},{3,4,1}};
        int n = 4, k = 2;
        System.out.println(networkDelayTime(times, n, k));
    }
}

Line Notes

Map<Integer, List<int[]>> graph = new HashMap<>()Adjacency list for graph edges to quickly access neighbors.

Arrays.fill(dist, Integer.MAX_VALUE)Initialize distances to max value to represent unknown paths.

PriorityQueue<int[]> heap = new PriorityQueue<>Min-heap to pick the closest node next for processing.

if (time > dist[node]) continueSkip stale entries in heap to avoid redundant work.

heap.offer(new int[]{dist[nei], nei})Add updated neighbor distances to heap for future processing.

#include <bits/stdc++.h>
using namespace std;

int networkDelayTime(vector<vector<int>>& times, int N, int K) {
    unordered_map<int, vector<pair<int,int>>> graph;
    for (auto &time : times) {
        graph[time[0]].push_back({time[1], time[2]});
    }
    vector<int> dist(N + 1, INT_MAX);
    dist[K] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, K});
    while (!pq.empty()) {
        auto [time, node] = pq.top(); pq.pop();
        if (time > dist[node]) continue;
        for (auto &[nei, w] : graph[node]) {
            if (dist[node] + w < dist[nei]) {
                dist[nei] = dist[node] + w;
                pq.push({dist[nei], nei});
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        if (dist[i] == INT_MAX) return -1;
        ans = max(ans, dist[i]);
    }
    return ans;
}

int main() {
    vector<vector<int>> times = {{2,1,1},{2,3,1},{3,4,1}};
    int n = 4, k = 2;
    cout << networkDelayTime(times, n, k) << "\n";
    return 0;
}

Line Notes

unordered_map<int, vector<pair<int,int>>> graphAdjacency list for graph edges to efficiently find neighbors.

vector<int> dist(N + 1, INT_MAX)Initialize distances to max int to represent unknown shortest paths.

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pqMin-heap for selecting the closest node next.

if (time > dist[node]) continueSkip outdated heap entries to avoid redundant processing.

pq.push({dist[nei], nei})Push updated neighbor distances into heap for processing.

function networkDelayTime(times, n, k) {
    const graph = new Map();
    for (const [u, v, w] of times) {
        if (!graph.has(u)) graph.set(u, []);
        graph.get(u).push([v, w]);
    }
    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;
    const heap = new MinPriorityQueue({priority: x => x[0]});
    heap.enqueue([0, k]);
    while (!heap.isEmpty()) {
        const [time, node] = heap.dequeue().element;
        if (time > dist[node]) continue;
        if (!graph.has(node)) continue;
        for (const [nei, w] of graph.get(node)) {
            if (dist[node] + w < dist[nei]) {
                dist[nei] = dist[node] + w;
                heap.enqueue([dist[nei], nei]);
            }
        }
    }
    const ans = Math.max(...dist.slice(1));
    return ans === Infinity ? -1 : ans;
}

// Example usage
// Note: MinPriorityQueue is from '@datastructures-js/priority-queue' or similar library
// For testing here, a simple priority queue implementation is needed or use a polyfill

// console.log(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2));

Line Notes

const graph = new Map()Build adjacency list for graph to quickly find neighbors.

const dist = new Array(n + 1).fill(Infinity)Initialize distances to infinity to represent unknown paths.

const heap = new MinPriorityQueue({priority: x => x[0]})Min-heap to pick the closest node next for processing.

if (time > dist[node]) continueSkip stale heap entries to avoid redundant work.

heap.enqueue([dist[nei], nei])Add updated neighbor distances to heap for processing.

⏱

Complexity

TimeO(E log N) where E is edges and N is nodes due to priority queue operations

SpaceO(N + E) for graph and distance arrays

Each edge is processed once and each node is pushed into the heap multiple times but bounded by O(E log N).

💡 For n=10^5 and E=10^5, this approach is efficient enough to run within time limits.

Interview Verdict: Accepted / Optimal for large inputs

This is the standard solution expected in interviews for weighted shortest path problems.

🧠

Bellman-Ford Algorithm (Relax edges repeatedly)

💡 Bellman-Ford algorithm relaxes all edges repeatedly to find shortest paths and can detect negative cycles, but is slower than Dijkstra for positive weights.

Intuition

Relax all edges up to n-1 times, updating shortest distances. If no updates occur early, we can stop.

Algorithm

1. Initialize distances with infinity except source node set to 0.
2. Repeat n-1 times: for each edge, relax the distance if a shorter path is found.
3. After n-1 iterations, check for negative cycles by trying to relax edges once more.
4. Return the maximum distance or -1 if any node is unreachable.

💡 Repeated relaxation is simple but can be slow; understanding this helps appreciate Dijkstra's efficiency.

</>

Code

def network_delay_time(times, n, k):
    dist = [float('inf')] * (n + 1)
    dist[k] = 0
    for _ in range(n - 1):
        updated = False
        for u, v, w in times:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break
    ans = max(dist[1:])
    return ans if ans < float('inf') else -1

# Example usage
if __name__ == '__main__':
    times = [[2,1,1],[2,3,1],[3,4,1]]
    n = 4
    k = 2
    print(network_delay_time(times, n, k))

Line Notes

dist = [float('inf')] * (n + 1)Initialize distances to infinity to represent unknown shortest paths.

for _ in range(n - 1)Repeat relaxation n-1 times as per Bellman-Ford algorithm.

if dist[u] != float('inf') and dist[u] + w < dist[v]Relax edge if a shorter path to v is found via u.

if not updated: breakStop early if no updates occurred to optimize runtime.

ans = max(dist[1:])Find maximum distance after all relaxations.

import java.util.*;
public class NetworkDelayTime {
    public static int networkDelayTime(int[][] times, int N, int K) {
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[K] = 0;
        for (int i = 0; i < N - 1; i++) {
            boolean updated = false;
            for (int[] time : times) {
                int u = time[0], v = time[1], w = time[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    updated = true;
                }
            }
            if (!updated) break;
        }
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }
    public static void main(String[] args) {
        int[][] times = {{2,1,1},{2,3,1},{3,4,1}};
        int n = 4, k = 2;
        System.out.println(networkDelayTime(times, n, k));
    }
}

Line Notes

Arrays.fill(dist, Integer.MAX_VALUE)Initialize distances to max value to represent unknown paths.

for (int i = 0; i < N - 1; i++)Repeat relaxation N-1 times as per Bellman-Ford algorithm.

if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])Relax edge if a shorter path to v is found via u.

if (!updated) breakStop early if no updates occurred to optimize runtime.

ans = Math.max(ans, dist[i])Track maximum distance after relaxation.

#include <bits/stdc++.h>
using namespace std;

int networkDelayTime(vector<vector<int>>& times, int N, int K) {
    vector<int> dist(N + 1, INT_MAX);
    dist[K] = 0;
    for (int i = 0; i < N - 1; i++) {
        bool updated = false;
        for (auto &time : times) {
            int u = time[0], v = time[1], w = time[2];
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        if (dist[i] == INT_MAX) return -1;
        ans = max(ans, dist[i]);
    }
    return ans;
}

int main() {
    vector<vector<int>> times = {{2,1,1},{2,3,1},{3,4,1}};
    int n = 4, k = 2;
    cout << networkDelayTime(times, n, k) << "\n";
    return 0;
}

Line Notes

vector<int> dist(N + 1, INT_MAX)Initialize distances to max int to represent unknown shortest paths.

for (int i = 0; i < N - 1; i++)Repeat relaxation N-1 times as per Bellman-Ford algorithm.

if (dist[u] != INT_MAX && dist[u] + w < dist[v])Relax edge if a shorter path to v is found via u.

if (!updated) breakStop early if no updates occurred to optimize runtime.

ans = max(ans, dist[i])Track maximum distance after relaxation.

function networkDelayTime(times, n, k) {
    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;
    for (let i = 0; i < n - 1; i++) {
        let updated = false;
        for (const [u, v, w] of times) {
            if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;
    }
    const ans = Math.max(...dist.slice(1));
    return ans === Infinity ? -1 : ans;
}

// Example usage
console.log(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2));

Line Notes

const dist = new Array(n + 1).fill(Infinity)Initialize distances to infinity to represent unknown paths.

for (let i = 0; i < n - 1; i++)Repeat relaxation n-1 times as per Bellman-Ford algorithm.

if (dist[u] !== Infinity && dist[u] + w < dist[v])Relax edge if a shorter path to v is found via u.

if (!updated) breakStop early if no updates occurred to optimize runtime.

const ans = Math.max(...dist.slice(1))Find maximum distance after all relaxations.

⏱

Complexity

TimeO(N * E) where N is nodes and E is edges due to repeated edge relaxation

SpaceO(N) for distance array

Each edge is relaxed up to N-1 times, making it slower than Dijkstra for large graphs.

💡 For n=1000 and E=2000, this could mean up to 2 million operations, which may be slow.

Interview Verdict: Accepted but slower than Dijkstra

Useful to know as an alternative, especially if negative weights are involved, but not optimal here.

📊

All Approaches - One-Glance Tradeoffs

💡 Dijkstra's algorithm with a min-heap is the best choice for this problem in 95% of interviews due to its efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS with relaxation)	O(n * E) or worse due to repeated DFS calls	O(n + E) for graph and recursion stack	Yes (deep recursion possible)	No	Mention only - never code
2. Dijkstra's Algorithm with Min-Heap	O(E log N)	O(n + E)	No	Yes (with parent tracking)	Code this approach
3. Bellman-Ford Algorithm	O(N * E)	O(N)	No	Yes	Mention as alternative or if negative weights

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem.Introduce Dijkstra's algorithm as the optimal solution for weighted graphs.Discuss alternative algorithms like Bellman-Ford if time permits.Write clean, tested code and analyze complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test & Optimize: 5min. Total ~20min

What the Interviewer Tests

Understanding of graph representations, shortest path algorithms, priority queues, and ability to optimize brute force solutions.

Common Follow-ups

• What if edges had negative weights? → Use Bellman-Ford algorithm.
• Can you reconstruct the shortest path? → Maintain parent pointers during relaxation.

💡 These follow-ups test deeper knowledge of shortest path algorithms and path reconstruction techniques.

🔍

Pattern Recognition

When to Use

1) Graph with weighted edges, 2) Single source shortest path needed, 3) Need minimum time/distance, 4) Directed edges with positive weights

Signature Phrases

minimum time to reach all nodesweighted directed edgessingle source shortest path

NOT This Pattern When

Unweighted shortest path problems solved by simple BFS, or all-pairs shortest path problems like Floyd-Warshall

Similar Problems

Dijkstra's Algorithm - core algorithm used hereShortest Path in Binary Matrix - BFS variant for unweighted graphs

Practice

1. You are given an undirected graph and need to determine if its vertices can be divided into two groups such that no edge connects vertices within the same group. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Greedy algorithm that assigns groups based on vertex degree

B. Dynamic Programming on subsets of vertices to find valid partitions

C. Depth-First Search (DFS) to find cycles and count their lengths

D. Breadth-First Search (BFS) coloring to assign two colors and check for conflicts

Solution

1. Step 1: Understand the problem as a 2-coloring challenge

   The problem requires checking if the graph is bipartite, which means it can be colored using two colors such that no adjacent vertices share the same color.

2. Step 2: Identify BFS coloring as the optimal approach

   BFS coloring systematically assigns colors level by level and detects conflicts efficiently, guaranteeing correctness and linear time complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS coloring is the standard method for bipartite checking [OK]

Hint: BFS coloring detects bipartite conflicts efficiently [OK]

Common Mistakes:

• Assuming greedy degree-based grouping works
• Confusing cycle detection with bipartite check

2. You are given a 2D grid representing land (1) and water (0). You need to find the largest connected group of land cells connected only horizontally or vertically. Which algorithmic approach guarantees finding the maximum size of such a connected land area efficiently?

easy

A. Graph traversal using Depth-First Search (DFS) or Breadth-First Search (BFS) to explore connected components

B. Dynamic Programming that stores maximum island size ending at each cell using previous computations

C. Greedy approach that expands from each land cell by always moving to the neighbor with the largest immediate value

D. Sorting all land cells by their coordinates and merging adjacent cells in sorted order

Solution

1. Step 1: Understand the problem as finding connected components in a grid graph

   Each land cell is a node connected to neighbors horizontally or vertically.

2. Step 2: Recognize that DFS or BFS explores all connected nodes in a component, allowing counting of island size

   Greedy or DP approaches do not guarantee exploring all connected cells correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Graph traversal is the standard method for connected components [OK]

Hint: Connected components in grids -> DFS or BFS [OK]

Common Mistakes:

• Thinking DP can solve connected components directly
• Assuming greedy expansion finds max island
• Confusing sorting with connectivity

3. You are given a 2D grid map of '1's (land) and '0's (water). You need to count the number of distinct islands, where an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Which algorithmic approach guarantees an optimal solution to this problem?

easy

A. Use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse connected components in the grid.

B. Use a sorting-based approach to group land cells and count islands.

C. Use Dynamic Programming to store intermediate island counts for subgrids.

D. Use a greedy approach to count islands by scanning rows and columns independently.

Solution

1. Step 1: Understand the problem as finding connected components in a grid

   The problem requires identifying groups of adjacent '1's connected horizontally or vertically, which is a classic graph traversal problem.

2. Step 2: Recognize that DFS or BFS traversals efficiently explore connected components

   DFS or BFS starting from each unvisited land cell will mark all connected land cells as visited, ensuring each island is counted exactly once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS/BFS is the standard approach for connected components in grids [OK]

Hint: Islands = connected components -> use DFS/BFS [OK]

Common Mistakes:

• Thinking greedy or sorting can identify islands correctly.

4. You are given a 2D grid containing 'X' and 'O'. The goal is to flip all 'O's that are completely surrounded by 'X's into 'X's themselves, but keep 'O's connected to the boundary unchanged. Which algorithmic approach best guarantees an optimal solution for this problem?

easy

A. Use a brute force approach checking each 'O' region independently with DFS to see if it touches the boundary.

B. Mark all 'O's connected to the boundary first using BFS or DFS, then flip the rest of the 'O's to 'X'.

C. Apply dynamic programming to store subproblems of surrounded regions and combine results.

D. Use a greedy approach to flip 'O's as soon as they are found surrounded by 'X's.

Solution

1. Step 1: Understand the problem constraints

   The problem requires flipping only those 'O's that are fully surrounded by 'X's, meaning 'O's connected to the boundary must remain unchanged.

2. Step 2: Identify the correct approach

   Marking all 'O's connected to the boundary first ensures these safe regions are preserved. Then flipping the rest is straightforward. This approach is efficient and guarantees correctness.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Boundary-connected marking prevents flipping safe 'O's [OK]

Hint: Mark boundary-connected 'O's first to preserve them [OK]

Common Mistakes:

• Trying to check each 'O' region independently leads to high complexity.
• Using greedy flips misses connected 'O's that should be preserved.
• Dynamic programming is not suitable for connectivity problems on grids.

5. The following code attempts to check if a graph is a valid tree. Which line contains a subtle bug that can cause incorrect results on disconnected graphs?

medium

A. Line checking if edge count equals n - 1

B. Line returning true without verifying all nodes visited

C. Line skipping neighbor if it equals parent

D. Line adding neighbor to queue

Solution

1. Step 1: Identify final return condition

   The code returns true without checking if all nodes were visited, missing disconnected components.

2. Step 2: Understand impact

   Disconnected graphs with correct edge count and no cycles will incorrectly return true.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Must verify visited nodes count equals n [OK]

Hint: Always check all nodes visited for connectivity [OK]

Common Mistakes:

• Forgetting connectivity check after BFS/DFS
• Misinterpreting cycle detection as full validation