Find the Degree of Each Vertex

Intuition #

The degree of a vertex is the number of edges connected to it, and matrix[i][j] is either 1 for connected or 0 for not connected.

We are tasked to return the number of edges connected to i, and the sum of matrix[i] is the number of edges connected to i.

Approach #

• Initialize result of type []int.
• Loop (i) over matrix:
  • Loop (j) over matrix[i]:
    • Add matrix[i][j] to result[i].
• Return result.

Complexity #

• Time complexity: $O(N^2)$.

  • We visit every cell once.

• Space complexity: $O(N)$.

  • result contains $N$ elements.

Code #

 1func findDegrees(matrix [][]int) []int {
 2	result := make([]int, len(matrix))
 3
 4	for i := range matrix {
 5		for j := range matrix[i] {
 6			result[i] += matrix[i][j]
 7		}
 8	}
 9
10	return result
11}