# Should be straightforward O(N) solution in C++

• ``````class Solution {
public:
string convert(string s, int nRows) {
if(s.length() == 0 ||
s.length()/nRows < 1 ||
nRows == 1)
{
return s;
}
int distance = 2*(nRows-1);
string result;
int offset = 0;
for (int row = 0; row < nRows; row++)
{
for (int index = row; index < s.length(); index += distance)
{
result+=s[index];
if (offset != 0 && index + distance - offset < s.length())
{
result+=s[index + distance - offset];
}
}
offset += 2;
offset = offset % distance;
}
return result;
}
};
``````

The idea is, the first row and last row has no offset. Each element has a fixed difference of 2(nRows-1);
For the rows in between, there is a incremental offset of 2;

``````0       6       12    -> distance = 2(nRows-1) = 6 offset = 0
1    5  7     11        -> offset =  distance - 2 = 4
2  4    8  10            -> offset = distance -2 -2 = 2
3       9                  -> distance = 2(nRows-1) = 6 offset = 0
``````

Easy to observe. There is a catch, that you need to add the offset element with previous regular element.
5 follows 1, 4 follows 2. Otherwise, you will miss the tail if there is no vertical column in the end.Looks like a CS homework:)

• int length = s.length();
if( length <= nRows)
{
return s;
}
if(nRows == 1)
{
return s;
}

``````char * newstring = new (nothrow) char[length+1];
if( !newstring)
{
cout<<"error on allocate memory for new string"<<endl;
}
newstring[length] = 0;
int newpos = 0;
for( int i = 0; i < nRows; i++)
{
int col = 0;
int pos = 0;
while((pos = i + ((nRows-2)*2+2)*col) < length)
{
if( i > 0 && i < nRows -1 )
{
newstring[newpos++] = s[pos];
if( pos + 2*(nRows-i-1) < length)
newstring[newpos++] = s[pos+2*(nRows-i-1)];
}
else
{
newstring[newpos++] = s[pos];
}

col++;
}
}
return string(newstring);``````

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