Scale Engineer

Zigzag Grid Traversal With Skip

Easy
#3036Time: O(rows * cols). The first pass to populate `zigzagOrder` takes O(rows * cols) time as it visits every cell. The second pass to populate `result` also takes O(rows * cols) time. The total time is O(rows * cols) + O(rows * cols) = O(rows * cols).Space: O(rows * cols). An intermediate list `zigzagOrder` is created to store all `rows * cols` elements of the grid. The `result` list also stores up to `ceil((rows * cols) / 2)` elements. Thus, the space complexity is dominated by the intermediate list.
Data structures
ArrayMatrix

Prompt

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 following the below actions:

  • Start at the top-left cell (0, 0).
  • Move right within a row until the end of the row is reached.
  • Drop down to the next row, then traverse left until the beginning of the row is reached.
  • Continue alternating between right and left traversal until every row has been traversed.

Note that you must skip 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.

 

Example 1:

Input: grid = [[1,2],[3,4]]

Output: [1,4]

Explanation:

Example 2:

Input: grid = [[2,1],[2,1],[2,1]]

Output: [2,1,2]

Explanation:

Example 3:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,3,5,7,9]

Explanation:

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach breaks the problem into two distinct steps. First, it traverses the entire grid in the specified zigzag pattern and stores all the cell values in an intermediate list. This creates a linear sequence of all numbers as they would be encountered. In the second step, it iterates through this intermediate list and picks every alternate element (the first, third, fifth, etc.) to build the final result.

Algorithm

  • Initialize an empty ArrayList<Integer> called zigzagOrder.
  • Get the grid dimensions, rows and cols.
  • Iterate through each row of the grid from i = 0 to rows - 1.
  • If the row index i is even, traverse the columns from left to right (j = 0 to cols - 1) and add grid[i][j] to zigzagOrder.
  • If the row index i is odd, traverse the columns from right to left (j = cols - 1 down to 0) and add grid[i][j] to zigzagOrder.
  • After the first traversal is complete, initialize another empty ArrayList<Integer> called result.
  • Iterate through the zigzagOrder list with an index k, incrementing by 2 in each step (k = 0, 2, 4, ...).
  • In each step, add the element zigzagOrder.get(k) to the result list.
  • Return the result list.

Walkthrough

This method first linearizes the 2D grid into a 1D list according to the zigzag traversal rule. Once this complete sequence is stored, a second pass is made over the new list to select every other element, effectively applying the skipping rule.

import java.util.ArrayList;import java.util.List; class Solution {    public List<Integer> zigzagTraversal(int[][] grid) {        int rows = grid.length;        int cols = grid[0].length;        List<Integer> zigzagOrder = new ArrayList<>();         // First pass: Create a list of all elements in zigzag order        for (int i = 0; i < rows; i++) {            if (i % 2 == 0) { // Even row: traverse left to right                for (int j = 0; j < cols; j++) {                    zigzagOrder.add(grid[i][j]);                }            } else { // Odd row: traverse right to left                for (int j = cols - 1; j >= 0; j--) {                    zigzagOrder.add(grid[i][j]);                }            }        }         // Second pass: Pick every alternate element        List<Integer> result = new ArrayList<>();        for (int k = 0; k < zigzagOrder.size(); k += 2) {            result.add(zigzagOrder.get(k));        }         return result;    }}

Complexity

Time

O(rows * cols). The first pass to populate `zigzagOrder` takes O(rows * cols) time as it visits every cell. The second pass to populate `result` also takes O(rows * cols) time. The total time is O(rows * cols) + O(rows * cols) = O(rows * cols).

Space

O(rows * cols). An intermediate list `zigzagOrder` is created to store all `rows * cols` elements of the grid. The `result` list also stores up to `ceil((rows * cols) / 2)` elements. Thus, the space complexity is dominated by the intermediate list.

Trade-offs

Pros

  • Conceptually simple, as it separates the traversal logic from the skipping logic.

Cons

  • Requires significant extra memory to store the intermediate list of all grid elements.

  • Less efficient than a single-pass solution due to iterating over the data twice and higher memory allocation overhead.

Solutions

class Solution {public  List<Integer> zigzagTraversal(int[][] grid) {    boolean ok = true;    List<Integer> ans = new ArrayList<>();    for (int i = 0; i < grid.length; ++i) {      if (i % 2 == 1) {        reverse(grid[i]);      }      for (int x : grid[i]) {        if (ok) {          ans.add(x);        }        ok = !ok;      }    }    return ans;  }private  void reverse(int[] nums) {    for (int i = 0, j = nums.length - 1; i < j; ++i, --j) {      int t = nums[i];      nums[i] = nums[j];      nums[j] = t;    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem