Problem Description

Given a string s and a positive integer numRows, arrange the characters of s in a zigzag pattern across numRows rows, then read the result row by row to produce the final string.

Constraints

• s contains English letters (both lowercase and uppercase), commas, and periods
• 1 <= numRows <= 1000

Solution Approaches

Approach 1: Row-by-Row StringBuilder Array

This approach uses an array of StringBuilder objects, each representing one row of the zigzag pattern. Instead of pre-calculating matrix dimensions, we simply append characters to the appropriate row during traversal.

Algorithm:

1. Create an array of StringBuilder objects with size equal to numRows
2. Traverse the input string character by character
3. Maintain a currentRow index and a direction flag goingDown
4. When reaching the top or bottom row, reverse the direction
5. Concatenate all rows to form the final result

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1 || s.length() <= numRows) {
            return s;
        }
        
        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            rows.add(new StringBuilder());
        }
        
        int currentRow = 0;
        boolean goingDown = false;
        
        for (char ch : s.toCharArray()) {
            rows.get(currentRow).append(ch);
            
            if (currentRow == 0 || currentRow == numRows - 1) {
                goingDown = !goingDown;
            }
            
            currentRow += goingDown ? 1 : -1;
        }
        
        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) {
            result.append(row);
        }
        
        return result.toString();
    }
}

Approach 2: Optimized Array-Based Solution

This approach uses a simple array instead of a List, achieving better performance by avoiding dynamic list resizing. The logic remains identical but with more compact code.

Algorithm:

1. Initialize a StringBuilder array of size numRows
2. Use two variables: rowIndex for current position and stepDirection (+1 or -1)
3. Process each character and update the direction when at boundaries
4. Join all StringBuilders using Java 8 Streams

class Solution {
    public String convert(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }
        
        StringBuilder[] rowBuilders = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rowBuilders[i] = new StringBuilder();
        }
        
        int rowIndex = 0;
        int stepDirection = 1;
        
        for (char character : s.toCharArray()) {
            rowBuilders[rowIndex].append(character);
            
            if (rowIndex == 0 || rowIndex == numRows - 1) {
                stepDirection = -stepDirection;
            }
            
            rowIndex += stepDirection;
        }
        
        return Arrays.stream(rowBuilders)
                     .collect(Collectors.joining());
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the length of the input string. Each character is processed exact once.
• Space Complexity: O(n), as we store all characters in the StringBuilder array.

Key Insights

The zigzag pattern can be viewed as alternating betweeen downward and upward moveement:

• Moving down adds characters to successive rows (0 → 1 → 2 → ...)
• Moving up adds characters to preceding rows (... ← 2 ← 1 ← 0)
• The direction reverses whenever reaching the first or last row

This problem demonstrates the importance of identifying cyclic patterns in traversal problems and using appropriate data structures to simplify the solution.