We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Zigzag Grid Traversal With Skip

Number: 3708

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Traverse an m x n grid of positive integers in a zigzag pattern where you alternate between moving right and left on subsequent rows, but only pick every alternate cell from each row (starting with the first cell).

Key Insights

  • Traverse each row in a zigzag manner: for even-indexed rows move left-to-right, for odd-indexed rows move right-to-left.
  • In each row, pick every alternate cell (i.e., take an element then skip the next one).
  • Use simulation to iterate over rows and adjust your traversal order based on the row index.
  • Maintain a result list to accumulate the selected values.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. Space Complexity: O(m * n) in worst-case for the output list, though additional extra space is O(1).

Solution

The solution simulates the traversal by iterating over each row in the grid. For each row, determine the traversal direction:

  • For even-indexed rows, iterate from left-to-right.
  • For odd-indexed rows, iterate from right-to-left. Within each row, select every alternate cell (start from the first cell in the current direction and then skip one element for each subsequent selection). Append the chosen values to the result list and finally return the list.

Code Solutions

# Python solution for Zigzag Grid Traversal With Skip

def zigzagTraversalWithSkip(grid):
    # Initialize an empty list to store the result.
    result = []
    
    # Loop over each row with its index.
    for row_index, row in enumerate(grid):
        # Determine traversal direction based on the row index.
        if row_index % 2 == 0:
            # Even row: traverse from left-to-right.
            # Select every alternate cell starting at index 0.
            for col in range(0, len(row), 2):
                result.append(row[col])
        else:
            # Odd row: traverse from right-to-left.
            # Reverse the row first; select every alternate cell.
            for col in range(len(row) - 1, -1, -2):
                result.append(row[col])
    
    # Return the result list after processing all rows.
    return result

# Example usage:
# grid = [[1,2,3],[4,5,6],[7,8,9]]
# print(zigzagTraversalWithSkip(grid))  # Output: [1,3,5,7,9]
← Back to All Questions