# O(N) python solution in 8 lines

• Short solution but requires a lot of math. If the zigzag has period T, then every index in row r is equal to either r or -r (mod T). For example:

``````0     6     12  # 0 (mod 6)
1   5 7   11   # 1 or -1 (mod 6)
2 4   8 10    # 2 or -2 (mod 6)
3     9      # 3 (= -3) (mod 6)
``````

The indices in a given row also alternate between r and -r (mod T). To get from index i to the next index in the row, we can add an amount q which satisfies i + q = -i (mod T) and 0 < q <= T. With a bit of massaging we get q = T - (2*i % T). Once we get this the code is real simple.

``````class Solution(object):
def convert(self, s, numRows):
ret = ''
T = max((numRows - 1)*2, 1) # period of one zigzag
for r in range(numRows):
i = r
while i < len(s):
ret += s[i]
# increase by an amount q that satisfies
#  i + q = -i (mod T)  and  0 < q <= T
i += T - (2*i % T)
return ret
``````

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