Return to Revisions

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 (part one)

• 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 Thinking about the order letters within a row matching the order of letters in the input message me of [tree traversal