The O(n) Club: Zigzag Conversion – How to Break, Not Break, And Break Your Strings

The O(n) Club: Zigzag Conversion – How to Break, Not Break, And Break Your Strings

⚡ TL;DR

Take your input string, sprinkle it ‘downward’ across X rows, then ‘zig’ back up, then keep zigging. No grids. No performance crimes. Just some glorious row bookkeeping and a direction flag. Here’s Java doing its best impression of a rollercoaster attendant:

// Handle the easy way or ride the zigzag
if (numRows == 1 || numRows >= s.length()) return s;
StringBuilder[] rows = new StringBuilder[numRows];
for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
int currRow = 0, dir = 1;
for (char c : s.toCharArray()) {
    rows[currRow].append(c);
    if (currRow == 0 || currRow == numRows - 1) dir = -dir;
    currRow += dir;
}
StringBuilder result = new StringBuilder();
for (StringBuilder row : rows) result.append(row);
return result.toString();

🧠 How Devs Usually Mess This Up

If you thought “I should make a 2D matrix,” congratulations, you’ve over-engineered a problem so hard it might unionize. 90% of new devs build a grid, fill it with corners, forget about those pesky diagonals, and spend the rest of the day debugging off-by-one errors that could bankrupt a small startup. For bonus points, someone always tries an in-place rearrange and ends up knee-deep in null pointer exceptions and shame.

🔍 What’s Actually Going On

Imagine handing out name tags at a three-story tech meetup. First attendee gets floor 1, second moves down to floor 2, you keep descending until the lobby, then realize you’re out of stairs, so you sheepishly climb back up—one floor at a time. Everyone’s name lands on a floor. You lap the building, flipping direction at each end. The string’s characters are your attendees, each StringBuilder is a floor, and your only job is managing the party’s up/down order like a tired event coordinator.

🛠️ PseudoCode

• Edge Case? if numRows == 1 or numRows >= s.length() – Just hand back the original string. Nothing to zig. Nothing to zag.
• Initialize your rows: Build a StringBuilder for each row, because Java hates fun and loves explicit allocation.
• For each character in the string:
  • Slap it onto the current row’s StringBuilder.
  • If you’re on row 0 or the bottom, swap direction using dir = -dir like you’re flipping a sign on a coffee shop door.
  • Move up or down by tweaking currRow with dir.
• Finally: Merge all your StringBuilders into one—like collecting all your sticky notes at the end of a chaotic standup.

💻 The Code

public String convert(String s, int numRows) {
    if (numRows == 1 || numRows >= s.length()) return s;
    StringBuilder[] rows = new StringBuilder[numRows];
    for (int i = 0; i < numRows; i++) rows[i] = new StringBuilder();
    int currRow = 0, dir = 1;
    for (char c : s.toCharArray()) {
        rows[currRow].append(c);
        if (currRow == 0 || currRow == numRows - 1) dir = -dir;
        currRow += dir;
    }
    StringBuilder result = new StringBuilder();
    for (StringBuilder row : rows) result.append(row);
    return result.toString();
}

⚠️ Pitfalls, Traps & Runtime Smacks

• numRows == 1 or numRows >= s.length(): Sometimes the right thing is nothing at all. Return s and preserve your dignity.
• Forgetting to reverse direction at the row ends: Missing this gives you “flatline conversion” and an algorithm flatter than most midweek standups.
• Off-by-one Mistakes: Get your <= and >= right or you’ll zig where you should zag.
• Space/Time: O(n) each. Everyone else is lying if they tell you it can be done in less, and you don’t want to be those people.

🧠 Interviewer Brain-Tattoo

“Zigzags: Not just for secret agents and rollercoasters—they’re also for programmers who remember when to change direction.”