Zigzag string transformation

You are fifteen minutes into a Google phone screen when the interviewer says, "I have a string and a number of rows. I want you to write it in a zigzag pattern and read it back." At first glance this sounds like a trick question, but it is actually a clean simulation problem that tests your ability to model a physical pattern in code. This problem, also known as "Zigzag Conversion" on other platforms, shows up regularly at Google, Apple, Uber, and Amazon.

TL;DR

Distribute characters across numRows string buffers by bouncing a row index up and down. When you hit the top or bottom row, toggle direction. After processing every character, concatenate all rows. This runs in O(n) time and O(n) space. The key insight is that you do not need to build a 2D grid. Just track which row each character belongs to and append it there.

Why This Problem Matters

Zigzag string transformation is a pattern simulation problem. You are not applying a well-known algorithm like binary search or BFS. Instead, you need to observe a visual pattern, figure out how it maps to row indices, and translate that observation into clean code. That skill, turning a visual or physical intuition into an implementation, is exactly what interviewers are testing. It also makes a solid warm-up before harder string problems like longest substring without repeating characters or edit distance.

Understanding the Problem

Given a string s and an integer numRows, arrange the characters of s in a zigzag pattern across the specified number of rows, then read the result row by row.

For example, "FIRECODEHIRING" with 3 rows:

F   C   H   N
I E O E I I G
R   D   R

Reading each row left to right produces "FCHNIEOEIIGRDR".

With 4 rows, "PAYPALISHIRING" becomes:

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

Reading row by row: "PINALSIGYAHRPI".

Prefer a different language? Jump to solutions in other languages.

Edge Cases

Before diving into the algorithm, let's identify the cases where no real work is needed:

1. numRows == 1: Every character stays on the same row. Return s unchanged.
2. s.length() ≤ numRows: Each character lands on its own row, which reads back in original order. Return s.
3. numRows == 2: Characters alternate between two rows, producing a simple interleaving.

Handling the first two with an early return keeps the main loop clean.

The Zigzag Pattern

Look at the 3-row example more carefully. The row index for each character follows this sequence:

Character: F  I  R  E  C  O  D  E  H  I  R  I  N  G
Row:       0  1  2  1  0  1  2  1  0  1  2  1  0  1

The row index goes down from 0 to 2, then bounces back up to 0, then down again. It is a simple oscillation between 0 and numRows - 1.

Here is how the direction toggle works for 3 rows. The highlighted nodes show where the direction flips:

At row 0, goingDown flips to true. At row 2 (the last row), it flips to false. This bouncing behavior is the entire algorithm.

Solution Approach

The strategy is straightforward:

1. Create an array of numRows string buffers (one per row).
2. Walk through each character in s, appending it to the buffer for the current row.
3. When the current row hits the top (0) or bottom (numRows - 1), toggle the direction.
4. After processing all characters, concatenate the buffers in order.

No 2D array needed. No index math. Just a row counter that bounces.

Tracing Through "FIRECODEHIRING" with 3 Rows

Let's watch the row buffers fill up step by step:

After all 14 characters are distributed, the rows contain "FCHN", "IEOEIG", and "RDR". Concatenating them gives "FCHNIEOEIIGRDR".

Tracing with 4 Rows

The same algorithm works with more rows. Here is "PAYPALISHIRING" distributed across 4 rows:

The final result is "PIN" + "ALSIG" + "YAHR" + "PI" = "PINALSIGYAHRPI".

Implementation

public class Solution {
  public String convert(String s, int numRows) {
    // Early return for trivial cases
    if (numRows == 1 || s.length() <= numRows) {
      return s;
    }

    // Create a StringBuilder for each row
    StringBuilder[] rows = new StringBuilder[numRows];
    for (int i = 0; i < numRows; i++) {
      rows[i] = new StringBuilder();
    }

    int currentRow = 0;
    boolean goingDown = false;

    // Distribute each character to the appropriate row
    for (char c : s.toCharArray()) {
      rows[currentRow].append(c);

      // Toggle direction at the top and bottom rows
      if (currentRow == 0 || currentRow == numRows - 1) {
        goingDown = !goingDown;
      }

      // Move to the next row
      currentRow += goingDown ? 1 : -1;
    }

    // Concatenate all rows
    StringBuilder result = new StringBuilder();
    for (StringBuilder row : rows) {
      result.append(row);
    }
    return result.toString();
  }
}

Walk through the code:

1. Early exit: If there is only one row or the string is too short to zigzag, return immediately.
2. Row buffers: An array of StringBuilder objects, one per row.
3. Direction toggle: goingDown starts as false. On the very first iteration, currentRow == 0 triggers a flip to true, so we start moving downward. When we reach the bottom row, it flips back to false.
4. Row movement: currentRow increments by 1 when going down, decrements by 1 when going up.
5. Final assembly: Append each row's content to the result.

