Approach #1: Simulation [Accepted]
Intuition
We translate to code the steps a human would take to create the string.
Algorithm
For each letter in the string, we place that letter in the correct row cur_row
, then move our pointer to the next correct row. We will need to know not only the location of our pointer, but it's current direction cur_direction
: 1
for down and 1
for up.
Care must also be taken in the case that numRows
is 1
.
Python
class Solution(object):
def convert(self, S, numRows):
rows = [[] for _ in range(numRows)]
cur_row = 0
cur_direction = 1
for char in S:
rows[cur_row].append(char)
cur_row += cur_direction
if cur_row == numRows:
cur_row = max(numRows  2, 0)
cur_direction *= 1
elif cur_row == 1:
cur_row = min(numRows  1, 1)
cur_direction *= 1
return "".join("".join(row) for row in rows)
Complexity Analysis

Time Complexity: $$O(N)$$, where $$N$$ is the length of the string. We loop through every character in the string and do constant work inside the loop.

Space Complexity: $$O(N)$$ to hold the answer, which has size proportional to the initial string.
Approach #2: Index Generator [Accepted]
Intuition
Because knowing what row the next letter goes in is tricky, we write a helper generator that returns these indices.
Algorithm
We proceed as before: we will loop through the string and place the characters in rows. The index that we place it will be given by a generator.
The generator is straightforward: if there are N
rows, we go from 0
to N1
, then from N2
to 1
, then start over.
Python
class Solution(object):
def convert(self, S, numRows):
rows = [[] for _ in range(numRows)]
def staircase_indexes(N):
while True:
for i in range(N):
yield i
for i in range(N2, 0, 1):
yield i
gen_index = staircase_indexes(numRows)
for c in S:
rows[next(gen_index)].append(c)
return "".join("".join(row) for row in rows)
Complexity Analysis
 $$O(n)$$ time and space complexity. The analysis is the same as in Approach #1.
Approach #3: Mathematical [Accepted]
Intuition
For each row, let's try to know mathematically which string indices are going to be taken.
Algorithm
Say there are N
rows. When N > 1
, there are 2N2
indices in the loop: 0, 1, ..., N2, N1, N2, ..., 1
before the pattern of row indices repeats again. In the first and last row, we have string indices (zeroindexed) $$0 \mod 2N2$$ and $$N1 \mod 2N2$$. In other rows $$i$$, we have string indices $$i$$ and $$2N2i$$.
Python
class Solution(object):
def convert(self, S, N):
if N == 1:
return S
ans = []
for row in range(N):
if row == 0 or row == N1:
ans.append(S[row::2*N2])
else:
for i in range(0, len(S), 2*N2):
for j in (i + row, i + 2*N2row):
if j < len(S):
ans.append(S[j])
return "".join(ans)
Complexity Analysis
 $$O(n)$$ time and space complexity. The analysis is the same as in Approach #1.