algorithms and problem solving
Solutions, and why they work.
Articles I wrote for LeetCode problems. Each one explains the reasoning behind a solution as well as the code.
leetcode 167 · Two Sum II - Input Array Is Sorted
Why the two-pointer solution to Two Sum II works
The mathematics behind the well-known two-pointer solution, and why each pointer move safely rules out a whole group of pairs.
Two pointersSorted arraysProof of correctness
read the article →leetcode 23 · Merge k Sorted Lists
Merging k sorted lists the way merge sort does
The common solution uses a heap. This one comes from merge sort, which at one point in its execution is merging k sorted lists, and it also runs in O(N log k) time.
Merge sortQueuesLinked lists
read the article →leetcode 33 · Search in Rotated Sorted Array
Searching a rotated sorted array by finding the pivot first
The problem splits into finding the pivot and then running an ordinary binary search. The two regions on either side of the pivot give the rules for finding it in O(log n) time.
Binary searchRotated arraysBreaking a problem down
read the article →