DEV Community

kevin074
kevin074

Posted on

Leetcode diary: 6. Zigzag Conversion [Explanation enhanced]

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

This question is...interesting... It has a 1:2 ratio for likes:dislikes. However it also has a pretty high frequency of being asked in a real interview, mostly from Amazon. So I decided to give this a go even though the question itself is confusing af.

the question is that given a string, we want to rearrange it in a "zig zag" fashion.
ex: PAYPALISHIRING (paypal is hiring), below is the zigzag

P   A   H   N
A P L S I I G
Y   I   R
Enter fullscreen mode Exit fullscreen mode

I started imagining this question as via a 2D array, it's definitely a lot easier seeing the arrangement above as 2D arrays first. So the upper left corner is [0][0], then you move down to [1][0], then [2][0], then to [1][1], then [0][2]. Continue the same until the end.

Honestly this problem probably took longer to understand how the hell it is arranging rather than taking the time to come up with an algorithm for it.

Take you time to understand how the string is rearranged and read below:
.
.
.
.
.
.
.

below is how I came up with a step by step understanding for the algorithm:

what I notice is that 
    1.) start at 0,0, 
    2.) whenever starting at currentRow == 0, we put in one letter into each row
    3.) after that we are at currentRow == numRows-1;
    4.) next we are at numRows-2, because we are moving up;
    5.) we then only put a letter for row == numRows-2, all else is ""
    6.) we then decrement currentRow to 0 and repeat #5 until currentRow == 0 
    7.) we repeat 1 to 6 until all letters are used.

    we can then loop through the matrix and get the concatenated string
    we don't need a 2d array, we can just use array of strings
Enter fullscreen mode Exit fullscreen mode

The above are my notes while solving the problem.

Pseudocode below:
*every time I write "row" it refers to the row in the aforementioned 2D array imagination.

1.) we need a pointer for the currentRow, currentSIndex for string s, and the upwardIndex (upwardIndex explained later);
Also need a matrix of arrays, each index string value represents the entire string for the row.

2.) we then run a master for loop currentSIndex < s.length;

3.) we always start at currentRow = 0, so this means we iterate down the matrix and adding a letter to each row string.
currentSIndex++ at each step while currentRow-- at each.

4.) when we are at currentRow === matrix.length-1, this means we have reached the bottom and going to the upward phase.

5.) At this point, what happens is that:
5.a) upwardIndex = matrix.length-1;
upwardIndex moves from the bottom to the top.
5.b) each time we only add a letter if the upwardIndex == currentRow
5.c) currentRow-- after each upwardIndex loop;
So this means we need a while loop for currentRow > 0, inside is another while loop for the upwardIndex so that we add the letter only when currentRow === upwardIndex.

that's it, when 5 is done currentRow would be 0 so the master while loop would just restart the process until the end.

You also just have to be careful that we terminate any time when currentSIndex reaches s.length;

full code below:

var convert = function(s, numRows) {    
    let currentRow = 0; 
    let currentSIndex = 0;
    let upwardIndex = numRows-1;
    const matrix = new Array(numRows).fill("");

    while (currentSIndex < s.length) {
        while(currentRow < numRows && currentSIndex < s.length) {
            matrix[currentRow++] += s[currentSIndex++]
        }
        currentRow--                    //cause currentRow === numRows at this point;
        if(numRows >= 2) currentRow--;  //All start at numRows-2 except if numRows === 1

        while(currentRow > 0) {
            upwardIndex = numRows-1;
            while(upwardIndex >-1 && currentSIndex < s.length) {
                if(upwardIndex === currentRow) {
                    matrix[upwardIndex] += s[currentSIndex++];
                } 
                upwardIndex--
            }
            currentRow--;
        }
    }

    return matrix.join("")
};
Enter fullscreen mode Exit fullscreen mode

I realized while writing this that upwardIndex is completely unnecessary lol ... but you know... it's probably something you won't realize in the heat of interview. It's a nice follow up that the interviewer might ask you XD

The only special case is row == 1. row ==2 required some thinking to see that it is the same as everything else.

Let me know anything on your mind after reading through this, THANKS!

Discussion (0)