[Solution]Problem 4: ZigZag String [PayPal]

Medium Difficulty

Problem

This problem was asked by PayPal.

Given a string and a number of lines, print the string in a zigzag form. In zigzag, characters are printed out diagonally from top left to bottom right until reaching the kth line, then back up to top right, and so on.

For example, given the sentence "thisisazigzag" and k = 4, you should print:

——————————————————————————————————————.

Step 1: Simple Solution

Going over the problem and given example, we might notice something. To print zig-zag in the correct way, we need to make sure that the spaces between the characters in a row are calculated correctly. We can then save our representation as a matrix, and print it.

What should the dimensions of our matrix be? The example provides a useful hint. Our depth will be given our k value. Therefore we should have k rows. Since we want a zig-zag string, we know every column only contains one character. So we want len(sentence) columns.

Putting this all together we get

def zigzag(sentence, k):
    n = len(sentence)
    line_matrix = [[' ' for _ in range(n)] for _ in range(k)]

    row = 0
    for col, letter in enumerate(sentence):
        line_matrix[row][col] = letter

        if row == 0:
            descending = True
        elif row == k - 1:
            descending = False

        if descending:
            row += 1
        else:
            row -= 1

    for line in line_matrix:
        print("".join(line))

This algorithm requires O(k*n) time and space. How can we optimize this further?

Step 2: Analyzing the Components of the Solution

For problems such as this, it’s important to get into the components of the solution. The zigzag, variable depth, and arbitrary string length create a lot of moving parts. Working out these chinks will go a long way in helping us create an optimal solution.

Imagine we could go one line at a time, figure out what that line should be, and print it. An advantage of this method would be that we would only need O(N) space at any given time. Let's look at how this would work.

For the zigzag pattern in the example, we can see that the letters in the top and bottom lines are each separated by spaces. What about the middle lines? Here it depends on whether the pattern is descending or ascending. When we are ascending, we should put 3 spaces after the second line and 1 space after the third line, but if we are ascending the reverse is true.

How do we account for the number of spaces b/w 2 chars at a row? The first pair that has 3 spaces has 3 characters b/w them. Similarly, the next pair has only 1 char b/w them. And it has only 1 space. You should be able to see why the number of spaces b/w characters is equal to the number of characters b/w them. This takes advantage of the property that every column will have only one character.

Putting things together figure out the following formula for getting the spaces:

def get_spaces(row, desc, k):
    max_spaces = (k - 1) * 2 - 1
    if desc:
        spaces = max_spaces - row * 2
    else:
        spaces = max_spaces - (k - 1 - row) * 2
    return spaces

Share your explanations for the calculations in the comments below. The best explanation will get a shoutout+1 month free of the premium membership.

Next, we work out how to figure out whether we are ascending or descending. Note that if we have five rows, we will be descending for the first four, ascending for the next four, and so on. This can be represented mathematically like so:

def is_descending(index, k):
    if index % (2 * (k - 1)) < k - 1:
        return True
    else:
        return False

Note we did something similar in the simple solution. Look at when we say something and when it’s descending and how the code switches b/w them.

Putting these together, our algorithm will create a list of empty strings for the first row. After putting the first character in this list at the appropriate index, it will check whether the pattern is ascending or descending, find out how many spaces are needed, and move to the next index. When we get to the end of the row, we print it out and repeat this process for subsequent rows.

def zigzag(sentence, k):
    n = len(sentence)

    for row in range(k):
        i = row
        line = [" " for _ in range(n)]

        while i < n:
            line[i] = sentence[i]
            desc = is_descending(i, k)
            spaces = get_spaces(row, desc, k)
            i += spaces + 1

        print("".join(line))

Even though is_descending and get_spaces are constant-time operations, we still need to join and print each line of the string, which will take O(N) time, so the whole algorithm will be O(k * N).

Closing +Note about the Difficulty Level

Medium questions have a lot of variety. Sometimes they are relatively straightforward, with the challenge coming in the coding. This question, in particular, is difficult to optimize because of the many moving parts. That can be overwhelming at times.

The best way to approach this is to go one step at a time. Assume small constant values for the other variables, see how one changes the outcome. As you notice patterns you can develop the full solution.

Overall you should be able to solve this question in 35 minutes.

Bonuses/Promotion (Get Free Stuff)

To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:

Reach out to me on Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/