README_EN.md

comments	difficulty	edit_url	tags
true	Easy	https://github.com/doocs/leetcode/edit/main/solution/3400-3499/3417.Zigzag%20Grid%20Traversal%20With%20Skip/README_EN.md	Array Matrix Simulation

3417. Zigzag Grid Traversal With Skip

中文文档

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 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

Solutions

Solution 1: Simulation

We traverse each row. If the current row index is odd, we reverse the elements of that row. Then, we traverse the elements of the row and add them to the answer array according to the rules specified in the problem.

The time complexity is $O(m \times n)$, where $m$ and $n$ are the number of rows and columns of the 2D array $\textit{grid}$, respectively. Ignoring the space consumption of the answer array, the space complexity is $O(1)$.

Python3

class Solution:
    def zigzagTraversal(self, grid: List[List[int]]) -> List[int]:
        ok = True
        ans = []
        for i, row in enumerate(grid):
            if i % 2:
                row.reverse()
            for x in row:
                if ok:
                    ans.append(x)
                ok = not ok
        return ans

Java

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;
        }
    }
}

C++

class Solution {
public:
    vector<int> zigzagTraversal(vector<vector<int>>& grid) {
        vector<int> ans;
        bool ok = true;
        for (int i = 0; i < grid.size(); ++i) {
            if (i % 2 != 0) {
                ranges::reverse(grid[i]);
            }
            for (int x : grid[i]) {
                if (ok) {
                    ans.push_back(x);
                }
                ok = !ok;
            }
        }
        return ans;
    }
};

Go

func zigzagTraversal(grid [][]int) (ans []int) {
	ok := true
	for i, row := range grid {
		if i%2 != 0 {
			slices.Reverse(row)
		}
		for _, x := range row {
			if ok {
				ans = append(ans, x)
			}
			ok = !ok
		}
	}
	return
}

TypeScript

function zigzagTraversal(grid: number[][]): number[] {
    const ans: number[] = [];
    let ok: boolean = true;
    for (let i = 0; i < grid.length; ++i) {
        if (i % 2) {
            grid[i].reverse();
        }
        for (const x of grid[i]) {
            if (ok) {
                ans.push(x);
            }
            ok = !ok;
        }
    }
    return ans;
}