adamk.org

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 this 2 pointer solution:

Here is an alternative solution that uses 2 passes. The first pass looks for ascending bars, keeping track of the maximum bar and previous maximum. When it finds a new maximum, it then calculates the area between this maximum and the previous maximum by iterating backwards. After this forward pass we then do a reverse pass, looking for ascending bars from back to front. There is one tricky edge case, which is two bars that are equal size and are bigger than the rest of the bars. I have a check for this in the second loop, which skips the calculation.

Source code for the 2 pass solution:
https://gist.github.com/adamkorg/142f8a73d8db07eec43117a0842e9541

There are a few different ways to solve this including some ways that destroy some of the (out of bounds) values. My favoured solution keeps all the values but just rearranges them. I iterate through all the numbers and at each I do a loop to swap the value with the value at the index of the value if it is in bounds and is not equal to this number. Finally we do another pass to see which index contains a number different from index+1.

Different solution using clearing out of bounds values and marking index positions with negatives:

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:

Code for this solution:
https://gist.github.com/adamkorg/8966ddf341efca934ee839da2d0353a6

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:

And the c++ source code for my solution:

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:

Here is my c++ source code for the solution:

We can optimise lookups when we are checking when a cell is valid. So instead of iterating through 9 values in the 3 different dimensions, we can store the presence of those 9 values in 3 vector of bools. We test the presence by looking in index of value-1. This does complicate the code somewhat as we now have a separate set of data to maintain.

Note the following test case “()(()” will trip up a simple counting algorithm, which was my first attempt. So I then used a stack to keep track of outstanding open bracket positions. When they are matched with a close bracket, we can mark them off in a boolean vector. We then count the longest consecutive sequence of “true”s in the bool vector. There is an alternative nice O(n) time O(1) space approach that uses the simple counting algorithm both from left to right and right to left.

A few observations need to be made to solve this problem efficiently. The best way to make those observations is to write out a bunch of sequences (I used most of 1,2,3,4). Notice that we need to look for a pair of decreasing numbers going from right to left. The left of that pair will be the left number of our swap. Now we need to arrange the remaining numbers in descending order from right to left. We can shortcut that by inserting the number we are replacing such that the sequence is ascending from right to left, so then we can just reverse that sequence. The right number to swap will be where we have the smallest number that is bigger than the left number. Once the swap is done, we then reverse numbers after the left number. If all the numbers are ascending from right to left then we are at the last sequence and to get back to the first sequence we reverse all the numbers. Beware of duplicate numbers, which need skipped over in some of the if statements.

So it turns out this algorithm was first discovered a long time ago. According to Knuth (in The Art Of Computer Programming 7.2.1.2), it goes back to the 18th century. This is a nice writeup of the algorithm:
https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
There’s also a nice video discussing this here:
https://www.youtube.com/watch?v=quAS1iydq7U

Here is my c++ source code for the solution:

This problem is similar to reverse a linked list but we wrap that in a loop so we do it repeatedly while there are k nodes ahead. We also need to wire the previous k sequence end with the the current new start.

Beware of a test case (list:[1], k:2) where k being bigger than number of nodes in list despite the problem description saying that wouldn’t happen.

A more efficient way is to not count ahead but instead undo the final reversal if we reach the end before we process k nodes. Maybe I’ll try that another time. Count ahead solution seemed simpler to code.

Here are my whiteboard notes for solving this problem:

And here is my c++ source code for the solution:

https://gist.github.com/adamkorg/fb698c0785845576ff0b42a091547691

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.

Use recursion to walk through the combination space. I use an array of codes, which maps the index to the letter combinations for that index. In the recursive function we loop through all the possible letters for the current number and then recurse into the next digit. I use backtracking to save on creating a whole new combination string for each recursive call.

This is a tricky little leetcode problem:
https://leetcode.com/problems/median-of-two-sorted-arrays/

Here are some of my observations on a whiteboard:

There are a lot of fiddly edge cases. I think my solution could be simplified but here is the gist anyway:

https://gist.github.com/adamkorg/ffba283f298e7c2c2b748acb49ccc9f1