LeetCode ZigZag helper function code

Question

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

• I used a helper function approach after realizing that the "Grid" needs to be updated in the same manner over and over again

• I have received feedback that storing a grid may take too much memory

• Would a "mathematical" approach actually be more readable? And would it be something that can be though of within 20ish minutes (interview time)

• I have many if statements that are used to exit out of loops to avoid array index errors

Any feedback or criticism is appreciated - nitpick on anything that seems off

• glaring issue is that this doesn't handle edge cases well. For example: "A 2"

https://leetcode.com/problems/zigzag-conversion/

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        row = [''] * (len(s) // 2)
        self.s = s
        self.numRows = numRows
        self.final_grid = []

        for i in range(numRows):
            self.final_grid.append(list(row))

        self.addElements(0, 0)

        return "".join(map("".join, self.final_grid))


    def addElements(self, count, column):
        print(column, "beg")
        for i in range(self.numRows):
            if count > len(self.s) - 1:
                break
            self.final_grid[i][column] = self.s[count]
            count += 1

        for i in range(1, self.numRows - 1):
            if count > len(self.s) - 1:
                break

            self.final_grid[self.numRows - i - 1][column + i] = self.s[count]
            count += 1
            print(column, "end")
            print(column + self.numRows - 1)
        
        if count < len(self.s) - 1:
            self.addElements(count, (column + self.numRows - 1))

Answer 1

As you pointed out, you don't actually need to lay the characters out into a grid. It would be more efficient to use arithmetic to figure out the indexes of the characters in each row.

For example, if num_rows is 3, then each down-up cycle will consist of 4 characters. (zigzag_size = 2 * num_rows - 2). Then we also know that the top of each zigzag will consist of indexes 0, 4, 8, 12, … of the string (for z in range(0, len(s), zigzag_size)).

The middle row will consist of indexes z+1 and z+3. The bottom row will consist of indexes z+2. The zigzag_indexes() generator generalizes those calculations for any numRows.

import math

def zigzag_indexes(num_rows):
    yield (0, math.inf)                             # Top of each zigzag
    yield from zip(
        range(1, num_rows),                         # Downward
        range(2 * num_rows - 3, num_rows - 1, -1)   # Upward
    )
    yield (num_rows - 1, math.inf)                  # Bottom of each zigzag

def convert(s, num_rows):
    if num_rows == 1:
        return s
    zigzag_size = 2 * num_rows - 2
    return ''.join(
        (s[z+a] if z+a < len(s) else '') + (s[z+b] if z+b < len(s) else '')
        for a, b in zigzag_indexes(num_rows)
        for z in range(0, len(s), zigzag_size)
    )

print(convert('PAYPALISHIRING', 3))

Answer 2

Please don't get me wrong. The code works. Working code is a good thing. Working code that might break is not broken code.

Fundamentals

• Starting a Python module (or file in any language) with a comment describing what problem the code solves is helpful. It helps reviewers and future users understand what the programmer is trying to do. More importantly, it helps the programmer themselves understand what they are trying to do. Describing the problem first usually leads to better solutions.

• Starting Python functions with docstrings (or documenting functions/methods in other languages).

• Meaningful names. convert and addElement could be part of an alchemist's cookbook. Convert from what to what? Add what sort of element to what sort of aggregate?

• Language idioms: in Python, compound names use string_case not camelCase.

Leetcode

At a high level, Leetcode puzzles are designed as computer science challenges. The questions go beyond FizzBuzz's basic for loops and modulo application. Unlike FizzBuzz, good Leetcode answers are 'clever'...at least in the sense that they reflect application of computer science, experience, insight, etc.

Computer science, experience, insight, etc. help produce code that scales with about as much effort as writing brute force code. Brute force solutions are fine for FizzBuzz. They are not great solutions to Leetcode's puzzles.

The upside is that better solutions to Leetcode puzzles are easier to find with study and practice. Experience and knowledge help a programmer analyze its puzzles and provide insight into the problem at a high level.

What works for strings of length 1000 might sputter and stall at length ten billion...at least until the new hardware shows up or the AWS budget grows.

This problem

• The function signature is convert(String string_one) -> String string_two and string_one and string_two are the same multiset. That looks a bit like sorting. Many sorting algorithms that scale well on random data have space = O(n) and time = O(n log n).

• The grid solution in the question has space = O(mn) where m is the number of rows. That's worse than space = O(n), so we know we can do better...but only if we solve the right problem. One issue with the grid solution it solves a harder problem in order to solve the actual problem. The harder problem is pretty printing with all the spaces.

• The format of the question on Leetcode suggests the pretty printing solution. And pretty printing ultimately uses space = O(mn) because it has to include all the spaces and time = O(mn) because all those spaces get printed).

