# Diagonal Traverse

## Problem

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

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

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

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

{% endhint %}

### Thought Process

* Notice how essentially, we are only going in two directions, up and down. More specifically, going in a up-right pattern and a down-left pattern

* When going up, if you hit the top border, you have to go right one element; if you hit the far right border, you have to go down one element. Similarly, when going down, if you hit the bottom border, you have to go right one element; if you hit the far left border, you have to go down one element. 

* The reason a boolean works better for keeping track of direction compared to a variable (like in Spiral Order Matrix) is because we only need to keep track of two directions compared to four. The boolean allows us to flip between traversing the two directions like a light switch. 

## Solution

```
class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        #only going in two directions, up and down
        #use a boolean expression to flip between the directions
        
        if len(matrix) == 0:
            return
        
      
        bottom = len(matrix)-1
        left = 0
        right = len(matrix[0])-1
        goDown = False
        res = []
        row, col = 0,0
        
        while row <= bottom and col <= right:
            res.append(matrix[row][col])
            if goDown:
                if row == bottom or col == 0:
                    goDown = False
                    if row == bottom:
                        col+=1
                    else:     
                        row+=1
                else:
                    row+=1
                    col-=1
            else:
                if row == 0 or col == right:
                    goDown = True
                    if col == right:
                        row+=1
                    else:
                        col+=1
                else:
                    row-=1
                    col+=1
        return res
                
                
                    
           
```

## Key Facts

* Two cases we need to check for each direction:

  * When going down if we are in the first column **or** the last row
  * When going up if we are in the last column **or** top row

* To keep track of changing directions, we use a boolean variable since there are only two directions we are traversing. All we need to check is if this boolean is true or false to determine the direction we are traversing

## Time Complexity

* **Time**: $$O(n)$$&#x20;
* **Space:** $$O(n)$$for the return array


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://joshualbarb.gitbook.io/leetcode-problems/simulation-array/zigzag-traverse.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.