Sponsored
Sponsored
This approach involves directly filling a 2D array using the input array nums by iterating over the columns in tandem with rows, alternating between top-down and bottom-up directions for each new column.
The key idea is to iterate over the given nums array, and fill the current column based on whether its index is even or odd. For even indices we fill from the top row to the bottom row; for odd indices, from the bottom row to the top row.
The algorithm involves:
Time Complexity: O(ROWS * COLS) as each element must be traversed once.
Space Complexity: O(ROWS * COLS) for storing the result matrix.
The C solution first checks if product of rows and columns equals the size of the nums array. It initializes a dynamic 2D array to store the resulting matrix. Using a loop, it fills each column in either top-to-bottom or bottom-to-top order depending on the current column index, incrementing through the nums array sequentially.
This second approach draws on precomputing indices for traversing the nums array according to snail traversal rules using a two-pointer technique. Here, two pointers always mark top and bottom traversals of a given column.
In this strategy:
Time Complexity: O(ROWS * COLS)
Space Complexity: O(ROWS * COLS) due to resulting vector matrix.
1#include <vector>
2using namespace std;
3class Solution {
4public:
5 vector<vector<int>> snail(vector<int>& nums, int rowsCount, int colsCount) {
6 if (rowsCount * colsCount != nums.size()) return {};
7 vector<vector<int>> result(rowsCount, vector<int>(colsCount));
8 int idx = 0;
9 for (int c = 0; c < colsCount; ++c) {
10 if (c % 2 == 0) {
11 int top = 0;
12 while (top < rowsCount) {
13 result[top++][c] = nums[idx++];
14 }
15 } else {
16 int bot = rowsCount - 1;
17 while (bot >= 0) {
18 result[bot--][c] = nums[idx++];
19 }
20 }
21 }
22 return result;
23 }
24};
25The C++ solution uses vectors to dynamically allocate and manage the rows of matrices. With two pointers, iterating up or down depending on even or odd column indices results in efficient walking through each column without extra list operations.