X Algorithm – 250 LeetCode Coding Challenge Questions

This is a personal coding challenge collection, the source is from LeetCode. To practice how to solve algorithm problems.

Feel free to contact me if you have any problems related.

#	Problem	LeetCode Difficulty	Structure / Algorithm	Solving Ideas / Hints
1041	Robot Bounded in Circle	Medium	String, Simulate	– From LeetCode Tips, the robot stays in the circle if and only if (looking at the final vector) it changes direction (ie. doesn’t stay pointing north), or it moves 0.
7	Reverse integer	Medium	Math	– JS Max Integer is larger than 2**31;
13	Roman to Integer	Easy	Hash Map	– Roman numbers has a nature of sum calculation, so the tip is to have a hashmap/dict/opject to map Roman number to integer
14	Longest Common Prefix	Easy	String	– Read Requirement Carefully, prefix is the starting letters only, (I understands it wrongly in the beginning) – Brute Force, O(n*m), m is the longest string length
67	Add Binary	Easy	String, Calculation, Binary	– No different to add integers or binary, because the result are the same, the only difference is the format – Most of languages, there is a limit for integer, here the tricky part is that the binary number is above the maximum integer, so when transfer from the binary to integer, it lost some value, use `BigInt` in JS could solve the problem, but in Python 3, there would not be a problem, because there is no int and long in Python3
20	Valid Parenthesis	Easy	String, Stack	– Use Stack – If an input start with ] } ), it will never close – in JS Set is supported
21	Merge Two Sorted LinkList	Easy	LinkList	– The definition of the ListNode is a bit confused, it is ES5 style of class, so for using it, use new ListNode(0, null)
27	Remove Elements	Easy	Array, Two Pointers	– Two Pointers can be used here – JS Splice Function could be used too
26	Remove Duplication from a Sorted Array	Easy	Array, Two Pointers
28	strStr	Easy	String	– This basically required to write a `indexOf` function – Consider not using high level function, like indexOf
35	Search Insert Position	Easy	Binary Search	– Loop, use low and high and while loop – Recursion, try pass start and end index
49	Group Anagrams	Medium	String, Sort, Hash Map	– This one is not very hard, it is a combination of usages of different algorithm and data structure – Object.values(), Object.keys(), Obejct.entries()
53	Maximum Sub Array	Easy	Dynamic Programming, Divide and Conquer
58	Length of the Last Word	Easy		– Split String to Words (do not forget trim the end of the string) – Find last word and get the length
64	Minimum Path Sum	Medium	Path Find, Matrix	– This looks like to the 53, maximum sub array, but actually, put it in 2d matrix, make it different – This is a classical path finding problem – To avoid, time out, use dict/hashmap as a caching layer, caching will solve the problem, but it costs more storage, more about dynamic programming solution
66	Plus One	Easy	Array	– Unshift can be used to append 1 into the beginning of array – Shift is used to remove the 1st element, different with pop(). – i++/i– return the value before calculation, comparing to ++i/–i
67	Add Binary	Easy		– BigInt can be used here
69	Sqrtx	Easy	Math	– Use Binary Search here
70	Climbing Stairs	Easy	Dynamic Programming	– Find the pattern of the result, which it is Fibonacci
605	Can Place Flowers	Easy		– Read requirements carefully
83	Remove Duplicates from Sorted List	Easy	Linked List, Two Pointer	– I wrote a simple JS solution for this, in page 2, faster than 93% js solution
88	Merge Sorted Arrays	Easy		– Todo, I did not figure out a proper way to cover all cases in the beginning in time O(m+n) – There is a O(m+n) solution in page 3, try think reversely – But merge arrays and resort is the easiest solution, will be nLogN
94	Binary Tree Inorder Traversal	Easy	Tree, Binary Tree, Stack, Recursion, Depth First	– Recursion is easier for solving this – pop, push, shift unshift
100	Same Tree	Easy	Tree
101	Symmetric Tree	Easy	Tree, BFS, DFS	– DFS Recursion solution is easy to get – For interaction, this is a good discussion on LeetCode as a queue base BFS solution
104	Maximum Depth of Binary Tree	Easy	Tree, BFS, DFS,	– Good Stack Based DFS/ Queue Based BFS iteration examples on LeetCode, actually the DFS iteration solution is a bit hard to understand – DFS Recursion is easier to understand
108	Convert Sorted Array to Binary Search Tree	Easy	DFS
520	Detect Capital	Easy	String
110	Balanced Binary Tree	Easy	Balanced Tree	– Balanced Binary Tree, left height and right height differs in 1 – Both left, right and all sub trees are balanced
111	Minimum Depth of Binary Tree	Easy	BFS, DFS
112	Path Sum	Easy	DFS
113	Path Sum 2	Medium	DFS, Binary Tree
125	Valid Palindrome	Easy	String
136	Single Number	Easy	List, Bit Manipulation	– 5^5 = 0, XOR, Any same two elements XOR operation, it will be 0, this is why Bit Manipulation works in reduce
941	Valid Mountain Array	Easy	List
141	Linked List Cycle	Easy	Linked List, Slow And Fast, Two Pointers	– there are 3 ideas for this, – 1 use Set/Map, time O(n), Space O(n) – 2 use Slow Fast Pointers, time O(n), Space O(1) – 3 modify the nodes in the interaction, time O(n), space O(1)
144	Binary Tree PreOrder Traversal	Easy	DFS, Stack
145	Binary Tree PostOrder Traversal	Easy	DFS, Stack
118	Pascal’s Triangle	Easy	Dynamic Programming
160	Two Linked List Intersection	Easy	Linked List,	– O(1) Space Solution, – O(n) Space Solution, using Hash Map
167	Two Sum 2	Easy	Binary, Two Pointers, Hash Map	There are 3 ideas for this, 1 is brute force, O(n^2), 2 is through using Hash Map, like normal Two Sum, 3 is using 2 pointers, one start one end, because the array is sorted
168	Excel Sheet Column	Easy	String, Math
169	Majority Element	Easy	Hash Map, Divide and Conquer	The optional requirement here is to make it in O(1) space. – There is one amazing two line approach for this. nums.sort((a,b) => a - b); return nums[Math.floor(nums.length/2)]; O(nlog(n)) + O(1) – Boyer-Moore Voting Algorithm – leetcode submission O(n) + O(1) – For divide and conquer, it will be a bit more complicated, O(n) + O(1)
171	Excel Sheet Column Number	Easy	String, Math
1672	Richest Customer Wealth	Easy	Array, Matrix
190	Reverse Bits	Easy	Bit Manipulation, Divide and Conquer
121	Best Time To Buy and Sell Stock	Easy	Array, Dynamic Programming	Without dynamic programming, it will exceed time limit.
191	Number of 1 Bits	Easy	Bit Manipulation	0b111 & 1 => 1 0b110 & 1 => 0 0b111 >> 1 => 0b011
257	Binary Tree Paths	Easy	DFS, Backtracking, Binary Tree
202	Happy Number	Easy	Hash Set, Two Pointers	Coding Tips, reduce((a,b)=>a*a+b*b) is not the proper way to get sum of square Besides using Set, another idea is to use fast/slow two pointer
203	Remove Linked List Elements	Easy	Linked List
205	Isomorphic Strings	Easy	Hash Map	The key for this question is to check mapper value either unique or not. If not false, otherwise true.
206	Reversed Linked List	Easy	Linked List, Recursion
217	Contains Duplicate	Easy	Hash Set
219	Contains Duplicate 2	Easy	Hash Map	– Store higher index in Hash Map
225	Implement Stack using Queues	Easy	Queue, Stack	1 idea is using a nested queue Another idea is to use two queue
226	Invert Binary Tree	Easy	Tree, DFS, BFS
228	Summary Ranges	Easy	Array
231	Power of Two	Easy	Bit Manipulation	My own 1 line solution return 2**(n.toString(2).length-1) === n Better one from discussion n > 0 ? !(n & n-1) : false;
232	Implement Queue using Stacks	Easy	Queue, Stack
234	Palindrome Linked List	Easy	Linked List	One easy solution is to convert to array and check it. O(n), O(n) The other solution is to 1. detect middle of array 2. reverse the second part of array 3. check the first part and second part of array
235	Lowest Common Ancestor of a Binary Search Tree	Easy	BST	My own solution is through Recursion There is a simple iteration solution. (In Python) while (root.val - p.val) * (root.val - q.val) > 0: root = (root.left, root.right) [p.val > root.val] return root
389	Find Difference	Easy	String, Hash Map	Solution 1, using a Hash Map to store character frequency, O(n) O(n) Solution 2, using string replace O(n) O(n) for (let letter of s) t = t.replace(letter, ''); return t; Solution 3, using char operation, O(n) O(1) for (let i = 0; i < t.length; i++) { if(s[i]) charCode -= s[i].charCodeAt(); charCode += t[i].charCodeAt() }; return String.fromCharCode(charCode);
237	Delete Node In A Linked List	Easy	Linked List
238	Product of Array Except Self	Medium	Array	– for no divide, use left and right two multiplier , this solution is quite tricky, the actual space complexity is O(n)
242	Valid Anagram	Easy	String, Hash Map
#	Problem	Difficulty	Tags	Note