Watch 2 video solutions for Snail Traversal, a medium level problem. This walkthrough by Endeavour Monk has 1,010 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Write code that enhances all arrays such that you can call the snail(rowsCount, colsCount) method that transforms the 1D array into a 2D array organised in the pattern known as snail traversal order. Invalid input values should output an empty array. If rowsCount * colsCount !== nums.length, the input is considered invalid.
Snail traversal order starts at the top left cell with the first value of the current array. It then moves through the entire first column from top to bottom, followed by moving to the next column on the right and traversing it from bottom to top. This pattern continues, alternating the direction of traversal with each column, until the entire current array is covered. For example, when given the input array [19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15] with rowsCount = 5 and colsCount = 4, the desired output matrix is shown below. Note that iterating the matrix following the arrows corresponds to the order of numbers in the original array.
Example 1:
Input: nums = [19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15] rowsCount = 5 colsCount = 4 Output: [ [19,17,16,15], [10,1,14,4], [3,2,12,20], [7,5,18,11], [9,8,6,13] ]
Example 2:
Input: nums = [1,2,3,4] rowsCount = 1 colsCount = 4 Output: [[1, 2, 3, 4]]
Example 3:
Input: nums = [1,3] rowsCount = 2 colsCount = 2 Output: [] Explanation: 2 multiplied by 2 is 4, and the original array [1,3] has a length of 2; therefore, the input is invalid.
Constraints:
0 <= nums.length <= 2501 <= nums[i] <= 10001 <= rowsCount <= 2501 <= colsCount <= 250
Problem Overview: You are given a 1D array and a row count. The task is to convert it into a 2D matrix arranged in a snail traversal pattern: the first column fills from top to bottom, the next column from bottom to top, alternating direction for every column. If the array size cannot perfectly fill the matrix (rowsCount * colsCount != n), return an empty matrix.
Approach 1: Matrix Construction Using Snail Order with Iterative Filling (Time: O(n), Space: O(n))
Create a result matrix with rowsCount rows and colsCount = n / rowsCount columns. Iterate through the input array while tracking the current column index. For even-numbered columns, place values from top to bottom; for odd-numbered columns, place them from bottom to top. The direction flip creates the characteristic snail pattern. This approach relies on straightforward array traversal and explicit matrix construction. Each element is written exactly once, giving linear O(n) time and O(n) space for the output matrix. This is the most intuitive and readable implementation.
Approach 2: Two-Pointer Technique with Precomputed Indices (Time: O(n), Space: O(n))
Instead of switching traversal direction inside the matrix, compute the target row index mathematically. Maintain two pointers representing the top and bottom rows of the current column. For even columns, increment from the top pointer; for odd columns, decrement from the bottom pointer. Alternatively, derive the row using a formula like row = (col % 2 == 0) ? i % rowsCount : rowsCount - 1 - (i % rowsCount). This removes conditional iteration logic and treats placement as index mapping. The method uses ideas similar to two-pointer traversal and deterministic index calculation. Time complexity remains O(n) with O(n) space for the matrix.
Recommended for interviews: The iterative matrix construction approach is what most interviewers expect. It shows you can simulate traversal patterns clearly and handle matrix indexing without mistakes. The index-based two-pointer technique is slightly more mathematical and demonstrates deeper control over index mapping, but the simpler iterative version is usually easier to explain under interview pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Matrix Construction Using Snail Order | O(n) | O(n) | Best general solution. Clear logic and easy to implement in interviews. |
| Two-Pointer Technique with Precomputed Indices | O(n) | O(n) | Useful when you want constant-direction iteration and index math instead of explicit direction switching. |