Zigzag Traverse

• Time : O(nm)
• Space : O(1)

#include <vector>

using namespace std;

vector<int> zigzagTraverse(vector<vector<int>> array) {
    if(array.empty()) return {};
    vector<int> res;
    int n = array.size(), m = array[0].size();
    int dy = -1, dx = 1, i = 0, j = 0;
    while(i != n - 1 or j != m - 1) {
        res.push_back(array[i][j]);
        if(dy == -1) {
            if(i + 1 < n) i += 1;
            else j += 1;
            while(i and j != m - 1) {
                res.push_back(array[i][j]);
                i += dy, j += dx;
            }
            swap(dy, dx);
        } else {
            if(j + 1 < m) j += 1;
            else i += 1;
            while(i != n - 1 and j) {
                res.push_back(array[i][j]);
                i += dy, j += dx;
            }
            swap(dy, dx);
        }
    }
    res.push_back(array[i][j]);

    return res;
}