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.