Solving ZigZag Conversion in Go: Step-by-Step Guide

Introduction to the ZigZag Conversion Problem

The ZigZag Conversion is a classic algorithmic challenge, famously known as LeetCode Problem #6. The task is deceptively simple: given a string and a number of rows, you must arrange the characters of the string in a zigzag pattern across those rows, then read the result row by row to produce a new string. While the problem sounds like a visual puzzle, it is actually an excellent exercise in pattern recognition, index manipulation, and string building in Go.

In this tutorial, we will break down the problem, understand the underlying mathematical pattern, and implement a clean, efficient solution in Go. We will also explore alternative approaches, analyze time and space complexity, and discuss best practices to make your code production-ready.

What Is the ZigZag Conversion?

Imagine writing a string across multiple rows in a zigzag fashion. For example, with the input string "PAYPALISHIRING" and numRows = 3, the characters are placed as follows:

P   A   H   N
A P L S I I G
Y   I   R

Reading row by row, the converted string becomes "PAHNAPLSIIGYIR". The pattern works by moving downward character by character until you reach the bottom row, then moving upward diagonally until you reach the top row, and repeating this cycle until all characters are placed.

With numRows = 4, the same string produces a different layout:

P     I    N
A   L S  I G
Y A   H R
P     I

The converted output here is "PINALSIGYAHRPI". Notice that the number of rows directly affects the cycle length and the spacing between characters in each row.

Edge Cases to Consider

Before diving into the solution, it is important to identify edge cases that can simplify your logic:

• If numRows is 1, the zigzag pattern is just the original string.
• If numRows is greater than or equal to the length of the string, the output is also the original string.
• If the string is empty, return an empty string immediately.

Why This Problem Matters

You might wonder why this seemingly artificial problem is worth solving. The ZigZag Conversion tests several fundamental programming skills that are valuable in real-world development:

• Pattern recognition: Identifying the cyclic nature of the zigzag pattern is key to an efficient solution.
• Index arithmetic: Calculating which row a character belongs to based on its position strengthens your ability to work with modular arithmetic.
• String manipulation: Go strings are immutable, so building strings efficiently using strings.Builder is a practical skill.
• Algorithmic thinking: Comparing simulation versus mathematical approaches teaches you to evaluate trade-offs between clarity and performance.

These skills transfer directly to tasks like data serialization, matrix traversal, and encoding schemes where positional logic is essential.

Understanding the Pattern

The key insight is that the zigzag pattern repeats in cycles. For numRows = 4, one full cycle looks like this:

Row 0: 0           6           12
Row 1: 1       5   7       11  13
Row 2: 2   4       8   10      14
Row 3: 3           9           15

The cycle length is 2 * numRows - 2. For 4 rows, that is 2 * 4 - 2 = 6. Each cycle contains exactly numRows - 1 downward characters and numRows - 1 upward characters, totaling cycleLen characters.

For each row r in a cycle starting at index i:

• The first character in that row is at index i + r.
• If r is not the first or last row, there is a second character in the same cycle at index i + cycleLen - r.

This mathematical understanding allows us to build the output string without simulating the entire grid.

Approach 1: Simulation with Row Buffers

The most intuitive approach is to simulate the zigzag movement. We maintain a slice of strings, one for each row, and iterate through the input string, appending each character to the appropriate row. We track the current direction (down or up) and switch direction when we hit the top or bottom row.

Implementation

package main

import (
	"fmt"
	"strings"
)

func convertSimulation(s string, numRows int) string {
	if numRows == 1 || numRows >= len(s) {
		return s
	}

	// Create a buffer for each row
	rows := make([]strings.Builder, numRows)
	currentRow := 0
	goingDown := false

	for i := 0; i < len(s); i++ {
		rows[currentRow].WriteByte(s[i])

		// Change direction at the top or bottom row
		if currentRow == 0 || currentRow == numRows-1 {
			goingDown = !goingDown
		}

		if goingDown {
			currentRow++
		} else {
			currentRow--
		}
	}

	// Concatenate all rows
	var result strings.Builder
	for i := 0; i < numRows; i++ {
		result.WriteString(rows[i].String())
	}

	return result.String()
}

func main() {
	fmt.Println(convertSimulation("PAYPALISHIRING", 3)) // PAHNAPLSIIGYIR
	fmt.Println(convertSimulation("PAYPALISHIRING", 4)) // PINALSIGYAHRPI
	fmt.Println(convertSimulation("A", 1))              // A
}

How It Works

We start at row 0 and move downward. Each time we place a character, we check whether we have reached a boundary row. If so, we flip the direction. The strings.Builder type is used for each row to avoid the overhead of repeated string concatenation, which would be expensive in Go due to string immutability.

This approach is easy to understand and implement. Its time complexity is O(n) where n is the length of the string, and its space complexity is O(n) for storing the row buffers.

Approach 2: Mathematical Index Calculation

The simulation approach works well, but we can also solve the problem by directly calculating which indices belong to each row. This eliminates the need for direction tracking and can feel more elegant once you understand the cycle pattern.

Implementation

package main

import (
	"fmt"
	"strings"
)

func convertMath(s string, numRows int) string {
	if numRows == 1 || numRows >= len(s) {
		return s
	}

	n := len(s)
	cycleLen := 2*numRows - 2
	var result strings.Builder

	for r := 0; r < numRows; r++ {
		for i := 0; i+r < n; i += cycleLen {
			// First character in the cycle for this row
			result.WriteByte(s[i+r])

			// Middle rows have a second character in the cycle
			if r != 0 && r != numRows-1 && i+cycleLen-r < n {
				result.WriteByte(s[i+cycleLen-r])
			}
		}
	}

	return result.String()
}

