Jobs

Interviews

Discussions

Zigzag Conversion

Medium

PayPal

2 views

Topics:

Strings

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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:

string convert(string s, int numRows);

Example 1:

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

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

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

Zigzag Conversion

Medium

PayPal

2 views

Topics:

Strings

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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:

string convert(string s, int numRows);

Example 1:

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

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for `numRows`? Can it be zero, negative, or larger than the length of the input string?
Can the input string `s` be empty or null?
What should be the output if `numRows` is equal to 1?
Are there any specific memory constraints I should be aware of, given a potentially large input string and number of rows?
Is the goal to optimize for readability and maintainability, or is performance the primary focus?

Brute Force Solution

Approach

Imagine writing the input string down a zigzag pattern on a piece of paper with a given number of rows. The brute force way is like manually simulating writing and reading the string in that zigzag pattern. It involves meticulously building the zigzag row by row until the entire string is processed.

Here's how the algorithm would work step-by-step:

Create a separate empty container for each row that exists in our zigzag pattern.
Take the first letter of the input string and write it into the top row container.
Take the next letter and write it into the next row down.
Keep writing letters into consecutive rows downwards until you reach the bottom row.
Now, reverse direction and write the next letter into the row directly above the bottom row.
Continue writing letters into consecutive rows upwards until you reach the top row.
Repeat steps 3-6 until you have used all of the letters from the input string.
Finally, combine the contents of each row container from top to bottom into a single string. This combined string is the zigzag conversion.

Code Implementation

def zigzag_conversion(input_string, number_rows):
    if number_rows <= 1:
        return input_string

    row_containers = [""] * number_rows
    current_row = 0
    going_down = True

    for character in input_string:
        row_containers[current_row] += character

        # Determine if we need to change direction
        if current_row == 0:

            going_down = True

        elif current_row == number_rows - 1:

            going_down = False

        # Update the current row index
        if going_down:

            current_row += 1

        else:

            current_row -= 1

    result = "".join(row_containers)
    return result

Big(O) Analysis

Time Complexity

O(n) – The described algorithm iterates through each character of the input string once. For each character, it determines the appropriate row to which it should be added in the zigzag pattern. The operations performed for each character (appending to a row string) take constant time. Therefore, the overall time complexity is directly proportional to the length of the input string, resulting in a linear time complexity of O(n), where n is the length of the input string.

Space Complexity

O(N) – The algorithm creates a separate container (e.g., a list or string) for each row in the zigzag pattern. In the worst-case scenario, if numRows is equal to 1 or greater than or equal to the length of the input string, the algorithm essentially stores a copy of the entire input string across these row containers. Therefore, the space required for these containers grows linearly with the length of the input string, N. The space complexity is thus O(N), where N is the length of the input string.

Optimal Solution

Approach

The goal is to rearrange a string into a zigzag pattern with a specified number of rows. Instead of directly placing each letter, we simulate writing the string down each row in the zigzag pattern, then read it out row by row to construct the final converted string efficiently.

Here's how the algorithm would work step-by-step:

Imagine you are writing the string vertically down the rows in the zigzag pattern.
Then, when you reach the bottom row, change direction and write upwards, continuing to move diagonally.
Keep changing direction each time you hit the top or bottom row.
As you 'write' each letter, add it to a string representing its corresponding row.
Once you've processed all letters in the original string, combine all the row strings together in order from top to bottom to form the final zigzag converted string.

Code Implementation

def convert_string_to_zigzag(input_string, number_of_rows):
    if number_of_rows == 1:
        return input_string

    row_strings = [""] * number_of_rows
    current_row = 0
    going_down = False

    for character in input_string:
        row_strings[current_row] += character

        # Change direction when we hit the top or bottom row
        if current_row == 0 or current_row == number_of_rows - 1:
            going_down = not going_down

        # Update the current row based on the direction
        current_row += 1 if going_down else -1

    # Combine the row strings to get the final zigzag pattern
    result = "".join(row_strings)
    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n exactly once. Inside the loop, it performs constant-time operations like calculating the row index and appending to a string. Appending to a string happens row number of times, but row is constrained by numRows, hence can be thought of as constant. Therefore, the dominant factor is the single loop that iterates through the input string, resulting in a linear time complexity.

