3417. Zigzag Grid Traversal With Skip LeetCode Solution

In this guide, you will get 3417. Zigzag Grid Traversal With Skip LeetCode Solution with the best time and space complexity. The solution to Zigzag Grid Traversal With Skip problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Zigzag Grid Traversal With Skip solution in C++
  4. Zigzag Grid Traversal With Skip solution in Java
  5. Zigzag Grid Traversal With Skip solution in Python
  6. Additional Resources
3417. Zigzag Grid Traversal With Skip LeetCode Solution image

Problem Statement of 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.

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:

See also  830. Positions of Large Groups LeetCode Solution

Constraints:

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

Complexity Analysis

  • Time Complexity: O(mn)
  • Space Complexity: O(mn)

3417. Zigzag Grid Traversal With Skip LeetCode Solution in C++

class Solution {
 public:
  vector<int> zigzagTraversal(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector<int> ans;
    vector<int> zigzag;

    for (int i = 0; i < m; ++i)
      if (i % 2 == 0) {
        for (int j = 0; j < n; ++j)
          zigzag.push_back(grid[i][j]);
      } else {
        for (int j = n - 1; j >= 0; --j)
          zigzag.push_back(grid[i][j]);
      }

    for (int i = 0; i < zigzag.size(); i += 2)
      ans.push_back(zigzag[i]);

    return ans;
  }
};
/* code provided by PROGIEZ */

3417. Zigzag Grid Traversal With Skip LeetCode Solution in Java

class Solution {
  public List<Integer> zigzagTraversal(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    List<Integer> ans = new ArrayList<>();
    List<Integer> zigzag = new ArrayList<>();

    for (int i = 0; i < m; ++i)
      if (i % 2 == 0) {
        for (int j = 0; j < n; ++j)
          zigzag.add(grid[i][j]);
      } else {
        for (int j = n - 1; j >= 0; --j)
          zigzag.add(grid[i][j]);
      }

    for (int i = 0; i < zigzag.size(); i += 2)
      ans.add(zigzag.get(i));

    return ans;
  }
}
// code provided by PROGIEZ

3417. Zigzag Grid Traversal With Skip LeetCode Solution in Python

class Solution:
  def zigzagTraversal(self, grid: list[list[int]]) -> list[int]:
    zigzag = [row[::-1] if i % 2 else row for i, row in enumerate(grid)]
    return [num for row in zigzag for num in row][::2]
# code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.