Zigzag Conversion - Video Solutions

Problem Overview: You are given a string and a number of rows. Write the characters in a zigzag pattern across those rows, then read the rows sequentially to produce the final string. The challenge is correctly mapping characters to their zigzag positions without explicitly building a 2D grid.

Approach 1: Direct Zigzag Simulation (O(n) time, O(n) space)

This approach simulates the zigzag writing process row by row. Create an array (or list) of strings representing each row. Iterate through the characters of the input string and append each character to the current row. Maintain a direction flag that moves the pointer either down or up through the rows. When the pointer reaches the first or last row, flip the direction. After processing all characters, concatenate the rows to build the final string. The algorithm touches each character exactly once, giving O(n) time complexity and O(n) extra space for storing row strings. This approach is easy to implement and mirrors the visual zigzag pattern directly. It’s commonly used when solving string transformation problems.

Approach 2: Mathematical Index Calculation (O(n) time, O(1) extra space)

The zigzag pattern follows a repeating cycle. For numRows = r, one full cycle length is cycle = 2 * (r - 1). Characters in the first and last rows appear every cycle positions. For middle rows, characters appear twice in each cycle: once vertically and once diagonally. Iterate row by row and compute indices directly using this cycle pattern. For each base index i, append s[i + row] and, for middle rows, also append s[i + cycle - row] if it exists. This avoids maintaining row buffers and relies on predictable index jumps derived from the zigzag structure. Time complexity remains O(n) because each character is processed once. Extra space can be O(1) aside from the output string. This technique relies on pattern recognition and basic math observations applied to a string.

Recommended for interviews: The direct zigzag simulation is usually the expected answer in interviews. It demonstrates clear reasoning, correct state transitions, and clean string manipulation. The mathematical index method is slightly more optimized in memory and shows deeper pattern recognition, but it’s easier to make indexing mistakes. Showing the simulation first proves you understand the zigzag structure, while deriving the cycle formula highlights stronger algorithmic insight.