# Zigzag Conversion
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/zigzag-conversion)
Canonical: https://scaleengineer.com/dsa/problems/zigzag-conversion
**Data structures:** String
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Intuit](https://scaleengineer.com/companies/intuit), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [BitGo](https://scaleengineer.com/companies/bitgo), [ConsultAdd](https://scaleengineer.com/companies/consultadd), [Microstrategy](https://scaleengineer.com/companies/microstrategy), [Mitsogo](https://scaleengineer.com/companies/mitsogo), [PayPay](https://scaleengineer.com/companies/paypay), [carwale](https://scaleengineer.com/companies/carwale)
---
## Problem
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
## Sort by Row
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).
**Time:** O(n) · **Space:** O(n)
**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 `StringBuilder`s.; Involves managing state variables (`currentRow`, `goingDown`) within the loop, which adds slight overhead compared to a direct calculation.
### Explanation
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 `StringBuilder`s 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 `StringBuilder`s will contain the characters for their respective rows. The final step is to concatenate these `StringBuilder`s in order from row 0 to `numRows - 1` to get the final result.

```java
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();
    }
}
```
### 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 `StringBuilder`s in the list, from the first to the last.
*   Return the final concatenated string.

## Visit by Row
This approach constructs the result string by directly calculating the indices of characters for each row. Instead of simulating the path, we iterate through the rows from 0 to `numRows - 1` and, for each row, we append the corresponding characters from the input string based on a mathematical formula.
**Time:** O(n) · **Space:** O(n)
**Pros:** Highly efficient with minimal overhead, as it directly constructs the final string.; Uses O(1) extra space, not counting the space for the output string itself.
**Cons:** The logic for calculating indices is less intuitive and can be more difficult to derive and debug.
### Explanation
This approach avoids simulating the path and instead directly computes the final string. The key is to find a mathematical pattern for the indices of characters belonging to each row.

The characters in the zigzag pattern form a sequence of repeating cycles. The length of one full cycle (a 'V' shape) is `cycleLen = 2 * numRows - 2`.

We can build the result string row by row. For each row `i` from `0` to `numRows - 1`, we find all characters from the original string that belong to it.

*   For any row `i`, characters appear at intervals of `cycleLen`. The first character is at index `i`, the next is at `i + cycleLen`, then `i + 2*cycleLen`, and so on.
*   For the intermediate rows (not the first or the last), there is a second set of characters. These are the ones on the upward stroke of the zigzag. Within a cycle that starts at index `j`, this second character is located at index `j + cycleLen - i`.

By iterating through each row and then stepping through the string in increments of `cycleLen`, we can find and append all the necessary characters in the correct order.

```java
class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }

        StringBuilder result = new StringBuilder();
        int n = s.length();
        int cycleLen = 2 * numRows - 2;

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < n; j += cycleLen) {
                result.append(s.charAt(j + i));
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n) {
                    result.append(s.charAt(j + cycleLen - i));
                }
            }
        }
        return result.toString();
    }
}
```
### Algorithm
*   If `numRows` is 1, return the original string `s`.
*   Initialize an empty `StringBuilder` to build the result.
*   Calculate the length of a full zigzag cycle: `cycleLen = 2 * numRows - 2`.
*   Iterate from `i = 0` to `numRows - 1` (for each row).
*   In an inner loop, iterate through the string by jumping one cycle at a time. Let the index `j` start at `0` and increment by `cycleLen` in each step.
*   The first character for the current row `i` in a cycle starting at `j` is at index `j + i`. If this index is within the bounds of the string, append the character to the result.
*   For intermediate rows (where `i` is not 0 or `numRows - 1`), there is a second character on the upward stroke. Its index is `j + cycleLen - i`. If this index is also within bounds, append this character to the result.
*   After the loops complete, return the final string from the `StringBuilder`.

# Solutions
### CSharp

```csharp
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();
    }
}
```

### Java

```java
class Solution {
public
  String convert(String s, int numRows) {
    if (numRows == 1) {
      return s;
    }
    StringBuilder ans = new StringBuilder();
    int group = 2 * numRows - 2;
    for (int i = 1; i <= numRows; i++) {
      int interval = i == numRows ? group : 2 * numRows - 2 * i;
      int idx = i - 1;
      while (idx < s.length()) {
        ans.append(s.charAt(idx));
        idx += interval;
        interval = group - interval;
        if (interval == 0) {
          interval = group;
        }
      }
    }
    return ans.toString();
  }
}

```

### JavaScript

```javascript
/** * @param {string} s * @param {number} numRows * @return {string} */ var convert =
  function (s, numRows) {
    if (numRows === 1) {
      return s;
    }
    const g = new Array(numRows).fill(_).map(() => []);
    let i = 0;
    let k = -1;
    for (const c of s) {
      g[i].push(c);
      if (i === 0 || i === numRows - 1) {
        k = -k;
      }
      i += k;
    }
    return g.flat().join("");
  };

```

### CPP

```cpp
class Solution {
public:
  string convert(string s, int numRows) {
    if (numRows == 1)
      return s;
    string ans;
    int group = 2 * numRows - 2;
    for (int i = 1; i <= numRows; ++i) {
      int interval = i == numRows ? group : 2 * numRows - 2 * i;
      int idx = i - 1;
      while (idx < s.length()) {
        ans.push_back(s[idx]);
        idx += interval;
        interval = group - interval;
        if (interval == 0)
          interval = group;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def convert(self, s: str, numRows: int) -> str: if numRows == 1: return s group = 2 * numRows - 2 ans = [] for i in range(1, numRows + 1): interval = group if i == numRows else 2 * numRows - 2 * i idx = i - 1 while idx < len(s): ans . append(s[idx]) idx += interval interval = group - interval if interval == 0: interval = group return '' . join(ans)

```