When I am bored or get stuck on something, I like to solve puzzles and implement algorithms as a form of focused distraction.
This is a collection of my implementations of various things that I wrote to pass the time. They are in C++ and Obj-C because I enjoy working on those languages, but it's mostly C++ these days as I haven't done any iOS work in a while.
The data structures we take for granted.
The Red-Black tree especially was a lot of typing. You typically see it represented in books as about 20-30 lines of pseudocode, but when you actually code it its waaaaay more than that, especially if you are making it robust. This one was definitely more work than I expected.
Red Black Tree — Intruduction to Algorithms. Cormen, Leiserson, Rivest and Stein, MIT Press. (C++)
An implementation of trie. Never did one of these before, and it's been a hole in my knowledge for some time now. This was really fun to learn how it worked. Doesn't support delete. Yet.
For going on 30 years now I've had Donald Knuth's "The Art of Computer Programming" on my shelf, with the goal of someday working my way through it.
I once had dreams of getting a cheque. Now I think I'll be lucky to make it through one of the books. (If you know, you know).
This Leetcode solution is actually is Knuth's "Algorithm L" for generating the next permutation of elements, in lexicographical order, in place.
Leetcode № 31 (Medium) — Next Permutation (C++)
Heapsort — Intruduction to Algorithms. Cormen, Leiserson, Rivest and Stein, MIT Press. (Obj-C)
Mergesort — Intruduction to Algorithms. Cormen, Leiserson, Rivest and Stein, MIT Press. (Obj-C)
Quicksort — Intruduction to Algorithms. Cormen, Leiserson, Rivest and Stein, MIT Press. (Obj-C)
Improved Mergesort (C++)
Random cool things as well as snippets that can be dropped in to other projects so you don't have to re-type the wheel every time.
Heap's Algorithm for generating permutations (C++)
Fibonacci number generator (C++)
Drop in, int holding, memory safe linked list (C++)
This Binary tree implementation is sort of optimized for leetcode, which uses an array in the style of [1,2,null,4,6,7,null,8...] to represent the tree. I can't use a vector of ints because of the nulls, and I don't want to use a sentinel value which may occur in real data. This implementation uses std::optional, so you can put in std::nullopt in the data array.
Drop in, int holding, memory safe binary tree (C++)
Depth first search (C++)
If you are doing Leetcode you may find yourself typing the same thing over and over and over. Little things like dumping an array of ints, or a linked list, or building a tree from an array of values, etc. So I made a little cheatsheet (C++) that I can pull from.
Puzzles and problems from the meta careers interview preparation portal. These are sometimes annoying, because they often seem to be more word puzzles than software puzzles, but still rewarding when you get them working.
Cafeteria (C++)
Director of Photography (C++)
Kaitenzushi (C++)
Rotary Lock (C++)
Scoreboard Inference (C++)
Stack Stabilization (C++)
Uniform Integers (C++)
Director of Photography, Chapter 2 (C++)
Portals (C++)
Rotary Lock Chapter 2 (C++)
Balance Brackets (C++)
Balanced Split (C++)
Change in a Foreign Currency (C++)
Contiguous Subarrays (C++)
Counting Triangles (C++)
Encrypted Words (C++)
Matching Pairs (C++)
Minimum Length Substrings (C++)
Number of Visible Nodes (C++)
One Billion Users (C++)
Pair Sums (C++)
Revenue Milestones (C++)
Reverse To Make Equal (C++)
Rotational Cipher (C++)
slow-sums (C++)
Recently I've started re-visiting my old solutions to see how they held up to the test of time and improving their implementations as I've learned more.
Some of my earlier implementations were really bad. Like really, really, really bad.
As I go over these I have to keep reminding myself that this is a good thing. If I didn't look back at my code years later and see that it was bad, then that means that I haven't improved since I wrote it.
As of right now I am in the top 8% of Leetcode rankings!
Leetcode № 9 (Easy) — Palindrome Number (C++)
Leetcode № 14 (Easy) — Longest Common Prefix (C++)
Leetcode № 20 (Easy) — Valid Parentheses (C++)
Leetcode № 21 (Easy) — Merge Two Sorted Lists (C++)
Leetcode № 26 (Easy) — Remove Duplicates from Sorted Array (C++)
Leetcode № 27 (Easy) — Remove Element (C++)
Leetcode № 35 (Easy) — Search Insert Position (C++)
Leetcode № 67 (Easy) — Add Binary (C++)
Leetcode № 70 (Easy) — Climbing Stairs (C++)
Leetcode № 88 (Easy) — Merge Sorted Array (C++)
Leetcode № 94 (Easy) — Binary Tree Inorder Traversal (C++)
Leetcode № 100 (Easy) — Same Tree (C++)
Leetcode № 101 (Easy) — Symmetric Tree (C++)
Leetcode № 104 (Easy) — Maximum Depth of Binary Tree (C++)
Leetcode № 112 (Easy) — Path Sum (C++)
Leetcode № 118 (Easy) — Pascal's Triangle (C++)
Leetcode № 121 (Easy) — Best Time to Buy and Sell Stock (C++)
Leetcode № 125 (Easy) — Valid Palindrome (C++)
Leetcode № 136 (Easy) — Single Number (C++)
Leetcode № 141 (Easy) — Linked List Cycle (C++)
Leetcode № 163 (Easy) — Missing Ranges (C++)
Leetcode № 169 (Easy) — Majority Element (C++)
Leetcode № 202 (Easy) — Happy Number (C++)
Leetcode № 202 (Easy) — Happy Number (C++)
Leetcode № 205 (Easy) — Isomorphic Strings (C++)
Leetcode № 206 (Easy) — Reverse Linked List (C++)
Leetcode № 219 (Easy) — Contains Duplicate (C++)
Leetcode № 222 (Easy) — Count Complete Tree Nodes (C++)
Leetcode № 226 (Easy) — Invert Binary Tree (C++)
Leetcode № 234 (Easy) — Palindrome Linked List (C++)
Leetcode № 242 (Easy) — Valid Anagram (C++)
Leetcode № 257 (Easy) — Binary Tree Paths (C++)
Leetcode № 270 (Easy) — Closest Binary Search Tree Value (C++)
Leetcode № 283 (Easy) — Move Zeroes (C++)
Leetcode № 290 (Easy) — Word Pattern (C++)
Leetcode № 303 (Easy) — Range Sum Query Immutable (C++)
Leetcode № 338 (Easy) — Counting Bits (C++)
Leetcode № 345 (Easy) — Reverse Vowels of a String (C++)
Leetcode № 346 (Easy) — Moving Average From Data Stream (C++)
Leetcode № 349 (Easy) — Intersection of Two Arrays (C++)
Leetcode № 374 (Easy) — Guess Number Higher or Lower (C++)
Leetcode № 383 (Easy) — Ransom Note (C++)
Leetcode № 392 (Easy) — Is Subsequence (C++)
Leetcode № 408 (Easy) — Valid Word Abbreviation (C++)
Leetcode № 9 (Easy) — Longest Palindrome (C++)
Leetcode № 415 (Easy) — Add Strings (C++)
Leetcode № 496 (Easy) — Next Greater Element I (C++)
Leetcode № 509 (Easy) — Fibonacci Number (C++)
Leetcode № 543 (Easy) — Diameter of Binary Tree (C++)
Leetcode № 605 (Easy) — Can Place Flowers(C++)
Leetcode № 637 (Easy) — Average of Levels in Binary Tree (C++)
Leetcode № 643 (Easy) — Maximum Average Subarray I (C++)
Leetcode № 680 (Easy) — Valid Palindrome (C++)
Leetcode № 700 (Easy) — Sarch in a Binary Search Tree (C++)
Leetcode № 724 (Easy) — Find Pivot Index (C++)
Leetcode № 728 (Easy) — Self Dividing Numbers (C++)
Leetcode № 733 (Easy) — Flood Fill (C++)
Leetcode № 766 (Easy) — Toeplitz Matrix (C++)
Leetcode № 824 (Easy) — Goat Latin (C++)
Leetcode № 844 (Easy) — Backspace String Compare (C++)
Leetcode № 872 (Easy) — Leav Similar Trees (C++)
Leetcode № 933 (Easy) — Number of Recent Calls (C++)
Leetcode № 938 (Easy) — Range Sum of BST (C++)
Leetcode № 977 (Easy) — Squares of a Sorted Array (C++)
Leetcode № 1071 (Easy) — Greatest Common Divisor of Strings (C++)
Leetcode № 1207 (Easy) — Unique Number of Occurrences (C++)
Leetcode № 1295 (Easy) — Find Numbers With Even Number of Digits (C++)
Leetcode № 1399 (Easy) — Count Largest Group (C++)
Leetcode № 1480 (Easy) — Running Sum of 1D Array (C++)
Leetcode № 1539 (Easy) — Kth Missing Positive Number (C++)
Leetcode № 1732 (Easy) — Find The Highest Altitude(C++)
Leetcode № 1768 (Easy) — Merge Strings Alternately (C++)
Leetcode № 2119 (Easy) — A Number After a Double Reversal (C++)
Leetcode № 2215 (Easy) — Find the Difference of Two Arrays (C++)
Leetcode № 3396 (Easy) — Minimum Number of Operations to Make Elements in Array Distinct (C++)
Leetcode № 2 (Medium) — Add two Numbers (C++)
Leetcode № 3 (Medium) — Longest Substring Without Repeating Characters (C++)
Leetcode № 5 (Medium) — Longest Palindromic Substring (C++)
Leetcode № 7 (Medium) — Reverse Integer (C)
Leetcode № 8 (Medium) — String to Integer (C++)
Leetcode № 11 (Medium) — Container with Most Water (C++)
Leetcode № 15 (Medium) — 3Sum (C++)
Leetcode № 17 (Medium) — Letter Combinations of a Phone Number (C++)
Leetcode № 19 (Medium) — Remove Nth Node From End of List (C++)
Leetcode № 22 (Medium) — Generate Prentheses (C++)
Leetcode № 24 (Medium) — Swap Nodes in Pairs (C++)
Leetcode № 31 (Medium) — Next Permutation (C++)
Leetcode № 33 (Medium) — Search in Rotated Sorted Array (C++)
Leetcode № 34 (Medium) — Find First an Last Position of Element in Sorted Array (C++)
Leetcode № 36 (Medium) — Valid Sudoku (C++)
Leetcode № 38 (Medium) — Count and Say (C++)
Leetcode № 39 (Medium) — Combination Sum (C++)
Leetcode № 40 (Medium) — Combination Sum II (C++)
Leetcode № 47 (Medium) — Permutations II (C++)
Leetcode № 48 (Medium) — Rotate Image (C++)
Leetcode № 49 (Medium) — Group Anagrams (C++)
Leetcode № 50 (Medium) — Pow (C++)
Leetcode № 53 (Medium) — Maximum Subarray (C++)
Leetcode № 54 (Medium) — Spiral Matrix (C++)
Leetcode № 55 (Medium) — Jump Game (C++)
Leetcode № 56 (Medium) — Merge Intervals (C++)
Leetcode № 61 (Medium) — Rotate List (C++)
Leetcode № 71 (Medium) — Simplify Path (C++)
Leetcode № 73 (Medium) — Set Matrix Zeroes (C++)
Leetcode № 74 (Medium) — Search a 2D Matrix (C++)
Leetcode № 75 (Medium) — Sort Colors (C++)
Leetcode № 77 (Medium) — Combinations (C++)
Leetcode № 78 (Medium) — Subsets (C++)
Leetcode № 79 (Medium) — Word Search (C++)
Leetcode № 80 (Medium) — Remove duplicates from Sorted Array II (C)
Leetcode № 82 (Medium) — Remove Duplicates from Sorted List II II (C++)
Leetcode № 90 (Medium) — Subsets II (C++)
Leetcode № 92 (Medium) — Reverse Linked List II (C++)
Leetcode № 93 (Medium) — Restore IP Addresses (C++)
Leetcode № 98 (Medium) — Validate Binary Search Tree (C++)
Leetcode № 102 (Medium) — Binary Tree Level Order Traversal (C++)
Leetcode № 103 (Medium) — Binary Tree ZigZag Level Order Traversal (C++)
Leetcode № 105 (Medium) — Construct Binary Tree from Preorder and Inorder traversal (C++)
Leetcode № 116 (Medium) — Populating Next Right Pointers in Each Node (C++)
Leetcode № 117 (Medium) — Populating Next Right Pointers in Each Node II (C++)
Leetcode № 122 (Medium) — Best Time to Buy and Sell Stock II (C++)
Leetcode № 128 (Medium) — Longest Consecutive Sequence (C++)
Leetcode № 129 (Medium) — Sum Root to Leaf Numbers (C++)
Leetcode № 130 (Medium) — Surrounded Regions (C++)
Leetcode № 131 (Medium) — Palindrome Partitioning (C++)
Leetcode № 0133 (Medium) — Clone Graph (C++)
Leetcode № 134 (Medium) — Gas Station (C++)
Leetcode № 138 (Medium) — Copy List with Random Pointer (C++)
Leetcode № 139 (Medium) — Word Break (C++)
Leetcode № 146 (Medium) — LRU Cache (C++)
Leetcode № 148 (Medium) — Sort List (C++)
Leetcode № 150 (Medium) — Evaluate Reverse Polish Notation (C++)
Leetcode № 151 (Medium) — Reverse Words in a String (C++)
Leetcode № 153 (Medium) — Find minimum in rotated sorted array (C++)
Leetcode № 155 (Medium) — Min Stack (C++)
Leetcode № 162 (Medium) — Find Peak Element (C++)
Leetcode № 167 (Medium) — Two Sum II - Input Array is Sorted (C++)
Leetcode № 189 (Medium) — Rotate Array (C++)
Leetcode № 198 (Medium) — House Robber (C++)
Leetcode № 199 (Medium) — Binary Tree Right Side View (C++)
Leetcode № 200 (Medium) — Number of Islands (C++)
Leetcode № 207 (Medium) — Course Schedule (C++)
Leetcode № 209 (Medium) — Minimum Size Subarray Sum (C++)
Leetcode № 210 (Medium) — Course Schedule II (C++)
Leetcode № 215 (Medium) — Kth Largest Element in an Array (C++)
Leetcode № 236 (Medium) — Lowest Commong Ancestor of a Binary Tree (C++)
Leetcode № 238 (Medium) — Product of Array except Self (C++)
Leetcode № 249 (Medium) — Group Shifted Strings (C++)
Leetcode № 274 (Medium) — H-Index (C++)
Leetcode № 289 (Medium) — Game of Life (C++)
Leetcode № 314 (Medium) — Binary Tree Vertical Order Traversal (C++)
Leetcode № 325 (Medium) — Maximum Size Subarray Sum Equals K (C++)
Leetcode № 328 (Medium) — Odd Even Linked List (C++)
Leetcode № 328 (Medium) — Odd Even Linked List (C++)
Leetcode № 334 (Medium) — Increasing Triplet Subsequence (C++)
Leetcode № 339 (Medium) — Nested List Weight Sum (C++)
Leetcode № 347 (Medium) — Top K Frequent Elements (C++)
Leetcode № 394 (Medium) — Decode String (C++)
Leetcode № 399 (Medium) — Evaluate Division (C++)
Leetcode № 406 (Medium) — Queue Reconstruction by Height (C++)
Leetcode № 417 (Medium) — Pacific Island Water Flow (C++)
Leetcode № 433 (Medium) — Minimum Genetic Mutation (C++)
Leetcode № 435 (Medium) — Non Overlapping Intervals (C++)
Leetcode № 437 (Medium) — Path Sum III (C++)
Leetcode № 450 (Medium) — Delete Node in a BST (C++)
Leetcode № 452 (Medium) — Minimum number of arrows to burst balloons (C++)
Leetcode № 498 (Medium) — Diagonal Traverse (C++)
Leetcode № 523 (Medium) — Continuous Subarray Sum (C++)
Leetcode № 525 (Medium) — Contiguous Array (C++)
Leetcode № 528 (Medium) — Random Pick With Weight (C++)
Leetcode № 536 (Medium) — Construct Binary Tree (C++)
Leetcode № 542 (Medium) — 1 Matrix (C++)
Leetcode № 547 (Medium) — Number of Provinces (C++)
Leetcode № 560 (Medium) — Subarray Sum Equals K (C++)
Leetcode № 621 (Medium) — Task Scheduler (C++)
Leetcode № 647 (Medium) — Palindromic Substrings (C++)
Leetcode № 649 (Medium) — Dota2 Senate (C++)
Leetcode № 670 (Medium) — Maximum Swap (C++)
Leetcode № 684 (Medium) — Redundant Connection (C++)
Leetcode № 695 (Medium) — Max Area of Island (C++)
Leetcode № 708 (Medium) — Insert into a sorted circular linked list (C++)
Leetcode № 721 (Medium) — Accounts Merge (C++)
Leetcode № 735 (Medium) — Asteroid Collision (C++)
Leetcode № 739 (Medium) — Daily Temperature (C++)
Leetcode № 763 (Medium) — Partition Labels (C++)
Leetcode № 781 (Medium) — Rabbits in Forest (C++)
Leetcode № 784 (Medium) — Letter Case Permutation (C++)
Leetcode № 791 (Medium) — Custom Sort String (C++)
Leetcode № 797 (Medium) — All Paths from Source to Target (C++)
Leetcode № 802 (Medium) — Find Eventual Safe States (C++)
Leetcode № 841 (Medium) — Keys & Rooms (C++)
Leetcode № 845 (Medium) — Longest Mountain In Array (C++)
Leetcode № 863 (Medium) — All nodes distance K in binary tree (C++)
Leetcode № 875 (Medium) — Koko eating bananas (C++)
Leetcode № 907 (Medium) — Sum of Subarray Minimums (C++)
Leetcode № 921 (Medium) — Minimum add to make Parentheses Valid (C++)
Leetcode № 930 (Medium) — Binary Subarrays With Sum (C++)
Leetcode № 934 (Medium) — Shortest Bridge (C++)
Leetcode № 958 (Medium) — Check completeness of a Binary Tree (C++)
Leetcode № 973 (Medium) — K closest points to origin (C++)
Leetcode № 974 (Medium) — Subarray Sums Divisible by K (C++)
Leetcode № 981 (Medium) — Time Based Key Value Store (C++)
Leetcode № 986 (Medium) — Interval List Intersections (C++)
Leetcode № 994 (Medium) — Rotting Oranges (C++)
Leetcode № 1004 (Medium) — Max Consecutive Ones III (C++)
Leetcode № 1091 (Medium) — Shortest Path in Binary Matrix (C++)
Leetcode № 1094 (Medium) — Car Pooling (C++)
Leetcode № 1161 (Medium) — Maximum Level Sum of Binary Tree (C++)
Leetcode № 1209 (Medium) — Remove All Adjacent Duplicates In String II (C++)
Leetcode № 1248 (Medium) — Count Number of Nice Subarrays (C++)
Leetcode № 1249 (Medium) — Minimum Remove to Make Valide Parentheses (C++)
Leetcode № 1372 (Medium) — Longest ZigZag Path in a Binary Tree (C++)
Leetcode № 2 (Medium) — Design Underground System (C++)
Leetcode № 1423 (Medium) — Diagonal Traverse II (C++)
Leetcode № 1448 (Medium) — Count Good Nodes in Binary Tree (C++)
Leetcode № 1456 (Medium) — Maximum Number of Vowels in a Substring of Given Length (C++)
Leetcode № 1466 (Medium) — Re-order routes to make all paths lead to the city zero (C++)
Leetcode № 1493 (Medium) — Longest Subarray of 1's after Deleting One Element (C++)
Leetcode № 1570 (Medium) — Dot Product of Two Sparse Vectors (C++)
Leetcode № 1584 (Medium) — Min Cost to Connect All Points (C++)
Leetcode № 1644 (Medium) — Lowest Common Ancestor of a Binary Tree II (C++)
Leetcode № 1650 (Medium) — Lowest Common Ancestor of a Binary Tree III (C++)
Leetcode № 1657 (Medium) — Determine if two strings are close (C++)
Leetcode № 1679 (Medium) — Max Numbef of K-Sum Pairs(C++)
Leetcode № 1762 (Medium) — Buildings with an Ocean View (C++)
Leetcode № 1926 (Medium) — Nearest Exit From Entrance In Maze (C++)
Leetcode № 2095 (Medium) — Delete the Middle Node of a Linked List (C++)
Leetcode № 2104 (Medium) — Sum of Subarray Ranges (Obj-C)
Leetcode № 2130 (Medium) — Maximum Twin Sum of a Linked List (C++)
Leetcode № 2176 (Medium) — Count Equal and Divisible Pairs in an Array (C++)
Leetcode № 2192 (Medium) — All ancestors of a node in a directed acyclic graph (C++)
Leetcode № 2265 (Medium) — Count Nodes Equal to Average of Subtree (C++)
Leetcode № 2300 (Medium) — Successful Pairs of Spells and Potions (C++)
Leetcode № 2336 (Medium) — Smallets Number in an Infinite Set (C++)
Leetcode № 2352 (Medium) — Equal Row and Column Pairs (C++)
Leetcode № 3294 (Medium) — Convert Doubly Linked List To Array II (C++)
Leetcode № 23 (Hard) — Merge K Sorted Lists (C++)
Leetcode № 25 (Hard) — Reverse Nodes in K Group (C++)
Leetcode № 68 (Hard) — Text Justification (C++11,C++17).
Leetcode № 76 (Hard) — Minimum Window Substring (C++)
Leetcode № 84 (Hard) — Largest Rectangle in Histogram (C++11)
Leetcode № 124 (Hard) — Binary Tree Maximum Path Sum (C++).
Leetcode № 127 (Hard) — Word Ladder (C++)
Leetcode № 329 (Hard) — Longest Increasing Path in a Matrix (C++).
Leetcode № 987 (Hard) — Vertical Order Traversal of a Binary Tree (C++)
Solutions to problems from the book. Organized by category/chapter.
27.3 — Array Intersection (C++)
27.4 — Palindromic Sentence (C++)
27.2 — Smaller Prefixes (C++)
27.5 — Reverse Case Match (C++)