# C++ ZigZag Problem Set Summary

• Problem 6 ---- The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

``````class Solution {
public:
string convert(string s, int numRows) {
if (numRows <= 1)
return s;

const int len = (int)s.size();
string str[numRows];
int row = 0, step = 1;
//by flipping the step between 1 and -1, we can write all the str to its correct row position
for (int i = 0; i < len; i++) {
str[row].push_back(s[i]);
if (row == 0)
step = 1;
else if (row == numRows - 1)
step = -1;
row += step;
}
s.clear();
for (int j = 0; j < numRows; j++)  s.append(str[j]);
return s;
}
};
``````

Problem 103 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

``````class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
if(!root) return result;
deque<TreeNode*> dq;
dq.push_back(root);
int flag = 0;
while (!dq.empty()) {
/** use the count to record the level element count **/
int count = dq.size();
vector<int> level;
while (count-- > 0) {
TreeNode* cur = dq.front();
dq.pop_front();
level.push_back(cur->val);
if (cur->left)  dq.push_back(cur->left);
if (cur->right) dq.push_back(cur->right);
}
if (flag & 1)  reverse(level.begin(), level.end());
result.push_back(level);
flag ++;
}
return result;
}
};
``````

ZigZag Iterator Problem Given two 1d vectors, implement an iterator to return their elements alternately. For example, given two 1d vectors: v1 = [1, 2] v2 = [3, 4, 5, 6] By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

``````class ZigzagIterator {
public:
ZigzagIterator(vector<int>& v1, vector<int>& v2) {
v.push_back(v1);
v.push_back(v2);
i = j = 0;
}
int next() {
return i <= j ? v[0][i++] : v[1][j++];
}
bool hasNext() {
if (i >= v[0].size()) i = INT_MAX;
if (j >= v[1].size()) j = INT_MAX;
return i < v[0].size() || j < v[1].size();
}
private:
vector<vector<int>> v;
int i, j;
};
``````

Follow up , what should we do if we want to do zigzag iterator for K arrays :

``````class ZigzagIterator {
public:
ZigzagIterator(vector<int>& v1, vector<int>& v2) {
if (!v1.empty()) q.push(make_pair(v1.begin(), v1.end()));
if (!v2.empty()) q.push(make_pair(v2.begin(), v2.end()));
}
int next() {
auto it = q.front().first, end = q.front().second;
q.pop();
if (it + 1 != end) q.push(make_pair(it + 1, end));
return *it;
}
bool hasNext() {
return !q.empty();
}
private:
queue<pair<vector<int>::iterator, vector<int>::iterator>> q;
};
``````

Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
[1,2],
[3],
[4,5,6]
]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

Brute Force Solution

``````class Vector2D {
public:
Vector2D(vector<vector<int>>& vec2d) {
for (auto a : vec2d) {
v.insert(v.end(), a.begin(), a.end());
}
}
int next() {
return v[i++];
}
bool hasNext() {
return i < v.size();
}
private:
vector<int> v;
int i = 0;
};

``````

We can keep 2 variable x and y , we check whether x is valid and y is valid, and we can change to the new line once we meet the ending of the line

``````class Vector2D {
public:
Vector2D(vector<vector<int>>& vec2d) {
v = vec2d;
x = y = 0;
}
int next() {
return v[x][y++];
}
bool hasNext() {
while (x < v.size() && y == v[x].size()) {
++x;
y = 0;
}
return x < v.size();
}
private:
vector<vector<int>> v;
int x, y;
};

``````

Follow Up : implement it with iterator style

``````class Vector2D {
public:
Vector2D(vector<vector<int>>& vec2d) {
x = vec2d.begin();
end = vec2d.end();
}
int next() {
return (*x)[y++];
}
bool hasNext() {
while (x != end && y == (*x).size()) {
++x;
y = 0;
}
return x != end;
}
private:
vector<vector<int>>::iterator x, end;
int y = 0;
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.