# C code with O(n) complexity

• Since indexRet goes from 0 to len, this code just go through the string once, so its O(n).
the key point is to calculate the jump value

``````jump[2] = {2*(nRow-1-i), 2*i}
``````

besides the first row and last row, any other row goes its index by adding jump[0], jump[1], jump[0]....
and the first and last row go their indexes by adding 2*(nRow-1),2*(nRow-1)....So for the first and last row, the jump[2] becomes

``````jump[2] = { 2*(nRow-1), 2*(nRow-1) };
``````

You can draw a graph and then count the index, its easy to see.

Here is the code:

``````char* convert(char* s, int numRows) {
int len = strlen(s);
int n = numRows;
char *ret = (char*)malloc(len + 1);
int indexRet = 0;
int jump[2];
int i, j, k;

if (n == 1) {
free(ret);
return s;
}
ret[len] = 0;
for (i=0; i < n; i++) {
jump[0] = 2 * (n - 1 - i);
jump[1] = 2 * i;
if (i == 0 || i == n - 1)
jump[1] = jump[0] = 2 * (n - 1);
for (j = i,k=0; j < len; j += jump[k], k = (k + 1) % 2) {
ret[indexRet++] = s[j];
}
}
return ret;
}``````

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