Solving a Leetcode problem daily — Day 5 | Diagonal Traverse
Tags: diagonal, traversal, cpp, leetcode
Published: 2024-05-06 02:32:51

{% embed https://medium.com/@subhradeep_saha/solving-a-leetcode-problem-daily-day-5-diagonal-traverse-17b173927e95 %}

---


Here is the Leetcode problem:

> [https://leetcode.com/explore/learn/card/array-and-string/202/introduction-to-2d-array/1167/](https://leetcode.com/explore/learn/card/array-and-string/202/introduction-to-2d-array/1167/)

---


### **Problem Statement**

Given a matrix (`mat`) with dimensions `m x n` (rows and columns) the task is to write a function that returns a one-dimensional array containing all the elements of the matrix in a diagonal order.

**Example:**

Input: mat = \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\]  
Output: \[1,2,4,7,5,3,6,8,9\]



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/f5kg6tetj7mjrnsv2ugv.png)




Here, the elements are traversed diagonally, starting from the top-left corner and moving towards the bottom-right corner (direction is **↘**), zig-zagging between upward and downward diagonals.

**Constraints:**

* The number of rows (`m`) is equal to the length of the inner arrays (`mat.length`).
    
* The number of columns (`n`) is equal to the length of each inner array (`mat[i].length`).
    
* Both `m` and `n` can range from 1 to 10^4 (10,000).
    
* The total number of elements (`m * n`) can also range from 1 to 10^4.
    
* Individual elements in the matrix (`mat[i][j]`) can have values between -10^5 and 10^5 (inclusive).
    

### **Code Implementation**

Here’s the C++ code that solves this challenge:

```cpp
class Solution {
public:
  vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
    int left_r = 0, left_c = 0, right_r = 0, right_c = 0;
    int r = mat.size(), c = mat[0].size();
    bool traverseRight = true;
    vector<int> res;
    
    while (left_c != c && left_r != r && right_c != c && right_r != r) {
        traverse(mat, traverseRight, left_r, left_c, right_r, right_c, res);
        
        if (left_r + 1 < r) {
            left_r++;
        } 
        else {
            left_c++;
        }
  
        if (right_c + 1 < c) {
          right_c++;
        } 
        else {
          right_r++;
        }
  
        traverseRight = !traverseRight;
    }
    return res;
  }
private:
  void traverse(vector<vector<int>>& mat, bool traverseRight, int left_r, int left_c, int right_r, int right_c, vector<int>& res) {
    if (traverseRight) {
      while (left_r >= right_r) {
        res.push_back(mat[left_r--][left_c++]);
      }
    } 
    else {
      while (left_r >= right_r) {
        res.push_back(mat[right_r++][right_c--]);
      }
    }
  }
};
```

### **Breakdown of the Code**

This code defines a class `Solution` with two functions:

* `findDiagonalOrder`: This is the main function that takes the matrix (`mat`) as input and returns the diagonal order array (`res`).
    
* `traverse`: This is a helper function that performs the diagonal traversal based on a direction flag (`traverseRight`) and boundary indices (`left_r`, `left_c`, `right_r`, `right_c`).
    

**Initialization:**

* \[`left_r`, `left_c`\] and \[`right_r`, `right_c`\] are the 2 boundary items on a diagonal between which we need to traverse. The first one is the boundary item on the left of the diagonal and the other is on the right boundary.
    
* `r` stores the number of rows (`mat.size()`).
    
* `c` stores the number of columns (`mat[0].size()`).
    
* `traverseRight` Flag\*\*:\*\* This boolean variable controls the direction of traversal.
    

`true`: Indicates right-upward diagonal traversal (\[`left_r`, `left_c`\] to \[`right_r`, `right_c`\])


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/akg3sqq1qmo493z7w0wr.png)



`false`: Indicates left-downward diagonal traversal (\[`right_r`, `right_c`\] to \[`left_r`, `left_c`\]).


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qhbw32x01ogfnl8wua25.png)



* `res`**:** This vector stores the elements of the matrix in diagonal order as they are traversed.
    
* `while` loop: The core logic resides within this loop, which continues until all elements are processed. It checks if any of the indices (`left_c`, `left_r`, `right_c`, `right_r`) reach their respective matrix boundaries.
    
* `traverse` function: Inside the loop, the `traverse` helper function is called based on the current `traverseRight` flag. This function handles the actual diagonal element addition to the `res` vector based on the `traverseRight` flag.
    
* **Updating Indices:** After each iteration of the `traverse` function:
    

a) If there are still more elements in the current row (`left_r + 1 < r`), `left_r` is incremented (moving down).

b) Otherwise, `left_c` is incremented (moving right to the next column).

c) If there are items in the current column(`right_c + 1 < c`), we got to next column `right_c++` else we go 1 row down(`right_r++`).

d) **Toggling Direction:** Finally, the `traverseRight` flag is flipped (`!traverseRight`) to indicate a change in direction for the next iteration.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eqiqm9vevxhswzmnjppy.png)



`traverse`**Function:** This helper function takes several arguments:

* `mat`: The reference to the original matrix.
    
* `traverseRight`: The direction flag.
    
* Boundary indices (`left_r`, `left_c`, `right_r`, `right_c`): Define the starting and ending points for the current diagonal traversal.
    
* `res`: The reference to the result vector.
    
* Inside the `traverse` function, a `while` loop continues as long as all the items in the diagonal are pushed to the res vector.
    
* Based on the `traverseRight` flag:
    

\=&gt; If `true` (upward diagonal): elements from `mat[left_r][left_r]` are added to `res` ; `left_r` is decremented and `left_c` is incremented to indicate a diagonally right-upward movement

\=&gt; If `false` (downward diagonal): elements from `mat[right_r][right_c]` are added to `res` ; `right_r` is incremented and `right_c` is decremented implying a diagonally left-downward movement.

**Return Value:** The `findDiagonalOrder` function returns the final `res` vector containing all the matrix elements in diagonal order.

### **Dry Run with a Test Case**

Let’s use the provided example matrix:

Input: mat = \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\]

**Step 1: Initialization**

* `left_r = 0`, `left_c = 0` (left side of a diagonal)
    
* `right_r = 0`, `right_c = 0` (right side of the diagonal)
    
* `r = 3` (number of rows)
    
* `c = 3` (number of columns)
    
* `traverseRight = true` (initial upward diagonal)
    
* `res = []` (empty result vector)
    
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3rb1muaa2srowtud009o.png)



**Step 2: First Iteration (Upward Diagonal)**

We call the `traverse` function with `traverseRight = true`. It starts processing elements from `mat[0][0]` (1) and moves diagonally up until it reaches the boundary (`left_r < right_r`).

* `res = [1]` (1 added to `res`)
    

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4zhfxsivcx8qcegv884c.png)



**Step 3: Updating Indices**

Since there are more elements in the first row (`left_r + 1 < r`), we increment `left_r` to 1. Similarly we increment right\_c to 1. Hence our next diagonal boundaries are ready:

* `left_r = 1`, `left_c = 0`
    
* `right_r = 0`, `right_c = 1`
    

The `traverseRight` flag is now reversed to false indicating a left-downward diagonal movement

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/iivg39wkfvwp6r8h68ix.png)



**Step 4: Second Iteration (Left-Downward Diagonal)**

We call `traverse` again. This time, it moves diagonally left-down.

* `res = [1, 2, 4]`
    


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w3e874g69uidtmbi6zgd.png)


**Step 5: Updating Indices**

Same logic as Step 3

* `left_r = 2`, `left_c = 0`
    
* `right_r = 0`, `right_c = 2`
    

The `traverseRight` flag is now reversed to true indicating a right-upward diagonal movement.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/65597u341pyo8gnps4lc.png)




**Step 6: Third Iteration (Right-Upward Diagonal)**



* `res = [1, 2, 4, 7, 5, 3]`
    
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g51sgm4r9zho01bntf7w.png)



**Step 7: Updating Indices**