func main() {
	fmt.Println(convertMath("PAYPALISHIRING", 3)) // PAHNAPLSIIGYIR
	fmt.Println(convertMath("PAYPALISHIRING", 4)) // PINALSIGYAHRPI
	fmt.Println(convertMath("HELLOZIGZAG", 5))    // HOZILLGZAGE
}

How It Works

For each row r, we iterate through the string in steps of cycleLen. At each step, the character at index i + r belongs to row r. For middle rows (not the first or last), there is an additional character at index i + cycleLen - r within the same cycle. We append both characters to the result builder, being careful to check bounds before accessing the string.

This approach also runs in O(n) time and uses O(n) space for the result builder, but it avoids maintaining separate row buffers and direction state. The logic is more mathematical and less stateful, which some developers find cleaner.

Comparing the Two Approaches

Both approaches produce identical results and have the same asymptotic complexity, but they differ in style and readability:

• Simulation: More intuitive for beginners. The direction-flipping logic mirrors how you would physically draw the zigzag pattern. It is easier to explain in an interview setting.
• Mathematical: More concise and avoids mutable direction state. It demonstrates a deeper understanding of the cyclic pattern but requires careful index arithmetic.

In practice, either approach is perfectly acceptable. Choose the one that you find easier to reason about and maintain.

Best Practices for Go String Building

When solving string manipulation problems in Go, following a few best practices will keep your code efficient and idiomatic:

• Always use strings.Builder: Go strings are immutable, so concatenating with + creates a new string each time, leading to O(n²) behavior. The strings.Builder type amortizes allocations and keeps operations O(n).
• Pre-size when possible: If you know the final length, call builder.Grow(n) to preallocate the underlying byte slice and avoid reallocations.
• Handle edge cases early: Check for numRows == 1, empty strings, and cases where numRows >= len(s) at the top of your function to simplify the main logic.
• Avoid unnecessary allocations: Reuse variables and avoid creating intermediate slices when a direct calculation suffices.
• Write table-driven tests: Go's testing package makes table-driven tests trivial, and they are ideal for verifying multiple input combinations.

Example: Pre-sizing the Builder

func convertOptimized(s string, numRows int) string {
	if numRows == 1 || numRows >= len(s) {
		return s
	}

	n := len(s)
	cycleLen := 2*numRows - 2
	var result strings.Builder
	result.Grow(n) // Preallocate exact size

	for r := 0; r < numRows; r++ {
		for i := 0; i+r < n; i += cycleLen {
			result.WriteByte(s[i+r])
			if r != 0 && r != numRows-1 && i+cycleLen-r < n {
				result.WriteByte(s[i+cycleLen-r])
			}
		}
	}

	return result.String()
}

By calling result.Grow(n), we ensure that the builder's internal buffer is large enough to hold the entire result, eliminating reallocations during the write operations. Since the output length equals the input length, this is a safe and effective optimization.

Writing Tests for Your Solution

A robust solution deserves robust tests. Go's built-in testing framework makes it easy to verify your implementation against multiple cases using table-driven tests.

package main

import "testing"

func TestConvert(t *testing.T) {
	tests := []struct {
		name    string
		input   string
		rows    int
		expected string
	}{
		{"basic 3 rows", "PAYPALISHIRING", 3, "PAHNAPLSIIGYIR"},
		{"basic 4 rows", "PAYPALISHIRING", 4, "PINALSIGYAHRPI"},
		{"single row", "PAYPALISHIRING", 1, "PAYPALISHIRING"},
		{"single char", "A", 1, "A"},
		{"empty string", "", 3, ""},
		{"rows exceed length", "AB", 5, "AB"},
		{"two rows", "ABCDEF", 2, "ACEBDF"},
	}

	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			got := convertMath(tt.input, tt.rows)
			if got != tt.expected {
				t.Errorf("convertMath(%q, %d) = %q, want %q",
					tt.input, tt.rows, got, tt.expected)
			}
		})
	}
}

Run your tests with go test -v to see detailed output for each case. Table-driven tests make it trivial to add new cases as you discover edge scenarios, and they document the expected behavior of your function in a single, readable block.

Common Pitfalls to Avoid

When implementing the ZigZag Conversion, developers often encounter a few recurring mistakes:

• Forgetting the numRows == 1 edge case: When numRows is 1, the cycle length formula 2*numRows - 2 evaluates to 0, which causes an infinite loop or division by zero. Always handle this case explicitly.
• Off-by-one errors in index calculation: The second character in a cycle for middle rows is at i + cycleLen - r, not i + cycleLen + r. Double-check your arithmetic.
• Not checking bounds before indexing: Always verify that i + cycleLen - r < n before accessing s[i+cycleLen-r] to avoid panics.
• Using string concatenation instead of Builder: This leads to poor performance on large inputs. Always prefer strings.Builder for accumulating string output.

Conclusion

The ZigZag Conversion problem is a fantastic exercise in pattern recognition and string manipulation. By understanding the cyclic nature of the zigzag layout, you can implement an efficient O(n) solution in Go using either a simulation approach with row buffers or a mathematical approach with direct index calculation. Both methods leverage strings.Builder for efficient string construction, and both handle edge cases gracefully when implemented carefully. Whether you are preparing for a coding interview or simply sharpening your Go skills, mastering this problem reinforces valuable habits: identifying cycles, managing indices precisely, writing table-driven tests, and choosing the right data structures for the job. With the techniques covered in this guide, you are well-equipped to tackle the ZigZag Conversion and similar string manipulation challenges with confidence.