# Zigzag Grid Traversal With Skip
**Difficulty:** EASY
[External](https://leetcode.com/problems/zigzag-grid-traversal-with-skip)
Canonical: https://scaleengineer.com/dsa/problems/zigzag-grid-traversal-with-skip
**Data structures:** Array, Matrix
---
## Problem
You are given an `m x n` 2D array `grid` of **positive** integers.

Your task is to traverse `grid` in a **zigzag** pattern while skipping every **alternate** cell.

Zigzag pattern traversal is defined as following the below actions:

* Start at the top-left cell `(0, 0)`.
* Move _right_ within a row until the end of the row is reached.
* Drop down to the next row, then traverse _left_ until the beginning of the row is reached.
* Continue **alternating** between right and left traversal until every row has been traversed.

**Note** that you **must skip** every _alternate_ cell during the traversal.

Return an array of integers `result` containing, **in order**, the value of the cells visited during the zigzag traversal with skips.

**Example 1:**

**Input:** grid = \[\[1,2\],\[3,4\]\]

**Output:** \[1,4\]

**Explanation:**

**![](https://assets.glich.co/dsa/zigzag-grid-traversal-with-skip/image0.png)**

**Example 2:**

**Input:** grid = \[\[2,1\],\[2,1\],\[2,1\]\]

**Output:** \[2,1,2\]

**Explanation:**

![](https://assets.glich.co/dsa/zigzag-grid-traversal-with-skip/image1.png)

**Example 3:**

**Input:** grid = \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\]

**Output:** \[1,3,5,7,9\]

**Explanation:**

![](https://assets.glich.co/dsa/zigzag-grid-traversal-with-skip/image2.png)

**Constraints:**

* `2 <= n == grid.length <= 50`
* `2 <= m == grid[i].length <= 50`
* `1 <= grid[i][j] <= 2500`

# Approaches
## Two-Pass Traversal with Intermediate List
This approach breaks the problem into two distinct steps. First, it traverses the entire grid in the specified zigzag pattern and stores all the cell values in an intermediate list. This creates a linear sequence of all numbers as they would be encountered. In the second step, it iterates through this intermediate list and picks every alternate element (the first, third, fifth, etc.) to build the final result.
**Time:** O(rows * cols). The first pass to populate `zigzagOrder` takes O(rows * cols) time as it visits every cell. The second pass to populate `result` also takes O(rows * cols) time. The total time is O(rows * cols) + O(rows * cols) = O(rows * cols). · **Space:** O(rows * cols). An intermediate list `zigzagOrder` is created to store all `rows * cols` elements of the grid. The `result` list also stores up to `ceil((rows * cols) / 2)` elements. Thus, the space complexity is dominated by the intermediate list.
**Pros:** Conceptually simple, as it separates the traversal logic from the skipping logic.
**Cons:** Requires significant extra memory to store the intermediate list of all grid elements.; Less efficient than a single-pass solution due to iterating over the data twice and higher memory allocation overhead.
### Explanation
This method first linearizes the 2D grid into a 1D list according to the zigzag traversal rule. Once this complete sequence is stored, a second pass is made over the new list to select every other element, effectively applying the skipping rule.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> zigzagTraversal(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        List<Integer> zigzagOrder = new ArrayList<>();

        // First pass: Create a list of all elements in zigzag order
        for (int i = 0; i < rows; i++) {
            if (i % 2 == 0) { // Even row: traverse left to right
                for (int j = 0; j < cols; j++) {
                    zigzagOrder.add(grid[i][j]);
                }
            } else { // Odd row: traverse right to left
                for (int j = cols - 1; j >= 0; j--) {
                    zigzagOrder.add(grid[i][j]);
                }
            }
        }

        // Second pass: Pick every alternate element
        List<Integer> result = new ArrayList<>();
        for (int k = 0; k < zigzagOrder.size(); k += 2) {
            result.add(zigzagOrder.get(k));
        }

        return result;
    }
}
```
### Algorithm
- Initialize an empty `ArrayList<Integer>` called `zigzagOrder`.
- Get the grid dimensions, `rows` and `cols`.
- Iterate through each row of the grid from `i = 0` to `rows - 1`.
- If the row index `i` is even, traverse the columns from left to right (`j = 0` to `cols - 1`) and add `grid[i][j]` to `zigzagOrder`.
- If the row index `i` is odd, traverse the columns from right to left (`j = cols - 1` down to `0`) and add `grid[i][j]` to `zigzagOrder`.
- After the first traversal is complete, initialize another empty `ArrayList<Integer>` called `result`.
- Iterate through the `zigzagOrder` list with an index `k`, incrementing by 2 in each step (`k = 0, 2, 4, ...`).
- In each step, add the element `zigzagOrder.get(k)` to the `result` list.
- Return the `result` list.

## Single-Pass Direct Simulation
This is the most efficient approach. It simulates the zigzag traversal and makes the decision to add an element to the result list on the fly. A single boolean flag is used to keep track of whether the current cell is an 'add' or 'skip' cell in the overall traversal sequence. This avoids the need for an intermediate data structure and completes the task in a single pass over the grid.
**Time:** O(rows * cols). We iterate through each of the `rows * cols` cells in the grid exactly once. All operations inside the loops are constant time. · **Space:** O(rows * cols) or O(1). The space required for the output `result` list is O(rows * cols), as it can contain up to `ceil((rows * cols) / 2)` elements. If the output list is not considered as extra space, the space complexity is O(1) as we only use a few variables (`i`, `j`, `shouldAdd`) to perform the traversal.
**Pros:** Highly efficient in both time and space.; Processes the grid in a single pass.; Requires minimal auxiliary space (excluding the output list).
**Cons:** The logic for traversal and skipping is intertwined, which might be slightly less straightforward to read for a beginner compared to the two-pass approach.
### Explanation
This optimal solution performs the zigzag traversal and the skipping logic simultaneously. It maintains a state (a boolean flag `shouldAdd`) that tracks the overall position in the traversal (1st, 2nd, 3rd, etc.). This flag is toggled for every cell visited in the zigzag path, and the cell's value is added to the result only when the flag is true. This eliminates the need for extra space for an intermediate list.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> zigzagTraversal(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        List<Integer> result = new ArrayList<>();
        boolean shouldAdd = true;

        for (int i = 0; i < rows; i++) {
            if (i % 2 == 0) { // Even row: traverse left to right
                for (int j = 0; j < cols; j++) {
                    if (shouldAdd) {
                        result.add(grid[i][j]);
                    }
                    shouldAdd = !shouldAdd;
                }
            } else { // Odd row: traverse right to left
                for (int j = cols - 1; j >= 0; j--) {
                    if (shouldAdd) {
                        result.add(grid[i][j]);
                    }
                    shouldAdd = !shouldAdd;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty `ArrayList<Integer>` called `result`.
- Initialize a boolean flag, `shouldAdd`, to `true`.
- Get the grid dimensions, `rows` and `cols`.
- Iterate through each row of the grid from `i = 0` to `rows - 1`.
- Check the row index `i` to determine the direction of traversal.
- **If `i` is even:** Traverse columns from left to right (`j = 0` to `cols - 1`).
- **If `i` is odd:** Traverse columns from right to left (`j = cols - 1` down to `0`).
- For each cell encountered in the traversal:
  - If `shouldAdd` is `true`, add the cell's value to `result`.
  - Toggle the flag: `shouldAdd = !shouldAdd`.
- After iterating through all cells, return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> zigzagTraversal(int[][] grid) {
    boolean ok = true;
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < grid.length; ++i) {
      if (i % 2 == 1) {
        reverse(grid[i]);
      }
      for (int x : grid[i]) {
        if (ok) {
          ans.add(x);
        }
        ok = !ok;
      }
    }
    return ans;
  }
private
  void reverse(int[] nums) {
    for (int i = 0, j = nums.length - 1; i < j; ++i, --j) {
      int t = nums[i];
      nums[i] = nums[j];
      nums[j] = t;
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> zigzagTraversal(vector<vector<int>> &grid) {
    vector<int> ans;
    bool ok = true;
    for (int i = 0; i < grid.size(); ++i) {
      if (i % 2 != 0) {
        ranges ::reverse(grid[i]);
      }
      for (int x : grid[i]) {
        if (ok) {
          ans.push_back(x);
        }
        ok = !ok;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def zigzagTraversal(self, grid: List[List[int]]) -> List[int]: ok = True ans = [] for i, row in enumerate(grid): if i % 2: row . reverse() for x in row: if ok: ans . append(x) ok = not ok return ans

```