[Solution]Problem 66: ZigZag String[PayPal]

Strings, Logic, Math

Nov 25, 2022

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

Take the next step by subscribing here

Every vote I got on yesterday’s poll said that Google Assistant was funny,

Y’all are the best community online. Impeccable taste. With that out of the way, let’s get right in.

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 the top right, and so on.

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

Step 1: Brute Force

This can be an intimidating problem, especially for bigger test cases. There are no obvious patterns. So we’re going to start small. Let’s attack the Bruteforce variant of the solution first. We can optimize after we have something working. No point in biting off more than you can chew.

So what is our brute force solution?

Going over the problem and the given example, I want you to 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. Nothing too shocking. Once we do figure this out, we can then save our representation as a matrix, and print it.

This gives us a new sub-problem to attack. What should the dimensions of our matrix be? The example provides a useful hint. Our depth will give us 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.

Building this should not be too difficult. I’ll leave it as an exercise for you, to help you build your skills. If you have a really hard time, let me know. I’ll share the code with you.

Since we are building a 2D array of k*n dimensions, 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. Regular subscribers will know how powerful this technique is. By attacking one moving part at a time, you can hack down some extremely difficult problems.

Technology Made Simple

[Solution]Problem 47:File Syncing Code [Google]]

To learn more about the newsletter, check our detailed About Page + FAQs To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email. I hope y’all had fun with this question yesterday…

3 years ago · 2 likes · Devansh

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 figure out 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 in 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.

We know that the spaces between a pair will depend on three factors- the row we are in, whether we are going up on down, and the total number of rows (k). Using a few small test cases and these variables, we come up with the following rule.

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

This might seem tricky, but take a little bit of time to figure out how this works. I’m not sure how to explain my exact thought process for deriving this, since it was a lot of trial and error and building up from smaller test cases. If this makes absolutely no sense, and you want me to go through the steps I went through to figure out this rule, I can create a video for it. Let me know if that is something you would like.

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

These are the two major components of our solution. If we know the number of spaces between two chars in the same row (line), and whether we go up or down after this, we can effectively print our string line-line.

With that out of the way, let’s start putting together our algorithm.

Step 3: Algorithm

Putting our components together, we create this algorithm-

Create a list of chars for the current row (initialized by empty space).
Put the first character in this list at the appropriate index.
Check whether the pattern is ascending or descending and find out how many spaces are needed. Use this to move to the next index.
When we get to the end of the row, print it out and repeat this process for the subsequent rows.

This way, we don’t save all the rows at the end. This cuts down on the amount of space we need from O(K*n) to O(n). Let’s code this up.

Step 4: Coding It Up

Our code for the problem will look like this-

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))

Nothing here should be too shocking if you followed the solution so far.

Time Complexity- O(k* n). Printing Each Line takes O(N) time and we have k lines to print. Challenge for you- Can you tell me the EXACT formula for the time complexity (not the Big O complexity)? Hint- It’s a summation.

Space Complexity- O(n)

Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.