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 Sam K., 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

More Strings practice problems

See all Strings problems →