Difficulty: 🟢 Easy
Topics: Array, Matrix, Simulation

Solution

LeetCode 3417 - Zigzag Grid Traversal With Skip

Problem Understanding

This problem asks us to traverse a two-dimensional grid in a zigzag order while visiting only every other cell in the traversal sequence.

The zigzag traversal follows a very specific pattern:

Start at the top-left corner (0, 0).
Traverse the first row from left to right.
Move down one row.
Traverse the next row from right to left.
Continue alternating directions for every row.

If we listed all cells encountered during this zigzag traversal, we would obtain a linear sequence of positions. The problem then requires us to keep only every alternate cell from that sequence.

Another way to think about it is:

Generate the complete zigzag traversal order.
Visit positions at indices 0, 2, 4, 6, ... of that traversal.
Return the corresponding grid values.

The input is an m × n matrix of positive integers.

grid[i][j] represents the value stored in row i, column j.
2 <= m, n <= 50, so the grid contains at most 2500 cells.
Values are between 1 and 2500.

The output is an array containing the values of the visited cells after applying both the zigzag traversal and the skipping rule.

The constraints are very small. Even processing every cell multiple times would be acceptable. Therefore, the main challenge is implementing the traversal correctly rather than optimizing for performance.

Important edge cases include alternating row directions, grids with an odd number of cells, grids with an even number of cells, and ensuring that the skipping continues globally across rows rather than restarting for each row.

Approaches

Brute Force Approach

The most straightforward solution is to explicitly construct the entire zigzag traversal order.

For each row:

If the row index is even, append elements from left to right.
If the row index is odd, append elements from right to left.

This produces a one-dimensional array containing all grid values in zigzag order.

After that, iterate through this array and take elements at indices 0, 2, 4, ....

This approach is correct because it directly simulates the problem statement. However, it stores the entire traversal sequence before producing the answer, which uses unnecessary extra memory.

Optimal Approach

Instead of building the full zigzag sequence first, we can process cells as we traverse them.

Maintain a boolean variable indicating whether the current traversed cell should be included in the answer.

Initially:

The first cell must be included.
After processing each traversed cell, flip the boolean.

During the zigzag traversal:

If the boolean is True, append the current value.
Flip the boolean regardless of whether the value was appended.

This simulates the "visit one, skip one, visit one, skip one" pattern directly during traversal.

The key observation is that the skipping rule applies to the traversal order, not to row indices or column indices. Therefore, a single global toggle is sufficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(mn)	O(mn)	Builds complete zigzag sequence first
Optimal	O(mn)	O(1) auxiliary	Processes traversal directly while skipping

The output array itself is not counted as auxiliary space.

Algorithm Walkthrough

Create an empty result array.
Initialize a boolean variable take = True.

This variable represents whether the current cell in the zigzag traversal should be added to the answer. 3. Iterate through every row.

The row index determines traversal direction. 4. For even-indexed rows, traverse columns from left to right.

This matches the zigzag definition. 5. For odd-indexed rows, traverse columns from right to left.

This maintains the alternating direction pattern. 6. For each visited cell:

If take is True, append its value to the result.
Flip take using take = not take.

Continue until all rows have been traversed.
Return the result array.

Why it works

The zigzag traversal defines a unique linear ordering of all grid cells. The variable take alternates between True and False after every visited cell, meaning cells at traversal indices 0, 2, 4, 6, ... are included while cells at indices 1, 3, 5, 7, ... are skipped. Since every cell is processed exactly once in the correct zigzag order and the inclusion pattern exactly matches the problem requirement, the algorithm always produces the correct result.

Python Solution

from typing import List

class Solution:
    def zigzagTraversal(self, grid: List[List[int]]) -> List[int]:
        result = []
        take = True

        rows = len(grid)
        cols = len(grid[0])

        for row in range(rows):
            if row % 2 == 0:
                for col in range(cols):
                    if take:
                        result.append(grid[row][col])
                    take = not take
            else:
                for col in range(cols - 1, -1, -1):
                    if take:
                        result.append(grid[row][col])
                    take = not take

        return result

The implementation follows the traversal order directly.

The variable result stores the final answer. The boolean take tracks whether the current traversed cell should be included.

For each row, the code determines the traversal direction. Even rows are processed from left to right, while odd rows are processed from right to left.

Every visited cell participates in the alternating include-skip pattern. If take is true, the value is appended. After processing the cell, take is flipped so the next traversed cell receives the opposite treatment.

Because every cell is visited exactly once and the toggle is maintained globally across rows, the implementation faithfully reproduces the required traversal.

Go Solution

