loading...

The ZigZag Conversion Problem

alisabaj profile image Alisa Bajramovic ・7 min read

Algorithm of the Day (36 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 34 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events 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:

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!

Algorithm of the Day (36 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 34 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem

Posted on Jun 5 by:

alisabaj profile

Alisa Bajramovic

@alisabaj

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

Discussion

markdown guide