Snail Traversal LeetCode

The Snail Traversal LeetCode problem, a fascinating challenge encountered in coding assessments and LeetCode, asks us to transform a 1D array into a 2D array following a distinct traversal pattern. This pattern, known as snail traversal order, involves navigating through rows and columns alternately, simulating the movement of a snail climbing a pole. For instance, given a specific array, the resulting matrix is organized to follow the traversal path corresponding to the order of elements in the original array.

Problem statement

Given a one-dimensional array of numbers, the task is to write a function that organizes this array into a two-dimensional matrix using a snail traversal order pattern. This pattern mimics the movement of a snail by traversing the matrix from the top-left cell, starting with the first value of the input array. After that, it moves through the entire first column from top to bottom. Then, it transitions to the next column on the right, traversing it from bottom to top. This alternating direction continues column by column until the entire input array is traversed.

The input is considered invalid if rowsCount * colsCount !== nums.length. In such cases, the output should be an empty array.

For example, given the input array [19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14] with rowsCount = 4 and colsCount = 3, the desired output matrix is shown below.

Note: Iterating the matrix following the arrows corresponds to the order of numbers in the original array.

What is the output if the following are given as input?

Input array = [9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15, 19, 10, 3, 7]

rowsCount = 5

colsCount = 4

[
[9, 18, 6,  7],
[8, 12, 13, 3],
[5, 14, 11, 10],
[2, 16, 20, 19],
[1, 17, 4,  15]
]

[
[9, 17, 6,  15],
[8, 16, 13, 19],
[5, 14, 11, 10],
[2, 12, 20, 3],
[1, 18, 4,  7]
]

[
 [9,  8,  5,  2],
 [1, 17, 16, 14],
 [12, 18,  6, 13],
 [11, 20,  4, 15],
 [19, 10,  3,  7]
]

Question 1 of 30 attempted

Algorithm

To convert a 1D array into a 2D array using a snail traversal pattern, we will iterate through the input array while determining the position of each element in the 2D array.

To do this efficiently, we check the position of each element based on its index and the desired shape of the 2D array. For this, we move in a horizontal line from left to right, then vertically from top to bottom, then in a horizontal line from right to left, and so on in a zig-zag pattern.

Here’s how the algorithm works:

Check if the product of rows and columns in the input array is equal to the length of the array. Return an empty array if the desired 2D array cannot be constructed with the input data.
Initialize a 2D array with zeros.
Start iterating through the elements of an input array.
In each iteration:
1. Calculate the row and column index for the current element.
2. Depending on the current row, determine the direction of the traversal (normal or reversed).
3. Place the current element in the corresponding position in the 2D array.
4. If the end of the current row is reached, switch the direction of the traversal.

Let's look at the illustration below to better understand the algorithm.

def snail(arr, rowsCount, colsCount):
    if rowsCount * colsCount != len(arr):
        return []  
    res = [[0] * colsCount for _ in range(rowsCount)]
    isReversed = False  
    for i in range(len(arr)):
        row = i % rowsCount if not isReversed else rowsCount - 1 - (i % rowsCount)
        col = i // rowsCount
        res[row][col] = arr[i]
        if (i % rowsCount) == rowsCount - 1:
            isReversed = not isReversed
    return res
# Example usage:
inputArray = [9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15, 19, 10, 3, 7]
rows = 5
cols = 4
result = snail(inputArray, rows, cols)
for row in result:
    print(row)

Code explanation

Line 1: Define a function called snail, which takes three parameters: arr, rowsCount, and colsCount
Lines 2–3: It checks whether the input values are valid by taking the product of rowsCount, and colsCount. If the product isn't equal to the length of an array, then an empty array [] is returned.
Lines 5–6: In these lines, we declare the variables to be used in the solution.
- First, we initialize the result 2D array (res) with zeros.
- Next, we initialize a boolean variable isReversed to False. This variable will be used to track the direction of traversal (normal or reversed) as we iterate through the input array.
Lines 8–11: In this loop, we iterate over each input array element and calculate their corresponding row and column indices in the result 2D array, res.
- The row index is determined based on whether the traversal direction is normal or reversed. If isReversed is False, we calculate the row index normally using the modulo operator %. Otherwise, we calculate the row index in reverse order.
- The col index is calculated based on the current index, i and the number of rows, rowsCount.
- Lastly, the current element of the input array, arr[i], is placed in the correct position in the result array at res[row][col].
Lines 13–14: We check if the end of the current row is reached. If so, we toggle the isReversed value, switching the traversal direction for the next row.

Time complexity

Initializing the result 2D array, res requires $O(m * n)$ time, where m is the number of rows and $n$ is the number of columns. Then, we iterate through each element of the input array once, so the time complexity for this traversal is $O(n)$ , where $n$ is the length of the input array. All operations inside the loop take constant time.

Overall, the time complexity of the snail() is $O(m * n + n)$ , which simplifies to $O(m * n)$ .

Space complexity

The space complexity of the snail() is $O(m * n)$ , where $m$ is the number of rows and $n$ is the number of columns in the resulting 2D array.

Free Resources