Diagonal Traverse in C++

Suppose we have a matrix of M x N elements, we have to find all elements of the matrix in diagonal order. So if the matrix is like −

The output will be [1,2,4,7,5,3,6,8,9]

To solve this, we will follow these steps −

• Make an array ret, set row := 0 and col := 0, n := row count, m := col count, down := false
• for i in range 0 to n – 1
  • x := i, y := 0
  • create an array temp
  • while x >= 0 and y < m, do
    • insert matrix[x,y] into temp, and decrease x by 1 and increase y by 1
  • if down is true, then reverse the temp array
  • for i in range 0 to size of temp – 1, insert temp[i] into ret
  • down := inverse of down
• for i in range 1 to m – 1
  • x := n – 1, y := 1, create an array temp
  • while x >= 0 and y < m,
    • insert matrix[x, y] into temp and decrease x by 1 and increase y by 1
  • for i in range 0 to size of temp – 1, insert temp[i] into ret
  • down := inverse of down
• return ret.

Let us see the following implementation to get better understanding −

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; void print_vector(vector<int> v){    cout << "[";    for(int i = 0; i<v.size(); i++){       cout << v[i] << ", ";    }    cout << "]"<<endl; } class Solution {    public:    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {       vector <int> ret;       int row = 0;       int col = 0;       int n = matrix.size();       int m = n? matrix[0].size() : 0;       bool down = false;       for(int i = 0; i < n; i++){          int x = i;          int y = 0;          vector <int> temp;          while(x >= 0 && y < m){             temp.push_back(matrix[x][y]);             x--;             y++;          }          if(down) reverse(temp.begin(), temp.end());          for(int i = 0; i < temp.size(); i++)ret.push_back(temp[i]);          down = !down;       }       for(int i = 1; i < m; i++){          int x = n - 1;          int y = i;          vector <int> temp;          while(x >= 0 && y < m){             temp.push_back(matrix[x][y]);             x--;             y++;          }          if(down) reverse(temp.begin(), temp.end());          for(int i = 0; i < temp.size(); i++)ret.push_back(temp[i]);          down = !down;       }       return ret;    } }; main(){    vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};    Solution ob;    print_vector(ob.findDiagonalOrder(v)); }

Input

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

Output

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