# My Java answer with O(1) space, O(n) time with explanation.

• The basic view of this problem is we jump several steps in original to get the character in sequence.

The gap for first and last row is easy: 2k-2. But for rows between:

row 1: gap1: 2k - 2 - 2, gap2: 2

row 2: gap1: 2k - 2 - 4, gap2: 4

....

So there is a pattern for the jump gaps:
gap1: 2*(k - 1 - i)
gap2: 2 * i

Then we could just make sure for each row, we jump the gap1, gap2, gap1, gap2 ... etc to get next character. Be careful with the gap is 0. So we keep tracking of last position and make sure we move forward.

``````public String convert(String s, int nRows) {
//Special case
if (nRows >= s.length() || nRows == 1) {
return s;
}

StringBuffer sb = new StringBuffer();

for (int i = 0; i < nRows; i++) {
//Two gaps for the next character
int gap1 = 2 * (nRows - 1 - i);
int gap2 = 2 * i;

int j = i;
//Record the previous char position in original string
int prevPos = 0;

// Init buffer
sb.append(s.charAt(j));

while (j < s.length()) {
prevPos = j;
j += gap1;
//gap1 is 0 when it is last row, do not add it twice
if (j != prevPos && j < s.length()) {
sb.append(s.charAt(j));
}
prevPos = j;
j += gap2;
//gap2 is 0 when it is first row, do not add it twice
if (j != prevPos && j < s.length()) {
sb.append(s.charAt(j));
}
}
}

return sb.toString();
}``````

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