Top Interview 150

The Zigzag Conversion problem is a fascinating challenge that tests your ability to simulate patterns in strings. Let’s break down LeetCode 6: Zigzag Conversion and solve it efficiently.

🚀 Problem Description

Given a string s and an integer numRows, arrange the characters of s in a zigzag pattern with the specified number of rows and read them row by row.

💡 Examples
Example 1

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

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"  
Explanation: Only one row, so no zigzagging.

🏆 JavaScript Solution

Approach

• We simulate the zigzag traversal by:
  1. Using an array of strings (one for each row).
  2. Traversing the input string and appending each character to the correct row.
  3. Reversing direction when the current row is either the top or bottom.

Implementation

var convert = function(s, numRows) {
    if (numRows === 1 || s.length <= numRows) return s;

    const rows = new Array(numRows).fill('');
    let currentRow = 0;
    let goingDown = false;

    for (let char of s) {
        rows[currentRow] += char;

        if (currentRow === 0 || currentRow === numRows - 1) {
            goingDown = !goingDown;
        }

        currentRow += goingDown ? 1 : -1;
    }

    return rows.join('');
};

🔍 How It Works

1. Edge Cases:

   • If numRows is 1 or the string length is less than numRows, return the string as is (no zigzagging).

2. Simulate Zigzag:

   • Use an array of strings to represent rows.
   • Traverse the input string and append each character to the appropriate row.
   • Switch direction (up or down) when reaching the top or bottom row.

3. Combine Rows:

   • Concatenate all rows into a single string to form the result.

🔑 Complexity Analysis

• > Time Complexity: O(n), where n is the length of the string. Each character is visited once.
• > Space Complexity: O(n), for storing the zigzag pattern in the rows array.

📋 Dry Run
Input: s = "PAYPALISHIRING", numRows = 4

Output: "PINALSIGYAHRPI"

✨ Pro Tips for Interviews

• Clarify constraints: Confirm edge cases, such as single-row input or strings shorter than numRows.
• Optimize for readability: Explain how reversing direction ensures the zigzag pattern.
• Discuss scalability: Highlight how the solution scales efficiently with longer strings.

📚 Learn More

Check out the full explanation and code walkthrough on my Dev.to post:
👉 Reverse Words in a String - JavaScript Solution

How would you approach this problem? Let’s discuss! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving