Leetcode 6: Zigzag Conversion

 

1. Problem Statement (Simple Explanation):

• You are given:

• A string s

• An integer numRows

• You write the characters of s in a zigzag pattern across numRows rows, and then read the characters row by row to form a new string.

• You need to return that new string.

2. Examples:

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3

Output: "PAHNAPLSIIGYIR"

Explanation:

Zigzag pattern (3 rows):

P    A    H  N

A P L S I I G

Y    I     R

Read row by row → "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4

Output: "PINALSIGYAHRPI"

Explanation:

Zigzag pattern (4 rows):

P       I      N

A   L S    I G

Y A   H R

P      I

                Read row by row → "PINALSIGYAHRPI"

Example 3:

Input: s = "A", numRows = 1

Output: "A"

Explanation:

Only one row, so the result is the same string.

3. Key Observations:

1. When numRows == 1 or numRows >= len(s), there is no zigzag effect; return s directly.

2. The characters “go down” row by row, then “go up diagonally” and repeat:

• Row sequence goes: 0,1,2,...,numRows-1,numRows-2,...,1,0,...

3. We can simulate the process:

• Maintain a buffer string for each row.

• Traverse the input characters while moving a pointer currentRow up and down.

4. Approach 1 – Simulation with Row Strings (Recommended):

Intuition:

• Create an array/list of strings, one per row.

• Start at row 0, direction “down”.

• For each character:

• Append it to the current row’s string.

• If we’re at the top row, change direction to “down”.

• If we’re at the bottom row, change direction to “up”.

• Move currentRow accordingly.

• At the end, concatenate all row strings.

This directly simulates the zigzag writing.

Algorithm (Step-by-Step):

1. If numRows == 1 or numRows >= len(s), return s.

2. Initialize an array rows of min(numRows, len(s)) empty strings.

3. Set:

• currentRow = 0

• goingDown = false

4. For each character c in s:

• Append c to rows[currentRow].

• If currentRow == 0 or currentRow == numRows - 1, flip goingDown (toggle).

• If goingDown == true, currentRow++, else currentRow--.

5. Join all strings in rows and return the result.

Pseudo-code (Simulation):

Time and Space Complexity:

Let n=len(s).

• Time: O(n)

We visit each character exactly once and append it.

• Space: O(n)

for storing the output + row buffers.

This is efficient for n≤1000 and is the standard solution.

5. (Optional) Approach 2 – Index Arithmetic / Row Skipping:

• We can compute row-by-row indices using cycle length:

                    cycleLen=2×(numRows-1)

• For row 0 and last row, jump by full cycles.

• For middle rows, there are two positions per cycle.

But this is more complex to explain; the simulation approach is clearer and perfectly efficient for constraints.

6. Java code:

7. C code:

8. C++ code:

9. Python code:

10. JavaScript code:

<<<PREV

NEXT>>>