The general steps to do long multiplication are fairly straightforward but the implementation was a bit fiddly. I think it would be easier to to reverse the strings and work on them in reverse, then the least significant index will be zero. It is a bit fiddly to do the other way, which is how I did it below:
This is a tricky leetcode problem. There are a few observations that need to be made. Water traps between two bars and only fills each of those gaps to a volume that is the gap’s height taken away from the smaller of the two enclosing bars’ height. It is easier to calculate if the two enclosing bars are ascending, in which case we just compare each gap’s height to the first bar’s height. Descending is more tricky as we need to look ahead to find the next tallest bar and that requires an extra array pass, which would result in O(n²). We can use a two pointer (left and right) technique to ensure that we are always solving ascending bounding bars. We just iterate the pointer that has the smallest enclosing bar (max height bar). Here are my whiteboard notes, which might make it clearer:
And here are is my c++ source code for the solution:
This is tricky and probably not typical of a real world problem, so I don’t know how useful it is know. Given the criteria of running it O(n) time and only using constant extra space, the only way we can solve this is by rearranging the array. As we know that we don’t need to consider negative numbers, we can use negatives as switches for each element position. A negative will mark that we have a number equal to the element’s index. As we sequentially read through the element values, we will mark them off by looking up indexes by using the values, so for value a[i] we will look up a[a[i]]. We then do another pass to find the first non-negative value, which marks the first missing positive. Here are my whiteboard notes:
This is a problem that fits naturally to a recursive solution. I’m not sure how I’d implement without recursion. The recursion automatically does a backtrack to find valid solutions. By starting the search for sub-items from the current item and bigger, we eliminate duplicates as the numbers will be in ascending order. Here are my whiteboard notes:
This was an interesting problem that highlights that sometimes it is better to write an algorithm for a computer to execute in a different way to how we would solve the problem with a human mind. So I first attempted to code this in a way in which I would manually solve a sudoku puzzle by walking through each number and analysing the impact of rows and columns on boxes. This resulted in complicated code and did not work on hard sudoku puzzles.
My second attempt at a solution used backtracking. The result was simpler code and the ability to solve the hardest sudoku puzzles. The algorithm stops at every space sequentially and tries every number until it finds a number that results in a valid board. If it gets to a square where no number will work then it backtracks to the previous square and continues its search through the numbers. Here is a nice visualisation of backtracking from wikipedia:
This was probably the easiest leetcode “hard” question that I’ve done so far. My first attempt worked on the two examples in the description but failed on the following test case “()(()”. My first attempt just used counters and did not use a stack. It reset the valid sequence when the current open bracket counter went to zero and we encountered a close bracket. It did not account for an unmatched open bracket in the middle as in the failed test case above. So to address that I keep track of a stack of open brackets with their positions in the string as the stack values. I also keep track of matched bracket positions in a boolean array. Here are my whiteboard notes:
My first thoughts for reversing the group was to have start and end pointers, switching those and then moving pointers one step inwards. This is logically how I would tackle reversing array elements but it does not work well with a linked lists (lots of traversing for end pointers and then keeping track of surrounding pointers). I then realised that we could reverse a group of nodes by traversing along the group using three pointers and adjusting those pointers as we go. We can then keep track of the last pointer of the previous group to link groups together. Here are my whiteboard notes:
Initially I started off with what I thought was a simple inefficient way of finding the next smallest node but the implementation was actually a little complicated. The multimap version is more time efficient and possibly has less complicated edge cases. I think an even more efficient way to keep track of the smallest node would be to use a priority queue.
Recursion is a very natural fit for this problem. Iterate through each letter of each digit and recursively go into each of those letters to the next digit. If we are at the last digit then we add the current whole combination while we iterate the letters. We need to keep track of the progress of each digit through recursion. I used a vector size of digits to keep track of progress. Here is a gist of the source code: