Intuition

The main idea is to simulate the zigzag traversal row by row, alternating direction, and skip every alternate cell by toggling a flag. We only add a cell to the result if it is not skipped.

Approach

Initialize an empty result array and a skip flag set to False.
For each row in the grid:
- If the row index is even, traverse left to right; if odd, traverse right to left.
- For each cell in the current row (in the correct direction):
  - If skip is False, add the cell to the result.
  - Toggle the skip flag after each cell.
Return the result array after traversing all rows.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<int> zigzagTraversal(vector<vector<int>>& grid) {\n        vector<int> ans;\n        bool skip = false;\n        int n = grid.size(), m = grid[0].size();\n        for (int i = 0; i < n; ++i) {\n            if (i % 2 == 0) {\n                for (int j = 0; j < m; ++j) {\n                    if (!skip) ans.push_back(grid[i][j]);\n                    skip = !skip;\n                }\n            } else {\n                for (int j = m - 1; j >= 0; --j) {\n                    if (!skip) ans.push_back(grid[i][j]);\n                    skip = !skip;\n                }\n            }\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">zigzagTraversal</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">>></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> grid</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        vector</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;int></span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> ans;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        bool</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> skip </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> false</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n </span><span style=

Related Tags