Home > Reflections | ⏮️ ⏭️

2024-06-13

🏋️ Solution Planning Practice

I want to try something a bit different today.
Rather than spending 15-90 minutes going deep by planning, implementing, and testing a single problem, I’m going to take a shallow, broad pass by reading and planning several problems.
I’ll try to limit each problem to 2-10 minutes of planning, focusing on identifying the key algorithms, data structures, or insights that will be critical in solving the problem, and that also imply runtime complexity.
For each problem, I should also rate my confidence in my proposed solution.
Some problems, I won’t know how to do at all.
Some problems, I’ll be confident that I can implement the optimal solution in reasonable time.
And many will likely fall somewhere in between.
After briefly reviewing many problems, maybe I’ll identify some patterns that can be useful in guiding my continued study and practice.
It could also be interesting to later return to these plans and practice implementing a solution based on a previously derived plan.
Separating the steps in time may help me understand how valuable the plans actually are and how easily I can turn my own plan into a working solution.

Here we go.

6. Zigzag Conversion

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

1. This is not a traditional algorithmic problem.
2. It’s really just about sequencing.
3. I’ll need to fill n rows in the correct sequence, then print the rows with the proper format.
4. Two approaches could be taken here:
   1. Compute the indices that should go on each row (this doesn’t seem like an obvious calculation)
   2. Iterate between the N rows in an up and down pattern, filling each one character at a time until we’re out of characters.
5. The second options seems easier to implement quickly.
6. We could track the direction we’re moving between the rows (up or down) and change directions when reaching the top or bottom.

This will take O(N) time in the size of the input string.
Filling the arrays and then printing will take an additional O(N) space that wouldn’t be necessary if we came up with a computation for the position of each character in the sequence.
This should be fairly straight-forward to implement. Getting the details with the direction exactly right and avoiding out of bounds and null pointer errors could be a bit fiddly.

Planning Time: 6:35

🔗 Reminds me of 59. Spiral Matrix II

Reviewing Official Solution

✅ The official solution describes 2 similar approaches to what I described above, also preferring the local, steering approach
Note: They point out that Time Complexity is actually O(N * numRows) due to the extra time taken to process all the spaces

7. Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

1. Reversing the digits is easy: toString → toArray → Reverse → join → parseInt
2. The trick, however, is in the constraint that we can’t store a number that’s out of range.
3. So we’ll have to be able to identify when a number would be out of the 32 bit signed range before converting the string of digits back to a number.
4. Alternatively, they might want us to detect overflow (i.e. we attempt to store a number bigger than can fit in 32 bits and the result is simply the wrong 32 bit number).
5. If we simply had to detect overflow, we could just convert the reversed number back to a string after parsing the integer and check if it’s the same string as before parsing.
6. If we have to proactively decide if the (reversed) number will be too large before converting it to an integer, we can try several approaches
   1. How many digits is the biggest (or smallest if negative) number we can fit in 32 bits? If our string is fewer digits, we’re fine.
   2. If our string has the max number of digits we can fit in 32 bits, we can check digit-by digit, from largest to smallest: if our reversed number’s ith digit is smaller or equal to the max (min) able to fit in that place, we’re fine. As soon as we find a digit that is strictly smaller, the remaining digits don’t matter.

There are log10 digits in a base-10 integer, and the amount of work we’re doing is proportional to the number of digits, so:
Runtime complexity: O(log(N)) in the passed in integer.
Storing the digits will take O(log(N)) space.
If the first approach is acceptable (I think we’d have to simulate this overflow effect in JavaScript), this implementation seems pretty easy.
Implementing the second approach is quite doable, but could get a bit messy in tracking all of the details.

Planning Time: 11:44

Reviewing Official Solution

✅ They describe a similar approach to what I described above.
✅ Same runtime (though I used extra space and they didn’t)

11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.

