Solving a Leetcode problem daily — Day 5 | Diagonal Traverse

Here is the Leetcode problem:

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]

https://assets.leetcode.com/uploads/2021/04/10/diag1-grid.jpg

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:

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])

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

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

traverseFunction: 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:

\=> 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

\=> 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)

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)

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

Step 4: Second Iteration (Left-Downward Diagonal)

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

• res = [1, 2, 4]

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.

Step 6: Third Iteration (Right-Upward Diagonal)

• res = [1, 2, 4, 7, 5, 3]

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

Step 8: Fourth Iteration (Left-Downward Diagonal)

• 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)

Step 10: Fifth Iteration (Upward Diagonal)

• 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

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 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 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/ 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

• Cover Photo by Ricardo Gomez Angel on Unsplash

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 and check out my other posts as well. In case you are interested more on traversals, do checkout this post — Spiral Matrix Traversal, where I explained the spiral traversal of a matrix. Thanks!