For right boundary, there are no more elements in the current column (`right_c + 1 > c`), so we increment `right_r` to move down. Similarly for left boundary, there are no more items in the current row, so we move right by incrementing `left_c`

* `left_r = 2`, `left_c = 1`
    
* `right_r = 1`, `right_c = 2`
    

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sg4n8f5unvzws9gjemxr.png)



**Step 8: Fourth Iteration (Left-Downward Diagonal)**

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9402de2e89zo92bsy96r.png)




* `res = [1, 2, 4, 7, 5, 3, 6, 8]`
    

**Step 9: Updating Indices**

Same as step 7

* `left_r = 2`, `left_c = 2`
    
* `right_r = 2`, `right_c = 2` (reaches the end of the last row)
    
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6m1sw8w7mpo0hqyuga6f.png)




**Step 10: Fifth Iteration (Upward Diagonal)**


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zr8av07nofnm9ilmuyz5.png)





* `res = [1, 2, 4, 7, 5, 3, 6, 8, 9]`
    

**Step 11: Updating Indices**

Same as step 7

* `left_r = 2`, `left_c = 3`
    
* `right_r = 3`, `right_c = 2`
    

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r0d1ei9iab0x9x3io0u7.png)




**Step 12: Loop Termination**

The diagonal boundary is getting out of the actual input matrix dimensions so the while loop gets terminated.

**Final Result:**

The `res` vector now contains all the elements of the matrix in diagonal order: `[1, 2, 4, 7, 5, 3, 6, 8, 9]`.

### **Real-World Applications**

This diagonal order traversal technique can be applied to various real-world scenarios:

* **Image Processing:** When processing images, diagonal filtering techniques can be used for noise reduction or edge detection. By iterating over pixels in a diagonal order, filters can analyze neighboring pixels along diagonal patterns for specific effects.
    
* **Game Development:** In certain game genres like strategy games, pathfinding algorithms might consider diagonal movement for characters. Traversing the game map diagonally can help identify potential paths or obstacles.
    
* **Machine Learning:** In some machine learning algorithms, diagonal traversal can be used to access and process data stored in matrices. This can be relevant for tasks like image recognition or natural language processing.
    

### **Conclusion**

This blog explored the LeetCode challenge of traversing the diagonals of a matrix in C++. We tackled the problem statement, presented the code with explanations, performed a dry run with a test case and discussed few real-world applications.

### References

* **“Bilateral Filtering for Noise Reduction in Digital Images”**[https://people.csail.mit.edu/fredo/PUBLI/Siggraph2002/DurandBilateral.pdf](https://people.csail.mit.edu/fredo/PUBLI/Siggraph2002/DurandBilateral.pdf) by Sylvain Paris and Pierre Kornprobst: This paper explores bilateral filtering, a technique used for noise reduction in images. It mentions that bilateral filters can be applied along different directions, including diagonals.
    
* **“Pathfinding with Grids”**[https://brianlovin.com/hn/34594547](https://brianlovin.com/hn/34594547) by Christer Eklund on Gamasutra: This article discusses various pathfinding techniques for grid-based game worlds. It mentions that diagonal movement can be an important factor for characters to navigate efficiently within the game environment.
    
* **“Convolutional Neural Networks for Visual Recognition”**[https://cs231n.github.io/](https://cs231n.github.io/) by Andrej Karpathy et al.: CNNs heavily rely on matrix operations, and diagonal traversal can be a relevant concept for accessing and processing data within these matrices.
    
* Matrix diagrams are created using [Canva](https://www.canva.com/join/qsx-lqt-tpb)
    

If you liked this blog, do applaude the post by clicking on the clap hands icon. You can follow me [https://medium.com/@subhradeep\_saha](https://medium.com/@subhradeep_saha) and check out my other posts as well. In case you are interested more on traversals, do checkout this post — [Spiral Matrix Traversal](https://medium.com/@subhradeep_saha/solving-a-leetcode-problem-daily-day-3-spiral-matrix-e225fa1f15a9), where I explained the spiral traversal of a matrix. Thanks!