Zigzag Conversion

Difficulty: Medium | Acceptance: 52.19% | Paid: No

Topics: String

• Examples
• Constraints
• Brute Force Approach
• Visit by Row Approach
• Mathematical Pattern Approach

Examples

Input

s = "PAYPALISHIRING", numRows = 3

Output

"PAHNAPLSIIGYIR"

Input

s = "PAYPALISHIRING", numRows = 4

Output

"PINALSIGYAHRPI"

Explanation

P I N A L S I G Y A H R P I

Input

s = "A", numRows = 1

Output

"A"

Constraints

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

Brute Force Approach

Intuition

Build the zigzag pattern using a matrix or list of rows, then concatenate the strings from each row.

Steps

• Create a list of strings with size equal to numRows.
• Simulate the zigzag motion by traversing the input string character by character and placing each character in the appropriate row.
• Use a direction variable to keep track of moving down or up in the zigzag.
• Concatenate all rows at the end to form the result string.

def convert(s, numRows):
    if numRows == 1:
        return s
    rows = [''] * min(numRows, len(s))
    curRow = 0
    goingDown = False
    
    for c in s:
        rows[curRow] += c
        if curRow == 0 or curRow == numRows - 1:
            goingDown = not goingDown
        curRow += 1 if goingDown else -1
    
    return ''.join(rows)

Complexity

• Time: O(n) where n is the length of the input string. We iterate through each character once.
• Space: O(n) to store the characters in the rows. In the worst case, we store all characters.

Visit by Row Approach

Intuition

Instead of building the pattern, directly calculate which characters belong to each row based on the cycle pattern of the zigzag.

Steps

• Recognize that characters in each row follow a periodic pattern based on the cycle length (2 * numRows - 2).
• For each row, iterate through the string and collect characters that belong to that row based on their index positions.
• Handle the first and last rows separately as they have characters only at regular intervals.
• For middle rows, there are two characters per cycle that need to be collected.

def convert(s, numRows):
    if numRows == 1:
        return s
    
    res = ''
    cycle_len = 2 * numRows - 2
    
    for i in range(numRows):
        for j in range(0, len(s), cycle_len):
            if j + i < len(s):
                res += s[j + i]
            if i != 0 and i != numRows - 1 and j + cycle_len - i < len(s):
                res += s[j + cycle_len - i]
    
    return res

Complexity

• Time: O(n) where n is the length of the input string. Each character is visited exactly once.
• Space: O(1) if we don’t count the space for the output string. We only use a constant amount of extra space.

Mathematical Pattern Approach

Intuition

Use mathematical formulas to directly calculate the indices of characters in each row without simulation.

Steps

• Understand the zigzag pattern as a series of cycles with a specific length.
• For each row, determine the mathematical relationship between character indices.
• Use arithmetic progression to efficiently calculate all character positions in a row.
• Handle the special cases of first and last rows which have a simpler pattern.

def convert(s, numRows):
    if numRows == 1 or numRows >= len(s):
        return s
    
    result = []
    n = len(s)
    cycleLen = 2 * numRows - 2
    
    for i in range(numRows):
        for j in range(0, n - i, cycleLen):
            result.append(s[j + i])
            if i != 0 and i != numRows - 1 and j + cycleLen - i < n:
                result.append(s[j + cycleLen - i])
    
    return ''.join(result)

Complexity

• Time: O(n) where n is the length of the input string. We visit each character exactly once.
• Space: O(1) if we don’t count the space for the output string. We only use a constant amount of extra space.