LeetCode Practice Record

This repository contains my solutions and explanations for various LeetCode problems.

The problems are organized into directories based on the main technique or data structure needed to solve them.

Table of Contents

Data structure

• Array
• Linked List
• Hash Table
• Set
• String
• Stack
• Queue
• Heap
• Binary Tree
• Trie
• Monotonic Queue
• Disjoint Set

Algorithm

• LeetCode Practice Record
  • Table of Contents
    • Data structure
    • Algorithm
• 刷題訓練的四大能力
• 刷題方法
• Data Structure
  • Array
  • Hash Table
  • Linked List
  • Set
  • String
  • Stack
  • Queue
  • Binary Tree
  • Tree
  • Heap
  • Trie
  • Monotonic Queue
  • Disjoint Set
• 演算法策略
  • Sorting
  • Binary Search
  • Two-Pointers
  • Sliding Window
  • Bit Operation
  • Backtracking
  • Recursion
  • Graph Algorithm
  • Greedy
  • Dynamic Programming
• Divide and Conquer
• Reference：

刷題訓練的四大能力

• 抽象化能力：將題序看懂，並了解題序中的限制，問題和其他問題的結構是否有相似之處，是否有數學模型能套用到該問題上。
• 演算法、資料結構能力：題目的結構適合使用哪一個演算法策略來解，而在中間需要對資料進行什麼操作，是否有合適的資料結構來儲存，以節省這些資料操作的時間。
• 實作能力：如何將演算法轉成實際的程式語言，使用的程式語言中是否有既有的語法或函式庫來實作，是否有邊界條件的測資無法通過。
• 溝通能力：如何在 coding 過程中，將自己的想法清楚表達給面試官，在面試官給的題敘不夠詳盡、清楚時，是否可以透過溝通，將題目的需求和限制釐清

刷題方法

• 看懂題目的敘述、測資，手動依照題目推演過測資
• 思考 brute-force 的解法，注意各種邊界條件，邏輯縝密性
• 思考更近一步，如何優化時間複雜度或空間複雜度
• 將各種思路口頭敘述一遍，表達清楚（英語）
• 扮演面試官，在出題過程中，是否有什麼變形，是否有什麼假設，哪個解法的障礙等等
• 看別人的 discussion 和官方題解，是否有比自己更好的作法

刷題不是流水帳，不是解過一題是一題，重點在磨練這四個能力，不是在背題。

Data Structure

Array

• Dynamic Array (Vector) Implementation: C++

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
217	Contains Duplicate	C++		Easy	2024/06/12	[x]	[ ]
238	Product of Array Except Self	C++		Medium	2024/06/29	[x]	[ ]
350	Intersection of Two Arrays II	C++		Easy	2024/07/02	[x]	[ ]
42	Trapping Rain Water	C++		Hard	2024/07/02	[x]	[ ]
80	Remove Duplicates from Sorted Array II	C++		Medium	2024/07/02	[x]	[ ]
73	Set Matrix Zeroes	C++		Medium	2024/07/03	[x]	[ ]
56	Merge Intervals	C++		Medium	2024/07/04	[x]	[ ]
57	Insert Interval	C++		Medium	2024/07/04	[x]	[ ]
189	Rotate Array	C++		Medium	2024/07/04	[x]	[ ]
1701	Average Waiting Time	C++		Medium	2024/07/09	[x]	[ ]
36	Valid Sudoku	C++		Medium	2024/07/10	[x]	[ ]

Hash Table

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
49	Group Anagrams	C++		Medium	2024/06/17	[x]	[ ]
347	Top K Frequent Elements	C++		Medium	2024/06/17	[x]	[ ]
169	Majority Element	C++		Easy	2024/06/28	[x]	[ ]
380	Insert Delete GetRandom O(1)	C++		Medium	2024/06/28	[x]	[ ]
383	Ransom Note	C++		Easy	2024/07/04	[x]	[ ]
128	Longest Consecutive Sequence	C++		Medium	2024/07/04	[x]	[ ]
290	Word Pattern	C++		Medium	2024/07/04	[x]	[ ]
219	Contains Duplicate II	C++		Easy	2024/07/10	[x]	[ ]

