Unraveling the Zigzag: A Beginner's Guide to LeetCode 6 (Zigzag Conversion)

Hey LeetCoders and aspiring competitive programmers! aryan-subudhi here, ready to dive into another fascinating problem that looks tricky on the surface but unlocks a cool pattern-recognition skill. Today, we're tackling LeetCode Problem 6: Zigzag Conversion. Get ready to bend your string into some interesting shapes!

Problem Explanation

Imagine you're writing a message, but instead of straight lines, you write it in a zigzag pattern across a given number of rows. Once you've written it, you then read the message line by line, from left to right. Your task is to implement a function convert that takes a string s and an integer numRows and returns the converted string.

Let's look at an example. If our input string is s = "PAYPALISHIRING" and numRows = 3:

We write it like this:

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

Notice how P is in row 0, A in row 1, Y in row 2, then we go back up with P in row 1, A in row 0, and so on. It forms a 'N' or 'Z' shape.

Once written, we read it line by line:

Row 0: P, A, H, N
Row 1: A, P, L, S, I, I, G
Row 2: Y, I, R

Concatenating these gives us: "PAHNAPLSIIGYIR". This is our expected output!

Another example: s = "PAYPALISHIRING", numRows = 4

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

Reading line by line:

Row 0: P, I, N
Row 1: A, L, S, I, G
Row 2: Y, A, H, R
Row 3: P, I

Concatenating: "PINALSIGYAHRPI".

Constraints:

The string length s can be up to 1000 characters.
s consists of English letters (upper/lower-case), ',', and '.'.
numRows can be between 1 and 1000.

An important edge case: if numRows = 1, the zigzag pattern doesn't really form. The string remains unchanged. convert("A", 1) should return "A".

Intuition

At its core, this problem is about simulating the pattern. If we were doing this manually, we'd pick a character from the input string, place it in the correct row, then decide where the next character goes. This suggests we need a way to keep track of:

Which row we're currently placing characters into.
The direction we're moving (downwards or upwards).

The pattern repeats in cycles: go down from row 0 to numRows - 1, then go up from numRows - 2 to row 1, and then repeat. Notice that row 0 and numRows - 1 are only hit when going "down." The "up" phase skips these two rows to avoid double-counting or overshooting the pattern.

Approach: Simulating the Zigzag

Let's formalize our intuition into a concrete algorithm:

Handle the Edge Case: If numRows is 1, no zigzag conversion is needed. Simply return the original string s.
Initialize Rows: We need a way to store characters for each row. A list of lists (or list of strings/string builders) is perfect for this. Let's create numRows empty lists. For example, mat = [[] for _ in range(numRows)].
Traverse and Populate: We'll iterate through the input string s character by character. For each character, we need to append it to the correct row. The key is to manage our current_row index and the direction.

The pattern can be seen as a series of "full columns" going down, followed by "diagonal segments" going up-right.
- Phase 1: Going Down: We start at row 0 and append characters sequentially to mat[0], mat[1], ..., up to mat[numRows - 1].
- Phase 2: Going Up-Right: After reaching the bottom, we move "up and right." This means we append characters to mat[numRows - 2], mat[numRows - 3], ..., up to mat[1]. We stop before row 0 because row 0 is the start of the next "down" phase. Similarly, numRows - 1 is only hit when going down.
We repeat these two phases until all characters from s are processed.
Construct Result: Once all characters have been placed into their respective row lists, concatenate all the lists (or strings) in mat from row 0 to numRows - 1 to form the final result string.

Let's trace s = "PAYPALISHIRING", numRows = 3 with this approach:

mat = [[], [], []]
s_idx = 0

Cycle 1:

Down Phase:
- s[0] ('P') -> mat[0] -> ['P'], s_idx = 1
- s[1] ('A') -> mat[1] -> ['A'], s_idx = 2
- s[2] ('Y') -> mat[2] -> ['Y'], s_idx = 3 (Reached numRows - 1)
Up-Right Phase: (numRows - 2 down to 1 -> 3 - 2 = 1 down to 1)
- s[3] ('P') -> mat[1] -> ['A', 'P'], s_idx = 4 (Reached row 1)

Cycle 2:

Down Phase:
- s[4] ('A') -> mat[0] -> ['P', 'A'], s_idx = 5
- s[5] ('L') -> mat[1] -> ['A', 'P', 'L'], s_idx = 6
- s[6] ('I') -> mat[2] -> ['Y', 'I'], s_idx = 7
Up-Right Phase:
- s[7] ('S') -> mat[1] -> ['A', 'P', 'L', 'S'], s_idx = 8

Cycle 3:

Down Phase:
- s[8] ('H') -> mat[0] -> ['P', 'A', 'H'], s_idx = 9
- s[9] ('I') -> mat[1] -> ['A', 'P', 'L', 'S', 'I'], s_idx = 10
- s[10] ('R') -> mat[2] -> ['Y', 'I', 'R'], s_idx = 11
Up-Right Phase:
- s[11] ('I') -> mat[1] -> ['A', 'P', 'L', 'S', 'I', 'I'], s_idx = 12

Cycle 4:

Down Phase:
- s[12] ('N') -> mat[0] -> ['P', 'A', 'H', 'N'], s_idx = 13
- s[13] ('G') -> mat[1] -> ['A', 'P', 'L', 'S', 'I', 'I', 'G'], s_idx = 14 (String s exhausted)

Final mat:
mat[0] = ['P', 'A', 'H', 'N']
mat[1] = ['A', 'P', 'L', 'S', 'I', 'I', 'G']
mat[2] = ['Y', 'I', 'R']

Join them: "PAHN" + "APLSIIG" + "YIR" = "PAHNAPLSIIGYIR". Perfect!

Code

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # Edge case: If there's only one row, no zigzag conversion needed.
        if numRows == 1:
            return s

        # Initialize numRows empty lists to represent each row.
        # Each list will store characters that belong to that row.
        mat = [[] for _ in range(numRows)]

        # Pointer for the current character in the input string s.
        i = 0
        # Length of the input string s.
        n = len(s)

        # Loop until all characters from the input string are processed.
        while i < n:
            # Phase 1: Go down (from row 0 to numRows - 1)
            for down in range(numRows):
                if i < n: # Check if there are still characters left in s
                    mat[down].append(s[i])
                    i += 1

            # Phase 2: Go up-right (from numRows - 2 down to row 1)
            # We skip row 0 and numRows - 1 as they are handled exclusively by the 'down' phase
            # or will be the start/end of the next 'down' phase.
            for up in range(numRows - 2, 0, -1):
                if i < n: # Check if there are still characters left in s
                    mat[up].append(s[i])
                    i += 1

        # After populating all rows, join the characters in each row
        # and then concatenate all rows to form the final result string.
        result = []
        for row in mat:
            result.extend(row) # Use extend for efficiency, then join once

        return "".join(result)

Time & Space Complexity Analysis

Time Complexity: O(N)

We iterate through the input string s once using the while i < n loop.
Inside the loop, each character s[i] is appended to a list in mat exactly once.
Finally, we iterate through the mat (which collectively holds N characters) to build the result list and then join them into a string. The extend and join operations are proportional to the total number of characters, which is N.
Therefore, the overall time complexity is linear with respect to the length of the string s.

Space Complexity: O(N)

We create numRows lists in mat. In the worst case (e.g., numRows = N), each list holds one character. In general, all N characters of the string s are stored across these numRows lists.
The result list also temporarily stores all N characters before joining.
Therefore, the space complexity is linear with respect to the length of the string s.

Key Takeaways

Simulation Power: Many string manipulation or pattern-based problems can be solved by directly simulating the process described. Break down the pattern into repeatable steps.
State Management: Keeping track of current_row and direction (or explicit phases like "down" and "up-right") is crucial for controlling the simulation.
Edge Cases First: Always consider simple edge cases like numRows = 1 early on. They often simplify your logic or prevent errors.
List of Lists for Structure: When dealing with grid-like or row-based structures, a list of lists (or 2D array) is a very natural and effective data structure.
Concatenation Efficiency: For building strings from many smaller pieces, appending to a list of characters/strings and then using "".join(list) is generally more efficient in Python than repeated string concatenation (+=).