Anti Diagonals (IB)

Simulation Array

Problem

Given an NxN square matrix, return an array of it's anti-diagonals

For example:

Input: 	

1 2 3
4 5 6
7 8 9

Return the following :

[ 
  [1],
  [2, 4],
  [3, 5, 7],
  [6, 8],
  [9]
]

Solution

class Solution:
    def diagonal(self, A):
        matrix = []
        R = len(A[0])-1
        B = len(A) - 1
        for j in range(R+1):
            res = []
            col = j
            row = 0
            while col >= 0:
                res.append(A[row][col])
                row+=1
                col-=1
            matrix.append(res)
        for i in range(1, B+1):
            res2 = []
            row = i
            col = R
            while row <= B:
                res2.append(A[row][col])
                row+=1
                col-=1
            matrix.append(res2)
        return(matrix)

Key Facts

• What really helps solve this problem is understanding how with each movement of the diagonal, the row increases by 1 while the column decreases by 1 (or (1,-1)).

• When we're done traversing the top, we need to start from the next row.

• All you need to know is how to obtain the first numbers of each diagonal with the for loops and then apply the knowledge of (1, -1) to iterate through the diagonals.

Time Complexity

Time:$O(n^2)$because we are iterating through the matrix with two loops.

Space: $O(n^2)$ because we are storing the diagonals in a 2D array.