# Category Archives: programming

## 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

## Leetcode 99: Recover Binary Search Tree

The key observation is that the values should go up in an inorder traversal list and where they go down marks the value out of place. If the two out of place nodes are adjacent then we will have only … Continue reading

Posted in programming | Tagged , , | Leave a comment

## Leetcode 97: Interleaving String

I used recursion with DP memoization. A simple recursive solution will be O(2n) because there can potentially be a lot of repeating subtrees in the call graph. Memoization cuts out these duplicated paths. The idea is to recursively try all … Continue reading

Posted in programming | Tagged , , | Leave a comment

## Leetcode 85: Maximal Rectangle

We can use the Largest Rectangle in Histogram algorithm from leetcode 84, repeatedly over rows of column counts. This results in O(Rows * Cols) time and an extra O(Cols) space.

Posted in programming | Tagged , , | Leave a comment

## Leetcode 84: Largest Rectangle in Histogram

An O(n²) solution is simple but fails time limit on a leetcode test case. The O(n²) solution goes through each element and for each one it finds the next smallest to the left and next smallest to the right. That … Continue reading

Posted in programming | Tagged , , | Leave a comment

## Leetcode 76: Minimum Window Substring

My solution involves two pointers l and r to mark the begin and end of a sliding window. We will expand by incrementing r and shrink by incrementing l. So while we don’t have a complete window (complete in that … Continue reading

Posted in programming | Tagged , , | Leave a comment