Find the Degree of Each Vertex - Video Solutions

Problem Overview: You are given a graph and need to compute the degree of every vertex. The degree of a vertex is the number of edges connected to it. For an undirected graph, each edge contributes +1 to the degree of both endpoints.

Approach 1: Adjacency Matrix Scan (O(V²) time, O(V²) space)

If the graph is represented as an adjacency matrix, you can compute the degree of a vertex by summing all values in its row. Iterate through every column of the row and count how many edges exist. This approach works directly with matrix representations but scales poorly because you must scan V entries for each vertex. Prefer this only when the graph is already stored as a matrix or when the graph is dense.

Approach 2: Edge List Counting (O(E) time, O(V) space)

Most problems provide the graph as a list of edges. Initialize an array degree[V] with zeros. Iterate through each edge (u, v). Increment degree[u] and degree[v]. Each edge contributes to exactly two vertices in an undirected graph. The key insight: you never need to explicitly build the full structure of the graph—just count how many times each vertex appears in the edge list. This avoids unnecessary storage and runs in linear time relative to the number of edges.

Approach 3: Adjacency List Construction (O(V + E) time, O(V + E) space)

Another common solution builds an adjacency list first. Use an array of lists where each index represents a vertex. While iterating through edges, append neighbors to both vertices. Once the adjacency list is built, the degree of a vertex equals the length of its neighbor list. This representation is standard for many graph algorithms and becomes useful if additional traversal such as DFS or BFS is required later.

For simple counting tasks, Approach 2 is usually the cleanest. It relies only on an array and a single pass through the edges, making it both memory‑efficient and fast. The adjacency list method is slightly heavier but integrates naturally with other graph operations like traversal. Both rely on straightforward array indexing and sequential iteration.

Recommended for interviews: The edge list counting approach. Start by explaining the definition of vertex degree, then show that every edge increments two counters. The interviewer sees that you understand graph fundamentals and can reduce the problem to a simple linear pass. Mentioning the adjacency list alternative shows awareness of standard graph representations used in broader graph problems.