Zigzag Conversion - Practice Coding Problems

Zigzag Conversion - Problem

String Medium

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

Input & Output

Example 1 — Basic Case

$ Input: s = "PAYPALISHIRING", numRows = 3

› Output: "PAHNAPLSIIGYIR"

💡 Note: Characters form zigzag: Row 0 gets P,A,H,N; Row 1 gets A,P,L,S,I,I,G; Row 2 gets Y,I,R. Reading rows gives PAHNAPLSIIGYIR.

Example 2 — More Rows

$ Input: s = "PAYPALISHIRING", numRows = 4

› Output: "PINALSIGYAHRPI"

💡 Note: With 4 rows: Row 0: P,I,N; Row 1: A,L,S,I,G; Row 2: Y,A,H,R; Row 3: P,I. Result: PINALSIGYAHRPI.

Example 3 — Single Row

$ Input: s = "A", numRows = 1

› Output: "A"

💡 Note: With only 1 row, no zigzag pattern is formed. String remains unchanged.

Constraints

1 ≤ s.length ≤ 1000
s consists of English letters (a-z), ',' and '.'
1 ≤ numRows ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

String "PAYPALISHIRING" with numRows = 3

Zigzag Pattern

Write characters in down-up-down zigzag

Output

Read each row left to right

Key Takeaway

🎯 Key Insight: The zigzag pattern repeats every 2*(numRows-1) characters, allowing efficient character distribution or mathematical calculation

Asked in

M Microsoft 25 a Amazon 20 G Google 15

The key insight is recognizing the zigzag creates a repeating cycle pattern. Best approach uses row arrays to directly distribute characters. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ 2D Grid Simulation	O(n)	O(n)	Create a 2D grid and simulate the zigzag writing process
Mathematical Pattern Recognition (Optimal)	O(n)	O(n)	Calculate which row each character belongs to using mathematical formulas without simulation
Row Arrays	O(n)	O(n)	Use separate arrays for each row to collect characters directly
Mathematical Pattern	O(n)	O(1)	Calculate character positions using mathematical formulas based on cycle pattern

2D Grid Simulation — Algorithm Steps

Create 2D grid with enough columns
Place characters following zigzag pattern (down then up)
Read each row left to right to build final string

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Grid

Initialize 2D matrix

Fill Zigzag

Place characters going down then up

Read Rows

Concatenate each row left to right

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s, int numRows) {
    int len = strlen(s);
    if (numRows == 1 || numRows >= len) {
        char* result = malloc((len + 1) * sizeof(char));
        strcpy(result, s);
        return result;
    }
    
    int cycleLen = 2 * numRows - 2;
    int numCols = len / cycleLen * (numRows - 1) + numRows;
    char** grid = malloc(numRows * sizeof(char*));
    for (int i = 0; i < numRows; i++) {
        grid[i] = malloc(numCols * sizeof(char));
        for (int j = 0; j < numCols; j++) {
            grid[i][j] = ' ';
        }
    }
    
    int col = 0, row = 0;
    int goingDown = 1;
    
    for (int i = 0; i < len; i++) {
        grid[row][col] = s[i];
        if (goingDown) {
            if (row == numRows - 1) {
                goingDown = 0;
                row--;
                col++;
            } else {
                row++;
            }
        } else {
            if (row == 0) {
                goingDown = 1;
                row++;
            } else {
                row--;
                col++;
            }
        }
    }
    
    char* result = malloc((len + 1) * sizeof(char));
    int idx = 0;
    for (int r = 0; r < numRows; r++) {
        for (int c = 0; c < numCols; c++) {
            if (grid[r][c] != ' ') {
                result[idx++] = grid[r][c];
            }
        }
        free(grid[r]);
    }
    result[idx] = '\0';
    free(grid);
    
    return result;
}

int main() {
    char s[1001];
    int numRows;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &numRows);
    
    char* result = solution(s, numRows);
    printf("%s\n", result);
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string to place characters plus reading grid

✓ Linear Growth

Space Complexity

O(n)

2D grid stores all characters

⚡ Linearithmic Space

167.0K Views

Medium Frequency

~15 min Avg. Time

3.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Grid Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler