# Mathematical solution with complete explanation

• Hello everyone,
Here is a simple mathematical approach.

let's take a look at at the string "0123456789" with 3 rows.
Correct zigzag is thus:

``````0   4   8
1 3 5 7 9
2   6
``````

First, let's take a closer look at the complete columns only:

``````0   4   8
1   5   9
2   6
``````
• notice that the number of indices between two chars in the same row is constant.
• Let's call that constant number of indices spacesBetween and compute it.
• spacesBetween= numRows * 2 - 2.
• So with 3 rows as in this problem:
spacesBetween = 3*2 - 2
spacesBetween = 4
• The character at column X in row Y of zigzag is the character of given string s at index = Y + X*spacesBetween.
• 1st char of 1st row has index in string s = 0 + 0*4 = 0.
• 2nd char of 2nd row has index in string s = 1 + 1*4 = 5.
• 3rd char of 2nd row has index in string s = 1 * 2*4 = 9.

We can now generate the complete columns matrix using the following code

`````` string zigzag;  // used to store result

for (int rowNum = 0; rowNum < numRows; rowNum++){
for (int col = 0; col*spaceBetween + rowNum < s.size(); col++)
zigzag += s[col*spaceBetween + rowNum];

return zigzag;
``````

Now, Let's take a look at the entire zigzag but let's add more rows and a longer string to spot the pattern more clearly:

``````0     6       12
1   5 7    11 13
2 4   8 10    14
3     9       15
``````
• can we find a pattern for the chars that are in incomplete columns?
• First and last row don't have characters in incomplete columns.
• First, observe that there is max one character between two characters in complete columns.
• Then, notice that the 5 on row 1 is 1 less than 6 and the 11 on row 1 is 1 less than 12.
• similarly, the 4 on row 2 is 2 less than 6 and the 10 on row 2 is 2 less than 12.
• It appears we have identified a pattern!

Finally, let's put it all together !

``````    string convert(string s, int numRows) {

if (numRows == 1)
return s;  // simple base case!

// now calculat spacesBetween
int spacesBetween = 2*numRows - 2;

// used to store response
string zigzag;

for (int rowNum = 0; rowNum < numRows; rowNum++){
for (int col = 0; col * spacesBetween + rowNum < s.size(); col++){

// add char from complete column
zigzag += s[col*spacesBetween + rowNum];

// first and last row don't have chars in incomplete columns so we continue
if (rowNum == 0 || rowNum == numRows - 1)
continue;

// calculate index of character from incomplete column by finding the index of the first char of the next
// complete column and subtracting the rowNum from it, as dictated by the pattern we observed earlier.
int incompleteColumnCharIndex = (col + 1)*spacesBetween - rowNum;

// check that the index is a valid index in s. not too small not too large!
if(incompleteColumnCharIndex > 0 && incompleteColumnCharIndex < s.size())
zigzag += s[incompleteColumnCharIndex];

}

}
return zigzag;
}
``````

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