1. We want to find 2 lines that maximize the area of the rectangle formed between them
2. There’s an obvious, brute-force, O(N^2) solution that simply compares every line with every other line and computes the area for each
3. How can we reduce our search space?
4. Maybe we can compute a sort of rolling maximum while scanning left to right
   1. It’s never necessary to track a shorter line that comes after a taller line as the starting point
   2. Since we know how long the width is in advance, we can drop from consideration short starting lines with max values that are smaller than an option we’re already tracking
   3. Maybe we always keep track of the tallest starting and ending lines that we’ve seen

We can make a single forward pass and filter the list to all candidate starting lines.
Algorithm: keep all lines that are strictly taller than the previously kept line

We can do the same thing in reverse, keeping for consideration ending lines in increasing height (from end to start)

Then we can compare each start line with each end line.

In the worst case, we have a sort of pyramid where the lines grow to the middle, then shrink to the end
Then we still have N/2 start lines to compare to N/2 end lines, which is still O(N^2)
Example:
values : 1 2 3 3 2 1
indices: 0 1 2 3 4 5
In this case, we don’t need to make all comparisons, we only need to compare a start line with the furthest end line that is equal or shorter in height.
So we’d compare the following pairs of indices:
0,5 = 1 x 5 = 5
1,4 = 2 x 3 = 6
1,5 = 1 x 4 = 4 ← didn’t need because 0,5 already used 5, thus is taller because it’s wider
2,3 = 3 x 1 = 3
2,4 = 2 x 2 = 4 ← didn’t need because 1,4 already used 4, thus is taller because it’s wider
2,5 = 1 x 3 = 3 ← didn’t need because 1,5 already used 5, thus is taller because it’s wider

So maybe we can do this:

1. O(N) scan left to right finding candidate starting positions
2. O(N) scan right to left finding candidate ending positions
3. O(N) scan left to right, tracking a rolling max, comparing to the furthest end line that is equal or shorter in height AND hasn’t already been compared earlier

runtime complexity: O(N)
space complexity: O(N)

Planning Time: 40:52

I’m not 100% confident that this is correct, but very close to it.
I think I could implement this without too much trouble.

Reviewing Official Solution

❓ They have a 2 pointer solution that runs in linear time and looks quite a bit different than mine.
I believe that these algorithms amount to the same thing, but just looked at from different perspectives.
In my algorithm, I used extra space, where they didn’t have to.

• To be sure, I should implement my solution and see if it works.
  Note: this is yet another application of the 2 pointer pattern, which seems to turn O(N^2) brute-force solutions into clever O(N) solutions.

12. Integer to Roman

Seven different symbols represent Roman numerals with the following values:

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

• If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
• If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
• Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.
  Given an integer, convert it to a Roman numeral.

1. This problem seems amenable to recursion:
   1. decide the first symbol to use, based on the rules
   2. subtract the value of that symbol from the input value
   3. make a recursive call using the remainder of the input
   4. base cases: 0 (empty string) and any value in a lookup table of numbers to their roman numeral symbols

Time complexity: roman numerals follow a kind of logarithmic pattern, similar to Arabic numerals, so this feels like O(log(N)) in the number provided for conversion.
Space complexity is the same, and only needed for storing the output string.
I’m pretty confident I could code this up without much trouble.

Planning Time: 7:56

Reviewing Official Solution

✅ They propose an iterative version of the recursive solution I describe above.
Note: they claim O(1) time complexity due to the fixed upper bound on the roman numeral size. I guess that’s technically correct, but it’s a pretty big constant. I think the logarithmic argument applies equally well, but don’t think it’s particularly useful to argue the point.

15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

1. The obvious brute force solution is to assemble all triplets and filter them by which of them sum to 0
   1. O( N choose 3 ) = something like O( N! * K! * / (N - K)! ) … roughly exponential, which is unacceptable
2. I’ve worked on 2Sum and 3Sum somewhat recently, and recall that there are a couple of tricks:
   1. For 2Sum O(N * log(N)) time complexity / O(1) extra space complexity:
      1. sort the input, small to large
      2. use 2 pointers, starting at either end of the list
      3. if the sum is too small, increment left pointer
      4. if the sum is too big, decrement right pointer
      5. if the sum is equal, add the pair to the result set
      6. continue as long as the pointers aren’t equal
   2. Alternatively O(N) time complexity / O(N) extra space complexity:
      1. O(N) build a hash map from values to (lists of) indices
      2. O(N) for each value, check for target - value in the hash map, with different index
3. O(N^2) For 3 Sum, we can
   1. For each element E, fix 1 pointer at this element
   2. Apply 2Sum with the target = -E on the remainder

I believe I could implement either of these without too much difficulty.
I’m not sure I could explain exactly why the 2 pointers method works.
The hash map approach seems straight-forward to explain.

Planning Time: 16:09

Reviewing Official Solution

✅ They describe the same approaches I’ve described above, with some extra tips to avoid duplicates.
✅ Same O(N^2) runtime

🪞 Reflections

1. 5 problems planned, ranging from ~6 → ~40 minutes of planning time each.
2. Okay, so that’s still quite a bit of time spent on each problem. This isn’t necessarily a bad thing. I thought about each problem carefully and believe I came up with plans for workable solutions.
3. Even though it took about 40 minutes, I’m pretty happy with having come up with (what I believe to be) a linear time solution to 11. Container With Most Water
4. I want to try covering more problems to an even shallower depth, perhaps just reading the problem, coming to understand it, and jotting down any ideas that immediately come to mind. Maybe I time box this to time to read and understand the problem + 2 minutes.
5. However, before I move on, I think I should look at posted solutions for these problems to determine if my plans should actually work. I’d hate to convince myself that I’ve come up with a correct solution that turns out to be incorrect.
6. After reviewing the official solutions, I’m confident in all of my plans with a possible exception in 11. Container With Most Water. I think they amount to the same thing (but can’t know for sure without implementing it), the the official solution is more elegant.

⚡ Rapid Fire Solution Planning Practice

16. 3Sum Closest

1. Modify 3Sum to keep track of the triple with the value closest to the target

Planning Time: 0:54

17. Letter Combinations of a Phone Number

1. The inputs are incredibly short (up to 4 digits) so we could just hard code 4 nested for-loops, only use the ones we need, and loop over the possible possible characters creating the output array.
2. Runtime complexity is O(3^N) in the number of digits of the phone number provided

Planning Time: 2:44

18. 4Sum

1. Dare we use a linear pass, applying 3Sum at each index, resulting in an O(N^3) algorithm? I don’t see why 4 would be special.

Planning Time: 1:43

19. Remove Nth Node From End of List

Question: is the list always at least N nodes long? If not, we probably just return the list unchanged.

1. Store the head as the result
2. The trick is that we don’t know how long the list is, so we have to somehow iterate to the end and prepare to know which node was N nodes behind.
3. I think we can do the following:
   1. Store the head to return as the result
   2. Store the head again as our n-back cursor
   3. Create a new cursor and iterate across n nodes
   4. Now, for each additional iteration down the list, we iterate both cursors
   5. When we reach the end of the list, we have the node that is n behind our current position
   6. Okay, I guess we should be storing the (N + 1)th node back in our other cursor, so we can rewire the pointer to the node 2 in front of it
4. Runtime complexity: O(N), Extra space complexity: O(1)

Planning Time: 5:14

22. Generate Parentheses

1. Ooh, this seems a bit tricky.
2. We’ll have to understand how many valid ways we can open and close parentheses.
3. It’s a combinatorics problem.
4. We always must start by opening the first parenthesis.
5. Then, if N > 1, we have a choice of closing our first or opening our second.
6. At the third place, if N > 2, we have a choice of closing our first or second or opening our third.
7. A clear solution doesn’t pop into mind, but I’m thinking about bitstrings for encoding the choice of whether to open or close another paren.
8. I wonder if there’s a recursive solution that makes this easier… I think so, because we’ve got a backtracking kind of thing going on.
9. A stack is usually helpful in knowing when we can close a paren
10. Let’s see, recursively, this might look something like:
11. base cases:
    1. we have open parens available, but can’t close any, so open one
    2. we have no open parens available, but we have some to close, so close one
12. recursive steps:
    1. we could open or close a paren, so do both and recurse in each case
13. I think the recursive function arguments may need to include a stack (or perhaps a counter for how many unclosed open parens are in the input string; as well as a prefix string
14. This isn’t a perfect plan, but I think something to this effect will work and want to time box this exercise.
15. Runtime complexity of back tracking: something like… well, all combinations makes me think O(2^N), but the constraint on well-formed pairs may cut this down considerably. If I had to guess, I’d say something closer to O(N^2)

Planning Time: 13:38

24. Swap Nodes in Pairs

1. Linked list pointer rewiring… okay
2. We’re just doing swaps.
3. Linked lists are recursive data structures, so maybe recursion can save us some complexity.
4. How about this:
   1. initialize 3 cursors
   2. track the first 3 elements with them
   3. rewire the pointers
   4. save the new head as the return value
   5. recursively swap on the 4th element
   6. return the original head
5. Be careful with null pointers and detecting the end of the list
6. O(N) runtime, O(1) space
7. Seems like a bit of a pain to implement, but may not be too bad with recursion.

Planning Time: 5:37

26. Remove Duplicates from Sorted Array

1. Initialize 2 pointers: one for reading, one for writing
2. Scan from left to right
3. when duplicates appear, advance the reading pointer until the next unique element is found
4. write that element to the writing pointer and advance the writing pointer
5. continue forward, writing each element from the reading pointer to the writing pointer, except for duplicates, which we skip
6. Runtime complexity: O(N), O(1) extra space

Planning Time: 3:38

28. Find the Index of the First Occurrence in a String

1. If we’re allowed to use built-ins, I’m pretty sure find does this for us.
2. If we’re not allowed to use built-ins:
   1. Scan the input string left to right, looking for the first occurrence of the first character of the needle string
   2. when the first character of needle is found, continue scanning (with a new pointer) to see if the whole match is found
   3. If so, return the start index
   4. else continue scanning left to right
3. Runtime complexity: O(n * k) where n is the length of the input string and k is the length of needle

Planning Time: 3:44

31. Next Permutation

1. 🤔 A bit tricky
2. Observations
   1. If the input array is in ascending sorted order, we swap the last 2 elements
   2. If the input array is in descending sorted order, we reverse it
3. Almost seems like we can start at the end of the array and ask: is this element greater than the one previous?
   1. If so, swap them and we’re done
   2. Else step toward the front of the array and ask the same question again
   3. If we have to swap any but the last, sort the tail remainder in ascending order
4. That’s the best I’m coming up with right now.
5. Using a sophisticated (merge or quick) (in-place) sorting algorithm would give us O(N * log(N)) runtime complexity.
   1. But it could be a challenge to implement that in an interview
   2. Using a bubble sort would be easier, but take O(N^2) runtime complexity.
6. Maybe I should practice implementing merge or quick sort 😬

Planning Time: 12:50

32. Longest Valid Parentheses

1. drop any initial open parens
2. drop any final close parens
3. initialize an array of length of string
4. scan left to right
5. Initialize a counter to zero
6. For each paren, subtract one if it’s a closing paren, add one if it’s open
7. At each position, set the value of the array to the current count
8. The longest valid substring starts at the first zero and ends at the last zero
9. Runtime complexity: O(N); extra space: O(N)

Planning Time: 6:21

🪞 Reflections

1. I covered a lot of problems by skipping implementation.
2. I didn’t quite keep planning time as low as I wanted to on this last session, but I still go through 10 problems. Maybe I’ll use a timer next time.
3. It could be worth going back to the problems I couldn’t think of a solution for and try to work those out.
4. Or perhaps, the signal here is that I’m able to come up with decent solutions. Maybe I need to work on coding speed next.
5. I’ll call it a day for now.