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

Snail Traversal

Number: 2760

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a one-dimensional array of numbers and two integers, rowsCount and colsCount, transform the array into a 2D matrix filled in a snail traversal order. In this traversal, fill the first column from top to bottom with the first set of numbers, then the next column from bottom to top, alternating the direction for each column. If rowsCount * colsCount is not equal to the length of the array, return an empty matrix.

Key Insights

  • Validate input by checking if rowsCount * colsCount equals the length of the input array.
  • Create an empty 2D matrix with the specified number of rows and columns.
  • Use an alternating column fill:
    • For even-indexed columns, traverse from top row to bottom row.
    • For odd-indexed columns, traverse from bottom row to top row.
  • Maintain an index pointer into the original array to fill the matrix sequentially.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the input array. Space Complexity: O(n) for storing the 2D output matrix.

Solution

The solution first checks if the provided dimensions match the length of the input array. Then it initializes an empty matrix. A index pointer is used while iterating over each column. For each column, the algorithm fills it in snail order: top-to-bottom if the column index is even, and bottom-to-top if the column index is odd. This guarantees that the matrix is filled following the snail traversal order according to the given problem statement.

Code Solutions

# Python solution for Snail Traversal problem
def snail(nums, rowsCount, colsCount):
    # Check if dimensions match the length of nums
    if rowsCount * colsCount != len(nums):
        return []
    
    # Initialize empty matrix with rowsCount rows and colsCount columns
    matrix = [[0] * colsCount for _ in range(rowsCount)]
    index = 0  # pointer for nums list

    # Traverse each column accordingly
    for col in range(colsCount):
        if col % 2 == 0:  # Even-indexed column: top to bottom
            for row in range(rowsCount):
                matrix[row][col] = nums[index]
                index += 1
        else:  # Odd-indexed column: bottom to top
            for row in range(rowsCount - 1, -1, -1):
                matrix[row][col] = nums[index]
                index += 1
                
    return matrix

# Example usage:
# print(snail([19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15], 5, 4))
← Back to All Questions