Find the Degree of Each Vertex

Problem summary

We are given an n x n adjacency matrix of an undirected graph.

For each vertex i, we need to return its degree, meaning:

• how many edges are connected to vertex i

Key observation

In an adjacency matrix:

• matrix[i][j] = 1 means vertex i is connected to vertex j
• matrix[i][j] = 0 means no edge exists

So the degree of a vertex is simply the number of 1s in its connections.

Because the graph is undirected:

matrix[i][j] == matrix[j][i]

That means we can count degrees by summing either:

• each row
• or each column

The provided solution adds every matrix[i][j] into result[j], which is equivalent to summing columns.

Since the matrix is symmetric, that gives the same answer as summing rows.

Approach

1. Create an array result of size n filled with 0.
2. Traverse the whole matrix.
3. Add matrix[i][j] to result[j].
4. Return result.

Why this works

For a fixed vertex j, every 1 in column j represents one vertex connected to j.

So after scanning all rows:

result[j] = total number of edges incident to vertex j

which is exactly the degree of vertex j.

class Solution {
    public int[] findDegrees(int[][] matrix) {
        int[] result = new int[matrix.length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                result[j] += matrix[i][j];
            }
        }
        return result;
    }
}

Walkthrough

Take:

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

Start with:

result = [0, 0, 0]

After processing row 0:

result = [0, 1, 1]

After processing row 1:

result = [1, 1, 2]

After processing row 2:

result = [2, 2, 2]

So every vertex has degree 2.

Complexity analysis

Time Complexity: O(n^2)

• we visit every cell in the matrix once

Space Complexity: O(n)

• only the answer array is used

Common mistakes

1. Overthinking the graph part

This problem looks like a graph problem, but the input is already an adjacency matrix. So we do not need DFS, BFS, or adjacency-list conversion.

2. Forgetting symmetry

Because the graph is undirected, rows and columns represent the same connections. That is why summing columns still works.

3. Mixing up degree with total graph edges

We want the degree of each vertex individually, not the total number of edges in the graph.

Why I like this problem

It is a clean beginner-friendly graph question.

The nice part is that once you understand what an adjacency matrix stores, the implementation becomes just a nested loop with a running count.