Binary Search

Whenever I revisit binary search problems, I keep having to work out the edge cases whenever coming up with the algorithm. So I thought I’d make a note of the pseudo code template I always end up with:

l=0, r=0
while (l <= r) {
   m = l+(r-l)/2
   if (a[m] == target) return m
   if (a[m] < target) l = m+1
   else r = m-1
}
return -1  //not found 

This is a nice video lecture about binary search:
https://www.youtube.com/watch?v=GU7DpgHINWQ

Posted in programming | Tagged , | Leave a comment

Leetcode 45: Jump Game II

Only a linear solution will pass the leetcode tests. Use a three counters as we iterate: jumps, current steps left, next steps left. We only use next jump when we run out of current steps left. Continually update next steps left if the current position has > next steps left. I tried various other ways but they all timed out. Recursive is most obvious. Then recursive with DP memo. Then iterative DP O(n^2). Finally linear.

Source code for recursive+memo solution (too slow for leetcode test cases):
https://gist.github.com/adamkorg/4cd63f9cf0045ed58c9d9fd20712ef46
Iterative DP solution (also too slow for leetcode test cases):
https://gist.github.com/adamkorg/6bbd0487c0e29ec1d824d156e400cfc7
And here’s the linear solution that passes the leetcode test cases:

Posted in programming | Tagged , , | Leave a comment

Leetcode 30: Substring with Concatenation of All Words

Put words into hash map, step through each char in s checking for words in the hashmap. If we find a word then step through to the character after that match and attempt to match remaining words with the hash map. We need two separate hash maps, one will hold the counts of the words (as they can appear more than once in the words array) and the other will hold the counts for the current matching sequence. I call then counts and countsMatch respectively. It doesn’t make much difference how we reset countsMatch, I initially looped through resetting each element but then used countsMatch.clear(). One optimisation that makes a big difference is if we stop our outer loop of s when it is impossible to make a match, i.e. words.size() * words[0].size() characters before the end of s.

Posted in programming | Tagged , , | Leave a comment

Leetcode 23: Merge k Sorted Lists

There are a few different ways to solve this. I found the easiest way was to do a merge k-1 times. So you merge the first two lists. Then you merge that merged list with list 3. And repeat that until all lists are merged. That results in O(kN) time and O(1) space.

We improve the speed by either using a heap/priorityqueue or a map to allow us to quickly select the next smallest node out of the current nodes in all the lists. So we add the heads of all the lists to a map with the value as the key. We then remove the smallest (begin of map) and add it to our merged list. Then we add a new map entry of the next node of the node we just processed (if there is one). Repeat that until the map is empty. This results in O(Nlogk) time and O(k) space.

Here is the O(kN) time solution code: https://gist.github.com/adamkorg/665adeec343a9a114e1088833f96dbb8
And here is the O(Nlogk) solution code:

Posted in programming | Tagged , , | Leave a comment

Leetcode 10: Regular Expression Matching

The Kleene stars (the * wildcard character for regular expressions) make this difficult. We can’t just gobble up all the wildcard matching characters, otherwise subsequent matches might not work. One way to solve this is by recursing every possibility, so if we have p=“.*abc” and s=“xyzabcabc” then we call our match function with offsets match(s,p,0,2) then match(s,p,1,2) then match(s,p,2,2), etc.. until we have a complete match for the rest of the string. Note that once we’ve read all of string s then we need to step over any trailing wildcards, which don’t need any characters to match.

We can speed this up by using Dynamic Programming memoization to cache previous results. I have included the code for this below the non-memoized embedded code below.

DP solution: https://gist.github.com/adamkorg/67f7f5bd9eb1c8ae73f1e55c1d54d1b9

Posted in programming | Tagged , , | Leave a comment

Leetcode 4: Median of Two Sorted Arrays

Let’s call our two arrays A and B, where they have sizes a and b. A key insight is that we need to partition both arrays such that the left of both will be the same size as the right of both. The only exception is if we an odd total number of elements, in which case we will put the extra element in the left partition. Our partition index will be the start of the right hand partition. The partition can be before the first element 0, and up to after the last element arr.size(). Start with the smallest array as A. Start with our binary search constraints (hi and lo) as 0 to arr.size(). Calculate partitionA as (lo+hi)/2. Calculate partitionB as (a+b+1)/2-partA, where a and b are lengths of the arrays. Calculate the elements next to the partition. One thing to note here is that we use INF and -INF if an array’s partition is empty, which enables our comparisons to work. Check if we have reached our end condition, which is maxALeft <= minBRight and maxBRight <= minALeft, and if we have then return the value closest to the partition from left if odd or average of two closest values to partition from both left and right if even. Otherwise if not end condition the adjust the binary search bounds and loop again.

Key points:

  • Understand that we will partition both arrays and they need to be partitioned such that both left sides are the same size (or one more) than both right sides.
  • Understand we can use binary search to try to find the correct partition position in log(len) time.
  • The correct partition position will be when maxALeft <= minBRight and maxBLeft <= minARight. Where maxALeft is the biggest value in the left partition of array A.
  • The partition can be between any of the numbers in the array and can be before the first element and after the last element.
  • Start with binary search of first array (smallest array) to be lo=0 and hi=a.
  • Calculate partition A = (lo + hi) / 2
  • Calculate partition B = (a+b+1) / 2 – partA
  • Check if we are at the correct end partition position using calculated boundary values and if so then calculate median. If odd total number of elements then median is biggest value in left partition, which is: max(maxALeft, maxBLeft). If even then we need to get average of biggest in left and smallest in right, which is: max(maxALeft, maxBLeft)+min(minARight, minBRight) / 2.
  • If not at end partition position then step forward our binary search. If partition A is too far to right (maxAleft > minBRight) then we need to move our search to left half of search bounds, so: hi = partitionA – 1. The -1 is important as it allows us to get in front of the array. Otherwise move search to right half of search bounds, so: lo = partitionA + 1
Posted in programming | Tagged , , | Leave a comment

Trie Data Structure (Prefix Tree)

Use a TrieNode class that has a next member which is an array of 26 TrieNode pointers that represents a pointer to TreeNode object for each of 26 letters in the alphabet. We initialise these TrieNode pointers to NULL. We also have a bool member wordEnd initialised to false. An alternative, solution would be to use a hash map rather than vector to contain the next TrieNode pointers, which could contain a wider range of character sets.

class TrieNode {
public:
    vector next;
    bool wordEnd;
    TrieNode() : next(26, NULL), wordEnd(false) {};
};

We can then create a Trie class which will wrap the root TrieNode and a set of methods.
The Trie constructor creates a root TrieNode pointer member.
The Insert method steps through letters of the word, creating TrieNode objects and pointers in next as we go. Finally it sets wordEnd on the last letter.
The Search method goes through each letter in the word traversing through TrieNodes and returns wordEnd state on the final letter.
StartsWith is similar to search but it does not need the wordEnd check. I also created destructor that deleted all the TrieNode objects recursively.

Posted in programming | Tagged , | Leave a comment

Leetcode 188: Best Time to Buy and Sell Stock IV

To solve this we can use Dynamic Programming to gradually build upon previous solutions for t-1 transactions. The simplest to understand solution uses O(n²k) time and O(nk) space. We can optimise the time to O(nk) and space to O(n). The general idea of the algorithm is to step through the days of our current transaction row and see if we can add a transaction at any point of the previous row to increase the profit. See the whiteboard below to see the progression through the solutions to optimise time and space.

Inspired by the following great articles/videos:
https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/
https://www.youtube.com/watch?v=Pw6lrYANjz4 (algoexpert video)

Posted in programming | Tagged , , | Leave a comment

Leetcode 185: Department Top Three Salaries

Join Employee and Department tables by DepartmentId. In WHERE clause we need to filter to show only salaries higher than a subquery result. In that subquery we will try to return the third highest distinct salary. Do that subquery by listing Salaries of Employees ordered by Salary Descending and limit to 1 with offset 2. The problem is that departments with less than 3 employees will return an empty result set for that subquery, so we can make it return 0 by wrapping it in IFNULL(). Finally I order by department name and salary descending to make the output look nicer. I think it is also possible to solve this problem with the subquery logic returning a count distinct of salaries.

Here is the solution runnable online:
https://paiza.io/projects/BIfLpKxnZbaEOIjIk9f9EQ?language=mysql
And here is the code gist:

Posted in programming | Tagged , , | Leave a comment

Leetcode 174: Dungeon Game

My first attempt, where I tried top down DP, didn’t work. My second attempt used bottom up DP where I start from the last cell (bottom right) and work my way through to the first cell (top left). So at each cell we calculate its DP value by looking at its right and bottom neighbours to determine the minimum exit value we need to satisfy. So the calculated minimum entry value will be min neighbour – dungeon cell value. That calculated min entry value will be our dp cell. After calculating all dp cells our final result will be at cell 0,0 (top left).

Posted in programming | Tagged , , | Leave a comment