Trapping Rain Water 2D and 3D
This code is for solving the problem of being given a height map represented by either a 2D or 3D array, and calculating the maximum volume of water that could be held. These are both accomplished in an optimized fashion. The 2D solution exploits the fact that we can move a left and right pointer towards the center and iterate over the array only once, being able to always know what the lowest max to the left or right is for each visited space. The 3D solution uses a priority queue to visit each space, thus we can know the trapped water in each cell because we always visit adjacent cells from the lowest neighbor (with trapped water included).
Quick Merge Lists
This is code for a solution to a Merge K Sorted Linked Lists problem. This is, as far as I know, a novel solution to the problem. The best solutions utilize a divide and conquer approach, merging two lists at a time in a way that the lists are on average the same length, thus minimizing the number of comparisons done. Typically this is done iteratively by merging lists within a loop. My solution here takes a different approach, instead using a recursive divide and conquer algorithm similar to Quick Sort, effectively choosing a middle pivot element and merging the lists to the left of the pivot, and right of and including the pivot. This has similar performance to the iterative approach, having a Big O time complexity of O(N*Log(k)) in both cases, with N being the total number of nodes and K being the total number of lists.