This problem was really frustrating!!! The problem statement is deceptively simple!

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”.

The problem didn’t explain itself clearly. At first I thought the format was:
X X X X
X X X X X X
…
where the first row has one letter with three spaces in between, and the second row has one letter with one space in between.

Following this logic, I assumed odd rows had X letters and even rows had 2X-1 letters. I wrote the code based on this idea and submitted it confidently:
142 / 1158 test cases passed.
Passed 142 test cases… then it said ABCD 2 was WA?

I was completely confused. Finally, with no other options, I looked up how others interpreted the problem.
Turns out it means:
1 7
2 6 8
3 5 9
4
It should form a zigzag pattern… then output row by row… sigh.

So I started working on it, using a 2D array to store the values, changing direction, and filling empty spots with spaces… Got all kinds of RE on small test cases??? That didn’t make sense. Then I realized it might be RE on large data but just happened to be running on small data first.

Eventually I tried expanding the 2D array to 10000x10000 and it blew up with memory issues.

What to do? I almost gave up on this problem.

It all came down to my own inexperience. Later I thought of two approaches: either use a mathematical method to calculate the output order, or compress the space. I chose the latter – instead of storing a 2D map array, I stored each letter’s x, y coordinates and value, which greatly reduced the space usage.

Accepted on the first try after that!

Notes:

1. Need to handle the special case of a single row.
2. I was lazy and used the standard library’s sort.

Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include <algorithm>

using namespace std;

struct Node {
    int x;
    int y;
    char val;
}p[10000];

int cmp(Node a,Node b) {
    if(a.x == b.x) {
        return a.y < b.y;
    } else {
        return a.x < b.x;
    }
}

class Solution {
public:
    string convert(string s, int nRows) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int x = 0;
        int y = 0;
        int direction = 0;
        if(nRows == 1) return s;
        for(int i = 0; i < s.length(); i++) {
            p[i].x = x;
            p[i].y = y;
            p[i].val = s[i];
            if(direction == 0) {
                x++;
                if(x >= nRows) {
                    x--;
                    direction = 1;
                    x--;
                    y++;
                }
            } else {
                x--;
                y++;
                if(x < 0) {
                    x++;
                    y--;
                    direction = 0;
                    x++;
                }
            }
        }
        sort(p, p + s.length(), cmp);
        for(int i = 0; i < s.length(); i++) {
            s[i] = p[i].val;
        }
        return s;
    }
};