Leetcode: ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Understand the problem:
The crux of the problem is to understand what is the "zigzag" format. We can use examples to illustrate this. For number of rows is 2, 

0    A    C 
1    B    D

For nRows = 3,
0  A       E
1  B  D  F
2  C      G

For nRows = 4
0  A          G
1  B      F  H
2  C  E      I
3  D          M

It is actually easier to understand the problem putting the characters into a mesh grid.

Solution:
We can divide the zigzag format into several zigzags. For nRows = 4, 
1         | 7              |
2      6 | 8         12 |
3  5     | 9    11      |
4         | 10            |

So each zigzag has number of nRows * 2 - 2 elements. 

For each zigzag, the first row and last row, the distance between two indices is nRow * 2 - 2. For example, distance between 1 and 7 is 6, distance between 4 and 10 is 6, which  can be calculated as 4 * 2 - 2 = 6. 

For each other rows from 1 to nRows - 2, the distance between two indices is (nRows - i - 1 ) * 2 = nRows * 2 - 2 - 2 * i. Note that the distance between A to B is defined as [A, B). Also note that for each zigzag, there are at most two elements in a row. 

Based on the analysis above, we can come up the solution below:

Code (Java):

public class Solution {
    public String convert(String s, int nRows) {
        if (s == null || s.length() == 0 || nRows <= 0)
            return "";
        if (nRows == 1) return s;
        
        StringBuilder sb = new StringBuilder(); //non-thread safe
        int size = 2 * nRows - 2; // number of elements for each zigzag
        
        for (int i = 0; i < nRows; i++) {
            for (int j = i; j < s.length(); j += size) {
                sb.append(s.charAt(j));
                
                if (i != 0 && i != nRows - 1 && (j + size - 2 * i) < s.length()) {
                    sb.append(s.charAt(j + size - 2 * i));
                }
            }
        }
        return sb.toString();
    }
}

Discussion:
The time complexity is O(n) since we only traverse the string once. The space complexity is O(n) as well since we performed out-of-place transform.

Summary:
The crux of this problem is to convert the indices from zigzag-major to row-major. Be familiar with the zigzag-major format.