Linked List

• Singly Linked List Implementation: C++
• Circular Linked List Implementation: C++
• Double Linked List Implementation: C++

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
2095	Delete the Middle Node of a Linked List	C		Medium	2024/02/28	[x]	[ ]
82	Remove Duplicates from Sorted List II	C		Medium	2024/02/28	[x]	[ ]
25	Reverse Nodes in k-Group	C		Hard	2024/02/29	[x]	[ ]
92	Reverse Linked List II	C++		Medium	2024/04/03	[x]	[ ]
116	Populating Next Right Pointers in Each Node	C++		Medium	2024/04/03	[x]	[ ]
23	Merge k Sorted Lists	C		Hard	2024/03/01	[x]	[ ]
2181	Merge Nodes in Between Zeros	C++		Medium	2024/07/04	[x]	[ ]
2058	Find the Minimum and Maximum Number of Nodes Between Critical Points	C++		Medium	2024/07/05	[x]	[ ]
141	Linked List Cycle	C++		Easy	2024/07/05	[x]	[ ]
1836	Remove Duplicates From an Unsorted Linked List	C++		Medium	2024/07/09	[x]	[ ]

Set

#	Title	Solution	Note	Difficulty	Date	Done	Think Again

String

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
2743	Count Substrings Without Repeating Character	C++		Medium	2024/06/28	[x]	[ ]
13	Roman to Integer	C++		Easy	2024/07/02	[x]	[ ]
12	Integer to Roman	C++		Medium	2024/07/02	[x]	[ ]
58	Length of Last Word	C++		Easy	2024/07/02	[x]	[ ]
14	Longest Common Prefix	C++		Easy	2024/07/02	[x]	[ ]
151	Reverse Words in a String	C++		Medium	2024/07/02	[x]	[ ]
6	Zigzag Conversion	C++		Medium	2024/07/03	[x]	[ ]
28	Find the Index of the First Occurrence in a String	C++		Easy	2024/07/03	[x]	[ ]
1598	Crawler Log Folder	C++		Easy	2024/07/10	[x]	[ ]

Stack

• Stack Implementation: C++

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
225	Implement Stack using Queues	C++		Easy	2024/03/12	[x]	[ ]
20	Valid Parentheses	C++		Easy	2024/03/12	[x]	[ ]
71	Simplify Path	C++		Medium	2024/03/13	[x]	[ ]
1249	Minimum Remove to Make Valid Parentheses	C++		Medium	2024/03/13	[x]	[ ]
227	Basic Calculator II	C++		Medium	2024/03/14	[x]	[ ]
155	Min Stack	C++		Hard	2024/03/25	[x]	[ ]
1193	Reverse Substrings Between Each Pair of Parentheses	C++		Medium	2024/07/11	[x]	[ ]
2751	Robot Collisions	C++		Hard	2024/07/13	[x]	[ ]
726	Number of Atoms	C++		Hard	2024/07/14	[x]	[ ]
224	Basic Calculator	C++		Hard	2024/03/14	[ ]	[ ]

Queue

• Queue Implementation by Singly Linked-list: C++

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
232	Implement Queue using Stacks	C++		Easy	2024/03/12	[x]	[ ]
362	Design Hit Counter	C++		Medium	2024/03/17	[x]	[ ]
387	First Unique Character in a String	C++		Easy	2024/03/18	[x]	[ ]
353	Design Snake Game	C++		Medium	2024/03/18	[x]	[ ]
239	Sliding Window Maximum	C++		Hard	2024/03/19	[ ]	[ ]

Binary Tree

• Morris Traversal: C++

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
94	Binary Tree Inorder Traversal	C++		Easy	2024/03/21	[x]	[ ]
98	Validate Binary Search Tree	C++		Medium	2024/03/21	[x]	[ ]
101	Symmetric Tree	C++		Easy	2024/03/22	[x]	[ ]
102	Binary Tree Level Order Traversal	C++		Medium	2024/03/22	[x]	[ ]
104	Maximum Depth of Binary Tree	C++		Easy	2024/03/22	[x]	[ ]
105	Construct Binary Tree from Preorder and Inorder Traversal	C++		Medium	2024/03/22	[x]	[ ]
108	Convert Sorted Array to Binary Search Tree	C++		Medium	2024/03/23	[x]	[ ]
114	Flatten Binary Tree to Linked List	C++		Medium	2024/03/23	[x]	[ ]
145	Binary Tree Postorder Traversal	C++		Easy	2024/03/26	[x]	[ ]
270	Closest Binary Search Tree Value	C++		Easy	2024/03/26	[x]	[ ]
95	Unique Binary Search Trees II	C++		Medium	2024/03/26	[x]	[ ]
110	Balanced Binary Tree	C++		Easy	2024/03/26	[x]	[ ]
222	Count Complete Tree Nodes	C++		Medium	2024/03/26	[x]	[ ]
99	Recover Binary Search Tree	C++		Medium	2024/03/27	[x]	[ ]
100	Same Tree	C++		Easy	2024/07/06	[x]	[ ]
226	Invert Binary Tree	C++		Easy	2024/07/06	[x]	[ ]
129	Sum Root to Leaf Numbers	C++		Medium	2024/07/10	[x]	[ ]
124	Binary Tree Maximum Path Sum	C++		Hard	2024/07/10	[x]	[ ]
173	Binary Search Tree Iterator	C++		Medium	2024/07/11	[x]	[ ]
236	Lowest Common Ancestor of a Binary Tree	C++		Medium	2024/07/11	[x]	[ ]
530	Minimum Absolute Difference in BST	C++		Easy	2024/07/11	[x]	[ ]
230	Kth Smallest Element in a BST	C++		Medium	2024/07/11	[x]	[ ]
637	Average of Levels in Binary Tree	C++		Easy	2024/07/12	[x]	[ ]
2196	Create Binary Tree From Descriptions	C++		Medium	2024/07/15	[x]	[ ]
1740	Find Distance in a Binary Tree	C++		Medium	2024/07/15	[x]	[ ]
2096	Step-By-Step Directions From a Binary Tree Node to Another	C++		Medium	2024/07/16	[x]	[ ]
1110	Delete Nodes And Return Forest	C++		Medium	2024/07/17	[x]	[ ]
1530	Number of Good Leaf Nodes Pairs	C++		Medium	2024/07/18	[ ]	[ ]

Tree

#	Title	Solution	Note	Difficulty	Date	Done	Think Again

Heap

• Min Heap Implementation: C

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
703	Kth Largest Element in a Stream	C++		Easy	2024/03/04	[ ]	[ ]

Trie

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
208	Implement Trie (Prefix Tree)	C++		Medium	2024/01/18	[x]	[ ]

Monotonic Queue

#	Title	Solution	Note	Difficulty	Date	Done	Think Again

Disjoint Set

• Linked-list implementation: main.cpp
• Disjoint-sets Forest implementation: main.cpp

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
547	Number of Provinces	C++		Medium	2024/01/27	[x]	[ ]
261	Graph Valid Tree	C++		Medium	2024/01/27	[x]	[ ]

演算法策略

Sorting

• Insertion Sort Implementation: InsertionSort.c
• Selection Sort Implementation: SelectionSort.c
• Bubbble Sort Implementation: BubbleSort.c

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
75	Sort Colors	C++		Medium	2024/06/12	[x]	[ ]
274	H-Index	C++		Medium	2024/06/29	[x]	[ ]
148	Sort List	C++		Medium	2024/07/13	[x]	[ ]

Binary Search

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
704	Binary Search	Iterative Recursive	README Note	Easy	2023/12/30	[x]	[ ]
33	Search in Rotated Sorted Array	C++	README Note	Medium	2023/12/31	[x]	[ ]
287	Find the Duplicate Number	Sort and Binary Search Bit Sum	Note	Medium	2024/01/01	[x]	[ ]
162	Find Peak Element	C++	Note	Medium	2024/01/02	[x]	[ ]
74	Search a 2D Matrix	C++	Note	Medium	2024/01/04	[x]	[ ]
744	Find Smallest Letter Greater Than Target	C++	Note	Easy	2024/01/04	[x]	[ ]
1351	Count Negative Numbers in a Sorted Matrix	C++	Note	Easy	2024/01/04	[x]	[ ]
34	Find First and Last Position of Element in Sorted Array	C++	Note	Medium	2024/01/05	[x]	[ ]
436	Find Right Interval	C++	Note	Medium	2024/01/05	[x]	[ ]
981	Time Based Key-Value Store	C++	Note	Medium	2024/01/06	[x]	[ ]
153	Find Minimum in Rotated Sorted Array	C++		Medium	2024/01/11	[x]	[ ]
154	Find Minimum in Rotated Sorted Array II	C++		Hard	2024/01/11	[x]	[ ]
702	Search in a Sorted Array of Unknown Size	C++		Medium	2024/01/17	[ x]	[ ]
362	Design Hit Counter	C++		Medium	2024/03/17	[x]	[ ]
633	Sum of Square Numbers	C++		Medium	2024/06/17	[x]	[ ]

Two-Pointers

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
88	Merge Sorted Array	C++		Easy	2024/01/06	[x]	[ ]
15	3Sum	C++		Medium	2024/01/06	[x]	[ ]
1	Two Sum	C++		Easy	2024/01/07	[x]	[ ]
11	Container With Most Water	C++	Note	Medium	2024/01/07	[x]	[ ]
34	Next Permutation	C++	Note	Medium	2024/01/07	[x]	[ ]
125	Valid Palindrome	C++		Easy	2024/07/03	[x]	[ ]
121	Best Time to Buy and Sell Stock	C++		Easy	2024/07/14	[x]	[ ]

Sliding Window

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
228	Summary Ranges	C++		Easy	2024/07/04	[x]	[ ]
3	Longest Substring Without Repeating Characters	C++		Medium	2024/07/05	[x]	[ ]

Bit Operation

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
1550	Three Consecutive Odds	C++		Easy	2024/07/01	[ ]	[ ]

Backtracking

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
17	Letter Combinations of a Phone Number	C++		Medium	2024/07/13	[x]	[ ]

Recursion

#	Title	Solution	Note	Difficulty	Date	Done	Think Again

Graph Algorithm

• Adjacency List Implementation: main.cpp
• BFS Implementation main.cpp
• DFS Implementation dfs-with-adjacency-matrix.cpp

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
547	Number of Provinces	C++		Medium	2024/01/27	[x]	[ ]
261	Graph Valid Tree	C++		Medium	2024/01/27	[x]	[ ]
490	The Maze	C++		Medium	2024/03/19	[x]	[ ]
802	Find Eventual Safe States	C++		Medium	2024/01/28	[ ]	[ ]
695	Max Area of Island	C++		Medium	2024/06/13	[x]	[ ]
286	Walls and Gates	C++		Medium	2024/06/13	[x]	[ ]
994	Rotting Oranges	C++		Medium	2024/06/13	[x]	[ ]
2285	Maximum Total Importance of Roads	C++		Medium	2024/06/28	[x]	[ ]
841	Keys and Rooms	C++		Medium	2024/07/06	[x]	[ ]
1129	Shortest Path with Alternating Colors	C++		Medium	2024/07/06	[x]	[ ]
997	Find the Town Judge	C++		Easy	2024/07/06	[x]	[ ]
200	Number of Islands	C++		Medium	2024/07/09	[x]	[ ]
1926	Nearest Exit from Entrance in Maze	C++		Medium	2024/07/09	[x]	[ ]
1557	Minimum Number of Vertices to Reach All Nodes	C++		Medium	2024/07/09	[x]	[ ]
399	Evaluate Division	C++		Medium	2024/07/13	[x]	[ ]
733	Flood Fill	C++		Medium	2024/07/13	[x]	[ ]
207	Course Schedule	C++		Medium	2024/06/14	[ ]	[ ]

Greedy

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
948	Bag of Tokens	C++		Medium	2024/03/04	[x]	[ ]
1564	Put Boxes Into the Warehouse I	C++		Medium	2024/06/15	[x]	[ ]
134	Gas Station	C++		Medium	2024/06/29	[ ]	[ ]
1580	Put Boxes Into the Warehouse II	C++		Medium	2024/06/15	[x]	[ ]
135	Candy	C++		Hard	2024/07/02	[x]	[ ]
1509	Minimum Difference Between Largest and Smallest Value in Three Moves	C++		Medium	2024/07/02	[x]	[ ]
452	Minimum Number of Arrows to Burst Balloons	C++		Medium	2024/07/10	[x]	[ ]
1717	Maximum Split of Positive Even Integers	C++		Medium	2024/07/12	[x]	[ ]
68	Text Justification	C++		Hard	2024/07/16	[x]	[ ]

Dynamic Programming

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
70	Climbing Stairs	C++		Easy	2024/01/04	[x]	[ ]
1137	N-th Tribonacci Number	C++		Easy	2024/01/05	[x]	[ ]
746	Min Cost Climbing Stairs	C++		Easy	2024/01/05	[x]	[ ]
198	House Robber	C++		Medium	2024/01/05	[x]	[ ]
740	Delete and Earn	C++	Note	Medium	2024/01/06	[x]	[ ]
62	Unique Paths	C++	Note	Medium	2024/01/06	[x]	[ ]
64	Minimum Path Sum	C++		Medium	2024/01/06	[x]	[ ]
63	Unique Paths II	C++		Medium	2024/01/11	[x]	[ ]
120	Triangle	C++		Medium	2024/01/13	[x]	[ ]
931	Minimum Falling Path Sum	C++		Medium	2024/01/16	[x]	[ ]
221	Maximal Square	C++		Medium	2024/01/17	[x]	[ ]
5	Longest Palindromic Substring	C++	Note	Medium	2024/01/17	[x]	[ ]
139	Word Break	C++	Note	Medium	2024/01/18	[x]	[ ]
516	Longest Palindromic Subsequence	C++		Medium	2024/01/18	[x]	[ ]
72	Edit Distance	C++		Medium	2024/01/22	[x]	[ ]
712	Minimum ASCII Delete Sum for Two Strings	C++		Medium	2024/01/25	[x]	[ ]
300	Longest Increasing Subsequence	C++		Medium	2024/01/25	[x]	[ ]
673	Number of Longest Increasing Subsequence	C++		Medium	2024/01/25	[x]	[ ]
646	Maximum Length of Pair Chain	C++		Medium	2024/01/25	[x]	[ ]
1218	Longest Arithmetic Subsequence of Given Difference	C++		Medium	2024/01/26	[x]	[ ]
416	Partition Equal Subset Sum	C++		Medium	2024/06/13	[x]	[ ]
55	Jump Game	C++		Medium	2024/06/29	[x]	[ ]
45	Jump Game II	C++		Medium	2024/07/02	[x]	[ ]
2582	Pass the Pillow	C++		Easy	2024/07/07	[x]	[ ]
1823	Find the Winner of the Circular Game	C++		Medium	2024/07/08	[x]	[ ]
53	Maximum Subarray	C++		Medium	2024/07/13	[x]	[ ]

Divide and Conquer

#	Title	Solution	Note	Difficulty	Date	Done	Think Again
427	Construct Quad Tree	C++		Medium	2024/07/13	[x]	[ ]

Reference：

• Leetcode刷題學習筆記--心得統整 - HackMD
• 0到100的軟體工程師面試之路 :: 2022 iThome 鐵人賽
• 演算法學習之-Leetcode-破關總指南（一）. 新手村與基本功訓練 | by Arthur Lin | AppWorks School | Medium
• Re: [請益] Leetcode刷一輪到能面試的程度要多久？ - 看板Soft_Job - PTT網頁版 (pttweb.cc)
• Re: [討論] 軟體工作真的有需要刷題嗎? - 看板 Soft_Job - 批踢踢實業坊 (ptt.cc)
• 思而不學則殆 站在大神的肩膀上
• coding interview university
• Blind 75
• Grind 169
• How to practice for 2200+ rating in LC
• 從面試官角度來看程式面試：兩大能力與七個階段