Problem Description
You are given an m x n 2D array grid of positive integers. Your task is to traverse grid in a zigzag pattern while skipping every alternate cell. Zigzag pattern traversal is defined as starting at the top-left cell (0, 0), moving right within a row until the end is reached, dropping down to the next row, and then traversing left until the beginning of the row is reached. Continue alternating between right and left traversal until every row has been traversed, skipping every alternate cell during the traversal. Return an array of integers result containing, in order, the value of the cells visited during the zigzag traversal with skips.
Key Insights
- Zigzag traversal alternates between moving right and left through rows.
- Every alternate cell must be skipped during the traversal.
- The pattern of cell selection depends on the row's index (even or odd).
- The solution requires careful indexing to ensure we only access the cells we need.
Space and Time Complexity
Time Complexity: O(m * n)
Space Complexity: O(1) (excluding the output array)
Solution
To solve the problem, we can simulate the zigzag traversal of the 2D grid. We will iterate over each row, using the row index to determine the direction of traversal (left or right). While traversing, we will skip every alternate cell by checking the index of each cell. If the index of the cell is even, we will add its value to the result array. We will keep track of the current direction of the traversal using a boolean flag.