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

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

Example 2:

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

Constraints:

• m == mat.length

• n == mat[i].length

• 1 <= m, n <= 104

• 1 <= m * n <= 104

• -105 <= mat[i][j] <= 105

Intuition

Approach:

Simulation

Links

https://leetcode.com/problems/diagonal-traverse/

Video Links

Approach 1:

C++

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        pair<int,int> cod = {0,0};
        bool up = true;
        vector<int> ans;

        while(cod.first<m and cod.second<n){
            int a = cod.first, b = cod.second;
       
            if(up){
                int i,j;
                for(i=a, j=b; i>=0 and j<n; i--,j++){
                    ans.push_back(mat[i][j]);
                }
              
                i++; j--;
                if(j+1<n)
                    cod = {i,j+1};
                else
                    cod = {i+1,j};
            }
            else{
                int i,j;
                for(i=a, j=b; i<m and j>=0; i++,j--){
                    ans.push_back(mat[i][j]);
                }
                i--; j++;
    
                if(i+1<m)
                    cod = {i+1,j};
                else
                    cod = {i,j+1};
            }
            
            up = !up;
        }

        return ans;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems