Solution: Zigzag Conversion

Grokking 75: Top Coding Interview Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Zigzag Conversion

Table of Contents

Contents are not accessible

Problem Statement

Given a string s and a numRows integer representing the number of rows, write the string in a zigzag pattern on the given number of rows and then read it line by line, and return the resultant string.

The zigzag pattern means writing characters in a diagonal down-and-up fashion. For example, given the string "HELLOPROGRAMMING" and 4 rows, the pattern would look like:

H     R     M
E   P O   M I
L O   G A   N
L     R     G

Reading it line by line gives us "HRMEPOMILOGANLRG".

Examples

Example 1:

Input: s = "HELLOPROGRAMMING", numRows = 4
Expected Output: "HRMEPOMILOGANLRG"
Explanation: The zigzag pattern is:
```
H     R     M
E   P O   M I
L O   G A   N
L     R     G
```
Reading line by line gives "HRMEPOMILOGANLRG".

Example 2:

Input: s = "PROBLEMCHALLENGE", numRows = 5
Expected Output: "PHRCAEOMLGBELNLE"

Explanation: The zigzag pattern is:

P       H       
R     C A     E 
O   M   L   G   
B E     L N     
L       E

Reading line by line gives "LCCETEHLDELOEGAEEN".

Example 3:

Input: s = "ABCDE", numRows = 2
Expected Output: "ACEBD"
Explanation: The zigzag pattern is:
```
A C E
B D
```
Reading line by line gives "ACEBD".

Constraints:

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

Solution

To solve this problem, we need to create the zigzag pattern and then read the characters row by row. We can use an array of strings to store characters for each row. By iterating through the input string, we place each character in the appropriate row and switch direction (up or down) whenever we reach the top or bottom row. This approach ensures we correctly form the zigzag pattern. After forming the pattern, we concatenate the strings from each row to get the final result.

This method is effective because it simulates the actual zigzag writing process and uses a direct and intuitive approach to manage the character placement. It is also efficient in terms of both time and space complexity.

Step-by-Step Algorithm

Edge Case Handling:
- If numRows is 1, return the input string as is because there's no zigzag pattern possible with one row.
Initialize Rows:
- Create an array of empty strings (or StringBuilder objects) to hold characters for each row. The number of elements in this array should be equal to numRows.
Set Direction:
- Initialize variables currentRow to 0 and goingDown to False. These will help in tracking the current row being filled and the direction of filling (down or up).
Place Characters:
- Iterate through each character in the input string s:
  - Append the character to the current row.
  - If currentRow is 0 (top row) or currentRow is numRows - 1 (bottom row), change the direction (toggle goingDown).
  - Move to the next row based on the current direction (goingDown). If goingDown is True, increment currentRow. If goingDown is False, decrement currentRow.
Concatenate Rows:
- After iterating through all characters, join all the strings (or contents of StringBuilder objects) from each row to form the final zigzag string.

Algorithm Walkthrough

Using the input s = "HELLOPROGRAMMING", numRows = 4:

Edge Case Handling:
- numRows is 4, not 1, so we proceed.
Initialize Rows:
- rows = ["", "", "", ""]
Set Direction:
- currentRow = 0
- goingDown = False
Place Characters:
- Iterate through the string "HELLOPROGRAMMING":
  - 'H':
    - rows[0] = "H"
    - currentRow = 1
    - goingDown = True
  - 'E':
    - rows[1] = "E"
    - currentRow = 2
    - goingDown = True
  - 'L':
    - rows[2] = "L"
    - currentRow = 3
    - goingDown = True
  - 'L':
    - rows[3] = "L"
    - currentRow = 2
    - goingDown = False
  - 'O':
    - rows[2] = "LO"
    - currentRow = 1
    - goingDown = False
  - 'P':
    - rows[1] = "EP"
    - currentRow = 0
    - goingDown = False
  - 'R':
    - rows[0] = "HR"
    - currentRow = 1
    - goingDown = True
  - 'O':
    - rows[1] = "EPO"
    - currentRow = 2
    - goingDown = True
  - 'G':
    - rows[2] = "LOG"
    - currentRow = 3
    - goingDown = True
  - 'R':
    - rows[3] = "LR"
    - currentRow = 2
    - goingDown = False
  - 'A':
    - rows[2] = "LOGA"
    - currentRow = 1
    - goingDown = False
  - 'M':
    - rows[1] = "EPOM"
    - currentRow = 0
    - goingDown = False
  - 'M':
    - rows[0] = "HRM"
    - currentRow = 1
    - goingDown = True
  - 'I':
    - rows[1] = "EPOMI"
    - currentRow = 2
    - goingDown = True
  - 'N':
    - rows[2] = "LOGAN"
    - currentRow = 3
    - goingDown = True
  - 'G':
    - rows[3] = "LRG"
    - currentRow = 2
    - goingDown = False
Concatenate Rows:
- Join all rows to form the final zigzag string:
  - result = "HRM" + "EPOMI" + "LOGAN" + "LRG"
  - result = "HRMEPOMILOGANLRG"

Code

Python3

. . . .

Complexity Analysis

Time Complexity

The time complexity of the algorithm is $O(n)$ , where n is the length of the input string. This is because we are iterating through each character in the string exactly once.

Space Complexity

The space complexity of the algorithm is $O(n)$ as well. This is due to the array of strings used to hold the rows. Each character is stored exactly once in one of the rows, resulting in a total space requirement proportional to the length of the input string.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible