Zigzag grid traversal with skip

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

Constraints:

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

Approach: Traversal With Skip

func zigzagTraversal(grid [][]int) []int {
	ans := []int{}
	for i, nums := range grid {
		if (i % 2) == 0 {
			for j, num := range nums {
				if ((i + j) % 2) == 0 {
					ans = append(ans, num)
				}
            }
		} else {
            for j := len(nums) - 1; j >= 0; j-- {
				if ((i + j) % 2) == 0 {
					ans = append(ans, nums[j])
				}
			}
        }
	}
	return ans
}

Time Complexity O(n*m)

Space Complexity O(1)

Intuition

The idea is to traverse the grid row by row in a zigzag manner. For even-indexed rows, we move left-to-right; for odd-indexed rows, we traverse right-to-left. Additionally, we only collect numbers from positions where the sum of the row and column indices is even.

Algorithm

Traverse Rows: Loop over each row in the grid using its index i.
Determine Traversal Order:
- If i is even, iterate through the row from the beginning (left-to-right).
- If i is odd, iterate in reverse (right-to-left).
Skip Based on Condition: For each element, check if (i + j) % 2 == 0 (where j is the column index). Only if the condition holds, append the element to the answer list.
Return Result: After processing all rows, return the list of collected elements.

Complexity Analysis

Time Complexity:
O(n * m)
Each element in the grid (with n rows and m columns) is processed exactly once.
Space Complexity:
O(n * m) (in the worst-case scenario)
The output list may store almost all the elements of the grid if the condition (i + j) % 2 == 0 holds for many elements.
Apart from the output, the extra space usage is constant.

Wrap up

If you found this guide helpful, consider subscribing to my newsletter on jyotirmoy.dev/blogs , You can also follow me on Twitter jyotirmoydotdev for updates and more content.