Personal notes for leetcode.com solutions with support for local building and unit testing.

Top interviewed: 64 / 145

Appear in nowcoder.com: 2 / 148

In total: 70 / 1350

Solutions that are 99.00%+ in running time: 43

1. Two Sum

• Brutal force: 72ms (top 43.79%)
• Hash table (map): 4ms (top 100.00%)

2. Add Two Numbers

• Linked list: 16ms (top 100.00%)

3. Longest Substring Without Repeating Characters

• Hash table (map): 8ms (top 100.00%)

4. Median of Two Sorted Arrays

• Non-recursive: 28 ms (top 96.13%)
• Recursion: 16 ms (top 100.00%)

5. Longest Palindromic Substring

• Brutal force: 8ms (top 87.41%)
• Manacher's algorithm: 0ms (top 100.00%)

6. ZigZag Conversion

• Brutal force: 40ms (top 55.26%)
• Fast for-loop: 8ms (top 100.00%)

7. Reverse Integer

• Use INT_MAX: 4ms (top 100.00%)

8. String to Integer (atoi)

• Use INT_MAX: 8ms (top 99.90%)

9. Palindrome Number

• Lookup table: 52ms (top 100.00%)

10. Regular Expression Matching

• Dynamic programming: 4ms (top 100.00%)

11. Container With Most Water

• Two pointers: 12ms (top 100.00%)

12. Integer to Roman

• Two arrays: 28ms (top 99.20%)
• Lookup table: 28ms (top 99.20%)

13. Roman to Integer

• Two vectors: 36ms (top 98.41%)
• Map: 44ms (top 97.72%)

14. Longest Common Prefix

• 4ms (top 100.00%)

15. 3Sum

• Two pointers: 112ms (top 99.88%)

16. 3Sum Closest

• Two pointers: 8ms (top 100.00%)

17. Letter Combinations of a Phone Number

• Deque: 4ms (top 100.00%)

18. 4Sum

• Set: 40ms (top 82.57%)
• Fast for-loop: 20ms (top 90.04%)

19. Remove Nth Node From End of List

• One pass: 8ms (top 100.00%)

20. Valid Parentheses

• Stack: 4ms (top 100.00%)

21. Merge Two Sorted Lists

• Two swaps: 12ms (top 100.00%)

22. Generate Parentheses

• Deque: 8ms (top 100.00%)

23. Merge k Sorted Lists

• Use 021: 176ms (top 25.72%)
• Priority queue: 32ms (top 98.10%)

26. Remove Duplicates from Sorted Array

• 20ms (top 99.75%)

28. Implement strStr()

• 8ms (top 98.99%)
• KMP: 4ms (top 91.65%)

29. Divide Two Integers

• All int without <limits.h>: 8ms (top 100.00%)

33. Search in Rotated Sorted Array

• 0ms (top 100.00%)

34. Find First and Last Position of Element in Sorted Array

• 8ms (top 98.52%)

36. Valid Sudoku

• 8ms (top 99.96%)

38. Count and Say

• 4ms (top 97.84%)

41. First Missing Positive

• 4ms (top 96.34%)

42. Trapping Rain Water

• 4ms (top 99.71%)

44. Wildcard Matching

• 4ms (top 99.84%)

46. Permutations

• Recursive: 20ms (top 22.83%)
• Better loop: 12ms (top 96.86%)

48. Rotate Image

• Direct rotation: 4ms (top 98.21%)
• Flip & swap: 4ms (top 98.21%)

49. Group Anagrams

• 40ms (top 95.50%)

50. Pow(x, n)

• 4ms (top 96.07%)

53. Maximum Subarray

• Divide and conquer: 8ms (top 96.32%)
• Kadane: 4ms (top 99.88%)

54. Spiral Matrix

• 0ms (top 100.00%)

55. Jump Game

• 4ms (top 99.99%)

56. Merge Intervals

• 8ms (top 100.00%)

62. Unique Paths

• 4ms (top 93.30%)

66. Plus One

• 0ms (top 100.00%)

69. Sqrt(x)

• 0ms (top 100.00%)

70. Climbing Stairs

• 4ms (top 90.67%)

73. Set Matrix Zeroes

• 44ms (top 98.55%)

75. Sort Colors

• 0ms (top 100.00%)

76. Minimum Window Substring

• sliding window: 32ms (top 38.25%)
• optimized sliding window: 44ms (top 19.33%)
• hash: 4ms (top 99.92%)

78. Subsets

• 8ms (top 90.16%)
• 4ms (top 98.41%)

79. Word Search

• 92ms (top 48.94%)
• 72ms (top 52.02%)

84. Largest Rectangle in Histogram

• recursion: 32ms (top 14.84%)
• non-recursion: 4ms (top 100.00%)

88. Merge Sorted Array

• additional space: 4ms (top 96.53%)
• 3 pointers: 0ms (top 100.00%)

