# A 10-lines one-pass o(n)-time o(1)-space accepted solution with detailed explantation

• The distribution of the elements is period.

``````P   A   H   N
A P L S I I G
Y   I   R
``````

For example, the following has 4 periods(cycles):

``````P   | A   | H   | N
A P | L S | I I | G
Y   | I   | R   |
``````

The size of every period is defined as "cycle"

``````cycle = (2*nRows - 2), except nRows == 1.
``````

In this example, (2*nRows - 2) = 4.

In every period, every row has 2 elements, except the first row and the last row.

Suppose the current row is i, the index of the first element is j:

``````j = i + cycle*k, k = 0, 1, 2, ...
``````

The index of the second element is secondJ:

``````secondJ = (j - i) + cycle - i
``````

(j-i) is the start of current period, (j-i) + cycle is the start of next period.

``````string convert(string s, int nRows) {
if(nRows <= 1) return s;
string result = "";
//the size of a cycle(period)
int cycle = 2 * nRows - 2;
for(int i = 0; i < nRows; ++i)
{
for(int j = i; j < s.length(); j = j + cycle){
result = result + s[j];
int secondJ = (j - i) + cycle - i;
if(i != 0 && i != nRows-1 && secondJ < s.length())
result = result + s[secondJ];
}
}
return result;
}``````

• The following is python version:

`````` def convert(self, s, numRows):
if numRows<=1: return s
cycle, slen, res = numRows*2 - 2, len(s), ""
for i in xrange(numRows):
for j in xrange(i, slen, cycle):
res += s[j]
secondJ = (j - i) + cycle - i
if (secondJ-j) % cycle != 0 and secondJ < slen:
res += s[secondJ]
return res``````

• Nice idea! But I think maybe you can use StringBuffer because String in Java is immutable and it may cost some time for the "+" operation.

• How is it 'O(1) space'? You accumulate the result in a separate string, so it's actually O(len(s)).
It may be possible to devise an in-place algo in the same vein as used for 'rotate array'.

• u are right. But the result is output. Usually the space does't consider the output.

• edit from your code,4ms

``````public String convert(String s, int nRows) {
if(nRows <= 1) return s;
char[]c=s.toCharArray();
char[]result=new char[c.length];
int r=0;
//the size of a cycle(period)
int cycle = 2 * nRows - 2;
for(int j = 0; j < c.length; j = j + cycle){
result[r++]=c[j];
}
for(int i = 1; i < nRows-1; ++i)
{
for(int j = i; j < c.length; j = j + cycle){
result[r++]=c[j];
int secondJ = (j - i) + cycle - i;
if(secondJ < c.length )
result[r++]=c[secondJ];
}
}
for(int j = nRows-1; j < c.length; j = j + cycle){
result[r++]=c[j];
}
return String.valueOf(result);
}
``````

• very clear idea.i like it.

• C Version

``````char* convert(char* s, int numRows) {
int slen = strlen(s) ;

if(numRows <= 1) return s;
if(s == NULL) return s;
if(slen <= 2) return s;
char*ret_s = malloc(slen+1);
int ith_2 = 0;
int ret_idx = 0;
int n = 0;
int items_per_round = numRows*2 -2;
int final_row = numRows - 1;
while(n < numRows) {
for(int ith = n; ith < slen; ith += items_per_round) {
ret_s[ret_idx++] = s[ith];
ith_2 = ith +  items_per_round - (n << 1);
if(ith_2 < slen && n!=0 && n!= final_row) {
ret_s[ret_idx++] = s[ith_2];
}
}
n++;
}
ret_s[ret_idx] = '\0';
return ret_s;
}
``````

• how could it's space complixity be o(1) ? the space you used is according to the string's length

• @yy.zhang it is string ,not String

• Nice idea, I like the cycle concept. Thank you for sharing.

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