Crack the Zigzag Code

Zigzag Conversion – Mastering Directional Patterns in Strings

Problem Statement

You're given a string s and an integer numRows. Your task is to return a new string that represents the original string written in a zigzag pattern over numRows, and then read line by line.

For example, if s = "PAYPALISHIRING" and numRows = 3, the zigzag would look like:

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

Reading row by row: "PAHNAPLSIIGYIR"

Best Data Structure for the Job

The most suitable data structure for this problem is an array of StringBuilders.

  • Each StringBuilder will represent a row in the zigzag pattern.

  • They're fast for appending and don't require manual resizing.

  • Efficient in both time and space for this use case.

Avoid using a matrix or list of lists — they add unnecessary complexity.

Different Approaches

1. Brute Force with 2D Character Grid

This approach simulates placing each character into a 2D grid. After the simulation, you scan the grid row by row and build the result.


public String convert(String s, int numRows) {
    if (numRows == 1 || s.length() <= numRows) return s;

    char[][] grid = new char[numRows][s.length()];
    int row = 0, col = 0;
    boolean goingDown = true;

    for (int i = 0; i < s.length(); i++) {
        grid[row][col] = s.charAt(i);

        if (goingDown) {
            if (row == numRows - 1) {
                goingDown = false;
                row--;
                col++;
            } else {
                row++;
            }
        } else {
            if (row == 0) {
                goingDown = true;
                row++;
            } else {
                row--;
                col++;
            }
        }
    }

    StringBuilder result = new StringBuilder();
    for (int r = 0; r < numRows; r++) {
        for (int c = 0; c < s.length(); c++) {
            if (grid[r][c] != 0) {
                result.append(grid[r][c]);
            }
        }
    }

    return result.toString();
}

Not recommended for production code, but great for visualizing the zigzag pattern if you're a beginner.

2. Directional Append using Row Tracking

This elegant approach simulates the zigzag path using an array of StringBuilders.

public String convert(String s, int numRows) {
    if (numRows == 1 || s.length() <= numRows) return s;

    StringBuilder[] rows = new StringBuilder[numRows];
    for (int i = 0; i < numRows; i++)
        rows[i] = new StringBuilder();

    int row = 0;
    boolean goingDown = false;

    for (char c : s.toCharArray()) {
        rows[row].append(c);
        if (row == 0 || row == numRows - 1) goingDown = !goingDown;
        row += goingDown ? 1 : -1;
    }

    StringBuilder result = new StringBuilder();
    for (StringBuilder sb : rows)
        result.append(sb);

    return result.toString();
}

Clean, readable, and effective — a great go-to approach.

3. Optimized Cycle-Based Indexing

Use math to determine exactly which indices belong to each row based on a cycle pattern.

public String convert(String s, int numRows) {
    if (numRows == 1 || s.length() <= numRows) return s;

    StringBuilder result = new StringBuilder();
    int cycleLen = 2 * numRows - 2;

    for (int row = 0; row < numRows; row++) {
        for (int j = row; j < s.length(); j += cycleLen) {
            result.append(s.charAt(j));
            int diag = j + cycleLen - 2 * row;
            if (row != 0 && row != numRows - 1 && diag < s.length())
                result.append(s.charAt(diag));
        }
    }

    return result.toString();
}

Ideal when performance is a priority. Super efficient for large strings and low row counts.

⚠️ Common Mistakes to Avoid

  • Flipping direction incorrectly (or not flipping at all) during row transitions

  • Using a 2D grid and forgetting to read characters row-wise afterward

  • Miscalculating the diagonal index in the cycle-based method

  • Ignoring edge cases like numRows = 1

📊 Time and Space Complexity Analysis

  • All three approaches run in O(n) time, where n is the length of the input string. Every character is visited exactly once.

  • Space complexity is also O(n) — you need extra space to store the transformed characters before returning the result.

Even the grid simulation is linear in space, although it allocates more than needed (wasting space in unused grid cells).

🌍 Real-World Applications

  • Stylized text rendering in apps or games

  • Secret message encoders in basic encryption methods

  • Data visualization or pattern-based layout generation


I hope you found this article insightful! Keep exploring, keep learning, and don’t forget to check back daily for more exciting problem breakdowns. If you know someone who would benefit from this, share it with them and help them grow too! That’s it for today—see you in the next post!

                                                                                                                                         Signing off!! 

                                                                                                Master DSA One Problem at a Time :)

Comments

Post a Comment

Popular posts from this blog

Trailing Zeros in Factorial – How Many and Why?

Trailing Zeros – Counting Zeros in Factorial Factorial-related problems are a fundamental part of Data Structures and Algorithms (DSA). One such classic problem involves counting the number of trailing zeros in N! . In this article, we will explore different approaches to solving this problem, optimize our solution, and examine its real-world applications. Optimal Data Structure for Solving the Problem For this problem, no additional data structures are required. Since factorials grow exponentially, storing the actual factorial value is impractical. Instead, we leverage mathematical properties and division operations to efficiently determine the number of trailing zeros. This approach ensures an optimal solution in terms of both time and space complexity. Approach – From Brute Force to an Optimized Solution Brute Force Approach – Compute and Count A naive approach involves computing the factorial of N and counting the number of trailing zeros. However, this method is highly ineff...
Read more

Divisible Drama — Who’s In, Who’s Out?

 Divisible Drama — Who’s In, Who’s Out? Problem Statement You’re given two positive integers n and m . num1 = sum of all numbers from 1 to n not divisible by m num2 = sum of all numbers from 1 to n divisible by m Your mission, should you choose to accept it: Return num1 - num2 Example Input: n = 10 , m = 3 Output: 19 Breakdown: Not divisible by 3 → [ 1 , 2 , 4 , 5 , 7 , 8 , 10 ] → num1 = 37 Divisible by 3 → [ 3 , 6 , 9 ] → num2 = 18 Answer = 37 - 18 = 19 Best Data Structure for Solving the Problem This one’s a math.  Why overthink it when Gauss already gave us the formula for sum of 1 to n? Different Approaches (from Brute Force to Optimized) Approach 1: Brute Force (aka List & Sum Vibes) Loop from 1 to n , split the nums based on whether they’re divisible by m , and sum them up. class Solution { public int differenceOfSums ( int n, int m) { int num1 = 0 , num2 = 0 ; for ( int i = 1 ; i <= n; i++)...
Read more

Zero Array After Queries

Zero Array After Queries You are given an integer array nums and a list of queries, where each query is a pair [li, ri] representing a range. Each query allows you to decrement any subset of elements in the range [li, ri] by 1. Your task is to determine if it is possible to make every element in nums equal to zero after applying all queries in order . Example Input: nums = [ 1 , 0 , 1 ] queries = [[0, 2]] Output: true Explanation: We can select indices 0 and 2 and decrement both by 1 to obtain [0, 0, 0] . Best Data Structure for the Job We are working with multiple range updates and need to evaluate coverage over indices. The best choice here is the difference array combined with a prefix sum . It allows efficient range additions and helps track how many times each index is affected by the queries. Different Approaches Approach 1: Brute Force This naive method iterates over every index for every query and performs the decrement operations directly. class Solution {...
Read more