91. Decode Ways

• 4ms (top 90.46%)

94. Binary Tree Inorder Traversal

• 4ms (top 87.58%)
• 0ms (top 100.00%)

98. Validate Binary Search Tree

• 4ms (top 99.99%)

101. Symmetric Tree

• 0ms (top 100.00%)

102. Binary Tree Level Order Traversal

• 12ms (top 25.64%)
• one queue: 8ms (top 82.74%)

103. Binary Tree Zigzag Level Order Traversal

• 4ms (top 89.75%)

104. Maximum Depth of Binary Tree

• 12ms (top 61.51%)

105. Construct Binary Tree from Preorder and Inorder Traversal

• 40ms (top 19.30%)
• hash: 16ms (top 89.76%)

108. Convert Sorted Array to Binary Search Tree

• 24ms (top 80.31%)

111. Minimum Depth of Binary Tree

• 4ms (top 99.83%)

116. Populating Next Right Pointers in Each Node

• 16ms (top 95.40%)

118. Pascal's Triangle

• swap: 4ms (top 51.26%)
• resize: 0ms (top 100.00%)

121. Best Time to Buy and Sell Stock

• priority queue: 12ms (top 17.37%)
• 4ms (top 97.69%)

122. Best Time to Buy and Sell Stock II

• 0ms (top 100.00%)

124. Binary Tree Maximum Path Sum

• 16ms (top 99.85%)

125. Valid Palindrome

• 4ms (top 99.16%)

127. Word Ladder

• 32ms (top 94.91%)

150. Evaluate Reverse Polish Notation

• 12ms (top 91.72%)

• Ubuntu 18.04
• Visual Studio Code with following extensions:
  • C/C++ (ms-vscode.cpptools)
  • C/C++ Clang Command Adapter (mitaki28.vscode-clang)
  • CMake (twxs.cmake)
  • CMake Tools (vector-of-bool.cmake-tools)
  • CodeLLDB (vadimcn.vscode-lldb)

sudo snap install --classic code
sudo apt-get install pylint

• clang (clang++-8 is used by default. You can use other tools as long as your .vscode/c_cpp_properties.json file is modified correctly)

wget -O - http://apt.llvm.org/llvm-snapshot.gpg.key|sudo apt-key add -
sudo apt-get update
sudo apt-get install clang-8 lldb-8

• CMake
• Boost (for unit testing)

wget -O boost_1_70_0.tar.gz https://dl.bintray.com/boostorg/release/1.70.0/source/boost_1_70_0.tar.gz
tar xzvf boost_1_70_0.tar.gz
cd boost_1_70_0/
sudo apt-get update
sudo apt-get install build-essential g++ python-dev autotools-dev libicu-dev build-essential libbz2-dev libboost-all-dev
./bootstrap.sh --prefix=/usr/
./b2
sudo ./b2 install

Each folder contains 3 files: solution.hpp, solution.cpp and solution_test.cpp. The first folder 001-Two-Sum contains an additional main.cpp file, in case you don't feel like using unit testing and you can test your own cases in main.cpp.

Add following lines to your settings.json to configure the building and linting:

{
 "clang.executable": "clang++-8",
 "clang.cflags": ["c11"],
 "clang.cxxflags": ["-std=c++14"],
 "lldb.executable": "lldb-8"
}

Steps to build a solution:

1. Change the line set(PROBLEM_NAME {Problem_Folder}) in CMakeLists.txt to choose the problem you want to solve, in which {Problem_Folder} is the folder name of the problem. For example, set(PROBLEM_NAME "001-Two-Sum").

2. Press Ctrl + Shift + P to bring up the Command Palette of VSCode. Type in CMake, and look for a CMake: Configure command, select it. It will configure the cache files and makefile which are located in build folder by default.

3. Type in or look for a CMake: Build command in the Command Palette and execute it. It will compile the source codes of the solution that you previously chose.

4. Debug Press Ctrl + Shift + D or click the bug icon on the left. The .vscode/launch.json for debugging is already set up for you, and both GDB and LLDB is supported.

   gdb: Choose (gdb) Launch and you're good to go.

   lldb: Choose (lldb) Launch. You may need to disable and re-enable ms-vscode.cpptools and mitaki28.vscode-clang extensions in case the variables won't properly display in "Watch" Panel. Data visualization is supported (https://github.com/vadimcn/vscode-lldb/wiki/Data-visualization).

5. Unit testing Type in or look for a CMake: Run tests command in the Command Palette and execute it. It will run all test cases in solution_test.cpp. Feel free to add your own test cases.

Clear build folder:

1. Press Ctrl + Shift + P to bring up the Command Palette. Type in Task: Run Task and press enter. Choose clean will delete everything in the build folder. Bear in mind that you need to configure the project after cleaning the folder or switching to another solution, by either executing Task: Run Task -> configure or CMake: Configure.