Problem Description

You have a 2D grid of positive integers with m rows and n columns. Your task is to traverse this grid in a zigzag pattern while skipping every other cell you encounter.

The zigzag traversal works like this:

• Start at the top-left corner at position (0, 0)
• Move right across the first row until you reach the end
• Drop down to the second row and move left until you reach the beginning
• Continue this pattern, alternating between moving right and left for each subsequent row

The key constraint is that you must skip every alternate cell during your traversal. This means:

• Visit the 1st cell, skip the 2nd cell
• Visit the 3rd cell, skip the 4th cell
• And so on...

The skipping continues across row boundaries - if you end a row on a "skip", you'll start the next row on a "visit" and vice versa.

For example, with a 3×3 grid:

1 2 3
4 5 6  
7 8 9

The zigzag order would be: 1, 2, 3, 6, 5, 4, 7, 8, 9 After applying the skip pattern: 1 (visit), skip 2, 3 (visit), skip 6, 5 (visit), skip 4, 7 (visit), skip 8, 9 (visit) Result: [1, 3, 5, 7, 9]

Return an array containing the values of only the visited cells in the order they were encountered during the zigzag traversal.

Intuition

The key insight is to recognize that we need to handle two distinct patterns: the zigzag traversal and the alternating skip pattern.

For the zigzag traversal, we notice that:

• Even-indexed rows (0, 2, 4, ...) are traversed left to right
• Odd-indexed rows (1, 3, 5, ...) are traversed right to left

Instead of implementing complex logic to traverse backwards, we can simply reverse the odd rows before processing them. This transforms the problem into a straightforward left-to-right traversal of all rows.

For the skip pattern, we need to maintain a global state that tracks whether the current cell should be visited or skipped. This state must persist across row boundaries - if we end row i on a "skip", we should start row i+1 on a "visit".

We can use a boolean flag ok that:

• When True: add the current element to our result
• When False: skip the current element
• Toggle after processing each cell, regardless of whether we visited or skipped it

By combining these two ideas:

1. Process rows in order, reversing odd-indexed rows to simulate the zigzag
2. Maintain a single boolean that toggles for every cell encountered

This gives us a clean solution that handles both the zigzag pattern and the skip logic without complex index calculations or special cases for row boundaries.

Solution Approach

The implementation follows a simulation approach where we process the grid row by row while maintaining the zigzag pattern and skip logic.

Step 1: Initialize variables

• Create a boolean flag ok = True to track whether the current cell should be visited
• Create an empty list ans to store the visited cell values

Step 2: Process each row with zigzag logic

for i, row in enumerate(grid):
    if i % 2:
        row.reverse()

• Iterate through each row with its index
• For odd-indexed rows (when i % 2 is truthy), reverse the row in-place
• This simulates moving right-to-left without changing our traversal direction

Step 3: Process cells with skip pattern

for x in row:
    if ok:
        ans.append(x)
    ok = not ok

• For each element x in the current row (possibly reversed)
• Check if ok is True - if so, add the element to our answer
• Toggle ok using ok = not ok regardless of whether we visited or skipped
• This ensures the skip pattern continues correctly across row boundaries

Step 4: Return the result

• After processing all rows, return the ans list containing visited cells in order

The time complexity is O(m × n) where m is the number of rows and n is the number of columns, as we visit every cell once. The space complexity is O(k) where k is the number of visited cells (approximately half of all cells), not counting the space needed for the output array.

The elegance of this solution lies in its simplicity - by reversing odd rows, we transform a complex bidirectional traversal into a simple unidirectional one, while a single boolean efficiently handles the alternating skip pattern.

Example Walkthrough

Let's trace through a 3×4 grid to illustrate the solution approach:

Grid:
1  2  3  4
5  6  7  8
9  10 11 12

Initial State:

• ok = True (start by visiting)
• ans = [] (empty result list)

Processing Row 0 (index = 0, even):

• Row remains as-is: [1, 2, 3, 4] (no reversal for even rows)
• Process element 1: ok = True, so append 1 to ans → ans = [1], toggle ok → ok = False
• Process element 2: ok = False, so skip, toggle ok → ok = True
• Process element 3: ok = True, so append 3 to ans → ans = [1, 3], toggle ok → ok = False
• Process element 4: ok = False, so skip, toggle ok → ok = True

Processing Row 1 (index = 1, odd):

• Reverse the row: [5, 6, 7, 8] becomes [8, 7, 6, 5]
• Process element 8: ok = True, so append 8 to ans → ans = [1, 3, 8], toggle ok → ok = False
• Process element 7: ok = False, so skip, toggle ok → ok = True
• Process element 6: ok = True, so append 6 to ans → ans = [1, 3, 8, 6], toggle ok → ok = False
• Process element 5: ok = False, so skip, toggle ok → ok = True

Processing Row 2 (index = 2, even):

• Row remains as-is: [9, 10, 11, 12] (no reversal for even rows)
• Process element 9: ok = True, so append 9 to ans → ans = [1, 3, 8, 6, 9], toggle ok → ok = False
• Process element 10: ok = False, so skip, toggle ok → ok = True
• Process element 11: ok = True, so append 11 to ans → ans = [1, 3, 8, 6, 9, 11], toggle ok → ok = False
• Process element 12: ok = False, so skip, toggle ok → ok = True

Final Result: [1, 3, 8, 6, 9, 11]

The zigzag traversal order was: 1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12 After applying the skip pattern (visit, skip, visit, skip...): we get [1, 3, 8, 6, 9, 11]

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n), where m is the number of rows and n is the number of columns in the 2D array grid.

The algorithm iterates through each row of the grid exactly once using the outer loop, which runs m times. For each row, it processes all n elements in that row. Even though odd-indexed rows are reversed with row.reverse() which takes O(n) time, and then we iterate through the row with another O(n) operation, these are sequential operations that still result in O(n) time per row. Therefore, the total time complexity is O(m × n).

Space Complexity: O(1) (excluding the output array ans).

The algorithm uses only a constant amount of extra space for variables like ok, i, and x. The reverse() operation modifies the row in-place and doesn't require additional space. While the answer array ans grows to potentially store up to O(m × n) elements, following the convention stated in the reference answer, we exclude the space consumed by the answer array from our space complexity analysis.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Modifying the Original Input Grid

The current solution modifies the input grid by reversing odd-indexed rows in-place using row.reverse(). This is a destructive operation that permanently alters the input data, which can cause issues if:

• The grid needs to be reused elsewhere in the program
• The function is called multiple times on the same grid
• The input grid is immutable or shared across different parts of the application

Example of the problem:

grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
solution = Solution()
result1 = solution.zigzagTraversal(grid)
# grid is now modified: [[1, 2, 3], [6, 5, 4], [7, 8, 9]]
result2 = solution.zigzagTraversal(grid)  # Wrong result!

Solution: Use Non-Destructive Traversal

Instead of modifying the input grid, traverse the elements without changing the original data structure:

class Solution:
    def zigzagTraversal(self, grid: List[List[int]]) -> List[int]:
        should_include = True
        result = []
      
        for row_index, row in enumerate(grid):
            # Determine traversal direction based on row index
            if row_index % 2 == 0:
                # Even rows: traverse left to right
                for col_index in range(len(row)):
                    if should_include:
                        result.append(row[col_index])
                    should_include = not should_include
            else:
                # Odd rows: traverse right to left
                for col_index in range(len(row) - 1, -1, -1):
                    if should_include:
                        result.append(row[col_index])
                    should_include = not should_include
      
        return result

Alternative solution using slicing (creates a copy):

class Solution:
    def zigzagTraversal(self, grid: List[List[int]]) -> List[int]:
        should_include = True
        result = []
      
        for row_index, row in enumerate(grid):
            # Create a reversed copy for odd rows instead of modifying in-place
            current_row = row[::-1] if row_index % 2 == 1 else row
          
            for element in current_row:
                if should_include:
                    result.append(element)
                should_include = not should_include
      
        return result

Both solutions maintain the same time complexity O(m × n) while preserving the input grid's integrity.