Problem Statement:

Given an m x n matrix mat, you are required to return all elements of the matrix in diagonal order. Diagonal order refers to the order in which the matrix elements are traversed diagonally. The traversal starts from the top-left corner of the matrix, moves in the diagonal direction, and changes direction when necessary to ensure all elements are covered.

Examples

Example 1:

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

Different Approaches

Things to Remember:

When performing diagonal traversal in a matrix. Two common types of diagonal traversal are:

1. From Top-Left to Bottom-Right.
2. From Top-Right to Bottom-Left.

Each of these traversals has a specific characteristic based on how the row (i) and column (j) indices sum up or differ.

🅰️ Top-Left to Bottom-Right Diagonal (i + j):

Intuition: When traversing from the top-right corner to the bottom-left corner diagonally, the difference between the row index i and the column index j stays constant for elements on the same diagonal.

Reason:

• For elements lying along a diagonal in this direction, the difference i - j remains constant. This makes sense because moving diagonally from top-right to bottom-left involves both increasing the row index and decreasing the column index, which keeps their difference the same.

How to Use:

• Group the elements of the matrix by their i - j values. For each unique value of i - j, the elements belong to the same diagonal.

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

Diagonals based on i + j:

Diagonal 0 (i + j = 0): [1]
Diagonal 1 (i + j = 1): [2, 4]
Diagonal 2 (i + j = 2): [3, 5, 7]
Diagonal 3 (i + j = 3): [6, 8]
Diagonal 4 (i + j = 4): [9]

🅱️ Top-Right to Bottom-Left Diagonal (i - j):

Intuition: When traversing from the top-right corner to the bottom-left corner diagonally, the difference between the row index i and the column index j stays constant for elements on the same diagonal.

Reason:

• For elements lying along a diagonal in this direction, the difference i - j remains constant. This makes sense because moving diagonally from top-right to bottom-left involves both increasing the row index and decreasing the column index, which keeps their difference the same.

How to Use:

• Group the elements of the matrix by their i - j values. For each unique value of i - j, the elements belong to the same diagonal.

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

Diagonals based on i - j:

Diagonal 0 (i - j = 0): [1, 5, 9]
Diagonal 1 (i - j = -1): [2, 6]
Diagonal 2 (i - j = -2): [3]
Diagonal 1 (i - j = 1): [4, 8]
Diagonal 2 (i - j = 2): [7]

Comparison:

1️⃣ Using Diagonal Grouping (i + j)

Intuition:

The key observation in the diagonal traversal of a matrix is that elements that belong to the same diagonal share a common property. For any element at position (i, j) in the matrix:

• Diagonal Identification: All elements on the same diagonal have the same value for the sum i + j (row index + column index). This allows us to group the matrix elements by their diagonal.

Thus, by using i + j as a key, we can group all matrix elements into diagonals. After grouping, we can traverse the diagonals and collect the elements in the required order:

• Odd diagonals are traversed from left to right (normal order).
• Even diagonals are traversed from right to left (reversed order).

Dry Run:

Initialization:

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

Step 1: Group Elements by i + j (Diagonal Grouping):

We traverse the matrix, calculating i + j for each element:

We group the elements based on the diagonal i + j:

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

Step 2: Traverse the Diagonals:

We now traverse the diagonals in order of i + j:

Diagonal 0 (even): [1] remains the same → add [1] to the result.
Diagonal 1 (odd): [2, 4] remains the same → add [2, 4] to the result.
Diagonal 2 (even): [3, 5, 7] is reversed to [7, 5, 3] → add [7, 5, 3] to the result.
Diagonal 3 (odd): [6, 8] remains the same → add [6, 8] to the result.
Diagonal 4 (even): [9] remains the same → add [9] to the result.

Final Output:

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

Code:

vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
    unordered_map<int, vector<int>> diagonals;
    int m = mat.size();
    int n = mat[0].size();
    vector<int> result;

    // Step 1: Group all elements by the sum of their indices (i + j)
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            diagonals[i + j].push_back(mat[i][j]);
        }
    }

    // Step 2: Traverse the diagonals
    for (int k = 0; k <= m + n - 2; ++k) {
        if (k % 2 == 0) {
            // Reverse elements for even diagonal
            reverse(diagonals[k].begin(), diagonals[k].end());
        }
        // Add all elements of this diagonal to the result
        for (int num : diagonals[k]) {
            result.push_back(num);
        }
    }

    return result;
}

Complexity Analysis:

• Time Complexity: O(m * n)
  • Grouping Elements: We iterate through every element in the matrix once, so grouping takes O(m*n), where m is the number of rows and n is the number of columns.
  • Reversing and collecting diagonals: Processing each diagonal (reversing even diagonals) takes O(m*n), since every element is processes once.
  • Total Time Complexity: O(m*n)
• Space Complexity: O(m*n)
  • We use an extra unordered_map to store the diagonals, which takes O(m*n) space.
  • The result vector also takes O(m*n) space.
  • Total Space Complexity: O(m*n).