Monthly Archives: September 2019

Leetcode 67: Add Binary

Similar to the previous problem (Leetcode 66 – Plus One). Loop around both input strings from last char to first char. Add each digit and remember carries if needed. Source code for above solution:https://gist.github.com/adamkorg/7f7cc67a39fe8198ccdf1974c4eb7961And below is code for a slightly … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 66: Plus One

Straightforward. Just add one to the rightmost number and then perform a carry to next significant digits if necessary.

Posted in programming | Tagged , , | Leave a comment

Leetcode 65: Valid Number

This is not a great leetcode question because it is not clearly defined. This would be fine as a real interview question where you can work out the requirements by asking the interviewer questions but in leetcode you just have … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 64: Minimum Path Sum

This is a variation of the the two previous problems (Unique Paths). So we just use dynamic programming to calculate running costs at each cell in the grid. We add the current grid cell cost to the lesser value of … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 63: Unique Paths II

This is fairly similar to the previous problem “Leetcode 62: Unique Paths” but here we will set the memo cell value to zero if there is an obstacle in that cell, as there is no route to the finish from … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 62: Unique Paths

I came up with 5 different solutions for this: Simple recursive O(n!) Recursive with dynamic programming memoization O(nm) Iterative with dynamic programming O(nm) Mathematical using binomial coefficient O(max(n,m)) Mathematical using binomial coefficient optimised Source code for the different solutions:RecursiveRecursive with … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 61: Rotate List

This is an O(n) time, O(1) space solution. Find out list length by iterating through it. Recalculate k by mod len to reduce k to less than len. If new k is 0 return. Use slow and fast pointers to … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 60: Permutation Sequence

The simple, obvious, inefficient way to solve this is to call next_permutation() k times. But that results in O(n!), which is slow. It is also possible in O(n) time, which relies on cutting through the problem space for each digit. … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 59: Spiral Matrix II

Process using one layer at a time, starting from the outer layer. The fiddly bit is getting the matrix coordinates correct and I plan that up front taking out the complication of layers. Here is the code for the above … Continue reading

Posted in programming | Tagged , , | Leave a comment

Leetcode 58: Length of Last Word

This is an easy problem, iterate from end of string counting characters until we reach a space. I just wanted to make this post as a reminder to myself about creating a table of variable values when running through a … Continue reading

Posted in programming | Tagged , , | Leave a comment