Zigzag Grid Traversal With Skip | Leetcode : 3417 | Simple and Easy Explanation

Zigzag traversal is a fascinating grid-related problem that combines traversal logic and pattern handling. In this blog, we'll explore "3417. Zigzag Grid Traversal With Skip" from LeetCode, breaking down the problem, discussing multiple approaches, and understanding their nuances. By the end, you'll feel confident tackling similar problems with ease.

Problem Description

You are given an m x n grid of positive integers. Your task is to traverse the grid in a zigzag pattern while skipping every alternate cell. The zigzag pattern is defined as follows:

1. Start at the top-left cell (0, 0).

2. Move right within a row until the end of the row is reached.

3. Drop down to the next row, then traverse left until the beginning of the row is reached.

4. Repeat the above steps for all rows.

You must skip every alternate cell while traversing the grid.

Input and Output

• Input: A 2D grid grid of positive integers.

• Output: An array of integers containing the values of the visited cells in order.

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

Observations and Insights

1. Zigzag Traversal:

   • Even-indexed rows (“row 0, 2, ...”) traverse from left to right.

   • Odd-indexed rows (“row 1, 3, ...”) traverse from right to left.

2. Skipping Alternate Cells:

   • Use a boolean variable or logic to skip every second cell across the traversal, not just within a single row but across rows.

3. Dimensions and Constraints:

   • The grid size is relatively small, making solutions feasible.

Approach 1: Brute Force Traversal

This approach implements the zigzag traversal with a straightforward row-by-row logic. A flag (skip) is used to determine whether to skip the current cell. The skipping condition carries over between rows to ensure consistent alternation.

Implementation (C++)

class Solution

{

public:

    vector<int> zigzagTraversal(vector<vector<int>> &grid)

    {

        int rows = grid.size();

        int cols = grid[0].size();

        vector<int> result;

        bool skip = false; // Whether to skip the next cell

        for (int i = 0; i < rows; i++)

        {

            if (i % 2 == 0)

            {

                // Traverse left to right

                for (int j = 0; j < cols; j++)

                {

                    if (!skip)

                        result.push_back(grid[i][j]);

                    skip = !skip;

                }

            }

            else

            {

                // Traverse right to left

                for (int j = cols - 1; j >= 0; j--)

                {

                    if (!skip)

                        result.push_back(grid[i][j]);

                    skip = !skip;

                }

            }

        }

        return result;

    }

};

Walkthrough for Example 3

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

• Row 0: Visit 1, skip 2, visit 3.

• Row 1: Skip 6, visit 5, skip 4.

• Row 2: Visit 7, skip 8, visit 9.

• Result: [1, 3, 5, 7, 9]

Complexity

• Time Complexity: O(row * col) , as each cell is visited once.

• Space Complexity: O(1), excluding the result vector.

---

Approach 2: Optimized Traversal with Cleaner Logic

To further optimize and simplify the traversal, we dynamically determine the start, end, and step size for each row based on its parity (even/odd). This avoids conditional checks inside the loops.

Implementation (C++)

class Solution

{

public:

    vector<int> zigzagTraversal(vector<vector<int>> &grid)

    {

        int rows = grid.size();

        int cols = grid[0].size();

        vector<int> result;

        bool skip = false;

        for (int i = 0; i < rows; i++)

        {

            int start = (i % 2 == 0) ? 0 : cols - 1;

            int end = (i % 2 == 0) ? cols : -1;

            int step = (i % 2 == 0) ? 1 : -1;

            for (int j = start; j != end; j += step)

            {

                if (!skip)

                    result.push_back(grid[i][j]);

                skip = !skip;

            }

        }

        return result;

    }

};

Key Changes

1. Dynamic Ranges:

   • For even rows, traverse from 0 to cols - 1 with step 1.

   • For odd rows, traverse from cols - 1 to 0 with step -1.

2. Simplified Loop Logic:

   • Eliminated redundant conditions inside the loops.

Complexity

• Time Complexity: O(row * col), as each cell is visited once.

• Space Complexity: O(1), excluding the result vector.

---

Tackling Similar Problems

When faced with traversal-based grid problems:

1. Understand the Pattern:

   • Is it row-wise, column-wise, or diagonal?

   • Does the traversal alternate or follow a strict sequence?

2. Handle Special Conditions:

   • Skipping cells, wrapping around, or conditional visiting.

3. Optimize with Ranges:

   • Dynamically determine the start, end, and step sizes for loops.

   • Avoid unnecessary condition checks inside nested loops.

4. Test Edge Cases:

   • Minimal grid sizes.

   • Skipping logic at boundaries.

The Zigzag Grid Traversal problem is an excellent exercise for building traversal skills and learning how to handle alternating patterns. By combining simple logic with efficient looping, we can solve the problem cleanly and confidently. If you found this post helpful, don’t forget to share it with your peers and keep practicing similar problems to solidify your understanding.