We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Zigzag Conversion

Number: 6

Difficulty: Medium

Paid? No

Companies: Google, Zopsmart, Amazon, Microsoft, Bloomberg, PayPal, Salesforce, Microstrategy, PayPay, Zoho, Oracle, Meta, ServiceNow, Mitsogo, Apple, Adobe, carwale, Uber, Infosys, FreshWorks, BitGo

Problem Description

Given a string and a number of rows, rearrange the string in a zigzag pattern by writing the characters in a down-up cycle across rows and then concatenating the rows to form the final string.

Key Insights

  • The zigzag pattern can be simulated by iterating over the characters and appending them to rows.
  • Maintain an index for the current row and a direction (up or down) for adding characters.
  • When the direction reaches the top or bottom row, the traversal direction reverses.
  • Concatenating all rows produces the final result.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(n), used to store characters in rows.

Solution

The solution involves simulating the zigzag writing process by iterating over the string once while keeping track of the current row and the direction of movement. An array (or list) of strings is used where each element corresponds to a row in the zigzag pattern. As we iterate through the string:

  1. Append the current character to the string corresponding to the current row.
  2. Reverse the direction if the current row is either the top or bottom row.
  3. Adjust the current row index accordingly.
  4. Finally, join all row strings to produce the output.

This simulation approach efficiently arranges the characters and is intuitively easy to follow.

Code Solutions

def convert(s: str, numRows: int) -> str:
    # Handle the edge case when the zigzag pattern is not applicable.
    if numRows == 1 or numRows >= len(s):
        return s
    
    # Initialize a list to hold strings for each row.
    rows = [''] * numRows
    current_row = 0
    going_down = False
    
    # Loop over each character in the input string.
    for char in s:
        rows[current_row] += char
        # Reverse direction at the first or last row.
        if current_row == 0 or current_row == numRows - 1:
            going_down = not going_down
        current_row += 1 if going_down else -1
        
    # Concatenate all row strings to form the final result.
    return ''.join(rows)

# Example usage:
# print(convert("PAYPALISHIRING", 3))
← Back to All Questions