Zigzag Grid Traversal With Skip

Difficulty: Easy | Acceptance: 65.20% | Paid: No Topics: Array, Matrix, Simulation

You are given an m x n integer matrix grid. Return a 1D array containing all the elements of the grid in zigzag order, but skip any element that is equal to 0.

Zigzag order means that you traverse the grid row by row. For even-indexed rows (0, 2, 4, …), you traverse from left to right. For odd-indexed rows (1, 3, 5, …), you traverse from right to left.

• Examples
• Constraints
• Simulation with Direction Flag
• Row Reversal and Filter

Examples

Example 1:

Input: grid = [[1,2,3],[4,0,6],[7,8,9]] Output: [1,2,3,6,4,7,8,9] Explanation:

• Row 0 (even): Traverse 1, 2, 3.
• Row 1 (odd): Traverse 6, 0, 4. Skip 0. Result: 6, 4.
• Row 2 (even): Traverse 7, 8, 9. Combined: [1, 2, 3, 6, 4, 7, 8, 9]

Example 2:

Input: grid = [[0,1,2],[3,4,5]] Output: [1,2,5,4,3] Explanation:

• Row 0 (even): Traverse 0, 1, 2. Skip 0. Result: 1, 2.
• Row 1 (odd): Traverse 5, 4, 3. Combined: [1, 2, 5, 4, 3]

Example 3:

Input: grid = [[0]] Output: [] Explanation: The only element is 0, so it is skipped.

Constraints

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

Simulation with Direction Flag

Intuition We iterate through each row of the matrix. We maintain a boolean flag or check the row index parity to determine the traversal direction (left-to-right or right-to-left). As we visit each cell, we check if the value is non-zero before adding it to our result list.

Steps

• Initialize an empty list result.
• Iterate through each row i from 0 to m - 1.
• If i is even, iterate through columns j from 0 to n - 1.
• If i is odd, iterate through columns j from n - 1 down to 0.
• For each cell grid[i][j], if the value is not 0, append it to result.
• Return result.

from typing import List

class Solution:
    def zigzagTraversal(self, grid: List[List[int]]) -> List[int]:
        result = []
        m = len(grid)
        if m == 0:
            return result
        n = len(grid[0])
        
        for i in range(m):
            if i % 2 == 0:
                # Left to right
                for j in range(n):
                    if grid[i][j] != 0:
                        result.append(grid[i][j])
            else:
                # Right to left
                for j in range(n - 1, -1, -1):
                    if grid[i][j] != 0:
                        result.append(grid[i][j])
        return result

Complexity

• Time: O(m × n) — We visit every cell exactly once.
• Space: O(m × n) — In the worst case (no zeros), the result array stores all elements.
• Notes: This is the most efficient approach as it processes elements in a single pass with constant auxiliary space.

Row Reversal and Filter

Intuition We can simplify the logic by treating every row as a left-to-right traversal. For odd-indexed rows, we simply reverse the row (or iterate it in reverse) before filtering out the zeros. This approach leverages built-in functions to make the code concise, though it may involve extra memory if we create copies of rows.

Steps

• Initialize an empty list result.
• Iterate through each row i from 0 to m - 1.
• If i is odd, reverse the row (or iterate from end to start).
• Iterate through the elements of the (potentially reversed) row.
• If the element is not 0, append it to result.
• Return result.

from typing import List

class Solution:
    def zigzagTraversal(self, grid: List[List[int]]) -> List[int]:
        result = []
        for i, row in enumerate(grid):
            # If row is odd, reverse it for traversal
            if i % 2 != 0:
                row = row[::-1]
            
            for val in row:
                if val != 0:
                    result.append(val)
        return result

Complexity

• Time: O(m × n) — Reversing a row takes O(n), and we do this for m rows.
• Space: O(m × n) — In the worst case, we create a copy of the grid (or rows) for reversal, plus the output array.
• Notes: While conceptually simple, this approach uses more memory due to row copying/reversing compared to the simulation approach.