Zigzag Grid Traversal With Skip - Practice Coding Problems

Zigzag Grid Traversal With Skip - Problem

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

Input & Output

Example 1 — Basic 2x3 Grid

$ Input: grid = [[1,2,3],[4,5,6]]

› Output: [1,3,5]

💡 Note: Zigzag traversal: 1→2→3, then 6→5→4. With skipping: take positions 0,2,4 which are values 1,3,5

Example 2 — Single Row

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

› Output: [1,3]

💡 Note: Only one row, traverse left to right: 1→2→3→4. Skip alternates: take positions 0,2 which are 1,3

Example 3 — Single Column

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

› Output: [1,3]

💡 Note: Zigzag on single column: 1 (pos 0), 2 (pos 1), 3 (pos 2). Take even positions: 1,3

Constraints

1 ≤ m, n ≤ 100
1 ≤ grid[i][j] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D grid with positive integers

Zigzag + Skip

Traverse in zigzag pattern, skip every alternate cell

Result Array

Values from non-skipped cells in traversal order

Key Takeaway

🎯 Key Insight: Use position counter during zigzag traversal to directly identify cells to include

Asked in

M Microsoft 25 a Amazon 20 G Google 15

The key insight is to use a position counter during zigzag traversal to determine which cells to include. Best approach is direct skip during traversal with Time: O(m×n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Full Traversal then Filter	O(m×n)	O(m×n)	First collect all cells in zigzag order, then filter alternates
Direct Skip During Traversal	O(m×n)	O(1)	Skip cells directly during zigzag traversal using position counter

Brute Force - Full Traversal then Filter — Algorithm Steps

Step 1: Traverse grid in zigzag pattern collecting all values
Step 2: Create result array with values at even positions only

Visualization

Tap to expand

Step-by-Step Walkthrough

Zigzag Collection

Traverse grid collecting all values in zigzag order

Filter Alternates

Keep only values at even positions (0, 2, 4, ...)

Result

Final array with skipped values

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int** grid, int gridSize, int* gridColSize, int* returnSize) {
    if (gridSize == 0 || gridColSize[0] == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    int m = gridSize, n = gridColSize[0];
    int* allValues = (int*)malloc(m * n * sizeof(int));
    int allCount = 0;
    
    // Collect all values in zigzag order
    for (int i = 0; i < m; i++) {
        if (i % 2 == 0) { // Even row: left to right
            for (int j = 0; j < n; j++) {
                allValues[allCount++] = grid[i][j];
            }
        } else { // Odd row: right to left
            for (int j = n - 1; j >= 0; j--) {
                allValues[allCount++] = grid[i][j];
            }
        }
    }
    
    // Filter alternate positions
    int* result = (int*)malloc((allCount + 1) / 2 * sizeof(int));
    int resultCount = 0;
    for (int i = 0; i < allCount; i += 2) {
        result[resultCount++] = allValues[i];
    }
    
    free(allValues);
    *returnSize = resultCount;
    return result;
}

int main() {
    // Simple parsing for small test cases
    int grid[10][10] = {{1,2,3},{4,5,6}};
    int* gridRows[10];
    int colSizes[10] = {3, 3};
    gridRows[0] = grid[0];
    gridRows[1] = grid[1];
    
    int returnSize;
    int* result = solution(gridRows, 2, colSizes, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Single pass through all m×n cells to collect values, then O(m×n) to filter

✓ Linear Growth

Space Complexity

O(m×n)

Stores all m×n values in intermediate array before filtering

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Full Traversal then Filter — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler