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:
(0, 0).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:
Example 2:
Input: grid = [[2,1],[2,1],[2,1]]
Output: [2,1,2]
Explanation:
Example 3:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,3,5,7,9]
Explanation:
Constraints:
2 <= n == grid.length <= 502 <= m == grid[i].length <= 501 <= grid[i][j] <= 2500Problem Overview: You are given a 2D grid and must traverse it in zigzag order. The first row is read left to right, the next right to left, alternating for every row. While traversing, you include one cell in the result and skip the next cell in the traversal order.
Approach 1: Simulation of Zigzag Traversal (O(m*n) time, O(1) extra space)
The grid is processed row by row while alternating traversal direction. For even-indexed rows iterate from column 0 → n-1, and for odd-indexed rows iterate from n-1 → 0. Maintain a boolean flag that represents whether the current cell should be skipped. When visiting each cell in traversal order, append the value only if the flag indicates it should be taken, then flip the flag.
This works because the zigzag pattern simply changes the order of column iteration, while the skip rule applies to the traversal sequence itself. Treat the entire traversal as a stream of visited cells. Every second element in that stream is ignored. No additional data structures are required beyond the result array.
The approach is straightforward to implement and avoids building an intermediate flattened list. You directly simulate the traversal pattern and decide on each step whether the element belongs in the answer.
Recommended for interviews: The simulation approach is what interviewers expect. It shows you understand matrix traversal patterns and can carefully control iteration order. The key observation is separating the zigzag traversal logic from the skipping rule. Implement the zigzag using simple loops, then apply the skip toggle during iteration. Problems involving array traversal and simulation frequently use this pattern.
We traverse each row. If the current row index is odd, we reverse the elements of that row. Then, we traverse the elements of the row and add them to the answer array according to the rules specified in the problem.
The time complexity is O(m times n), where m and n are the number of rows and columns of the 2D array grid, respectively. Ignoring the space consumption of the answer array, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Flatten then Filter | O(m*n) | O(m*n) | Simple approach when building the full traversal list first |
| Direct Zigzag Simulation | O(m*n) | O(1) | Optimal solution that processes the grid in-place without extra memory |
Leetcode | 3417 Zigzag Grid Traversal With Skip | Java | Simple Approach | Weekly • Komal Vhanmane • 686 views views
Watch 9 more video solutions →Practice Zigzag Grid Traversal With Skip with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor