Please don't get me wrong. The code works. Working code is a good thing. Working code that might break is not broken code.
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).
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.
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.
The function signature is
convert(String string_one) -> String string_two 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).
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])
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 row1 contains a character that is earlier in the message than row2. 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
"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
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(n2 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.
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
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.
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.