func zigzagTraversal(grid [][]int) []int {
    result := []int{}
    take := true

    rows := len(grid)
    cols := len(grid[0])

    for row := 0; row < rows; row++ {
        if row%2 == 0 {
            for col := 0; col < cols; col++ {
                if take {
                    result = append(result, grid[row][col])
                }
                take = !take
            }
        } else {
            for col := cols - 1; col >= 0; col-- {
                if take {
                    result = append(result, grid[row][col])
                }
                take = !take
            }
        }
    }

    return result
}

The Go implementation is nearly identical to the Python version.

The main difference is that Go uses slices instead of Python lists. The result slice grows dynamically through append. The boolean toggle is implemented with take = !take.

There are no concerns about integer overflow because grid values are at most 2500. The function assumes the input satisfies the problem constraints, so grid[0] is always valid.

Worked Examples

Example 1

Input:

[[1,2],
 [3,4]]

Full zigzag order:

1, 2, 4, 3

Traversal trace:

Traversal Index	Value	take Before	Added?	Result
0	1	True	Yes	[1]
1	2	False	No	[1]
2	4	True	Yes	[1,4]
3	3	False	No	[1,4]

Output:

[1,4]

Example 2

Input:

[[2,1],
 [2,1],
 [2,1]]

Full zigzag order:

2, 1, 1, 2, 2, 1

Traversal trace:

Traversal Index	Value	take Before	Added?	Result
0	2	True	Yes	[2]
1	1	False	No	[2]
2	1	True	Yes	[2,1]
3	2	False	No	[2,1]
4	2	True	Yes	[2,1,2]
5	1	False	No	[2,1,2]

Output:

[2,1,2]

Example 3

Input:

[[1,2,3],
 [4,5,6],
 [7,8,9]]

Full zigzag order:

1, 2, 3, 6, 5, 4, 7, 8, 9

Traversal trace:

Traversal Index	Value	take Before	Added?	Result
0	1	True	Yes	[1]
1	2	False	No	[1]
2	3	True	Yes	[1,3]
3	6	False	No	[1,3]
4	5	True	Yes	[1,3,5]
5	4	False	No	[1,3,5]
6	7	True	Yes	[1,3,5,7]
7	8	False	No	[1,3,5,7]
8	9	True	Yes	[1,3,5,7,9]

Output:

[1,3,5,7,9]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(mn)	Every cell is visited exactly once
Space	O(1) auxiliary	Only a boolean and loop variables are used

The algorithm traverses each cell of the matrix exactly once. Since there are m × n cells, the running time is O(mn).

Apart from the output array, only a few scalar variables are maintained. Therefore the auxiliary space usage is constant.

Test Cases

from typing import List

s = Solution()

assert s.zigzagTraversal([[1, 2], [3, 4]]) == [1, 4]  # Example 1

assert s.zigzagTraversal([
    [2, 1],
    [2, 1],
    [2, 1]
]) == [2, 1, 2]  # Example 2

assert s.zigzagTraversal([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]) == [1, 3, 5, 7, 9]  # Example 3

assert s.zigzagTraversal([
    [1, 2],
    [3, 4],
    [5, 6]
]) == [1, 4, 5]  # Global skipping across row boundaries

assert s.zigzagTraversal([
    [1, 2, 3, 4]
]) == [1, 3]  # Single row

assert s.zigzagTraversal([
    [1, 2],
    [3, 4]
]) == [1, 4]  # Smallest valid dimensions

assert s.zigzagTraversal([
    [10, 20, 30],
    [40, 50, 60]
]) == [10, 30, 50]  # Even total cell count

assert s.zigzagTraversal([
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1]
]) == [1, 1, 1, 1, 1]  # Duplicate values

Test Summary

Test	Why
`[[1,2],[3,4]]`	Basic example from statement
Three-row alternating example	Verifies zigzag direction changes
`3×3` grid	Verifies odd number of cells
`[[1,2],[3,4],[5,6]]`	Ensures skipping continues across rows
Single row grid	Tests pure left-to-right traversal
Smallest valid dimensions	Boundary size check
`2×3` grid	Tests even total number of cells
Duplicate values grid	Ensures logic depends on positions, not values

Edge Cases

Global Skipping Across Row Boundaries

A common mistake is restarting the skip pattern at the beginning of every row. The problem defines skipping according to the overall zigzag traversal sequence, not separately within each row. The implementation avoids this bug by maintaining a single global take variable throughout the entire traversal.

Odd Number of Total Cells

When the total number of cells is odd, the final traversed cell may need to be included. For example, a 3×3 grid contains nine cells, so indices 0, 2, 4, 6, 8 are visited. Since the toggle is flipped after every processed cell, the implementation naturally handles this situation without any special logic.

Direction Changes Between Rows

Another potential source of bugs is traversing every row left-to-right. The zigzag pattern requires alternating directions. The implementation explicitly checks the row parity. Even rows use increasing column indices, while odd rows use decreasing column indices. This guarantees the traversal order matches the specification exactly.