3898. Find the Degree of Each Vertex

Easy

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a 2D integer array matrix of size n x n that represents the adjacency matrix of an undirected graph. The graph has n vertices, labeled from 0 to n - 1.

The adjacency matrix tells us how the vertices are connected:

matrix[i][j] = 1 means there is an edge between vertex i and vertex j.
matrix[i][j] = 0 means there is no edge between vertex i and vertex j.

The degree of a vertex is defined as the number of edges connected to that vertex.

Your task is to return an integer array ans of size n, where ans[i] represents the degree of vertex i.

In other words, for each vertex i, you need to count how many vertices it is directly connected to. Since each connection corresponds to a 1 in row i of the matrix, the degree of vertex i is simply the sum of all the values in matrix[i].

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Following the described procedure step by step produces the solution.

Open in Flowchart

Intuition

The key observation comes from understanding what the adjacency matrix represents. In row i of the matrix, each entry matrix[i][j] tells us whether vertex i is connected to vertex j. A value of 1 means there is an edge, and a value of 0 means there is no edge.

Since the degree of a vertex is just the number of edges connected to it, we only need to count how many 1s appear in row i. Each 1 in that row corresponds to exactly one edge from vertex i to another vertex.

Because the values are only 0 or 1, counting the 1s is the same as summing up all the values in the row. This means the degree of vertex i equals the sum of all elements in matrix[i].

So instead of checking each entry one by one and incrementing a counter, we can simply add up every value in the row to directly get the degree. Repeating this for every row gives us the degree of all vertices, which forms our answer array.

Solution Approach

We use simulation to directly compute the degree of each vertex.

The idea is straightforward: for each vertex i, we look at its corresponding row matrix[i] and add up all the values in that row. Since every entry is either 0 or 1, this sum equals the number of edges connected to vertex i, which is exactly its degree.

Step-by-step implementation:

Initialize the answer array: Create an array ans of size n (where n is the number of rows in the matrix), filled with 0s. The value ans[i] will hold the degree of vertex i.
```
ans = [0] * len(matrix)
```
Iterate over each row: We use enumerate(matrix) to loop through every row together with its index i. The index i corresponds to the current vertex.
```
for i, row in enumerate(matrix):
```
Sum the values in the row: For each value x in row, we add it to ans[i]. Because each 1 represents an edge and each 0 represents no edge, accumulating these values gives the total number of edges for vertex i.
```
for x in row:
    ans[i] += x
```
Return the result: After processing all rows, ans contains the degree of every vertex, and we return it.
```
return ans
```

Complexity Analysis:

Time Complexity: O(n^2), where n is the number of vertices. We visit every entry of the n x n matrix exactly once.
Space Complexity: O(n) for the answer array (ignoring the space used by the output itself, the extra space is O(1)).

This approach is simple and optimal, since we must read every cell of the matrix at least once to determine all the degrees.

Example Walkthrough

Let's trace through the solution approach using a small example.

Input:

matrix = [
  [0, 1, 1],
  [1, 0, 0],
  [1, 0, 0]
]

This is a 3 x 3 adjacency matrix representing a graph with 3 vertices (0, 1, 2). Looking at the matrix, we can see:

Vertex 0 connects to vertex 1 and vertex 2.
Vertex 1 connects to vertex 0.
Vertex 2 connects to vertex 0.

Step 1 — Initialize the answer array:

We create ans of size 3, filled with zeros:

ans = [0, 0, 0]

Step 2 & 3 — Iterate over each row and sum its values:

We process one row at a time, where index i is the current vertex.

i = 0, row = [0, 1, 1] We add up each value: 0 + 1 + 1 = 2. This means vertex 0 has 2 edges. Update ans[0] = 2.
```
ans = [2, 0, 0]
```
i = 1, row = [1, 0, 0] We add up each value: 1 + 0 + 0 = 1. This means vertex 1 has 1 edge. Update ans[1] = 1.
```
ans = [2, 1, 0]
```
i = 2, row = [1, 0, 0] We add up each value: 1 + 0 + 0 = 1. This means vertex 2 has 1 edge. Update ans[2] = 1.
```
ans = [2, 1, 1]
```

Step 4 — Return the result:

After processing all rows, we return:

ans = [2, 1, 1]

Verification:

This matches our earlier observation perfectly — vertex 0 is connected to two vertices (degree 2), while vertices 1 and 2 are each connected to one vertex (degree 1). Each 1 in a row directly corresponds to one edge, so summing the row gives the exact degree of that vertex.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def findDegrees(self, matrix: List[List[int]]) -> List[int]:
6        # Number of vertices, equal to the size of the adjacency matrix
7        n = len(matrix)
8
9        # Initialize the degree list, one entry per vertex
10        degrees = [0] * n
11
12        # Iterate over each row of the adjacency matrix
13        for i, row in enumerate(matrix):
14            # Sum up all entries in the current row;
15            # this represents the degree of vertex i
16            for value in row:
17                degrees[i] += value
18
19        # Return the computed degrees for all vertices
20        return degrees
21```
22
23Notes on the changes:
24
251. **Type hints** – Replaced the lowercase built-in `list[list[int]]` style with `List[List[int]]` imported from `typing`, which is the conventional, broadly compatible Python 3 type-hint syntax.
26
272. **Naming standardization** – Renamed the result variable from the generic `ans` to the more descriptive `degrees`, and the loop variable `x` to `value` to clarify what each element represents. Added `n` to capture the matrix size, improving readability.
28
293. **Comments** – Added clear English comments explaining each step: initialization, iteration, accumulation, and the final return.
30
31If you prefer a more concise, Pythonic version, you could simplify the inner loop using the built-in `sum`:
32
33```python3
34from typing import List
35
36
37class Solution:
38    def findDegrees(self, matrix: List[List[int]]) -> List[int]:
39        # The degree of each vertex equals the sum of its row in the adjacency matrix
40        return [sum(row) for row in matrix]
41

