LeetCode 3898 - Find the Degree of Each Vertex

The problem asks us to calculate the degree of each vertex in an undirected graph represented by an adjacency matrix. The input is a 2D integer array matrix of size n x n, where matrix[i][j] = 1 indicates an edge between vertices i and j, and matrix[i][j] = 0 indicates no edge.

leetcodeeasy

LeetCode Problem 3898

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

The problem asks us to calculate the degree of each vertex in an undirected graph represented by an adjacency matrix. The input is a 2D integer array matrix of size n x n, where matrix[i][j] = 1 indicates an edge between vertices i and j, and matrix[i][j] = 0 indicates no edge. Because the graph is undirected, the matrix is symmetric: matrix[i][j] == matrix[j][i]. Each vertex's degree is simply the number of edges connected to it, which is equivalent to counting the number of 1s in its corresponding row (or column) in the adjacency matrix.

The expected output is an array ans of size n, where ans[i] is the degree of vertex i.

Constraints ensure the input is a valid adjacency matrix: each diagonal element is 0 (no self-loops), each element is either 0 or 1, and the matrix is symmetric. The maximum size is 100 x 100, which is small enough for simple nested iterations.

Important edge cases include a single vertex graph (n = 1), vertices with no connections, and a fully connected graph where each vertex is connected to all others. These cases could expose off-by-one errors or mishandling of empty rows.

Approaches

A brute-force approach would iterate through every cell in the adjacency matrix and, for each vertex, count the number of 1s. This approach works because the degree is exactly the number of edges connected to the vertex. However, it unnecessarily checks all n^2 elements even though symmetry allows counting just the rows.

The optimal approach leverages the symmetry of the adjacency matrix and the fact that the degree of a vertex is the sum of 1s in its row. Instead of checking each pair multiple times, we simply sum each row to get the degree of the corresponding vertex. This reduces unnecessary operations and is simple to implement.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Iterate over entire matrix; count 1s for each vertex
Optimal O(n^2) O(n) Sum each row directly; simpler and avoids redundant checks

In this case, both approaches are O(n^2) because we still must inspect each row of length n for n vertices, but the optimal approach is cleaner and easier to reason about.

Algorithm Walkthrough

  1. Initialize an array ans of size n with zeros to store the degree of each vertex. Each index i will correspond to vertex i.
  2. Iterate over each vertex i from 0 to n - 1.
  3. For vertex i, calculate the sum of matrix[i]. Since each element is 0 or 1, this sum represents the number of edges connected to vertex i.
  4. Assign this sum to ans[i].
  5. After iterating through all vertices, return the array ans.

Why it works: The sum of each row directly counts the edges connected to that vertex because the adjacency matrix encodes a 1 for every connected vertex. The symmetry and constraints guarantee that each edge is counted exactly once per vertex in its row, giving the correct degree.

Python Solution

class Solution:
    def findDegrees(self, matrix: list[list[int]]) -> list[int]:
        n = len(matrix)
        ans = [0] * n
        for i in range(n):
            ans[i] = sum(matrix[i])
        return ans

In this implementation, we first determine the size of the matrix n. We initialize ans to store the degrees. For each vertex, we sum the corresponding row in matrix, which counts the number of edges connected to that vertex. Finally, we return ans.

Go Solution

func findDegrees(matrix [][]int) []int {
    n := len(matrix)
    ans := make([]int, n)
    for i := 0; i < n; i++ {
        degree := 0
        for j := 0; j < n; j++ {
            degree += matrix[i][j]
        }
        ans[i] = degree
    }
    return ans
}

In Go, we similarly determine the size of the matrix and create a slice ans of length n to hold the degrees. For each vertex, we iterate through its row and accumulate the sum of 1s in a variable degree, which we then assign to ans[i]. This version handles slices explicitly and does not rely on built-in sum functions.

Worked Examples

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

Vertex Row Sum Degree
0 [0,1,1] 2 2
1 [1,0,1] 2 2
2 [1,1,0] 2 2

Result: [2, 2, 2]

Example 2: matrix = [[0,1,0],[1,0,0],[0,0,0]]

Vertex Row Sum Degree
0 [0,1,0] 1 1
1 [1,0,0] 1 1
2 [0,0,0] 0 0

Result: [1, 1, 0]

Example 3: matrix = [[0]]

Vertex Row Sum Degree
0 [0] 0 0

Result: [0]

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) We iterate through each of the n rows, and each row has n elements, so O(n * n)
Space O(n) We store the degree of each of the n vertices in an output array

Even though we only sum rows, each row has n elements, so the algorithm is O(n^2), which is acceptable for n ≤ 100. Space is linear in the number of vertices because we only store the result.

Test Cases

solution = Solution()

# Provided examples
assert solution.findDegrees([[0,1,1],[1,0,1],[1,1,0]]) == [2,2,2]  # Fully connected 3-node graph
assert solution.findDegrees([[0,1,0],[1,0,0],[0,0,0]]) == [1,1,0]  # Sparse graph
assert solution.findDegrees([[0]]) == [0]  # Single vertex, no edges

# Edge cases
assert solution.findDegrees([[0,0],[0,0]]) == [0,0]  # Two disconnected vertices
assert solution.findDegrees([[0,1],[1,0]]) == [1,1]  # Two connected vertices
assert solution.findDegrees([[0]*100 for _ in range(100)]) == [0]*100  # Large disconnected graph
assert solution.findDegrees([[0 if i==j else 1 for j in range(100)] for i in range(100)]) == [99]*100  # Fully connected large graph
Test Why
[[0,1,1],[1,0,1],[1,1,0]] Validates fully connected small graph
[[0,1,0],[1,0,0],[0,0,0]] Validates sparse connections
[[0]] Validates single vertex case
[[0,0],[0,0]] Disconnected small graph
[[0,1],[1,0]] Two-node connected graph
100x100 zero matrix Validates large disconnected graph
100x100 fully connected matrix Validates large fully connected graph

Edge Cases

One important edge case is a single vertex graph (n = 1). The adjacency matrix is [[0]], and the algorithm correctly sums the row to return [0].

Another edge case is vertices with no connections. The algorithm handles rows full of 0s correctly, producing a degree of 0.

A third edge case is a fully connected graph where every vertex is connected to every other vertex. This tests that the algorithm correctly sums n-1 edges for each vertex and does not mistakenly include the diagonal element, which is guaranteed to be 0. This ensures no off-by-one errors.