The direction toggle is worth dwelling on. Notice that goingDown starts false, not true. The toggle happens before the row index moves. So on the first character (row 0), we flip to true and then move down to row 1. This handles the starting condition without a special case.

Complexity Analysis

Time Complexity: O(n)

Each of the n characters is visited exactly once. Appending to a StringBuilder is amortized O(1). The final concatenation of all rows is also O(n) total since the combined length of all rows equals n.

Space Complexity: O(n)

The StringBuilder array stores all n characters across its rows. The result string is another O(n). Total auxiliary space is O(n).

The Mathematical Alternative

There is another approach that computes the output directly using cycle lengths. Each zigzag cycle has length 2 * numRows - 2. For each row, you can calculate which indices from the original string belong to that row using modular arithmetic.

While this avoids the row buffers, it is harder to implement correctly under interview pressure. The cycle-based approach requires handling diagonal characters separately from the main cycle positions, which introduces more opportunities for off-by-one errors. Both approaches have identical time and space complexity, so the simulation approach is the practical choice for interviews.

Common Mistakes

1. Initializing goingDown to true: This causes an off-by-one error where the first character ends up on row 1 instead of row 0. Starting with false and letting the toggle at row 0 handle it is cleaner.

2. Forgetting the early return: Without the numRows == 1 check, the toggle logic breaks because currentRow will always be 0 and the direction will flip every single iteration.

3. Using a 2D char array: Some candidates allocate a numRows x n grid with lots of empty cells. This wastes space and complicates the reading step. The row-buffer approach avoids all of that.

4. Off-by-one in direction check: The direction should toggle when currentRow == 0 or currentRow == numRows - 1, not when it would exceed those bounds. Checking after appending (not before) makes the code straightforward.

Interview Tips

When you get this problem in an interview:

1. Draw the zigzag first. Write out a small example on the whiteboard. The pattern becomes obvious once you see the row indices oscillating.

2. State the edge cases early. Mentioning numRows == 1 and short strings upfront shows thoroughness.

3. Explain the toggle clearly. "I maintain a boolean that flips at the boundaries" is a crisp one-sentence explanation that interviewers appreciate.

4. Mention the math approach as a follow-up. If the interviewer asks about alternatives, describe the cycle-length formula: cycleLen = 2 * numRows - 2, with characters at indices j and cycleLen - j for each row j. You do not need to implement it, just knowing it exists demonstrates depth.

Key Takeaways

• The zigzag pattern is just a row index bouncing between 0 and numRows - 1. Model it with a direction boolean that toggles at the boundaries.
• Use an array of string buffers (one per row) instead of a 2D grid. This keeps the implementation clean and avoids wasted space.
• Always handle numRows == 1 and short strings with an early return. These edge cases break the toggle logic if left unchecked.
• Both the simulation and mathematical approaches run in O(n) time and O(n) space. The simulation is easier to implement correctly under pressure.
• Starting goingDown as false and relying on the toggle at row 0 is the cleanest way to handle the initial direction without a special case.

Solutions in Other Languages

Python

class Solution:
    def convert(self, s: str, num_rows: int) -> str:
        if num_rows == 1 or num_rows >= len(s):
            return s

        rows = [''] * num_rows
        current_row = 0
        going_down = False

        for char in s:
            rows[current_row] += char
            if current_row == 0 or current_row == num_rows - 1:
                going_down = not going_down
            current_row += 1 if going_down else -1

        return ''.join(rows)

JavaScript

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

    const rows = Array.from({ length: Math.min(numRows, s.length) }, () => "");
    let currentRow = 0;
    let goingDown = false;

    for (let char of s) {
      rows[currentRow] += char;
      if (currentRow === 0 || currentRow === numRows - 1) {
        goingDown = !goingDown;
      }
      currentRow += goingDown ? 1 : -1;
    }

    return rows.join("");
  }
}

TypeScript

class Solution {
  convert(s: string, numRows: number): string {
    if (numRows === 1 || s.length <= numRows) {
      return s;
    }

    const rows: string[] = Array.from({ length: Math.min(numRows, s.length) }, () => "");
    let currentRow = 0;
    let goingDown = false;

    for (const char of s) {
      rows[currentRow] += char;
      if (currentRow === 0 || currentRow === numRows - 1) {
        goingDown = !goingDown;
      }
      currentRow += goingDown ? 1 : -1;
    }

    return rows.join("");
  }
}

C++

#include <string>
#include <sstream>
#include <vector>

class Solution {
public:
  std::string convert(std::string &s, int numRows) {
    if (numRows == 1 || numRows >= s.size()) {
      return s;
    }

    std::vector<std::string> rows(std::min(numRows, int(s.size())));
    int currentRow = 0;
    bool goingDown = false;

    for (char c : s) {
      rows[currentRow] += c;
      if (currentRow == 0 || currentRow == numRows - 1) {
        goingDown = !goingDown;
      }
      currentRow += goingDown ? 1 : -1;
    }

    std::string result;
    for (const std::string &row : rows) {
      result += row;
    }
    return result;
  }
};

Scala

class Solution {
  def convert(s: String, numRows: Int): String = {
    if (numRows == 1 || s.length <= numRows) return s

    val rows = Array.fill(math.min(numRows, s.length))("")
    var currentRow = 0
    var goingDown = false

    for (c <- s) {
      rows(currentRow) += c
      if (currentRow == 0 || currentRow == numRows - 1) goingDown = !goingDown
      currentRow += (if (goingDown) 1 else -1)
    }

    rows.mkString
  }
}

Kotlin

class Solution {
  fun convert(s: String, numRows: Int): String {
    if (numRows == 1 || s.length <= numRows) {
      return s
    }

    val rows = Array(numRows) { StringBuilder() }
    var currentRow = 0
    var goingDown = false

    s.forEach { c ->
      rows[currentRow].append(c)
      if (currentRow == 0 || currentRow == numRows - 1) {
        goingDown = !goingDown
      }
      currentRow += if (goingDown) 1 else -1
    }

    return rows.joinToString("") { it.toString() }
  }
}

Swift

import Foundation

class Solution {
    func convert(_ s: String, _ numRows: Int) -> String {
        if numRows == 1 || s.count <= numRows {
            return s
        }

        var rows = [String](repeating: "", count: numRows)
        var currentRow = 0
        var goingDown = false

        for c in s {
            rows[currentRow].append(c)
            if currentRow == 0 || currentRow == numRows - 1 {
                goingDown = !goingDown
            }
            currentRow += goingDown ? 1 : -1
        }

        return rows.joined()
    }
}

Ruby

class Solution
  def convert(s, num_rows)
    return s if num_rows == 1 || s.length <= num_rows

    rows = Array.new(num_rows) { '' }
    current_row = 0
    going_down = false

    s.each_char do |c|
      rows[current_row] += c
      going_down = !going_down if current_row == 0 || current_row == num_rows - 1
      current_row += going_down ? 1 : -1
    end

    rows.join
  end
end

Rust

pub struct Solution;

impl Solution {
    pub fn convert(&self, s: String, num_rows: i32) -> String {
        if num_rows == 1 || s.len() <= num_rows as usize {
            return s;
        }

        let mut rows: Vec<String> = vec![String::new(); num_rows as usize];
        let mut current_row: i32 = 0;
        let mut going_down = false;

        for c in s.chars() {
            rows[current_row as usize].push(c);
            if current_row == 0 || current_row == num_rows - 1 {
                going_down = !going_down;
            }
            current_row += if going_down { 1 } else { -1 };
        }

        rows.concat()
    }
}

Dart

class Solution {
  String convert(String s, int numRows) {
    if (numRows == 1 || s.length <= numRows) {
      return s;
    }

    List<StringBuffer> rows = List.generate(numRows, (_) => StringBuffer());
    int currentRow = 0;
    bool goingDown = false;

    for (String c in s.split('')) {
      rows[currentRow].write(c);
      if (currentRow == 0 || currentRow == numRows - 1) {
        goingDown = !goingDown;
      }
      currentRow += goingDown ? 1 : -1;
    }

    return rows.map((sb) => sb.toString()).join();
  }
}

C#

using System.Text;

public class Solution {
    public string Convert(string s, int numRows) {
        if (numRows == 1 || s.Length <= numRows) {
            return s;
        }

        var rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }

        int currentRow = 0;
        bool goingDown = false;

        foreach (char c in s) {
            rows[currentRow].Append(c);
            if (currentRow == 0 || currentRow == numRows - 1) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }

        var result = new StringBuilder();
        foreach (var row in rows) {
            result.Append(row);
        }
        return result.ToString();
    }
}

PHP

class Solution {
    public function convert(string $s, int $numRows): string {
        if ($numRows === 1 || strlen($s) <= $numRows) {
            return $s;
        }

        $rows = array_fill(0, $numRows, '');
        $currentRow = 0;
        $goingDown = false;

        for ($i = 0; $i < strlen($s); $i++) {
            $rows[$currentRow] .= $s[$i];
            if ($currentRow === 0 || $currentRow === $numRows - 1) {
                $goingDown = !$goingDown;
            }
            $currentRow += $goingDown ? 1 : -1;
        }

        return implode('', $rows);
    }
}

Related Problems

Once you are comfortable with zigzag conversion, try these related string and simulation problems to broaden your skills:

• Reverse a string in-place
• Longest palindromic substring
• String rotation check
• Spiral matrix traversal (another "read pattern from grid" problem)

Consistent practice turns problems like this from tricky to routine. This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed offers at top companies. Whether you are targeting Google, Apple, or your next startup role, building fluency with simulation and string problems will pay dividends.