• Is time = O(mn) better or worse than time = O(n log n)? It depends. Here it is probably better because convert (my_string, 1) -> my_string and because convert(my_string, length(my_string) -> my_string. It looks like this is a case where time = O(mn) is linear. Which means it might not be a sorting problem.

A space improvement to the grid solution

One way to improve the space requirements is to only record the grid coordinates of the letters and ignore the spaces. For example "PAYPALISHIRING", numRows = 3 has an intermediate data structure [(1,1, "P"), (2,1,"A"}, (3,1,"Y")...(2,7,"G")]...a one-indexed list of tuples (row, column, string).

The high level solution (in psuedo-code) might be something like:

# Program A
temp_array =  make_array(input length)
for i in input
  temp_array[i] = get_row_and_column(input[i])
end for
return sort_into_rows(temp_array)

Sorting isn't free

As a starting point we should expect time = O(n log n) but pretty printing is probably linear time = O(mn). Smells like just recording grid coordinates has traded less space for more time. Another code smell is that we are generating a new value and sorting solely on that value. The original string doesn't play a role. Yoda's "HIRIINGISPAYPAL", numRows=3 produces a list tuples with identical row and column values.

This is why we have the intuition that a 'mathematical' solution is possible. We know that strings of the same length pretty print the same number of rows into congruent patterns.

I spent some time stuck on sorting.

I came to Program A not long after reading this question a few times and thinking about how to answer it. Thinking about sorting the grid got me worried about stable sorting even though it's ultimately not an issue because row, column is a unique value.

But the reason I was worried about sort stability was if I looked at a rows within the grid row₁ contains a character that is earlier in the message than row₂. Within a row, earlier values in the message are earlier values within a row. It's also true for columns, but it turns out rows are enough.

Improving on the grid and the sort

I spent a while thinking about the algorithm in terms of sorting and rows. Thinking lexographically. None of it was obvious. Eventually, it dawned on me.

output = row_1 + row_2 + ... row_n

for example

"PAYPALISHIRING", numRows = 4" -> "PIN" + "ALSIG" + "YAHR" + "PI"

and an O(n) solution might be

make a linked list for each row
for each character in the input
  determine its row
  place it at the end of the corresponding list
end for
concatenate the linked lists
output the concatenation

In terms of space, there are no empty nodes with linked lists. "PAYPALISHIRING", numRows = 4" produces rows 3,5,4,2. Using four arrays of size 5 would utilize 70% of the capacity...with array's it's still the grid.

Still stuck in sorting

Thinking in terms of rows changes a generalized sort into a [bucket sort(https://en.wikipedia.org/wiki/Bucket_sort). I knew I was in O(n) space but bucket sorting has a worst case of O(n² and that's worse than general sorting at O(n log n) even though intuition says it will be faster.

Making the problem simpler

Eventually it dawned on me. There's bucketing but no sorting. It's like dealing cards. An (honest) dealer deals round the table without considering the values of the cards. It's the same procedure when a hand is three cards as when a hand is five cards or seven. There is a cycle.

When the ZigZag is over three rows, row placement cycles (1,2,3,2). With four rows the cycle is (1,2,3,4,3,2). With five rows its (1,2,3,4,5,4,3,2). There is no conditional logic.

Some computer science

The length of the cycle is (2*numRows)-2. An algorithm for space = O(m+n) and time = O(m+n):

generate the cycle based on numRows

for each character in input
  put character at current row in cycle  
  next row in cycle

• There are tradeoffs regarding how the cycle is stored. One option is to use an array or list and keep track of where we are in the list and reset to the head of the list whenever we reach its end. Another alternative is to use a generator and call it each time we need another value. For example we might use itertools.cycle in Python. In the end, Python's itertools.cycle is probably going to be better than the code I am likely to write. YMMV.

• Is a one step solution better? Writing each character to the correct row and then merging the rows after all characters have been processed requires two reads and two writes for each character. Mathematically it is possible to allocate an output array and then write each character to it's appropriate place in a single step. This requires only one read and one write for each character.

• A difference between engineering and mathematics is that the one step solution assumes that input, output, and the program all fit in available memory. When they don't, the second reads and writes of the two step solution wind up happening implicitly.

• Many interesting data processing problems don't fit all into memory at once. The two step divide and conquer approach has the additional advantage of simpler logic than the pointer tracking required for a one step solution...fewer i's and j's is a good thing.

20 minutes to solve

If it's not obvious already, I spent more than 20 minutes thinking about the problem.

Leetcode revisited

Any problem I can solve in less than twenty minutes has to be a problem I can solve in twenty hours. Getting to good solutions quickly means having ideas about good and bad solutions in the context of Leetcode.

So there are two kinds of practice Leetcode offers. Practice at working through problems quickly and practice working through problems deeply. It's the depth makes Leetcode's puzzles interesting. It's the range of possible approaches that make it useful for bucket sorting programmers when programmers need to be bucket sorted.

Both kinds of practice matter. This answer went deeper than was ultimately necessary. But that depth might help us recognize when a question is simpler than first thought.

Answer 3

Earlier today I was driving home and came across this question, and thought of a method to do this in seconds.

1. Each message has a 'chunk' depending on the amount of rows.

   In the example, this is the first chunk:

   P
   A P
   Y
   

2. Each chunk uses the same indexes from the rest of the message. And so you can do a simple slice, message[start::chunk_size].

3. The size of the chunk is easy to calculate, as it increases by 2 for each row. Starting with 1, 2, 4 ...

4. You can determine the row the slice is on by:

   1. By going in order for the first row slices; and
   2. By going backward for the last row-2 slices starting from the second to last row.

   Take:

   1
   2 6
   3 5
   4
   

   At first I thought of this in a slightly different way, in which it was:

   1
   2 6
   3 5
     4
   

5. From this you just intertwine the rows in those indexes. Which was a recent Code Golf HNQ.

This can be achieved using the following code in under 20 minutes. Where the hardest part is (4).

import functools
import itertools
import operator


def intertwine(*lists):
    return functools.reduce(operator.add, itertools.zip_longest(*lists, fillvalue=''))


def change(text, rows):
    chunk_size = max((rows-1) * 2, 1)
    slices = [text[start::chunk_size] for start in range(chunk_size)]
    backward_rows = max(rows - 2, 0)
    rows = zip(slices[:rows], [''] + slices[:backward_rows + 1:-1] + [''])
    return ''.join([
        ''.join(intertwine(first, second))
        for first, second in rows
    ])

Answer 4

Although you already accepted an answer, here is my two cents.

The code:

Although recursive functions can lead to elegant solutions for some problems, in addElement() I think the recursive call complicates things. So I changed that to an iterative solution, and kept track of the column index. The function is also complicated by terminating the loops when you run out of letters in the string. This can be handled by iterating over the string and using a try ... except StopIteration construct to catch when the letters are exhausted. Note, we don't need to pass in count or column any longer.

def addElements(self):
    letter = iter(self.s)
    column = 0

    try:
        while True:
            # fill in down a column
            for row in range(self.numRows):
                self.final_grid[row][column] = next(letter)

            # fill in up a diagonal
            column += 1 
            for row in range(self.numRows - 2, 0, -1):
                self.final_grid[row][column] = next(letter)
                column += 1 

    except StopIteration:
        # ran out of letters
        pass

I think this is simple enough to move it into the convert() function:

class Solution:
    def convert(s, numRows):
        grid = [['']*(len(s)//2) for _ in range(numRows)]

        letter = iter(s)
        column = 0

        try:
            while True:
                # fill in down a column
                for row in range(numRows):
                    grid[row][column] = next(letter)

                # fill in up a diagonal
                column += 1 
                for row in range(numRows - 2, 0, -1):
                    grid[row][column] = next(letter)
                    column += 1 

        except StopIteration:
            # ran out of letters
            pass

        return "".join(map("".join, grid))

Getting rid of the grid

At the end, the final string is read out of the grid row by row, skipping the empty cells. Notice that within a row, the column just serves to keep the letters in the same order as in the original string. But this can be done by keeping a string for each row. Then iterate over the string adding the letters to the end of the appropriate row.

    def convert(s, numRows):
        rows = [''] * numRows

        letter = iter(s)
        column = 0

        try:
            while True:
                # fill in down a column
                for row in range(numRows):
                    rows[row] += next(letter)          # << append letter to the row

                # fill in up a diagonal
                column += 1 
                for row in range(numRows - 2, 0, -1):
                    rows[row] += next(letter)          # << append letter to the row
                    column += 1 

        except StopIteration:
            # ran out of letters
            pass

        return "".join(rows)

Direct calculation

The row number for a letter cycles through the pattern 0, 1, ..., numRows-2, numRows-1, numRows-2, ... 1, 0, 1, .... The length of the cycle is numRows + (numRows - 2) = 2*numRows - 2. So the position in a cycle can be found by index % cycle_length. With a little algebra, that can be converted to the row:

    def convert(s, numRows):
        rows = [''] * numRows
        cycle_length = 2*numRows - 2

        for i,c in enumerate(s):
            row = numRows - 1 - abs(numRows - 1 - i % cycle_length)
            rows[row] += c

        return "".join(rows)

Look ma, no math

Observe, that the row index starts at 0 and steps upward until it gets to the last row. Then it reverses direction and counts back down to 0, where it starts counting up again. Here is another take on a solution:

def convert(s, numRows):
    row = [''] * numRows

    index = 0
    step = 1

    for c in s:
        row[index] += c
        index += step

        # reverse step direction when hit the top or bottom row
        if index in (0, numRows-1):
            step = -step

    return ''.join(row)