Tag Archives: algorithms

Binary Indexed Tree (Fenwick Tree)

Binary Indexed Trees (also known as Fenwick Trees) are useful for finding sum ranges between two elements in a set of numbers, particularly when we need to update the numbers often. If we have a static set of values then … Continue reading

Posted in programming | Tagged , | Leave a comment

Boyer-Moore Majority Vote Algorithm

If we need to find a number that appears in more than half of the elements in an array, we can do so in O(n) time and O(1) space using the Boyer-Moore majority vote algorithm. We use a variable to … Continue reading

Posted in programming | Tagged , | Leave a comment

Smart pointers

Disclaimer: This is post is just showing example smart pointer implementations for illustrative purposes. In production code I would recommend using the standard library unique_ptr and shared_ptr instead. A basic smart pointer will wrap a pointer, so the object gets … Continue reading

Posted in programming | Tagged , | Leave a comment

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=a.size()-1 … Continue reading

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 … Continue reading

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 … Continue reading

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 … Continue reading

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 … Continue reading

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 … Continue reading

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 … Continue reading

Posted in programming | Tagged , | Leave a comment