The Zigzag Challenge: Solving the Conversion Problem with Algorithms and Data Structures

11 min readFeb 2, 2023

The Movie Twist: If Superman was learning Data Structure and Algorithm the story would be different.

SYNOPSIS: Superman, a journalist by day, discovers the world of data structures and algorithms and uses his powers to solve the challenging problem of zigzag conversion in a thrilling and unexpected twist. Will he save the day in the tech world too?

The opening scene shows the journalist, Clark Kent, sitting at his desk at the Daily Planet in Metropolis. He appears to be typing away on his computer, but as the camera zooms in, we see that he is not typing anything. Instead, he seems to be staring intensely at the screen, as if he is reading something that is not there. Suddenly, his eyes widen and he quickly stands up, grabs his coat and rushes out of the office, leaving his coworkers confused.

As Clark makes his way through the streets of Metropolis, we see that he is using his super speed to quickly scan through rows and rows of code on his phone, seemingly searching for something specific. He comes to a stop in front of a building, the headquarters of a Tech Company, and enters. Inside, he is greeted by a group of developers and technologists working on a mysterious problem, “THE ZIGZAG CONVERSION.”

Clark approaches the team leader and explains that he has a unique ability, he can read minds and has the power of speed reading. He offers his help to solve the problem, but the Tech Manager is hesitant, not believing that such powers could even exist. Since no one had solve this problem just yet. But Clark assures them that he is serious and offers to prove it by solving the problem and learning coding on the way.

INT. METROPOLIS — TECH OFFICE — COMPUTER -READING & TYPING

Narrator: Superman is sitting in the Tech office start explaining the problem. As he opens the website, he start speed reading.

Problem Leetcode: Mysterious Zigzag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

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"

Constraints:

1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ',' and '.'.
1 <= numRows <= 1000

Scene: Clark has seen the problem, now he is teaching the Developers the steps to solve the mysterious ZigZag Conversion.

Step 1: The Struggle

INT -THE CONVERSATION

Scene: Data Structure

Superman: Imagine you have a string of letters, like a secret code, and you need to unscramble it. But instead of just reading it straight across, you have to read it in a zigzag pattern, like a labyrinth. The key to solving this problem is understanding the underlying data structure and algorithm.

Developer: What is Data Structure?

Superman: According to google data structure is a specialized format for organizing, processing, retrieving and storing data. There are several basic and advanced types of data structures, all designed to arrange data to suit a specific purpose. Data structures make it easy for users to access and work with the data they need in appropriate ways.

Examples: Data Structures are Arrays, Linked Lists, Stack, Queue, Trees

Arrays: An array is a collection of similar types of data. Code example below show the array cannot store more than 100 names. The number of values in a Java array is always fixed.

1. //ArrayExamples
String[] array = new String[100];

2. Linked Lists : The LinkedList class of the Java collections framework provides the functionality of the linked list data structure (doubly linkedlist)

Each element in a linked list is known as a node. It consists of 3 fields:

Prev — stores an address of the previous element in the list. It is null for the first element
Next — stores an address of the next element in the list. It is nullfor the last element
Data — stores the actual data

import java.util.LinkedList;

class Main {
  public static void main(String[] args){

    // create linkedlist
    LinkedList<String> animals = new LinkedList<>();

    // Add elements to LinkedList
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);
  }
}

3. Stack: A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack is removed first.

//Example of Stack 
import java.util.Stack;

class Main {
  public static void main(String[] args) {

    // create an object of Stack class
    Stack<String> animals= new Stack<>();

    // push elements to top of stack
    animals.push("Dog");
    animals.push("Horse");
    animals.push("Cat");
    System.out.println("Stack: " + animals);

    // pop element from top of stack
    animals.pop();
    System.out.println("Stack after pop: " + animals);
    }
}

There are some basic operations that allow us to perform different actions on a stack.

Push: Add an element to the top of a stack
Pop: Remove an element from the top of a stack
IsEmpty: Check if the stack is empty
IsFull: Check if the stack is full
Peek: Get the value of the top element without removing it

4. Queue: Queue follows the First In First Out (FIFO) rule — the item that goes in first is the item that comes out first.

Basic Operations of Queue

A queue is an object (an abstract data structure — ADT) that allows the following operations:

Enqueue: Add an element to the end of the queue
Dequeue: Remove an element from the front of the queue
IsEmpty: Check if the queue is empty
IsFull: Check if the queue is full
Peek: Get the value of the front of the queue without removing it

5. Tree: A tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes

Binary Search Trees(BSTs) are used to quickly check whether an element is present in a set or not.
Heap is a kind of tree that is used for heap sort.
A modified version of a tree called Tries is used in modern routers to store routing information.
Most popular databases use B-Trees and T-Trees, which are variants of the tree structure we learned above to store their data
Compilers use a syntax tree to validate the syntax of every program you write.

INT-OFFICE-DEVELOPER-SUPERMAN CONTINUES READING & EXPLAINING

Developer: What is next?

Superman: Algorithms, think of algorithms as a set of rules, like the laws of physics, that tell a computer what to do. These rules help the computer make decisions, solve problems, and accomplish tasks efficiently, just like my abilities allow me to use my powers for good. But unlike my powers, algorithms need to be carefully crafted and tested to ensure they work correctly every time. By understanding and utilizing algorithms, we can harness the power of technology to make the world a better place.

INT -ALGORITHMS

Scene: Algorithms

Developer: What are the types of Algorithms?

Superman: “According to google there are seven types of algorithms are the brute force-based algorithm, greedy algorithm, recursive algorithm, backtracking algorithm, divide and conquer algorithm, dynamic programming algorithm, and randomized algorithm.”

INT-OPEN THE DOOR-MANAGER IS OUT OF BREATH

Tech Manager: Superman, we’re running out of time! The world depends on us to solve the Mysterious Zigzag Conversion.

Superman: Listen closely, as I give you a brief rundown of these seven algorithms.

Brute Force-based Algorithm: An algorithm that tries all possible solutions to a problem and checks if any of them work. It is straightforward and simple but may not be efficient for larger problems.
Greedy Algorithm: An algorithm that makes the best choice at each step to reach the optimal solution. It prioritizes immediate benefits over long-term benefits.
Recursive Algorithm: An algorithm that solves a problem by breaking it down into smaller subproblems and solving those subproblems recursively.
Backtracking Algorithm: An algorithm that explores all potential solutions to a problem and abandons a potential solution as soon as it determines it cannot lead to a solution.
Divide and Conquer Algorithm: An algorithm that solves a problem by dividing it into smaller subproblems and solving those subproblems independently.
Dynamic Programming Algorithm: An algorithm that solves a problem by breaking it down into smaller subproblems and remembering the solutions to those subproblems to avoid redundant work.
Randomized Algorithm: An algorithm that uses random numbers to solve a problem. It can be useful when finding an approximate solution is sufficient or when other algorithms are too slow.

INT-OFFICE-DEVELOPER-THE SHOCK

Developer: WOW!

Superman: Remember, with this knowledge, we can harness the power of technology to make the world a better place.

INT. TECH OFFICE -UNDERSTANDING THE PROBLEM

Narrator: Superman is explaining the problem to the developers with all the steps.

Superman: Listen carefully, I’ll lay out the steps of the solution. Get your pens ready!

Scene: The developers are hanging on to every word as Superman rapidly explains the 7 steps to solve the mysterious zigzag conversion problem. They are fully focused and taking notes, ready to put the solution into action.

STEP 2: Understanding the Problem

The problem is asking to convert a given string into a zigzag pattern with a given number of rows, and then return the resulting string read line by line.

To solve this problem, you can follow these steps:

Create a 2D array or 1D array with the given number of rows and the length of the input string.
Initialize a variable row to 0 and a variable direction to 1.
Iterate through each character in the input string.
For each character, assign it to the current position in the (1D array or 2D array) and then update the rowand direction variables.
If the row is at the top or bottom of the (1D array or 2D array), change the direction variable to its opposite value.
After the iteration, iterate through the (1D array or 2D array) row by row and append each character to a result string.
return the result string.

INT. TECH OFFICE -THE IMPLEMENTATION

Narrator: As the clock ticked closer to the deadline, Superman finished explaining the intricacies of data structures and algorithms to the developer. The solution was clear, and it is now time to put that knowledge into action.

Developers: We are ready to proceed!

Superman: I’ll explain the solution first, We must ensure that every line of code is accurate and efficient.

