Problem Statement in English

You’re given a string s and an integer numRows. You need to write the string in a zigzag pattern on a given number of rows and then read it line by line.

Approach

There’s a pattern that you need to figure out here so that you don’t have to create a 2D array to store the zigzag pattern. Instead, you can directly calculate the indices of the characters in the original string that will appear in each row of the zigzag pattern.

There are 2 parts to the zigzag pattern:

  • Reading it linewise
  • Factoring in the diagonal elements that appear in the zigzag pattern and how they interop with the linewise reading

Reading it linewise

The first element of any row is the element at index r of the original string s, where r is the row number (0-indexed).

The next element in the same row can be found by adding a certain increment to the current index. This increment is calculated as 2 * (numRows - 1).

Factoring in the diagonal elements

The diagonal elements appear in the rows that are not the first or last row. For a given row r, the diagonal element can be found at the index i + increment - 2 * r, where i is the current index of the character in the original string.

Putting it all together

We iterate through each row and for each row, we iterate through the characters in the original string using the calculated increment. We also check for diagonal elements and add them to the result if they exist.

And we’re done!

Solution in Python


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

        res = []
        for r in range(numRows):
            increment = 2 * (numRows - 1)
            for i in range(r, len(s), increment):
                res.append(s[i])
                extra = i + increment - 2 * r
                if r > 0 and r < numRows - 1 and extra < len(s):
                    res.append(s[extra])
        
        return ''.join(res)

Complexity

  • Time: $O(n)$
    Since we are iterating through the string s once, the time complexity is linear with respect to the length of the string.

  • Space: $O(n)$
    Since we are storing the result in a list before joining it into a string, the space complexity is also linear with respect to the length of the string.

Mistakes I Made

I had to look it up :(

And we are done.