algoadvance

Leetcode 498. Diagonal Traverse

Problem Statement:

Given an m x n matrix mat, return an array of all the elements of the array 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]

Clarifying Questions:

  1. Q: What are the constraints on the matrix dimensions?
    • A: The matrix dimensions m (number of rows) and n (number of columns) are such that 1 <= m, n <= 10^4.
  2. Q: Are there any conditions where the matrix could contain negative numbers?
    • A: Yes, the matrix can contain any integers within the conventional integer range in programming.
  3. Q: What should we return if the matrix is empty?
    • A: An empty matrix should return an empty list.

Strategy:

To solve this problem, we can traverse the matrix diagonally. We maintain a boolean flag to control the direction of traversal. We will switch directions when we hit boundaries (edges of the matrix).

Here’s how we can break down the solution:

  1. Start at the top-left element of the matrix.
  2. Maintain a direction flag where true means moving upward diagonally and false means moving downward diagonally.
  3. For each move:
    • If moving upward and you hit the top boundary (i == 0), you need to move right (j++). If you hit the right boundary (j == n-1), you need to move down (i++).
    • If moving downward and you hit the left boundary (j == 0), you need to move down (i++). If you hit the bottom boundary (i == m-1), you need to move right (j++).
  4. Continue this process until all elements are traversed.

Code:

#include <vector>

std::vector<int> findDiagonalOrder(std::vector<std::vector<int>>& mat) {
    if (mat.empty() || mat[0].empty()) return {};

    int m = mat.size();
    int n = mat[0].size();
    std::vector<int> result;
    result.reserve(m * n);

    int i = 0, j = 0;
    bool goingUp = true;

    while (result.size() < m * n) {
        result.push_back(mat[i][j]);
        if (goingUp) {
            if (j == n - 1) {
                i++; // Hit right boundary, move down
                goingUp = false;
            } else if (i == 0) {
                j++; // Hit top boundary, move right
                goingUp = false;
            } else {
                i--;
                j++;
            }
        } else {
            if (i == m - 1) {
                j++; // Hit bottom boundary, move right
                goingUp = true;
            } else if (j == 0) {
                i++; // Hit left boundary, move down
                goingUp = true;
            } else {
                i++;
                j--;
            }
        }
    }

    return result;
}

Time Complexity:

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI