Scale Engineer

Zigzag Conversion

Med
#0006Time: O(n)Space: O(n)22 companies
Data structures
String
Companies
AdobeAmazonAppleBloomberg

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"

 

Constraints:

  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the zigzag path of the characters. We maintain a list of string builders, one for each row. We iterate through the input string, and for each character, we append it to the string builder of the correct row. We keep track of the current row and the direction of movement (down or up).

Algorithm

  • If numRows is 1, return the original string s as no conversion is needed.
  • Create a list of StringBuilder objects, one for each row. The size of the list will be numRows.
  • Initialize a variable currentRow to 0 and a boolean flag goingDown to false. This flag will determine the direction of traversal (downwards or upwards).
  • Iterate through each character of the input string s.
  • For each character, append it to the StringBuilder at the currentRow index in the list.
  • Check if the currentRow has reached the top (row 0) or the bottom (row numRows - 1). If it has, reverse the direction by flipping the goingDown flag.
  • Update currentRow by incrementing it if goingDown is true, and decrementing it otherwise.
  • After iterating through all characters, concatenate the strings from all StringBuilders in the list, from the first to the last.
  • Return the final concatenated string.

Walkthrough

This approach works by distributing the characters of the input string into numRows different "buckets", where each bucket corresponds to a row in the zigzag pattern. We create a list of StringBuilders to act as these buckets.

We then iterate through the input string s from left to right. To determine the correct row for each character, we simulate the vertical movement. We start at row 0 and move downwards. When we hit the last row (numRows - 1), we change direction and start moving upwards. When we hit the first row (row 0), we change direction again. A currentRow variable tracks the current row index, and a goingDown boolean tracks the direction.

After iterating through all characters, the StringBuilders will contain the characters for their respective rows. The final step is to concatenate these StringBuilders in order from row 0 to numRows - 1 to get the final result.

class Solution {    public String convert(String s, int numRows) {        if (numRows == 1) {            return s;        }         List<StringBuilder> rows = new ArrayList<>();        for (int i = 0; i < Math.min(numRows, s.length()); i++) {            rows.add(new StringBuilder());        }         int curRow = 0;        boolean goingDown = false;         for (char c : s.toCharArray()) {            rows.get(curRow).append(c);            if (curRow == 0 || curRow == numRows - 1) {                goingDown = !goingDown;            }            curRow += goingDown ? 1 : -1;        }         StringBuilder result = new StringBuilder();        for (StringBuilder row : rows) {            result.append(row);        }        return result.toString();    }}

Complexity

Time

O(n)

Space

O(n)

Trade-offs

Pros

  • Intuitive and easy to understand as it directly models the problem description.

  • Relatively straightforward to implement.

Cons

  • Requires extra space proportional to the input string's length to hold the list of StringBuilders.

  • Involves managing state variables (currentRow, goingDown) within the loop, which adds slight overhead compared to a direct calculation.

Solutions

public class Solution {    public string Convert(string s, int numRows) {        if (numRows == 1) {            return s;        }        int n = s.Length;        StringBuilder[] g = new StringBuilder[numRows];        for (int j = 0; j < numRows; ++j) {            g[j] = new StringBuilder();        }        int i = 0, k = -1;        foreach(char c in s.ToCharArray()) {            g[i].Append(c);            if (i == 0 || i == numRows - 1) {                k = -k;            }            i += k;        }        StringBuilder ans = new StringBuilder();        foreach(StringBuilder t in g) {            ans.Append(t);        }        return ans.ToString();    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem