---
description: Simulation Array
---

# Anti Diagonals (IB)

## Problem

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

{% hint style="info" %}
For example:

```
Input: 	

1 2 3
4 5 6
7 8 9

Return the following :

[ 
  [1],
  [2, 4],
  [3, 5, 7],
  [6, 8],
  [9]
]
```
{% endhint %}

## 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.
