# LeetCodeCollections

[](https://hackmd.io/oFGEhcbSS2OSunc6adfa1w)


## Introduction
This note is my personal Leetcode practice. Trying to articulate them after my learning. At the same time I'd like to practice English writing as well so as these notes would be completed in English. This way it would be easier to review in the future if needed.

- [Github](https://github.com/Jaimecclin/LeetCodeCollections)

## Categories

### Tree
- Problems
1. Medium [144. Binary Tree Preorder Traversal](https://hackmd.io/zZk01ti-RRWkcDXigm1ayg)
2. Medium [94. Binary Tree Inorder Traversal](https://hackmd.io/ivApRuhVQEyjMYJhHNutBQ)
3. Hard [145. Binary Tree Postorder Traversal](https://hackmd.io/rck1NUdnQp2EmJ9sxQ95jg)
4. Medium [102. Binary Tree Level Order Traversal](https://hackmd.io/0PSEluNbSByMXeedCW2_Jw)
5. Easy [108. Convert Sorted Array to Binary Search Tree](/9yHJ1lqEQ2K_E-BSyRpaSw)
6. Easy [100. Same Tree](https://hackmd.io/jKv-6ydHQW-j6uxzBYLXKQ)
7. Easy [101. Symmetric Tree](https://hackmd.io/h0wlxDL6TtCMphddrEFXMQ)
8. Easy [226. Invert Binary Tree](https://hackmd.io/MOk4wB92Tdy7ERvVzNuL7g)
9. Easy [257. Binary Tree Paths](https://hackmd.io/3w79PJA4Su6YUnwV8Tva2g)
10. Easy & Medium [112. Path Sum I & II](https://hackmd.io/X8BMywz0Q3qV2co8Ooy7jw)
11. Medium [129. Sum Root to Leaf Numbers](https://hackmd.io/xXTzDelzTDG7midQSwoDBw)
12. 298. Binary Tree Longest Consecutive Sequence (Cant write)
13. Easy [111. Minimum Depth of Binary Tree](https://hackmd.io/hP-lAWAISZaoPwt89ZBJug)
14. Easy [104. Maximum Depth of Binary Tree](https://hackmd.io/0CRV6MFJRaGek8BTvlPLDQ)
15. Easy [110. Balanced Binary Tree](https://hackmd.io/V1QgcuVURpaaox5fizZ2Gw)
16. Hard [124. Binary Tree Maximum Path Sum
](https://hackmd.io/Ucst_AvCTTmgTSS-5k7DvQ)
16. [250. Count Univalue Subtrees](https://hackmd.io/zpsx3k4yQ26RrcBjQaGsog)
17. 366. Find Leaves of Binary Tree (Cant write)
18. Medium [337. House Robber III](https://hackmd.io/soSVP8ANQDeCtfR0YG1DQA)
19. Easy [107. Binary Tree Level Order Traversal II](https://hackmd.io/JS9gBNR-SKOAW1_BNg1RGg)
20. Easy [103. Binary Tree Zigzag Level Order Traversal](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/)
21. Medium [199. Binary Tree Right Side View](https://hackmd.io/v59LyFAZSS-fiEipiy0yrA)
22. Medium [98. Validate Binary Search Tree](https://hackmd.io/NItMkXJ0Rw68KX2X3HTwyQ)
23. Medium [116. Populating Next Right Pointers in Each Node](https://hackmd.io/rJcvys3sS1W5hq5ojUy7OQ)
- Note
1. Three ways of Depth First Search: (1)Preorder (2)Inorder (3)Postorder are very important.
2. (Cont'd) It's better to understand recursive and iterative implementation of DFS.
3. Classic Tree Height

    int getHeight(TreeNode* root) {
        if(!root) {
            return 0;
        }
        int leftH = getHeight(root->left);
        int rightH = getHeight(root->right);
        int maxH = max(leftH, rightH);
        return maxH + 1;
    }

---

### Array
- Problems
1. Easy [27. Remove Element](https://hackmd.io/JZISslIOQUaq_wj5rlHLTA)
2. Easy [26. Remove Duplicates from Sorted Array](https://hackmd.io/Smz2SJ57QFe_4K0Gqeyzig)
3. Medium 80. [Remove Duplicates from Sorted Array II](https://hackmd.io/ow-3prR1Sc2WNJWJzZ_z5Q)
4. Unknown 277. Find the Celebrity
5. Easy 189. [Rotate Array](https://hackmd.io/yQ0XjBRqQVySVij7RMbM1w)
6. Hard 41. [First Missing Positive](https://hackmd.io/rWIvxsXxQxumb187Zyy4zw)
7. Easy [ 299. Bulls and Cows](https://hackmd.io/CAbJ7lNbT-O-fKjvwGfzFw)
8. Medium 134. [Gas Station](https://hackmd.io/ogUTvf_BQ6uBd0XO7DAYZA)
9. Medium 274.& 275. [H-Index](https://hackmd.io/mRIs13zZQRWBnzX7SkvkvA)
10. Easy & Medium 243. 244. 245 [Shortest Word Distance I, II, III](https://hackmd.io/0YOnPYVGRiO09c7bP1ECJA)
11. Easy [217. Contains Duplicate](https://hackmd.io/3fLIOv39RKeYpRvmJuBCGw)
12. Easy 219. 220. [Contains Duplicate II & III](https://hackmd.io/9Cuqqr16RR6piKthWvdWCg)
13. Medium 55. Hard 45 [Jump Game I & II](https://hackmd.io/KAhEVPc6SemUntgRYOBJrw) (So hard)
14. Hard [121. 188. Best Time to Buy and Sell Stock](https://hackmd.io/huYrV_FbTTqzAtEWM5xnFg)
15. Medium 11. [Container With Most Water](https://hackmd.io/NkSkdiMOSIu3scMctcaqZQ)
16. Hard [42. Trapping Rain Water](/thsXvd_CSMSl-axI1MqWOQ)
17. Medium [334. Increasing Triplet Subsequence](/p9TGRO7FTiaovOWA6Oshsg)
18. Hard [128. Longest Consecutive Sequence](/oAZsQ6EmSLyOlZ-djoatCQ)
19. Hard [164. Maximum Gap](/2NP1IPjTQqSLfFjn2-EMQw)
20. Medium [525. Contiguous Array](/QIe-FVy3QdaNOQy8wDBImQ)
21. Mediun [287. Find the Duplicate Number](/zwNvhxWtSIqP8jHgmBkfUw)
22. Easy [53. Maximum Subarray](/AoXMcftKR5yPFTCLtp5_vQ)

- Note
1. Be aware it is a sorted array.
2. Two pointers usually is good way to solve.
3. Be careful of negtive index in Python.
4. You have no precise array imagination. More practice needed.

---

### LinkedList
- Problems
1. Easy [206. Reverse Linked List](https://hackmd.io/TzUkBaBlSjuXJ2alR0UhEA)
2. Easy [1290. Convert Binary Number in a Linked List to Integer](/Q-O2MNFmRnC0b6K46OT72g)
3. Easy [876. Middle of the Linked List](/c0B8gOvpSoW1ruksN8n7Aw)
4. Easy [21. Merge Two Sorted Lists](/yoADbDLKQSqLFOCDB0NdHg)
5. Easy [237. Delete Node in a Linked List](https://hackmd.io/6d28t3ARSi-Xgg7xcF4F4A?both)
6. Easy [234. Palindrome Linked List](/O-Re3xflRnaJws3UdeTDcw)
7. Easy [141. Linked List Cycle](https://hackmd.io/dCY2MdBUS56Rc9DAWebn1g)
8. Easy [24. Swap Nodes in Pairs](https://hackmd.io/fGUrk1XYSL-LCzehPQyOaw)
9. Medium [1721. Swapping Nodes in a Linked List](/-ivcojW0RhiEFEiCW-2fsQ)
10. Medium [143. Reorder List](/u2K2S5o7Q-ihYbMVJQbp0w)
11. Medium [148. Sort List](/YkSImjM5SPaqgWEPA_jeLg)
12. Medium [328. Odd Even Linked List](https://hackmd.io/2rqJAKhcSam7fmhvrF7jTw)
13. Medium [142. Linked List Cycle II](/_aTXzrzYQjWkTnOPw4IYjg)
14. Medium [382. Linked List Random Node](/g7RyEQ9xRPmvx8cnQtPWPw)
15. Medium [92. Reverse Linked List II](/sIDEXRSCTBOTMuRtf96MLw)
16. Medium [2. Add Two Numbers](/O57PNKdvT--T3QF3OF10zQ)
17. Medium [445. Add Two Numbers II](/CCq3Pi6USuWRj7o5skZ6Jg)
18. Medium [61. Rotate List](/0Bq1VBgaQw2qbYpoU6Jvbw)
19. Medium [19. Remove Nth Node From End of List](/1q1KxpJNRsCxYoFGYeL96A)
20. Medium [2181. Merge Nodes in Between Zeros](/InokOrGBTiWy1rbtB3QrtA)
21. Medium [114. Flatten Binary Tree to Linked List](/obCpBlQuQ6uh31nFNus3mQ)
22. Easy [83. Remove Duplicates from Sorted List](https://hackmd.io/stOGxq_QT3as5DW3fLq26Q)
23. Easy [203. Remove Linked List Elements](https://hackmd.io/nHVP-6myQF-lAMYWNXmvhw)
24. Medium [Remove Duplicates from Sorted List II](https://hackmd.io/N4KXJWoDTk2d6lptlAnChw)
25. Medium [369 Plus One Linked List](https://hackmd.io/Lk0iSFYfTcSJBc_5Epmzrg)
26. Easy [Intersection of Two Linked Lists](https://hackmd.io/fmK2esz-QYCYYqXV1gNNKQ)
27. Add Two Numbers
28. Merge Two Sorted Lists
- Note
1. Adding a dummy node which points to the head might be helpful.
2. The fast and slow pointers helps you find the middle node. The middle one is the end of first list.
3. Tow pointers is the problem killer.

---

### Backtracking
- Problems
1. Medium [78. Subsets](https://hackmd.io/oHxTt4-AQLeLzlycvc1GgQ?edit)
2. Medium [90. Subsets II](/GkLo6PsAQ-q2EdpEBP_fgQ)
3. Medium [77. Combinations](/2cmF81g-THCwxQJpo7mxzA)
4. Medium [39. Combination Sum](/xCgk_Q4VTuG9DFVsLM_mOg)
5. Medium [40. Combination Sum II](https://hackmd.io/Lw9_W0IqRpqvrRFsgUnIHA)
6. Medium [216. Combination Sum III](https://hackmd.io/2TSjD5RNThGGvMgbFB3WSA)
7. Medium [377. Combination Sum IV](/0tWoZsA1SL2IthdPXRkw2w)
8. ? [254. Factor Combinations](/1k0AoqQrRXmvYu48snXZWw)
9. Medium [46. Permutations](/Fht3HQTQRz-6mVeX8DeaDA)
10. Medium [47. Permutations II](/B7g53XcmSAWyggd0nuj1JA)
11. Medium [31. Next Permutation](/kwYWfjZCTuuFnN6Bh3r6_A)
12. Hard [55. Jump Game](https://jaime-lin.medium.com/leetcode-55-jump-game-2496cd718c3e)
- Note
1. Please remember how to do combination and permuation. It's really important.

---

### Dynamic Programming

- Problems
1. Easy [70. Climbing Stairs](/eSKr1ZwYRXCSEbN-2_kQBw)
2. Medium [62. Unique Paths](/oCI1Z7lpQISmhJujGfQTgw)
3. Medium [63. Unique Paths II](/Dkh7_w3HTWCgm5rUEGOULw)
4. Medium [279. Perfect Squares](/eUtP0coQSs-6UzENS_x-4g)
5. Medium [375. Guess Number Higher or Lower II](https://hackmd.io/J5tuKMt_Sv628o-pNHc4nQ)

### Matrix

- Problems
1. Medium [48. Rotate Image](/kpZD6spsRfqPwUlB1rXG-g)
2. Medium [54. Spiral Matrix](/PPcLqOavTL2wFNL-r7T7UA)
3. Medium [59. Spiral Matrix II](/SkU4C895T2Osvhufzqdt-A)
4. Medium [73. Set Matrix Zeroes](/PSTI7UhVSvalKV7BoGm0BQ)
5. Medium [311. Sparse Matrix Multiplication](/AGozxOLmQFWz3UEFXWbfOg)
6. Hard [329. Longest Increasing Path in a Matrix](/gfBOG-VBSNSvKP_FJWNQsA)

---

### Binary Search
- Problems
1. Easy [278. First Bad Version](/_qvPJaLbRMmdyWzUykkkFQ)
2. Easy [35. Search Insert Position](/QZG5FcVXSty8hOEwynWOvQ)
3. Medium [33. Search in Rotated Sorted Array](/DoR6t8e3TXyOcy-ZiQLntg)
4. Medium [81. Search in Rotated Sorted Array II](https://hackmd.io/7SisJTJsQfaRJplstjpnjA)
5. Medium [153. Find Minimum in Rotated Sorted Array](/paC_5VYjRMW42v9pmnvA-A)
6. Hard [154. Find Minimum in Rotated Sorted Array II](https://hackmd.io/vniePA2ISZajm6H1m9IwIA)
7. Medium [162. Find Peak Element](https://hackmd.io/2qmLw0Z_S22ACI-7nNWmPA)
8. Easy [374. Guess Number Higher or Lower](https://hackmd.io/W1Gkp9jeTXKIL18Q2n_Mbw)
9. Medium [34. Find First and Last Position of Element in Sorted Array
](https://hackmd.io/VCSVjxZAS7q92R2Vf9fwPw)
- Note
1. Binary search summary [Grandyang](https://www.cnblogs.com/grandyang/p/6854825.html)
2. Be very careful of boundary.
3. Finding the best personal binary search implementaion can help you get rid of unnecessary troubles. For me, I like this:

    # Python version
    left, right = 0, len(nums)
    mid = 0
    while left < right:
        mid = left + (right-left) // 2
        if nums[mid] > target:
            right = mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            return mid
    # Not found
    return -1

or

    int find(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return right;
    }

---

### Graph

1. Medium 133. [Clone Graph](https://hackmd.io/Bd9YpSXoRpWXjdBa9kkiXQ?both)

- Note

def bfs(matrix):
    m = len(matrix[0])
    n = len(matrix)
    visited = [[0] * n for i in range(m)]
    s = [(0,0)]
    while s:
        x, y = s.pop(0)
        if visited[x][y] == 1:
            continue
        else:
            print(matrix[x][y])
            visited[x][y] = 1
            if x+1 < m:
                s.append((x+1, y))
            if y+1 < n:
                s.append((x, y+1))

def dfs(matrix):
    m = len(matrix[0])
    n = len(matrix)
    visited = [[0] * n for i in range(m)]
    s = [(0,0)]
    while s:
        x, y = s.pop()
        if visited[x][y] == 1:
            continue
        else:
            print(matrix[x][y])
            visited[x][y] = 1
            if x+1 < m:
                s.append((x+1, y))
            if y+1 < n:
                s.append((x, y+1))