Skip to main content
Talentd

Zigzag Grid Traversal With Skip - Solution & Explanation

EasyArrayMatrixSimulation6 min readAsked at: Meta, Google, TCS
Practice this problem

Problem Statement

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:

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 <= 50
  • 2 <= m == grid[i].length <= 50
  • 1 <= grid[i][j] <= 2500

Approach Overview

Problem 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.

Solution

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Flatten then FilterO(m*n)O(m*n)Simple approach when building the full traversal list first
Direct Zigzag SimulationO(m*n)O(1)Optimal solution that processes the grid in-place without extra memory

Video Solution

Leetcode | 3417 Zigzag Grid Traversal With Skip | Java | Simple Approach | Weekly • Cakot Coding • 698 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Zigzag Grid Traversal With Skip easy or hard?
Zigzag Grid Traversal With Skip is classified as an Easy problem. The main challenge is correctly handling alternating row directions while applying the skip rule consistently across the traversal order.
Zigzag Grid Traversal With Skip Python/Java solution
The implementation is identical across languages: iterate rows, reverse column direction for odd rows, and toggle a skip flag after each visited cell. FleetCode provides full working implementations in Python, Java, C++, Go, and TypeScript.
How to solve Zigzag Grid Traversal With Skip in O(n)?
Treat the traversal as a sequential stream of visited cells produced by a zigzag scan of the matrix. Maintain a boolean flag to alternate between taking and skipping elements. Each step flips the flag, giving an overall O(m*n) traversal with constant extra space.
What is the best approach for Zigzag Grid Traversal With Skip?
The most efficient method is direct simulation of the zigzag traversal. Iterate through the matrix row by row, reversing direction for every alternate row, and maintain a toggle to skip every second visited cell. This runs in O(m*n) time with O(1) additional space.
Is Zigzag Grid Traversal With Skip asked at Google/Amazon/Meta?
Zigzag-style matrix traversal problems frequently appear in interviews at companies like Amazon and Google because they test iteration control and simulation skills. Variants involving diagonals, spiral order, or zigzag patterns are common.
What data structure is used in Zigzag Grid Traversal With Skip?
The solution primarily uses arrays and basic matrix traversal. No advanced data structures are required—just loop control for rows and columns and a boolean variable to track whether the current element should be skipped.
What is the time complexity of Zigzag Grid Traversal With Skip?
The time complexity is O(m*n) because every cell in the grid is visited exactly once during the zigzag traversal. The algorithm only performs constant work per cell. Space complexity is O(1) excluding the output array.

Ready to solve this problem?

Practice Zigzag Grid Traversal With Skip with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Zigzag Level Order Traversal

Next

Longest ZigZag Path in a Binary Tree