loading...

The ZigZag Conversion Problem

alisabaj profile image Alisa Bajramovic ・7 min read

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:

String is set to equal "ABCDEFGH" and number of rows equals 3. Beneath that is a box with three rows. In the first row is "AE", second row is "BDFH", and third row is "CG". When taken as a whole, it looks like a zig-zag.

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

Box with three empty rows

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.

Box with three rows. At the start of the first row is "A", at the start of the second row is "B", at the start of the third row is "C". Beneath "C" is a blue arrow that's pointing up, signifying the direction we'll be going.

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.

Box with three rows. First row is "A [space] E", second row is "B D", third row is "C". After "E" there is a red arrow pointing down, signifying what direction it'll be going next.

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.

Two boxes. The first box has three rows. The first row is "A [space] "E", the second row is "B D F", the third row is "C [space] G". Under "G" is a blue arrow pointing up, signifying the next direction to go. The second box is very similar, but now in the second row there is an "H" at the end.

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

First string is "AE", then a plus sign next to the second string, "BDFH", then a plus sign next to the third string, "CG". Beneath all of this is the final string, "AEBDFHCG".

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.

On the left is a green column titled "currentRow", with the numbers 0, 1, and 2 beneath it. To the right is a three-row box. The first row is "A [space] "E", the second row is "B D", the third row is "C". Above the first column is "reverse: false" written in blue. From "A" to "B" to "C" are two blue arrows, with "+1" on each arrow. Beneath the first column is "reverse: true". Then there are red arrows from "C" to "D" to "E", with "-1" next to each of them.

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!

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

pic
Editor guide