Space Complexity

O(N) – The plain English description states that strings representing each row are created. In the worst-case scenario where numRows is equal to 1, a single string of length N (where N is the length of the input string) will be created to store the result. In other cases, multiple strings will be created whose combined lengths add up to the length of the original string, N. Thus the auxiliary space used is proportional to the length of the input string, giving us O(N) space complexity.

Edge Cases

Case	How to Handle
Empty string input	Return an empty string immediately since there's nothing to convert.
numRows is 1	Return the original string as the zigzag pattern is just a single line.
numRows is greater than or equal to the length of the string	Return the original string as each character forms its own row.
String with only one character and numRows > 1	Return the single character string as is.
Very long string and large numRows (performance)	The solution should use an efficient data structure like an array of strings to build the zigzag pattern to avoid excessive string concatenation.
String with special characters or unicode characters	The algorithm should handle any valid character without modification, as the problem only concerns the arrangement.
Negative numRows input	Throw an IllegalArgumentException or return null to signal invalid input as the number of rows cannot be negative.
numRows is zero	Throw an IllegalArgumentException or return null as the zigzag pattern requires at least one row.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range for `numRows`? Can it be zero, negative, or larger than the length of the input string?
Can the input string `s` be empty or null?
What should be the output if `numRows` is equal to 1?
Are there any specific memory constraints I should be aware of, given a potentially large input string and number of rows?
Is the goal to optimize for readability and maintainability, or is performance the primary focus?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Create a separate empty container for each row that exists in our zigzag pattern.
Take the first letter of the input string and write it into the top row container.
Take the next letter and write it into the next row down.
Keep writing letters into consecutive rows downwards until you reach the bottom row.
Now, reverse direction and write the next letter into the row directly above the bottom row.
Continue writing letters into consecutive rows upwards until you reach the top row.
Repeat steps 3-6 until you have used all of the letters from the input string.
Finally, combine the contents of each row container from top to bottom into a single string. This combined string is the zigzag conversion.

Code Implementation

def zigzag_conversion(input_string, number_rows):
    if number_rows <= 1:
        return input_string

    row_containers = [""] * number_rows
    current_row = 0
    going_down = True

    for character in input_string:
        row_containers[current_row] += character

        # Determine if we need to change direction
        if current_row == 0:

            going_down = True

        elif current_row == number_rows - 1:

            going_down = False

        # Update the current row index
        if going_down:

            current_row += 1

        else:

            current_row -= 1

    result = "".join(row_containers)
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you are writing the string vertically down the rows in the zigzag pattern.
Then, when you reach the bottom row, change direction and write upwards, continuing to move diagonally.
Keep changing direction each time you hit the top or bottom row.
As you 'write' each letter, add it to a string representing its corresponding row.
Once you've processed all letters in the original string, combine all the row strings together in order from top to bottom to form the final zigzag converted string.

Code Implementation

def convert_string_to_zigzag(input_string, number_of_rows):
    if number_of_rows == 1:
        return input_string

    row_strings = [""] * number_of_rows
    current_row = 0
    going_down = False

    for character in input_string:
        row_strings[current_row] += character

        # Change direction when we hit the top or bottom row
        if current_row == 0 or current_row == number_of_rows - 1:
            going_down = not going_down

        # Update the current row based on the direction
        current_row += 1 if going_down else -1

    # Combine the row strings to get the final zigzag pattern
    result = "".join(row_strings)
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return an empty string immediately since there's nothing to convert.
numRows is 1	Return the original string as the zigzag pattern is just a single line.
numRows is greater than or equal to the length of the string	Return the original string as each character forms its own row.
String with only one character and numRows > 1	Return the single character string as is.
Very long string and large numRows (performance)	The solution should use an efficient data structure like an array of strings to build the zigzag pattern to avoid excessive string concatenation.
String with special characters or unicode characters	The algorithm should handle any valid character without modification, as the problem only concerns the arrangement.
Negative numRows input	Throw an IllegalArgumentException or return null to signal invalid input as the number of rows cannot be negative.
numRows is zero	Throw an IllegalArgumentException or return null as the zigzag pattern requires at least one row.