C++ Coding Challenge Tutorials
A collection of over 70 tutorials and explanations I've created for solving coding challenges found on Leetcode!
I've been dissatisfied by some of the solution explanations I've found while working on these challenges. When I decided to write my own that explained the way the solutions work so that I could understand them, I found the explanations to be much more in-depth and comprehensive, and I wanted to share them with you!
These are all written by me, not by AI!!
If you would like to see a particular coding challenge written up as a tutorial, send an email to chordieapp@gmail.com and let me know! It might end up on this list.
The free version contains the following solution writeups:
1. Two Sum
13. Roman To Integer
70. Climbing Stairs
111. Minimum Depth of Binary Tree
202. Happy Number - A
234. Palindrome Linked List
Here's the current list of challenges I've written tutorials for, and the list is continuing to grow:
1. Two Sum*
9. Palindrome Number
13. Roman To Integer*
14. Longest Common Prefix
17. Letter Combinations of a Phone Number
18. 4Sum
20. Valid Parentheses
21. Merge Two Sorted Lists - A
21. Merge Two Sorted Lists - B
22. Generate Parentheses
26. Remove Duplicates from Sorted Array
27. Remove Element
28. Find the Index of the First Occurrence in a String
35. Search Insert Position - A
35. Search Insert Position - B
58. Length of Last Word
66. Plus One
67. Add Binary
69. Sqrt(x)
70. Climbing Stairs*
83. Remove Duplicates from Sorted List
88. Merge Sorted Array
94. Binary Tree Inorder Traversal
100. Same Tree
101. Symmetric Tree
104. Maximum Depth of Binary Tree
108. Convert Sorted Array to Binary Search Tree
110. Balanced Binary Tree
111. Minimum Depth of Binary Tree*
112. Path Sum
118. Pascal's Triangle
119. Pascal's Triangle II
121. Best Time to Buy and Sell Stock
125. Valid Palindrome
136. Single Number
141. Linked List Cycle - A
141. Linked List Cycle - B
144. Binary Tree Preorder Traversal
145. Binary Tree Postorder Traversal
160. Intersection of Two Linked Lists - A
160. Intersection of Two Linked Lists - B
168. Excel Sheet Column Title
169. Majority Element
171. Excel Sheet Column Number
190. Reverse Bits
191. Number of 1 Bits
202. Happy Number - A*
202. Happy Number - B
203. Remove Linked List Elements
206. Reverse Linked List
217. Contains Duplicate
234. Palindrome Linked List*
283. Move Zeroes
344. Reverse String
349. Intersection of Two Arrays
350. Intersection of Two Arrays II
414. Third Maximum Number
496. Next Greater Element I - A
496. Next Greater Element I - B
566. Reshape the Matrix
628. Maximum Product of Three Numbers - A
628. Maximum Product of Three Numbers - B
703. Kth Largest Element in a Stream
705. Design HashSet
706. Design HashMap
766. Toeplitz Matrix
867. Transpose Matrix
876. Middle of Linked List
883. Projection Area of 3D Shapes
933. Number of Recent Calls
1290. Convert Binary Number in a Linked List to Integer
1464. Maximum Product of Two Elements in an Array
1572. Matrix Diagonal Sum
1656. Design an Ordered Stream
1670. Design Front Middle Back Queue
1822. Sign of the Product of an Array
3033. Modify the Matrix
3507. Minimum Pair Removal to Sort Array I
3248. Snake in Matrix
* included in Free version
Here's a free preview of the write up for 70. Climbing Stairs:
Challenge:
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
URL: https://leetcode.com/problems/climbing-stairs/description/
class Solution {
public:
int climbStairs(int n) {
}
};Intuition
This challenge wants us to compute permutations.
How many different ways can we sum the values 1 and 2 to equal n?
The hint gives us a great starting point:
To reach nth step, what could have been your previous steps? (Think about the step sizes)
Let's look at the possible combos for the first few possibilities of N:
possible step combos:
n = 0:
0 combos
n = 1:
1 step
1 combo
n = 2:
2
1 + 1
2 combos
n = 3:
2 + 1
1+1 + 1
1 + 2
3 combosNotice that the various ways to combine for n=3 look like the various ways to combine n=2 and n=1, added together.
Let's check a few more n values:
n = 4:
2+2
2 + 1+1
1+1 + 1+1 or 1 + 1+1 + 1
1 + 2 + 1
1+1 + 2
5 combos
n = 5:
1+1+1+1+1
2+1+1+1
1+2+1+1
1+1+2+1
1+1+1+2
1+2+2
2+1+2
2+2+1
8 combosThe pattern is starting to emerge.
Notice that starting from n=3 onward, the pattern is always:numCombos for n = numCombos for n-1 + numCombos for n-2
When n = 4, the combo count is 5:n-1 count is 3n-2 count is 2
their sum is 5.
When n = 5:n-1 count is 5n-2 count is 3
Their sum is 8.
Let's confirm this by talking through n = 6:
We should get n=5 (8) + n=4 (5), or 13 combos:
n = 6:
1. 1+1+1+1+1+1
2. 2+1+1+1+1
3. 1+2+1+1+1
4. 1+1+2+1+1
5. 1+1+1+2+1
6. 1+1+1+1+2
7. 2+1+1+2
8. 2+1+2+1
9. 2+2+1+1
10. 1+2+2+1
11. 1+2+1+2
12. 1+1+2+2
13. 2+2+213 combos!
It's confirmed!
The pattern is:
combos @ n = combos @ n-1 + combos @ n-2With this pattern, we can build up a cache using a vector, with size n + 1, because the n needs to match the index, and not be zero based.
std::vector<int> cache (n + 1);We need to initialize the first two true N's:
cache[0] = 0;
cache[1] = 1;
cache[2] = 2;For the rest of the N's, we can use a loop, remembering that n needs to match the index, and not be zero-based. That means we use i <= n instead of i < n:
for( int i = 3; i <= n; ++i )
{
cache[i] = cache[i-1] + cache[i-2];
}Once we've built up the cache, we just return the appropriate index for whatever n we were given:
return cache[n];Here's the full solution:
Code
class Solution {
public:
int climbStairs(int n)
{
if( n <= 2 )
return n;
std::vector<int> cache (n + 1);
cache[0] = 0;
cache[1] = 1;
cache[2] = 2;
for( int i = 3; i <= n; ++i )
{
cache[i] = cache[i-1] + cache[i-2];
}
return cache[n];
}
};Looking for help with C++, coding challenges, and the JUCE framework?
Check out the JUCE & C++ Consultation Membership!
Thank you so much for supporting Matkat Music LLC, ChordieApp, and ProgrammingForMusicians!