Find the Degree of Each Vertex

Difficulty: Easy | Acceptance: 92.70% | Paid: No Topics: N/A

You are given an undirected graph with n vertices labeled from 0 to n - 1. The graph is represented by a 2D integer array edges where edges[i] = [ui, vi] denotes an edge between vertex ui and vertex vi.

Return an array answer of size n where answer[i] is the degree of the i-th vertex. The degree of a vertex is the number of edges connected to it.

• Examples
• Constraints
• Approach 1: Counting Array
• Approach 2: Adjacency List
• Approach 3: Brute Force Matrix

Examples

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 1: Counting Array

Intuition Since the vertices are labeled from 0 to n-1, we can use a simple array of size n to store the degree of each vertex. We iterate through the edge list and increment the count for both vertices involved in each edge.

Steps

• Initialize an array degree of size n with all zeros.
• Iterate through each edge [u, v] in the edges list.
• Increment degree[u] by 1.
• Increment degree[v] by 1.
• Return the degree array.

class Solution:
    def findDegree(self, n: int, edges: list[list[int]]) -> list[int]:
        degree = [0] * n
        for u, v in edges:
            degree[u] += 1
            degree[v] += 1
        return degree

Complexity

• Time: O(E), where E is the number of edges. We iterate through the edge list once.
• Space: O(N), to store the degree array.
• Notes: This is the most optimal approach for this problem.

Approach 2: Adjacency List

Intuition We can construct the graph using an adjacency list. For each vertex, we store a list of its neighbors. The degree of a vertex is simply the length of its adjacency list.

Steps

• Initialize an adjacency list adj as a list of n empty lists.
• Iterate through each edge [u, v].
• Append v to adj[u] and u to adj[v].
• Create a result array and map the length of each list in adj to the result.

class Solution:
    def findDegree(self, n: int, edges: list[list[int]]) -> list[int]:
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        return [len(neighbors) for neighbors in adj]

Complexity

• Time: O(N + E), to initialize the lists and process edges.
• Space: O(N + E), to store the adjacency list (2E integers total).
• Notes: This approach is useful if you need to traverse the graph later, but it uses more memory than Approach 1 if you only need degrees.

Approach 3: Brute Force Matrix

Intuition We can represent the graph using an adjacency matrix mat of size n x n. If an edge exists between u and v, we set mat[u][v] and mat[v][u] to 1. The degree of vertex i is the sum of the i-th row.

Steps

• Initialize an n x n matrix with zeros.
• Iterate through edges and mark the corresponding cells in the matrix.
• Iterate through each row of the matrix and sum the values to get the degree.

class Solution:
    def findDegree(self, n: int, edges: list[list[int]]) -> list[int]:
        mat = [[0] * n for _ in range(n)]
        for u, v in edges:
            mat[u][v] = 1
            mat[v][u] = 1
        return [sum(row) for row in mat]

Complexity

• Time: O(N² + E), iterating through the matrix to sum rows dominates.
• Space: O(N²), to store the matrix.
• Notes: This approach is highly inefficient for large n (e.g., n = 10⁵) as it requires allocating 10¹⁰ integers, which will cause a Memory Limit Exceeded error. It is only suitable for very small graphs.