Skip to main content
Talentd

Find the Degree of Each Vertex - Solution & Explanation

EasyArrayGraphMatrix6 min read
Practice this problem

Problem Statement

You are given a 2D integer array matrix of size n x n representing the adjacency matrix of an undirected graph with n vertices labeled from 0 to n - 1.

  • matrix[i][j] = 1 indicates that there is an edge between vertices i and j.
  • matrix[i][j] = 0 indicates that there is no edge between vertices i and j.

The degree of a vertex is the number of edges connected to it.

Return an integer array ans of size n where ans[i] represents the degree of vertex i.

 

Example 1:

Input: matrix = [[0,1,1],[1,0,1],[1,1,0]]

Output: [2,2,2]

Explanation:

  • Vertex 0 is connected to vertices 1 and 2, so its degree is 2.
  • Vertex 1 is connected to vertices 0 and 2, so its degree is 2.
  • Vertex 2 is connected to vertices 0 and 1, so its degree is 2.

Thus, the answer is [2, 2, 2].

Example 2:

Input: matrix = [[0,1,0],[1,0,0],[0,0,0]]

Output: [1,1,0]

Explanation:

  • Vertex 0 is connected to vertex 1, so its degree is 1.
  • Vertex 1 is connected to vertex 0, so its degree is 1.
  • Vertex 2 is not connected to any vertex, so its degree is 0.

Thus, the answer is [1, 1, 0].

Example 3:

Input: matrix = [[0]]

Output: [0]

Explanation:

There is only one vertex and it has no edges connected to it. Thus, the answer is [0].

 

Constraints:

  • 1 <= n == matrix.length == matrix[i].length <= 100​​​​​​​
  • ​​​​​​​matrix[i][i] == 0
  • matrix[i][j] is either 0 or 1
  • matrix[i][j] == matrix[j][i]

Approach Overview

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.

Solution

We can directly simulate the process of computing the degree of each vertex.

For each vertex i, we traverse its corresponding row matrix[i] and count the number of elements equal to 1, which is exactly the degree of vertex i.

The time complexity is O(n^2), where n is the number of vertices in the graph. Ignoring the space consumed by the answer array, the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Adjacency Matrix ScanO(V²)O(V²)When the graph is already stored as an adjacency matrix or when the graph is dense
Edge List CountingO(E)O(V)Best general solution when edges are provided directly
Adjacency List ConstructionO(V + E)O(V + E)Useful when you also need BFS/DFS or other graph traversals

Video Solution

Find the Degree of Each Vertex | LeetCode XXXX | Weekly Contest 497 | Java Code | Developer Coder • Developer Coder • 170 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Find the Degree of Each Vertex easy or hard?
The problem is typically classified as Easy. It mainly checks whether you understand the definition of vertex degree and basic graph representations. The implementation is a straightforward linear scan of the edges.
Find the Degree of Each Vertex Python/Java solution
Most implementations use a degree array. In Python, create a list of size V and increment counts while iterating through edges. In Java or C++, use an integer array or vector and update both endpoints for every edge.
How to solve Find the Degree of Each Vertex in O(n)?
Treat n as the number of edges. Create a degree array initialized to zero. Iterate once through the edge list and increment the degree for both endpoints of each edge. This single pass ensures O(E) time with constant work per edge.
What is the best approach for Find the Degree of Each Vertex?
The most efficient approach is counting degrees directly from the edge list. Initialize an array of size V and iterate through each edge (u, v). Increment degree[u] and degree[v]. This processes every edge once, giving O(E) time complexity and O(V) space.
Is Find the Degree of Each Vertex asked at Google/Amazon/Meta?
Degree counting appears frequently as a warm‑up or as part of larger graph problems in technical interviews. Companies like Amazon, Google, and Meta often embed this concept inside adjacency list construction, graph traversal, or connectivity problems.
What data structure is used in Find the Degree of Each Vertex?
The simplest structure is an integer array storing the degree of each vertex. If the graph needs further processing, an adjacency list built with arrays or lists is commonly used. Both approaches rely on basic graph representation techniques.
What is the time complexity of Find the Degree of Each Vertex?
The optimal time complexity is O(E), where E is the number of edges. Each edge contributes exactly two increments to the degree array. Space complexity is O(V) for storing the degree of each vertex.

Ready to solve this problem?

Practice Find the Degree of Each Vertex with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays