Zigzag Conversion [Code + Interactive Visualization]

String Medium

Python Java C++

def convert(s: str, numRows: int) -> str:
    # Handle edge cases
    if numRows == 1: return s
    
    # Create list of string builders for each row
    rows = [[] for _ in range(numRows)]
    index = 0
    
    # Process string character by character
    while index < len(s):
        # Move down
        for i in range(numRows) and index < len(s):
            rows[i].append(s[index])
            index += 1
            
        # Move up diagonally
        for i in range(numRows-2, 0, -1) and index < len(s):
            rows[i].append(s[index])
            index += 1
    
    # Join all rows together
    return ''.join(''.join(row) for row in rows)

public class Solution {
    public String convert(String s, int numRows) {
        // Create list of StringBuilders for each row
        List rows = new ArrayList<>();
        
        for (int i = 0; i < numRows; i++){
            rows.add(new StringBuilder());
        }
        
        int index = 0;
        
        // Process string character by character
        while (index < s.length()) {
            // Move down
            for (int i = 0; i < numRows && index < s.length(); i++) {
                StringBuilder curr = rows.get(i);
                char letter = s.charAt(index);
                curr.append(letter);
                index++;
            }
            
            // Move up diagonally
            for (int i = rows.size() - 2; i > 0 && index < s.length(); i--) {
                StringBuilder curr = rows.get(i);
                char letter = s.charAt(index);
                curr.append(letter);
                index++;
            }
        }
        
        // Join all rows together
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < rows.size(); i++) {
            result.append(rows.get(i).toString());
        }
        
        return result.toString();
    }
}

class Solution {
public:
    string convert(string s, int numRows) {
        // Handle edge cases
        if (numRows == 1) return s;
        
        // Create vector of strings for each row
        vector rows(numRows);
        int index = 0;
        
        // Process string character by character
        while (index < s.length()) {
            // Move down
            for (int i = 0; i < numRows && index < s.length(); i++) {
                rows[i] += s[index];
                index++;
            }
            
            // Move up diagonally
            for (int i = numRows - 2; i > 0 && index < s.length(); i--) {
                rows[i] += s[index];
                index++;
            }
        }
        
        // Join all rows together
        string result;
        for (const string& row : rows) {
            result += row;
        }
        
        return result;
    }
};

Problem Statement

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:

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 the number of rows.

Detailed Explanation

Approach

Instead of actually creating the zigzag pattern, we can simulate the movement and append characters to the appropriate rows. The pattern consists of two movements: straight down and up diagonally.

Key Concepts

1. Row Buffers: Each row gets its own string builder/buffer
2. Two Movements: Down movement fills all rows, up movement fills middle rows
3. Pattern Repeat: Down then up diagonal repeats until string is processed
4. Final Join: Concatenate all rows in order

Algorithm Steps

1. Create array of string builders for each row
2. Process string character by character:
   • Move down: append to each row from top to bottom
   • Move up diagonally: append to each row from bottom-1 to 1
   • Repeat until all characters are processed
3. Join all rows together to create result

Time and Space Complexity

• Time Complexity: O(n) where n is the length of the input string
• Space Complexity: O(n) to store all characters in row buffers

Why This Works

The solution works because:

• Each character is placed in exactly one row
• The zigzag pattern naturally emerges from alternating down/up movements
• Reading row by row produces the correct result order
• Middle rows get filled during both movements

Edge Cases

• numRows = 1: Return original string
• numRows ≥ string length: Each character gets its own row
• Empty string: Return empty string
• Two rows: No diagonal movement needed

Common Mistakes

• Not handling single row case
• Incorrect diagonal movement bounds
• Not checking string length in both movement loops
• Trying to create actual 2D grid

Previous Step Next Step Reset

Input String

PAYPALISHIRING

Current Index

0

Movement

DOWN

Result String

Click "Next Step" to begin the visualization