Maximum Messages Sent — Problem Statement & Solution Guide

GraphsMediumMixed

TimeO(N + M)

SpaceO(N)

Problem Description

In a distributed communication network modeled as a directed graph, each node represents a server capable of transmitting data packets. The topology is defined by an adjacency list where an edge from node u to node v indicates that u can directly send a message to v. Each server is restricted to sending at most one message to any specific neighbor. Your task is to identify the server that has the highest transmission capacity, defined as the total number of unique neighbors it can reach directly. If multiple servers share the maximum transmission capacity, return the one with the smallest node identifier to ensure deterministic output.

The input is provided as a dictionary (or map) where the keys are integer node identifiers and the values are lists of integer identifiers representing the direct outgoing connections. The output should be the identifier of the node with the maximum out-degree. If the graph is empty, return -1.

DSA Pattern Breakdown

"Maximum Messages Sent"

medium

WHY DOES IT MATTER?

Counting degrees is a fundamental graph‑pattern that appears in many real‑world analytics tasks—identifying influencers, bottlenecks, or highly connected services. Mastering this pattern equips you to handle a wide class of problems where local connectivity dictates global behavior.

OPTIMIZATION CHALLENGE

The key insight is to avoid pairwise edge checks. By processing each adjacency list exactly once, you turn a potentially quadratic scan into a linear pass, achieving O(N+M) time and O(N) space.

REAL-WORLD CONNECTION

Think of a social media platform: each user can broadcast a post to all followers exactly once. The user with the most followers (out‑degree) can disseminate information most widely in a single step—mirroring the maximum‑messages‑sent server in a distributed network.

During an interview, first ask clarifying questions about graph representation and edge uniqueness, then immediately propose a single pass over the adjacency list to tally out‑degrees—this shows you think in terms of optimal data‑structure usage before writing code.

COMPLEXITY AT A GLANCE

⏱ Time:O(N + M)

💾 Space:O(N)

Core Theory — Why This Approach?

The problem reduces to computing the out-degree of every vertex in a directed graph and selecting the vertex with the highest count. In graph theory, the out-degree of a node u is the number of edges that originate from u, which directly corresponds to the number of distinct neighbors u can send a message to (given the "at most one message per neighbor" constraint). A naïve solution might iterate over every possible pair of vertices to check for an edge, leading to O(N^2) time on dense graphs, which quickly becomes infeasible for N up to 10^5 or more. The optimal paradigm leverages the adjacency‑list representation: a single linear scan of all adjacency lists accumulates out‑degree counts in O(N + M) time, where M is the total number of directed edges, and uses only O(N) auxiliary space for the degree array. This approach scales to massive networks because each edge is processed exactly once.

Interview Questions on This Problem

Q1Given a directed graph as an adjacency list, how would you find the node that can reach the most other nodes in exactly one hop?

Count the size of each node's adjacency list (its out‑degree). The node with the largest list can reach the most distinct neighbors in one hop. This can be done in O(N+M) by iterating over the adjacency lists once.

Q2How would you modify the solution if each server could send at most K messages to each neighbor, and you need the server that can send the most total messages?

Multiply each out‑degree by K (or sum the per‑edge capacities if they differ). The total messages a server can send equals K * outDegree. The node with the highest product is the answer, still computable in O(N+M).

Q3In a large distributed system, why might you prefer an adjacency‑list representation over an adjacency‑matrix when solving degree‑related queries?

Adjacency lists store only existing edges, using O(N+M) memory versus O(N^2) for a matrix. For sparse graphs (common in real‑world networks), this dramatically reduces memory and allows linear‑time traversals, making degree calculations fast and scalable.

Examples

Example 1

Input

graph = {1: [2, 3, 4], 2: [1], 3: [1, 4], 4: []}

Output

Explanation: Node 1 has 3 outgoing edges (to 2, 3, 4). Node 2 has 1 outgoing edge. Node 3 has 2 outgoing edges. Node 4 has 0 outgoing edges. The maximum count is 3, belonging to Node 1. Thus, the answer is 1.

Example 2

Input

graph = {10: [20, 30], 20: [10, 30, 40], 30: [20], 40: [10]}

Output

Explanation: Node 10 has 2 neighbors. Node 20 has 3 neighbors (10, 30, 40). Node 30 has 1 neighbor. Node 40 has 1 neighbor. The maximum count is 3, belonging to Node 20. Thus, the answer is 20.

Example 3

Input

graph = {5: [6], 6: [5, 7], 7: [6, 8], 8: [7]}

Output

Explanation: Node 5 has 1 neighbor. Node 6 has 2 neighbors (5, 7). Node 7 has 2 neighbors (6, 8). Node 8 has 1 neighbor. The maximum count is 2, shared by Node 6 and Node 7. Since we must return the smallest identifier in case of a tie, the answer is 6.

Example 4

Input

graph = {}

Output

-1

Explanation: The graph is empty, meaning there are no nodes. According to the problem specification, return -1 for an empty graph.

Constraints

1 <= number of nodes <= 10^5
1 <= node identifier <= 10^9
The graph is simple, meaning no self-loops and no duplicate edges in the adjacency lists.
The total number of edges in the graph does not exceed 10^5.

Optimal Approach & Strategy

Iterate over each adjacency list once, increment a degree counter for the source node, and track the maximum while scanning.

Brute Force Approach

Check every possible pair of nodes to see if an edge exists, increment a counter for the source node, and finally pick the node with the highest counter.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N + M)

function solution(graph) { let maxReachable = 0; let maxNode = null; for (let node in graph) { let visited = new Set(); let reachable = 0; dfs(graph, node, visited); reachable = visited.size - 1; if (reachable > maxReachable) { maxReachable = reachable; maxNode = node; } } return maxNode; function dfs(graph, node, visited) { visited.add(node); for (let neighbor of graph[node]) { if (!visited.has(neighbor)) { dfs(graph, neighbor, visited); } } } }

class Solution { public: std::string solution(std::unordered_map<std::string, std::vector<std::string>> graph) { int maxReachable = 0; std::string maxNode; for (auto& node : graph) { std::unordered_set<std::string> visited; dfs(graph, node.first, visited); int reachable = visited.size() - 1; if (reachable > maxReachable) { maxReachable = reachable; maxNode = node.first; } } return maxNode; } private: void dfs(std::unordered_map<std::string, std::vector<std::string>> graph, std::string node, std::unordered_set<std::string>& visited) { visited.insert(node); for (const auto& neighbor : graph[node]) { if (visited.find(neighbor) == visited.end()) { dfs(graph, neighbor, visited); } } } }

import java.util.HashSet; import java.util.Set; class Solution { public String solution(java.util.Map<String, String[]> graph) { int maxReachable = 0; String maxNode = null; for (String node : graph.keySet()) { Set<String> visited = new HashSet<>(); dfs(graph, node, visited); int reachable = visited.size() - 1; if (reachable > maxReachable) { maxReachable = reachable; maxNode = node; } } return maxNode; } private void dfs(java.util.Map<String, String[]> graph, String node, Set<String> visited) { visited.add(node); for (String neighbor : graph.get(node)) { if (!visited.contains(neighbor)) { dfs(graph, neighbor, visited); } } } }

def solution(graph): max_reachable = 0; max_node = None; for node in graph: visited = set(); reachable = 0; dfs(graph, node, visited); reachable = len(visited) - 1; if reachable > max_reachable: max_reachable = reachable; max_node = node; return max_node; def dfs(graph, node, visited): visited.add(node); for neighbor in graph[node]: if neighbor not in visited: dfs(graph, neighbor, visited)

function solution(graph) { let maxReachable = 0; let maxNode = null; for (let node in graph) { let visited = new Set(); let reachable = 0; dfs(graph, node, visited); reachable = visited.size - 1; if (reachable > maxReachable) { maxReachable = reachable; maxNode = node; } } return maxNode; function dfs(graph, node, visited) { visited.add(node); for (let neighbor of graph[node]) { if (!visited.has(neighbor)) { dfs(graph, neighbor, visited); } } } }

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.

Maximum Messages Sent Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Graphs

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Maximum Messages Sent — 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