Skip to main content

6. Zigzag Conversion

medium

Write a string row by row in a zigzag pattern across numRows lines, then read it off row by row. Pure index simulation, no clever data structures required.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a string s and an integer numRows, write s in a zigzag pattern on numRows lines (going down then diagonally up, repeating) and then read it row by row to produce a new string. Return that string. If numRows is 1 or numRows >= s.length, the answer is just s.

Constraints

  • 1 <= s.length <= 1000
  • s consists of English letters (lower-case and upper-case), ',' and '.'.
  • 1 <= numRows <= 1000

Examples

Example 1

Input
s = "PAYPALISHIRING", numRows = 3
Output
"PAHNAPLSIIGYIR"

Explanation: Rows: P A H N A P L S I I G Y I R

Example 2

Input
s = "PAYPALISHIRING", numRows = 4
Output
"PINALSIGYAHRPI"

Example 3

Input
s = "A", numRows = 1
Output
"A"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Build numRows separate row buffers. Walk the input once and append each character to the right row.

Hint 2

Track the current row and a direction (+1 going down, -1 going up). Flip direction when you hit row 0 or row numRows-1.

Hint 3

Concatenate the row buffers in order to get the answer. Handle numRows == 1 as a no-op.

Solution approach

Reveal approach

Row-by-row simulation. Edge case: if numRows == 1 or numRows >= s.length, return s. Otherwise allocate rows = array of numRows empty strings. Walk s once with row index r starting at 0 and direction d starting at +1. For each character c: append c to rows[r], then if r == 0 set d = +1, else if r == numRows-1 set d = -1; finally r += d. After the walk, join rows into a single string. O(n) time, O(n) space.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • simulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Adobe

Practice these live with InterviewChamp.AI

Drill Zigzag Conversion and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →