medium Zigzag Conversion

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

1. Edge Case Handling:

   • If numRows is 1, return the input string as is because there's no zigzag pattern possible with one row.

2. 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.

3. 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).

4. 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.

5. 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:

1. Edge Case Handling:

   • numRows is 4, not 1, so we proceed.

2. Initialize Rows:

   • rows = ["", "", "", ""]

3. Set Direction:

   • currentRow = 0
   • goingDown = False

4. 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

5. Concatenate Rows:

   • Join all rows to form the final zigzag string:
     • result = "HRM" + "EPOMI" + "LOGAN" + "LRG"
     • result = "HRMEPOMILOGANLRG"

Code

class Solution {
    public String convert(String s, int numRows) {
        // Edge case: if there's only one row, return the string as is
        if (numRows == 1) return s;
        
        // Create an array of StringBuilder objects to hold rows
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }
        
        // Initialize variables to track the current row and direction
        int currentRow = 0;
        boolean goingDown = false;
        
        // Iterate through each character in the string
        for (char c : s.toCharArray()) {
            // Append the character to the current row
            rows[currentRow].append(c);
            // Change direction at the first and last rows
            if (currentRow == 0 || currentRow == numRows - 1) {
                goingDown = !goingDown;
            }
            // Move to the next row based on the direction
            currentRow += goingDown ? 1 : -1;
        }
        
        // Combine all rows to form the final result
        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) {
            result.append(row);
        }
        
        return result.toString();
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.convert("HELLOPROGRAMMING", 4)); // HRMEPOMILOGANLRG
        System.out.println(solution.convert("PROBLEMCHALLENGE", 5)); // PHRCAMLOEBLNGLEN
        System.out.println(solution.convert("ABCDE", 2)); // ACEBD
    }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , 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 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.