#3417

Easy

LeetCode Problem Workspace

Zigzag Grid Traversal With Skip

Traverse a 2D grid in a zigzag pattern while skipping alternate cells, focusing on array and matrix manipulation challenges.

array matrix simulation

Problem Statement

Given an m x n grid of positive integers, traverse it in a zigzag pattern where the direction alternates every row. While moving through the grid, skip every alternate cell to collect a sequence of values.

Implement a function that outputs an array of integers representing the values collected in order. Zigzag traversal requires moving left-to-right on one row, right-to-left on the next, and continuing this pattern, always skipping the next cell after collecting a value.

Examples

Example 1

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

Output: [1,4]

Example 2

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

Output: [2,1,2]

Example 3

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

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

Constraints

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

Solution Approach

Iterate Row by Row with Skip

Loop through each row, determining the direction based on the row index. Collect elements by skipping every second cell, toggling the starting index to maintain the zigzag order. This direct simulation matches the pattern of 'Array plus Matrix' accurately.

Track Skip Using a Boolean Flag

Use a boolean flag to indicate whether to include or skip the current cell. Flip the flag after each visited cell. This prevents off-by-one errors in the zigzag traversal and ensures skipped cells are consistently handled.

Build Output Dynamically

Append collected elements to a result array as traversal progresses. Adjust indices carefully at the row ends to avoid revisiting elements. This dynamic construction keeps memory usage minimal and maintains correct zigzag ordering.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) since each cell is visited at most once for consideration. Space complexity is O(k) where k is the number of collected elements, proportional to roughly half of m n due to skips.

What Interviewers Usually Probe

Ask about handling edge rows with uneven lengths or skips at boundaries.
Check if the candidate correctly toggles direction for zigzag and skips every other cell.
Probe whether the solution dynamically tracks positions without hardcoding indices.

Common Pitfalls or Variants

Common pitfalls

Failing to toggle direction for every row, leading to linear instead of zigzag traversal.
Off-by-one errors when skipping cells at row ends or matrix boundaries.
Collecting skipped elements due to incorrect flag handling or index calculation.

Follow-up variants

Traverse the grid diagonally while skipping elements in a defined step pattern.
Apply the zigzag skip pattern but start from the bottom-left corner instead of top-left.
Use a different skip interval, such as every third cell, to test generalized simulation logic.

FAQ

What is the expected output for Zigzag Grid Traversal With Skip on a 2x2 grid?

For grid [[1,2],[3,4]], the traversal collects [1,4] following the zigzag skip pattern.

How do I handle skipping cells in a zigzag traversal efficiently?

Use a boolean flag or index increment to skip every other cell while toggling direction at each row.

Does the zigzag always start left-to-right?

Yes, the traversal starts left-to-right on the first row and alternates direction on subsequent rows.

Can the solution handle non-square grids?

Yes, the row-by-row simulation adapts to m x n grids regardless of differing row lengths.

What pattern is crucial for solving Zigzag Grid Traversal With Skip?

Understanding the 'Array plus Matrix' pattern with alternating direction and consistent skipping is key to correctness.

terminal

Solution

Solution 1: Simulation

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.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#3242 design neighbor sum service #2946 matrix similarity after cyclic shifts #2679 sum in a matrix