Author Archives: adam

Leetcode 149: Max Points on a Line

For every point we need to compare the slope to every other point and remember the most that are the same. The obvious way to calculate slope is y/x but that could suffer from floating point rounding errors when comparing … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 145: Binary Tree Postorder Traversal

A recursive solution is very simple, it just recurses into the left node then recurses into the right node and then handles the current node. The iterative solution is more difficult to come up with. The trick with iterative is … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 140: Word Break II

The easiest way to solve this is recursively with memoization. Note that there is a horrible test case that makes my iterative DP solution fail. That test case is not fair because those sorts of length strings will never work … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 135: Candy

In the O(n^2) solution we just start with all 1s and then we step through each element and if ranking[i] is bigger than it’s neighbours and candy[i] is not then add 1 to candy[i]. Repeat that until we make no … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 132: Palindrome Partitioning II

The obvious fairly simple recursive solution is very slow (exponential). The recursive base case start->end is 1 char or isPalindrome(start->end) return 0 cuts. In the recursive function we go through each character in the range trying to place a cut … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 128: Longest Consecutive Sequence

Solving this problem in O(n) time and space relies on using a hash set to store all numbers. You then go through each element in the array and see if a[n]-1 is in the set, and if it isn’t then … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 126: Word Ladder II

I used a similar approach to Word Ladder I (leetcode 126), where I used BFS to go through all adjacent words (1 character different). The main difference is that I need to keep track of the whole path, which I … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 124: Binary Tree Maximum Path Sum

The key here is that a single path through a node (through one child of the node rather than two) is fairly easily handled by using bottom up preorder traversal and checking which is bigger out of the left and … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 123: Best Time to Buy and Sell Stock III

We need to figure out max profit at each day going from left to right and going from right to left. We store those profits in two vectors called let and right. For each element in left we calculate the … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 115: Distinct Subsequences

My first attempt was a recursive solution without memoization, which I suspected would not pass all leetcode test cases and it didn’t. I then modified this to use memoization, which saved doing the same calculations over and over again. Here … Continue reading

Posted in programming | Tagged , , | Leave a comment