The ZigZag Conversion Problem

Today's algorithm of the day is the ZigZag Conversion Problem. You're given a string, and a number of rows. The idea is that the given string is written in a zigzag pattern, and the function should return what the string would read like when read line-by-line.

I think the problem is written out in a particularly confusing way, so let's take a look at an example.

If the given string was "ALGORITHMOFTHEDAY", and the number of rows was 4, it would look like this:

A      T      H
L   I  H   T  E
G  R   M  F   D  Y
O      O      A

Read line-by-line, you get the string "ATHLIHTEGRMFDYOOA", which would be the output of this function.

I think this is the kind of algorithm where breaking down an example helps you come up with the solution. So, I'll start by working through an example and considering how I'll approach the problem, and then I'll go into the code.

Approaching the ZigZag Problem

Let's say you're given the string "ABCDEFGH", and the number of rows in the zigzag is 3. Written out, that'd look like this:

Taking all of the letters away, we have three rows, which can be thought of like three arrays.

Now, to build this zig zagged word, we can go letter by letter in the given string. Starting with the first three letters, "ABC", we can put them at the start of the three rows (or arrays). Once we get to the bottom row, we know we can't add any more letters in that direction, so we'll have to start reversing direction.

We'll add "D" and "E" in this reverse direction, but once we get to the first row, we again know we can't continue in this direction.

We can keep doing the same thing, adding letters in one direction until we get to the bottom row, and then reversing direction, until we've added all of the letters of the string.

Taking the lines of the arrays away (essentially converting these arrays to strings), we get three strings.

Adding them together, line by line, we get the result: "AEBDFHCG".

This example shows how I'll be approaching this problem: build the same number of arrays for rows that are given, add the letters of the given string to each array until we get to the last array, then reverse direction. Once we get to the first array, reverse direction again. Keep doing this until we run out of letters from the inputted string. Finally, join the letters of the separate arrays to make strings, and join those strings to make one final string.

Coding the ZigZag Problem

Now that we've gone through an example, we can go ahead and code the solution. In the problem, we're given the string, s, and a number of rows, numRows. The first thing to do will be to consider the base cases: if there's only one row, then no zigzag will even be possible, so we can just return the string back. The other base case is if the string is shorter than the number of rows that are given--in which case, a zig zag also won't be possible, so we can again return the string.

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

Now we'll need to build some variables. The first thing will be an array that'll store other arrays, rows. Each array in rows will store one row of the zig zag pattern. We also need to build a counter, currentRow, for the current row we're on, which will start at 0. We need a variable equal to a boolean value that signifies if we're switching direction, reverse. And finally, we need to create an empty string which will be returned in the end, result.

function convert(s, numRows) {
  if (numRows === 1 || s.length < numRows) {
    return s;
  }
  let rows = [];
  let currentRow = 0;
  let reverse = false;
  let result = "";

  //...
}

We now want to build the number of rows that are given in numRows. To do this, we can create a for loop, going from 0 to numRows, and build a new blank array each time.

function convert(s, numRows) {
  if (numRows === 1 || s.length < numRows) {
    return s;
  }
  let rows = [];
  let currentRow = 0;
  let reverse = false;
  let result = "";

  for (let i = 0; i < numRows; i++) {
    rows[i] = [];
  }

  //...
}

Now, we'll want to go through each character in "s", and push it to different rows, until we're done with every letter. So, this is a good place to use a for loop, going from the first letter (at index 0), until the last (at s.length).

Inside the for loop, we'll want to push this letter (s[i]) to the row based on currentRow. currentRow will get bigger if we're going down, and get smaller if we're reversing directions--so we should have a conditional statement here. If reverse is true, then currentRow should get smaller; otherwise, currentRow should get bigger.

Thinking about the example from earlier, reverse started out as false, so the currentRow count continued to get bigger. Once we got to the bottom row, reverse was set equal to true, at which point currentRow count continued to get smaller.

So, in our for loop, we can check if reverse is true or false. If it's false, then we can increment currentRow. Otherwise, we can decrement currentRow.

function convert(s, numRows) {
  if (numRows === 1 || s.length < numRows) {
    return s;
  }
  let rows = [];
  let currentRow = 0;
  let reverse = false;
  let result = "";

  for (let i = 0; i < numRows; i++) {
    rows[i] = [];
  }

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

    //...
  }

  //...
}

The last thing we'll want to do in the for loop is check if we're either in the last row or in the first row. In both of those instances, we'll want to go in the opposite direction that we were just going, so we can set reverse equal to !reverse.

function convert(s, numRows) {
  if (numRows === 1 || s.length < numRows) {
    return s;
  }
  let rows = [];
  let currentRow = 0;
  let reverse = false;
  let result = "";

  for (let i = 0; i < numRows; i++) {
    rows[i] = [];
  }

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

    if (currentRow === numRows - 1 || currentRow === 0) {
      reverse = !reverse;
    }
  }

  //...
}

Once the for loop is done executing, we'll come out of it with multiple arrays. We want to turn each of those arrays into strings, and then add those strings to each other.

To do this, we can call .forEach() on each row in rows. For each of those rows, we can turn it into a string using .join(). We can then add each of those strings to result. Finally, outside of the forEach method, we can return the result.

function convert(s, numRows) {
  if (numRows === 1 || s.length < numRows) {
    return s;
  }
  let rows = [];
  let currentRow = 0;
  let reverse = false;
  let result = "";

  for (let i = 0; i < numRows; i++) {
    rows[i] = [];
  }

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

    if (currentRow === numRows - 1 || currentRow === 0) {
      reverse = !reverse;
    }
  }

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

  return result;
}

Please let me know in the comments if you have any questions or other ideas for how to approach this problem!

Comments

[gantonas]

Bit late, but I only just found out about the ZigZag problem. Never knew this existed.
Instead of using a bool for the reverse, wouldn't it be better and faster to use the reverse as a variable = 1 which gets added to the rownumber and when it needs to be reversed, you multiply it by -1 to then subtract the row number?
And to find out if you need to reverse can you do "Rownumber mod numrows -1"?