## Solution

#### Approach 1: Sort by Row

**Intuition**

By iterating through the string from left to right, we can easily determine which row in the Zig-Zag pattern that a character belongs to.

**Algorithm**

We can use lists to represent the non-empty rows of the Zig-Zag Pattern.

Iterate through from left to right, appending each character to the appropriate row. The appropriate row can be tracked using two variables: the current row and the current direction.

The current direction changes only when we moved up to the topmost row or moved down to the bottommost row.

**Complexity Analysis**

- Time Complexity: , where
- Space Complexity:

#### Approach 2: Visit by Row

**Intuition**

Visit the characters in the same order as reading the Zig-Zag pattern line by line.

**Algorithm**

Visit all characters in row 0 first, then row 1, then row 2, and so on...

For all whole numbers ,

- Characters in row are located at indexes
- Characters in row are located at indexes
- Characters in inner row are located at indexes and .

**Complexity Analysis**

- Time Complexity: , where . Each index is visited once.
- Space Complexity: . For the cpp implementation, if return string is not considered extra space.