INT. TECH OFFICE -THE TWIST-CHANGE OF PLANS

Scene: And so, with a few swift strokes of his pen, Superman drew out a diagram that mapped out the solution to the mysterious zigzag conversion. The developer listened intently, taking notes and nodding as Superman explained each step of the process.

STEP 3: Implementing a Solution

Superman: Now let’s write the code piece by piece. First, you define a class named Solution and within it, a method named convert which takes in two parameters: a String "s" and an integer"numRows".

The method starts by checking if (we check this by using an if statement)number of rows is equal to 1. If it is, the method immediately returns the input string as it is, since no conversion is needed.

Then it creates a new array of StringBuilder objects called sb with a size of numRows. Each element in the array is initialized as a new empty StringBuilder.

Next, it declares two variables named n which is the length of the input string and i which is initialized to 0.

The code then enters a while loop that continues as long as i is less than n. Within the while loop, there are two for loops.

The first for loop iterates through the range of 0 to numRows and appends the character at index i in the input string to the corresponding StringBuilder in the sb array and increases i by 1.

The second for loop iterates through the range of numRows-2 to 1 and appends the character at index i in the input string to the corresponding StringBuilder in the sb array and increases i by 1.

After the while loop, a new StringBuilder object named result is created. Then it iterates through the sb array and append each StringBuilder element to the result StringBuilder.

Finally, the method returns the result as a String by calling the toString() method on the result StringBuilder object.

So the code reads the input string, convert them into zigzag pattern by storing them in StringBuilder array, then join all the element of the array into a single string and return the final string.

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        
        StringBuilder[] sb = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            sb[i] = new StringBuilder();
        }
        
        int n = s.length();
        int i = 0;
        
        while (i < n) {
            for (int j = 0; j < numRows && i < n; j++) {
                sb[j].append(s.charAt(i++));
            }
            for (int j = numRows-2; j >= 1 && i < n; j--) {
                sb[j].append(s.charAt(i++));
            }
        }
        
        StringBuilder result = new StringBuilder();
        for (int j = 0; j < numRows; j++) {
            result.append(sb[j]);
        }
        
        return result.toString();
    }
}

INT. TECH OFFICE -MANAGER RUSH-IN- clock ticking down!

Scene: The developers sat at their computer, eager to put their newfound knowledge of data structures and algorithms into practice. But before they could begin writing code, Manager Rushes in for a second time.

Tech Manager: Superman! Have we found a solution to the problem yet? The clock is ticking and we only have five seconds left!

Narrator (in the background): “The hands of the clock raced towards the final second. The fate of the world of tech hung in the balance. Superman sat at his computer, his eyes scanning the code. He had to act fast.”

Superman: (typing quickly) Yes, I have a solution! I’m writing the code now.

Narrator: “His fingers moved at lightning speed, his mind working with the efficiency of a supercomputer. The code flowed onto the screen like a river, every line flawless and precise.”

Tech Manager: Three seconds left! We need this code to work!

Narrator: “Superman’s expression was focused, determined. He had never been under this much pressure before. But he was Superman, and he was up to the task.”

Superman: (typing even faster) Got it! Compiling and executing now!

Narrator: “The code compiled without a hitch. The program ran, and the results appeared on the screen. The world held its breath.”

Tech Manager: And…we have a solution! The world of tech is saved!

Narrator: “The clock struck zero, and the room erupted in cheers. Superman had saved the day once again. The world of tech was secure, and the future looked bright.”

STEP 4: Conclusion

In the conclusion of the story, Superman once again saves the day by using his super power to learn Data Structures and Algorithms. He understood the assignment in mastering these concepts, and thanks to his expertise in technology, he was able to prevent a major disaster and protect the Tech Company of Metropolis.

Moral of the story is that, just like Superman, we all have the ability to unlock our full potential and achieve great things through continued learning and growth. Even though we might not have a superpowers.

Author: The city of Metropolis couldnt have a better day when Clark Kent save the day. Join me in the next chapter as I use my powers for good, and uncover the future of technology. Don’t miss the next chapter in my tech journey. — Toodle-oo

If you are interested in Product management tools check my previous blog “ Comparison of SDLC Methodologies.”

Do comment below and share your thoughts. I hope you have enjoyed learning about Data Structure and Algorithm through a leetcode problem.