O(n) clean java solution with explaination

  • 12

    The solution computes the next element in each row one by one. Take 4 rows for example. In the first row, the gap between each "column" element is (4-1)*2 = 6. In the second row, there is another element between each pair of "column" elements and it separate the gap to two parts. A variable offset is used to track the position of the separator.

    In the second row, initially offset equals gap - row_index2 = 6-12 = 4. The first element in the second row is s[1], the second one is s[1+offset] = s[5]. Then offset becomes gap-offset = 6-4 = 2. So the third element is s[5+offset] = s[7]. In fact, the offset for the next element is always equal to the gap - offset of the previous element.

    Using the method we could get the elements of each row. Be careful that in the first and the last row, there is no element between the "column" elements so we need to avoid inserting duplicate elements (when offset is 0).

    public String convert(String s, int numRows) {
        if(numRows == 1) return s;
        int gap = (numRows-1)<<1;
        StringBuilder result = new StringBuilder();
        for(int i=0; i<numRows; i++) {
            int current = i;
            int offset = gap - (i<<1);
            while(current<s.length()) {
                if( offset != 0 ) { 
                    // avoid inserting duplicate elements
                    // in the first and the last row
                    current += offset;
                offset = gap-offset;
        return result.toString();

Log in to reply

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