1class Solution {
2    /**
3     * Computes the degree of each vertex in a graph represented by an adjacency matrix.
4     * The degree of vertex i is the sum of all entries in row i.
5     *
6     * @param matrix the adjacency matrix where matrix[i][j] indicates an edge/weight
7     *               between vertex i and vertex j
8     * @return an array where the i-th element holds the degree of vertex i
9     */
10    public int[] findDegrees(int[][] matrix) {
11        // Number of vertices (rows) in the matrix
12        int n = matrix.length;
13
14        // Result array to store the degree of each vertex
15        int[] degrees = new int[n];
16
17        // Iterate over each row (vertex)
18        for (int i = 0; i < n; i++) {
19            // Accumulate all values in the current row to compute its degree
20            for (int value : matrix[i]) {
21                degrees[i] += value;
22            }
23        }
24
25        return degrees;
26    }
27}
28

1class Solution {
2public:
3    // Compute the degree of each vertex from an adjacency matrix.
4    // The degree of vertex i equals the sum of the entries in row i.
5    vector<int> findDegrees(vector<vector<int>>& matrix) {
6        int n = matrix.size();      // Number of vertices (rows in the matrix)
7        vector<int> ans(n);         // ans[i] will hold the degree of vertex i
8
9        // Iterate over each row, i.e., each vertex.
10        for (int i = 0; i < n; ++i) {
11            // Accumulate all edge weights/connections in row i.
12            for (int x : matrix[i]) {
13                ans[i] += x;
14            }
15        }
16
17        return ans;                 // Return the list of degrees.
18    }
19};
20

1/**
2 * Computes the degree of each vertex in a graph represented by an adjacency matrix.
3 * The degree of vertex i is the sum of all entries in row i of the matrix.
4 *
5 * @param matrix - The adjacency matrix where matrix[i][j] represents the edge weight
6 *                 (or count) between vertex i and vertex j.
7 * @returns An array where the element at index i is the degree of vertex i.
8 */
9function findDegrees(matrix: number[][]): number[] {
10    // Number of vertices (rows) in the matrix.
11    const n: number = matrix.length;
12
13    // Initialize the result array with all degrees set to 0.
14    const ans: number[] = Array(n).fill(0);
15
16    // Iterate over each row (vertex) of the matrix.
17    for (let i = 0; i < n; ++i) {
18        // Accumulate the sum of all values in the current row.
19        for (const value of matrix[i]) {
20            ans[i] += value;
21        }
22    }
23
24    // Return the computed degrees for all vertices.
25    return ans;
26}
27

Time and Space Complexity

Time Complexity: O(n^2), where n is the number of vertices in the graph. The matrix is an n x n adjacency matrix, and the code iterates over every element via the outer loop (over rows) and the inner loop (over each value in a row). This results in n * n = n^2 operations, hence the time complexity is O(n^2).
Space Complexity: O(1). Ignoring the space consumed by the answer array ans (which is the required output of size n), only a constant amount of extra space is used for the loop variables i, row, and x. Therefore, the auxiliary space complexity is O(1).

Common Pitfalls

Pitfall: Counting self-loops twice (or incorrectly) along the diagonal.

A common mistake is to assume that matrix[i][i] is always 0. In a standard undirected graph without self-loops, the diagonal entries are 0, and summing the row works perfectly. However, if the input graph contains self-loops (i.e., matrix[i][i] = 1), the naive row-sum approach silently miscounts the degree.

The subtlety is in graph theory convention: a self-loop conventionally contributes 2 to the degree of a vertex (both endpoints of the loop attach to the same vertex), but sum(row) only counts it as 1. Conversely, in some problem definitions a self-loop should count as 1 or not at all. Blindly using sum(row) assumes there are no self-loops, which may produce wrong answers if that assumption is violated.

Why it happens:

return [sum(row) for row in matrix]

If matrix[2][2] = 1, this code adds 1 to vertex 2's degree, but the intended degree (per standard graph theory) might be +2, leaving the result off by one for that vertex.

Solution: Be explicit about how the diagonal is handled.

First, confirm the problem's convention. For this LeetCode-style problem, the matrix represents a simple undirected graph with no self-loops, so sum(row) is correct and safe. But to make the code robust and intent-clear, handle the diagonal explicitly:

from typing import List


class Solution:
    def findDegrees(self, matrix: List[List[int]]) -> List[int]:
        n = len(matrix)
        degrees = [0] * n

        for i in range(n):
            for j in range(n):
                # Skip the diagonal if self-loops are not part of the degree,
                # or add matrix[i][i] * 2 if self-loops count twice.
                if i == j:
                    continue  # assuming a simple graph with no self-loops
                degrees[i] += matrix[i][j]

        return degrees

If the problem's convention requires self-loops to count twice:

for i in range(n):
    for j in range(n):
        if i == j:
            degrees[i] += matrix[i][j] * 2   # self-loop adds 2
        else:
            degrees[i] += matrix[i][j]

Key takeaway: The one-liner [sum(row) for row in matrix] is concise and correct only under the assumption of a simple, self-loop-free graph. Whenever self-loops are possible, decide on the counting convention first, then handle the diagonal explicitly rather than relying on an implicit assumption baked into a row sum.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know