Problem

You are given a 2D integer array matrix of size n x n representing the adjacency matrix of an undirected graph with n vertices labeled from 0 to n - 1.

matrix[i][j] = 1 indicates that there is an edge between vertices i and j.
matrix[i][j] = 0 indicates that there is no edge between vertices i and j.

The degree of a vertex is the number of edges connected to it.

Return an integer array ans of size n where ans[i] represents the degree of vertex i.

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]

Examples:

matrix = [[0,1,0],[1,0,0],[0,0,0]] → [1,1,0]. Vertices 0 and 1 are connected to each other, vertex 2 is isolated.
matrix = [[0]] → [0]. A single vertex with no edges.

Walkthrough

Loop and count

Given that each row of the matrix has a 1 if there is an edge, to find out how many edges there are connecting to any given row, it is simply the number of 1's in that row.

We can walk each row, count the entries equal to 1 with an if check, and append that count to the result.

class Solution:
  def findDegrees(self, matrix: list[list[int]]) -> list[int]:
    result = []
    for row in matrix:
      count = 0
      for value in row:
        if value == 1:
          count += 1
      result.append(count)
    return result

This is O(n^2) as the matrix is of size n x n and we loop through every element in it. We can't really do better than that on the time front: the input itself has n^2 entries and we have to look at all of them at least once to know if there's an edge.

The memory requirement is O(n) as we create a new output array of size n. That's also the lower bound, since the answer itself is n numbers long.

List comprehension

As the absence of an edge is a zero then the count of the number of ones is the same as the sum of the row. We don't need the explicit counter or the if check at all, just sum(row).

This means we can do this with a simple list comprehension. This is much more like the python code you'll actually find people writing.

class Solution:
  def findDegrees(self, matrix: list[list[int]]) -> list[int]:
    return [sum(row) for row in matrix]

Submission result

Same O(n^2) time and O(n) memory as before, just much shorter to read.

In-place

We could go a step further and avoid that extra n memory entirely by overwriting each row of the matrix with its sum.

class Solution:
  def findDegrees(self, matrix: list[list[int]]) -> list[int]:
    for i, row in enumerate(matrix):
      matrix[i] = sum(row)
    return matrix