LeetCode #6 ZigZag Conversion

Behold the coveted hipster-cigarette-papers. 😎

Introduction

Hey reader, having trouble solving this leet code problem? Perhaps the whole thing is too darn intimidating? Or maybe you would like another solution for a quick reference. No worries, you came to the right place. Let’s dive into this medium-level problem using Javascript.

Prompt

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 s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
Output: "A"

Thoughts

This problem reads pretty easy. Nothing is too “mathy” or wordy, which can be nice. Sometimes some words sound weird, like ‘fixed font,’ but if you keep reading and look at the provided examples, it becomes clear. I like to read the Prompt and examples over a few times, and it’s worth taking the time to understand what the author is asking fully.

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)

The first bit seems pretty straightforward. We are given a string, which is written as a zigzag pattern.

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

This would be that pattern. Notice any patterns here? 3, 1,3,1,3,1,2. Hold on a minute…

length of 3 characters...
P   
A 
Y
also a length of 3 characters...
  
  A 
 P 
Y
Ahhh.... I see...
P   A
A P 
Y
...zigzag pattern...
P   A   H   N
A P L S I I G
Y   I   R
... got it !!!

Aside from that last two characters, it looks like a “zig-zag” pattern has a length of 3(either diagonally or vertically). It looks like we got a count of 2 at the end. Perhaps it’s cause we don’t have enough characters to fill in a row of 3. Let’s keep reading for more clues.

And then read line by line: "PAHNAPLSIIGYIR"

Interestingly, we are reading left to right and top to bottom, yet we wrote the string in a particular pattern (zigzag pattern in rows of 3).

Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);

The last bit here seems pretty reasonable to me. The author is saying we are given an input of a string and the size of each row.

Hold on… Let’s take a peek at those examples…

Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Cool, pretty much the same thing we broke down.

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

If we increase each row’s size in our zig-zag pattern, it should look like this. Cool, that checks out!

Input: s = "A", numRows = 1
Output: "A"

It looks like this one is a base case. If we are given a string with a single character, return the input string as-is!

Recap

• Input: A string
• Input: The size of the rows in each zig or zag pattern
• Output: A String, which is the Input string in a zig-zag pattern. We read this pattern from left to right and top to bottom.
• Base Case: return the string if it has a single character

ooooooooo…. so pretty🤩 😍 🤩

The Build Out

Right out the gate, let’s take care of that base case. I will use a conditional statement and check two things. We will also use an ‘or’ operator because we want to return the string if either of these cases happens.

The first is how long the string is, which should be the length of 0 or 1.

The second being something that takes a bit more thought. What happens if the string is the same size as the numRows value or the first zig. Wouldn’t it just be a line? If that’s the case, could we not just return the line? Since we are reading left to right and top to bottom… yeah! We would read that line. So let’s return it.

const convert = function(s, numRows) {
if(numRows <= 1 || s.length <= numRows) return s;
    
};

Okay, here is where we get a bit meta. Declaring variables, you should only declare what you need. Yet you’ll often make too little or too much… Catch 22. So start with what you know for sure you’ll need.

Now what? How about we look at this pattern again.

Let’s see if we can grab any ideas off of its structure …

How do I build this... 
then read it in a different way...
P   A   H   N
A P L S I I G
Y   I   R
what about some arrays...
[P   A   H   N]
[A P L S I I G]
[Y   I   R]
What if I nested them... like a grid or matrix...
[
 [P,A,H,N],
 [A,P,L,S,I,I,G],
 [Y,I,R]
]
... we can build one way, and read another way.

So how do we fill out this grid/matrix? I will have to build it, fill it in a zig-zag pattern, then read it differently. It looks like we will need an empty array, which we can build with our numRows input and for-loop.

if(numRows <= 1 || s.length <= numRows) return s;
    
    let rows = []; <-- empty array
for (let i = 0; i < numRows; i++) { <-- for loop + numRows
rows[i] = []; <-- Build grid/matrix with empty arrays
    }    
};

Next, we need to think about how we will fill this matrix. How will we get the zig-zag pattern to line up with our empty matrix? Let’s say we used a for loop, and we could iterate over the input string…

for (let i = 0; i < s.length; i++) { <-- for loop + input string
}

What if we used the numRow Input length to determine when and where we add/insert values into the array? We could use another for loop, but that won’t insert values in our desired zig-zag pattern. It’s also a little clunky. What if we try to use a counter instead. It’s cheaper for the run-time, and we can tinker a bit more with this idea.

Using bracket notation, we can access the nested array in our rows variable. If we place that inside our second loop, we can insert values into this structure.

let rows = [];
    let counter = 0; <--- counter 
 
    
    for (let i = 0; i < numRows; i++) {
        rows[i] = [];
    }
    
    for (let i = 0; i < s.length; i++) {
        rows[counter].push(s[i]); <--- will insert via counter! 
...

The Row + Counter combo is powerful. With this, we can control which row we insert into our matrix. Yet when we .push() into the array, we are inserting a value at the end of it. So if we think of rows and columns in a matrix, it inserts left to right. We can take advantage of this, inserting characters of our input string in a zig-zag pattern. So how do we make this work?

How about a boolean? Let’s make a variable set false and call it ‘reverse.’ It would allow us to reverse or divert how we insert our characters into this matrix. We increment or decrement this counter based on numRow Input or our zig-zag length. If it’s true, it zigs; if it’s false, it zags?

const convert = function(s, numRows) {
if(numRows <= 1 || s.length <= numRows) return s;
    
    let rows = [];
    let counter = 0;
    let reverse = false;
    
    for (let i = 0; i < numRows; i++) {
        rows[i] = [];
    }
    
    for (let i = 0; i < s.length; i++) {
rows[counter].push(s[i]); <-- Note: we insert first !!!
if (reverse === false) { <-- Now we check the counter!!!
            counter++;
        } else {
            counter--;        
        }

Let’s add some logic to this. Using a conditional statement, let’s check our counter. We have 2 cases to check for, if we increment and hit our numRow value or if we decrement and hit 0. In either case, it will reverse the variable, using a bang operator or ‘!’.

for (let i = 0; i < s.length; i++) {
        rows[counter].push(s[i]);
        if (reverse === false) {
            counter++;
        } else {
            counter--;        
        }
        
        if (counter === numRows - 1 || counter === 0) {
            reverse = !reverse;
        }
    }

Almost done, but will need to return this answer as a single output string. Let’s create a return variable, iterate over our matrix(rows) using .forEach(), and use .join() to tie up all those characters into a string.

... let rows = []; <-- matrix should be stored in here
    let counter = 0;
    let reverse = false;
    let result = '';
...
rows.forEach((row) => {
       result += row.join(""); 
    });

Let’s return that variable once the .forEach() is done. Run your code, and everything should pass the tests!

rows.forEach((row) => {
       result += row.join(""); 
    });
    
    return result;

Solution

const convert = function(s, numRows) {
if(numRows <= 1 || s.length <= numRows) return s;
    
    let rows = [];
    let counter = 0;
    let reverse = false;
    let result = '';
    
    for (let i = 0; i < numRows; i++) {
        rows[i] = [];
    }
    
    for (let i = 0; i < s.length; i++) {
        rows[counter].push(s[i]);
        if (reverse === false) {
            counter++;
        } else {
            counter--;        
        }
        
        if (counter === numRows - 1 || counter === 0) {
            reverse = !reverse;
        }
    }
    
    rows.forEach((row) => {
       result += row.join(""); 
    });
    
    return result;
};

Conclusion

The big takeaway for me was how to move in a zig-zag pattern in iteration using a boolean and a counter. Mind Blown and I learned a lot from this problem.

For those of you who figured it out while reading the article, kudos! If not, no worries. Keep at it, but spend time understanding your hangups. That’s the real treasure 💎 !

Huge shout out to Alisa Bajramovic, whose blog help me understand this problem in greater detail. You’ll find the link below; It’s worth the read! Keep learning and happy coding!

Links

- The ZigZag Conversion Problem by Alisa Bajramovic: https://dev.to/alisabaj/the-zigzag-conversion-problem-3nne
- Leetcode: leetcode.com