# A Python solution with O(n) complexity

• ``````class Solution:
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
# The best way to understand and formulate the solution is draw a grid and see how it works to fill the grid in a zigzag.
# The complexity of this algorithm is O(n). It captures and traverses each element only once in the string.
if numRows <= 1:
return s
str = ''
i = 0
for i in range(numRows):
if numRows -1 == i: # Here we say if its the last row we know the interval where the pattern will repeat.
m = 2 * i
else:
m = 2*(numRows - (i+1)) # In other case we need to formulate the interval like this as well.
j = i
while j < len(s): # Loop through until the row elements are extracted.
str += s[j]
if i % numRows != 0:
if j+m < len(s):
str += s[j+m] # Locate the next char with the m interval.
j += m + 2 * i # Jump to the next candidate.
else:
j += m # The first and last elements treated differently.
return str
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.