Leetcode diary: 6. Zigzag Conversion

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 i…


This content originally appeared on DEV Community and was authored by kevin074

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. What this means is that you read from up to down, then you read upwards until at the top again.
ex: PAYPALISHIRING (paypal is hiring), below is the zigzag

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

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:
.
.
.
.
.
.
.
I started imagining this question as via a 2D array, it's definitely a lot easier seeing the arrangement above as 2D arrays first.

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

what I notice is that 
    1.) start at 0, 
    2.) whenever starting at 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;
    5.) we then only put a letter for row == numRows-2, all else is ""
    6.) we then decrement currentRow 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

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("")
};

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!


This content originally appeared on DEV Community and was authored by kevin074


Print Share Comment Cite Upload Translate Updates
APA

kevin074 | Sciencx (2022-02-19T08:55:29+00:00) Leetcode diary: 6. Zigzag Conversion. Retrieved from https://www.scien.cx/2022/02/19/leetcode-diary-6-zigzag-conversion/

MLA
" » Leetcode diary: 6. Zigzag Conversion." kevin074 | Sciencx - Saturday February 19, 2022, https://www.scien.cx/2022/02/19/leetcode-diary-6-zigzag-conversion/
HARVARD
kevin074 | Sciencx Saturday February 19, 2022 » Leetcode diary: 6. Zigzag Conversion., viewed ,<https://www.scien.cx/2022/02/19/leetcode-diary-6-zigzag-conversion/>
VANCOUVER
kevin074 | Sciencx - » Leetcode diary: 6. Zigzag Conversion. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2022/02/19/leetcode-diary-6-zigzag-conversion/
CHICAGO
" » Leetcode diary: 6. Zigzag Conversion." kevin074 | Sciencx - Accessed . https://www.scien.cx/2022/02/19/leetcode-diary-6-zigzag-conversion/
IEEE
" » Leetcode diary: 6. Zigzag Conversion." kevin074 | Sciencx [Online]. Available: https://www.scien.cx/2022/02/19/leetcode-diary-6-zigzag-conversion/. [Accessed: ]
rf:citation
» Leetcode diary: 6. Zigzag Conversion | kevin074 | Sciencx | https://www.scien.cx/2022/02/19/leetcode-diary-6-zigzag-conversion/ |

Please log in to upload a file.




There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.