x12hengyu / algorithm-notes

Classical Algorithm and Data Structure Problems

Algorithm Practice Notes

Hi, this is Xizheng Yu. This is my note of solutions of classical algorithm and data structure problems. You can find solution files written in Java in my repository. All solutions are written by myself and references (solution links) are from public sources include YouTube, LeetCode Community, Geekforgeeks etc., which are organized on the main page. Feel free to reach out if you have any question.

To find those questions, access this link and search the question number listed below.

Questions has been seperated into 2 types:

• Bold Questions: Clssical Question to practice for each category.
• Normal Questions: Additional Question for more practices.

In-page Hyperlinks:

• Data Structures
  • LinkedList
  • Tree
  • BST
  • Trie
  • Queue
  • Stack
  • HashTable
  • Graph
  • Priority Queue
• Algorithms
  • Two-Pointers
  • Sort
  • Greedy
  • Divide and Conquer (DC)
  • Dynamic Programming (DP)
  • Sliding Window
  • Backtrace
  • Binary-Search
• Others
  • Bit Manipulation
  • String
  • Math
  • Other

Data Structure

LinkedList

Questions	Solutions	Notes
2. Add Two Numbers	Solution
19. Remove Nth Node From End of List	Solution	use two pointers, Solution with Explanation
21. Merge Two Sorted Lists	Solution	Solution with Explanation
24. Swap Nodes in Pairs	Solution
83. Remove Duplicates from Sorted List	Solution
86. Partition List	Solution	seperate two list and join
92. Reverse Linked List II	Solution
114. Flatten Binary Tree to Linked List	Solution
160. Intersection of Two Linked Lists	Solution
206. Reverse Linked List	Solution
234. Palindrome Linked List	Solution	Solution with Explanation, Cut half, reverse, compare
328. Odd Even Linked List	Solution
445. Add Two Numbers II	Solution	stack
725. Split Linked List in Parts	Solution

Tree

Questions	Solutions	Notes
100. Same Tree	Solution
101. Symmetric Tree	Solution
102. Binary Tree Level Order Traversal	Solution	level-order traversal
104. Maximum Depth of Binary Tree	Solution
105. Construct Binary Tree from Preorder and Inorder Traversal	Solution
110. Balanced Binary Tree	Solution
111. Minimum Depth of Binary Tree	Solution	BFS is better than revursively DFS here
112. Path Sum	Solution
129. Sum Root to Leaf Numbers	Solution
199. Binary Tree Right Side View	Solution	bfs search from right to left, add first element
226. Invert Binary Tree	Solution
297. Serialize and Deserialize Binary Tree	Solution	deque, pre-prder
337. House Robber III	Solution	Solution with Explanation, DP memorization? or bottom to up backtrace?
404. Sum of Left Leaves	Solution
437. Path Sum III	Solution	dfs
543. Diameter of Binary Tree	Solution
572. Subtree of Another Tree	Solution
617. Merge Two Binary Trees	Solution
671. Second Minimum Node In a Binary Tree	Solution	This questions refers to a special tree that each node has exactly two or zero sub-node.
687. Longest Univalue Path	Solution
814. Binary Tree Pruning	Solution
1448. Count Good Nodes in Binary Tree	Solution	dfs
2415. Reverse Odd Levels of Binary Tree	Solution	bfs

Traversal:        1           
                /   \
               2     3       
             /   \ /   \     
            4    5 6    7    
In-order (Left, Root, Right): [4, 2, 5, 1, 3, 6, 7]
Pre-order (Root, Left, Right): [1, 2, 4, 5, 3, 6, 7]
Post-Order (Left, Right, Root): [4, 5, 2, 6, 7, 3, 1]
Level: [1, 2, 3, 4, 5, 6, 7]

Questions	Solutions	Notes
637. Average of Levels in Binary Tree	Solution	level-traversal
513. Find Bottom Left Tree Value	Solution	level-traversal, right to left on each level
144. Binary Tree Preorder Traversal	Solution	push right then left
94. Binary Tree Inorder Traversal	Solution
145. Binary Tree Postorder Traversal	Solution	Iterate from top to bottom, result from back to front

Morris traversal: an (in-order) tree traversal algorithm that does not employ the use of recursion or a stack, visit this link for details

Binary Search Tree (BST)

Questions	Solutions	Notes
108. Convert Sorted Array to Binary Search Tree	Solution	divide and conquer
109. Convert Sorted List to Binary Search Tree	Solution	divide and conquer
230. Kth Smallest Element in a BST	Solution	Stack, In-Order Traversal
235. Lowest Common Ancestor of a Binary Search Tree	Solution
236. Lowest Common Ancestor of a Binary Tree	Solution
501. Find Mode in Binary Search Tree	Solution
530. Minimum Absolute Difference in BST	Solution	In-order traversal
538. Convert BST to Greater Tree	Solution
653. Two Sum IV - Input is a BST	Solution	Three Approaches with Explanation
669. Trim a Binary Search Tree	Solution

Trie

Questions	Solutions	Notes
208. Implement Trie (Prefix Tree)	Solution
677. Map Sum Pairs	Solution
745. Prefix and Suffix Search	Solution	Since { is next to z in ASCII table, we use { to seperate suffix and prefix. For word apple, we are going to insert: apple{apple, pple{apple, ple{apple, le{apple, e{apple, {apple. This allow us to search suffix + { + prefix in the trie.
1268. Search Suggestions System	Solution	could also be solved by binary search, link
2416. Sum of Prefix Scores of Strings	Solution	use tire to record each score and sum

Queue

Questions	Solutions	Notes
225. Implement Stack using Queues	Solution	to implement LIFO with queue, we need to put every new element to the end of the queue

Stack

Questions	Solutions	Notes
20. Valid Parentheses	Solution
155. Min Stack	Solution	one normal stack, another stack tracks min values
232. Implement Queue using Stacks	Solution	use two stacks to reverse order
503. Next Greater Element II	Solution	This question is tricky because it's a circular array
682. Baseball Game	Solution
739. Daily Temperatures	Solution	monotonic stack
1472. Design Browser History	Solution	two stacks, one record past, another one for future

HashTable

Questions	Solutions	Notes
1. Two Sum	Solution
13. Roman to Integer	Solution	use a prev pointer to manage deduction
128. Longest Consecutive Sequence	Solution
217. Contains Duplicate	Solution	use HashSet to track unique element.
560. Subarray Sum Equals K	Solution	Detailed Explanation, use hashset to record previous occurrence of keys to reduce time complexity
594. Longest Harmonious Subsequence	Solution	subsequence is not consecutive
792. Number of Matching Subsequences	Solution	use start of each word as map key
820. Short Encoding of Words	Solution	hashset / trie
1074. Number of Submatrices That Sum to Target	Solution	Detailed Explanation, 3D version of 560
1630. Arithmetic Subarrays	Solution
2404. Most Frequent Even Element	Solution

Graph

Graph Theories:

• Search
  • Breath-First Search (BFS) - Video Explanation
  • Depth-First Search (DFS) - Video Explanation
• Shortest Path
  • Dijkstra's Algorithm - Video Explanation
  • Bellman Ford Algorithm - Video Explanation
• Topological Sort
  • Kahn's Algorithm - Video Explanation
• Strongly Connected Components
  • Tarjan's Strongly Connected Component (SCC) Algorithm - Video Explanation
• Union and Find
  • Disjoint Union and Find - Video Explanation
• Minimum Spanning Tree
  • Prim's Algorithm - Video Explanation
  • Kruskal's Algorithm - Video Explanation - Union and Find application
• Network Flow
  • Ford-Fulkerson Algorithm - Maximum Flow - Video Explanation, Java Code
  • Bipartite Matching -

Questions	Solutions	Notes
684. Redundant Connection	Solution	Classical Union and Find
695. Max Area of Island	Solution	dfs
785. Is Graph Bipartite?	Solution	graph coloring, dfs
1192. Critical Connections in a Network	Solution	Tarjan's Algorithm

Priority Queue

Questions	Solutions	Notes
295. Find Median from Data Stream	Solution	double pq
605. Can Place Flowers	Solution
630. Course Schedule III	Solution	greedy sort + pq
1046. Last Stone Weight	Solution
1354. Construct Target Array With Multiple Sums	Solution	Graphical Explanation, backtrace with pq
1642. Furthest Building You Can Reach	Solution	Solution with Explanation, use pq to record height difference
2406. Divide Intervals Into Minimum Number of Groups	Solution
2462. Total Cost to Hire K Workers	Solution

Algorithm

Two-Pointers

Questions	Solutions	Notes
15. 3Sum	Solution	Advanced version of 2 sum, same idea
88. Merge Sorted Array	Solution
125. Valid Palindrome	Solution	head and end pointers
141. Linked List Cycle	Solution	Use two different speed pointer to track if they meet
142. Linked List Cycle II	Solution
167. Two Sum II - Input Array Is Sorted	Solution
344. Reverse String	Solution
345. Reverse Vowels of a String	Solution
524. Longest Word in Dictionary through Deleting	Solution
541. Reverse String II	Solution
557. Reverse Words in a String III	Solution
633. Sum of Square Numbers	Solution
680. Valid Palindrome II	Solution	Two pointers from head and end
2410. Maximum Matching of Players With Trainers	Solution

Sort

QuickSort

• QuickSelect
• Hoare’s vs Lomuto partition scheme in QuickSort

Questions	Solutions	Notes
56. Merge Intervals	Solution
215. Kth Largest Element in an Array	Solution	priority queue: o(nlogn) quicksort: best o(n) worst o(n^2)
1996. The Number of Weak Characters in the Game	Solution	sort attack descending and defense ascending

Greedy

"Local Optimal is Global Optimal"

Questions	Solutions	Notes
53. Maximum Subarray	Solution
121. Best Time to Buy and Sell Stock	Solution
122. Best Time to Buy and Sell Stock II	Solution
135. Candy	Solution	iterate from left and right to ensure both children satisfy conditions
392. Is Subsequence	Solution
435. Non-overlapping Intervals	Solution
452. Minimum Number of Arrows to Burst Balloons	Solution
455. Assign Cookies	Solution
763. Partition Labels	Solution
1647. Minimum Deletions to Make Character Frequencies Unique	Solution	check if current freq has been used, if so, delete until find empty freq
1710. Maximum Units on a Truck	Solution	give each box takes same 1 space, sort by unit to maximize unit taken
2405. Optimal Partition of String	Solution	hashset

Divide and Conquer (DC)

Questions	Solutions	Notes
240. Search a 2D Matrix II	Solution	DC Approach, intuitively should use dc, but more efficent to search from top-right or bottom-left
315. Count of Smaller Numbers After Self	Solution	Explanation

Dynamic Programming (DP)

Questions	Solutions	Notes
5. Longest Palindromic Substring	Solution
32. Longest Valid Parentheses	Solution	think as a stack, count left then compare
55. Jump Game	Solution
62. Unique Paths	Solution	Graphical Explanation
63. Unique Paths II	Solution
64. Minimum Path Sum	Solution	use matrix to memorize every optimal minimum sum
70. Climbing Stairs	Solution	fibonacci
97. Interleaving String	Solution	Graphical Explanation, use 2d boolean array judge matches to s3, could also use 1d to save space, Time: O(mn) Space: O(mn)
118. Pascal's Triangle	Solution
120. Triangle	Solution	top-to-bottom memorization
198. House Robber	Solution	bellman equation: opt[i] = Math.max(opt[i-1], opt[i-2]+nums[i]);
213. House Robber II	Solution	Explanation
221. Maximal Square	Solution
303. Range Sum Query - Immutable	Solution	prefix sum
304. Range Sum Query 2D - Immutable	Solution	dp, prefix-sum
322. Coin Change	Solution	the idea of dp array is actually something like 0-1 knapsack, bellman equation: dp[i] = Math.min(dp[i], dp[prev] + 1);
376. Wiggle Subsequence	Solution	Bellman Equations: up = down + 1 or down = up + 1
406. Queue Reconstruction by Height	Solution	Explanation, Sort by height decending, then sort by k ascending
413. Arithmetic Slices	Solution	Explained
446. Arithmetic Slices II - Subsequence	Solution	Graphical Explanation， hashmap
474. Ones and Zeroes	Solution	Explained, like 0-1 knapsack, bellman equation: dp[i][j] = Math.max(dp[i][j], dp[i-zeroes][j-ones] + 1);
576. Out of Boundary Paths	Solution	use dp array to record various ways that each location could be reached
583. Delete Operation for Two Strings	Solution	1. find the longest common subsequence (1143), use two words' length minus it 2. edit distance
629. K Inverse Pairs Array	Solution
647. Palindromic Substrings	Solution
665. Non-decreasing Array	Solution	Explanation
746. Min Cost Climbing Stairs	Solution
968. Binary Tree Cameras (Hard)	Solution	Explanation, greedy + dfs search + binary tree
1048. Longest String Chain	Solution	Explanation Solution
1143. Longest Common Subsequence	Solution	Video Explanation
1277. Count Square Submatrices with All Ones	Solution	Graphical Explanation, Time: O(mn) Space: O(mn)
1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold	Solution	dp, prefix-sum, sliding window track
1332. Remove Palindromic Subsequences	Solution	Solution with Explanation, Two-Pointers Subarray vs Subsequence: Subarray need to be consecutive, Subsequence don't have to be consecutive.
1473. Paint House III	Solution
1696. Jump Game VI	Solution	dp + deque

Sliding Window

What is sliding window? View this link.

Questions	Solutions	Notes
3. Longest Substring Without Repeating Characters	Solution	Solution with Explanation
424. Longest Repeating Character Replacement	Solution	Explanation
1423. Maximum Points You Can Obtain from Cards	Solution	Visualization
1461. Check If a String Contains All Binary Codes of Size K	Solution	hashset
1658. Minimum Operations to Reduce X to Zero	Solution	Solution with Explanation
1695. Maximum Erasure Value	Solution	hashset
2414. Length of the Longest Alphabetical Continuous Substring	Solution
2461. Maximum Sum of Distinct Subarrays With Length K	Solution

Backtrace

Questions	Solutions	Notes
51. N-Queens	Solution	Graphical and Video Explanation, Use boolean list to record diagnals
52. N-Queens II	Solution	Different from 51, we do not actually place Queen. We only record the column availability instead
473. Matchsticks to Square	Solution

Binary-Search

Questions	Solutions	Notes
4. Median of Two Sorted Arrays	Solution	Solution with explanation
34. Find First and Last Position of Element in Sorted Array	Solution
300. Longest Increasing Subsequence	Solution	Video Explanation, Solution with Explanation, DP & Greedy & Binary-Search
354. Russian Doll Envelopes	Solution	Solution with Explanation, Similar to 300. Longest Increasing Subsequence

Others

Bit Manipulation

	Operators	Lemmas
1	^	a ^ b ^ b == a
2	<<	a << n == a * 2^n
3	>>	a >> n == a * 2^n

Questions	Solutions	Notes
29. Divide Two Integers	Solution	Solution with Explanation, This question sucks, use Lemma 2 & 3
191. Number of 1 Bits	Solution	Solution with Explanation, Bit shift
268. Missing Number	Solution	XOR Solution with Explanation, Lemma 1
318. Maximum Product of Word Lengths	Solution	Bit Mask Solution with Explanation
1342. Number of Steps to Reduce a Number to Zero	Solution
2411. Smallest Subarrays With Maximum Bitwise OR	Solution	Use an array to track every bit of number, and record their last positions.
2429. Minimize XOR	Solution
2433. Find The Original Array of Prefix Xor	Solution	a ^ b = c, b ^ c = a, a ^ c = b

String

Questions	Solutions	Notes
6. Zigzag Conversion	Solution	stringbuffer
9. Palindrome Number	Solution	1. use two pointers 2. no extra space, seperate to 2 ints then compare
205. Isomorphic Strings	Solution	use two seperate arr to track previous appeared position
242. Valid Anagram	Solution	use 26 chars array instead of hashmap is easier
387. First Unique Character in a String	Solution
409. Longest Palindrome	Solution	odd or even char
443. String Compression	Solution	two pointers
890. Find and Replace Pattern	Solution	normalize string with chars' location + 1
916. Word Subsets	Solution
1360. Number of Days Between Two Dates	Solution	leap year satisfy: y % 400 == 0 or y % 4 == 0 && y % 100 != 0
1446. Consecutive Characters	Solution
2434. Using a Robot to Print the Lexicographically Smallest String	Solution	stack

Math

Questions	Solutions	Notes
462. Minimum Moves to Equal Array Elements II	Solution	median
509. Fibonacci Number	Solution	fibonacci number
724. Find Pivot Index	Solution
2413. Smallest Even Multiple	Solution
2427. Number of Common Factors	Solution	gcd
2428. Maximum Sum of an Hourglass	Solution	brute force

Others

Questions	Solutions	Notes
867. Transpose Matrix	Solution
1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts	Solution
1480. Running Sum of 1d Array	Solution	prefix-sum
1689. Partitioning Into Minimum Number Of Deci-Binary Numbers	Solution	just return the max digit
2409. Count Days Spent Together	Solution
2432. The Employee That Worked on the Longest Task	Solution
2460. Apply Operations to an Array	Solution

References

• LeetCode
• https://github.com/CyC2018/cs-notes
• William Fiest's YouTube Channal, great explanation - https://www.youtube.com/c/WilliamFiset-videos