# lintcode

**Repository Path**: letItbe/lintcode

## Basic Information

- **Project Name**: lintcode
- **Description**: Yet another AC code for LintCode (253AC/292ALL)
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 2
- **Created**: 2018-03-14
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Yet Another Source Code for [LintCode](http://lintcode.com/problem/)
Current Status : 257`AC` / 292`ALL` in Language `C++`, Up to date (2017-04-27)
For more problems and solutions, you can see my [LintCode](https://git.oschina.net/eudiwffe/lintcode) repository.
I'll keep updating for full summary and better solutions. See [cnblogs](http://eudiwffe.cnblogs.com) to get details or click problem's `Note` directly. `Tip` means has been added tips and sketch (* means has note at cnblogs).
This context template fork from [kamyu104](https://github.com/kamyu104/LintCode) , thanks them very much!
## Algorithms
* [Array](./#array)
* [Backtracking](./#backtracking)
* [Binary Search](./#binary-search)
* [Binary Search Trees](./#binary-search-trees)
* [Bit Manipulation](./#bit-manipulation)
* [Breadth-First Search](./#breadth-first-search)
* [Data Structure](./#data-structure)
* [Depth-First Search](./#depth-first-search)
* [Dynamic Programming](./#dynamic-programming)
* [Greedy](./#greedy)
* [Hash Tables](./#hash-tables)
* [Heap](./#heap)
* [Linked List](./#linked-list)
* [Math](./#math)
* [OO Design](./#oo-design)
* [Queue](./#queue)
* [Recursion](./#recursion)
* [Sort](./#sort)
* [Stack](./#stack)
* [String](./#string)
* [System Design](./#system-design)
* [Tree](./#tree)

## Array
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|6|[Merge Sorted Array](http://lintcode.com/problem/merge-sorted-array/)| [C++](./C++/merge-sorted-array.cpp)| _O(m+n)_ | _O(1)_ | Easy | LeetCode | `Tip` [Merge](http://eudiwffe.cnblogs.com/p/6254394.html)|
|8|[Rotate String](http://lintcode.com/problem/rotate-string/)| [C++](./C++/rotate-string.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` Matrix Transpose |
|9|[Fizz Buzz](http://lintcode.com/problem/fizz-buzz/)| [C++](./C++/fizz-buzz.cpp)| _O(n)_ | _O(1)_ | Easy | | `Tip` Logic |
|30|[Insert Interval](http://lintcode.com/problem/insert-interval/)| [C++](./C++/insert-interval.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode, EPI | `Tip` Duplication |
|31|[Partition Array](http://lintcode.com/problem/partition-array/)| [C++](./C++/partition-array.cpp)| _O(n)_ | _O(1)_ | Medium | | `Tip` Partition |
|32|[Minimum Window Substring](http://lintcode.com/problem/minimum-window-substring/)| [C++](./C++/minimum-window-substring.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | todo |
|38|[Search a 2D Matrix II](http://lintcode.com/problem/search-a-2d-matrix-ii/)| [C++](./C++/search-a-2d-matrix-ii.cpp)| _O(m+n)_ | _O(1)_ | Medium | EPI | `Tip` Fast Search |
|39|[Recover Rotated Sorted Array](http://lintcode.com/problem/recover-rotated-sorted-array/)| [C++](./C++/recover-rotated-sorted-array.cpp)| _O(n)_ | _O(1)_ | Easy | | `Tip` Matrix Transpose |
|46|[Majority Number](http://lintcode.com/problem/majority-number/)| [C++](./C++/majority-number.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` Frequency Count |
|47|[Majority Number II](http://lintcode.com/problem/majority-number-ii/)| [C++](./C++/majority-number-ii.cpp)| _O(n)_ | _O(1)_ | Medium | EPI | `Tip` HashMap |
|48|[Majority Number III](http://lintcode.com/problem/majority-number-iii/)| [C++](./C++/majority-number-iii.cpp)| _O(n)_ | _O(k)_ | Medium | EPI | `Tip` HashMap |
|49|[Sort Letters by Case](http://lintcode.com/problem/sort-letters-by-case/)| [C++](./C++/sort-letters-by-case.cpp)| _O(n)_ | _O(1)_ | Medium | | `Tip` Partition |
|50|[Product of Array Exclude Itself](http://lintcode.com/problem/product-of-array-exclude-itself/)| [C++](./C++/product-of-array-exclude-itself.cpp)| _O(n)_ | _O(1)_ | Easy | | `Tip` State Store |
|51|[Previous Permutation](http://lintcode.com/problem/previous-permutation/)| [C++](./C++/previous-permutation.cpp)| _O(n)_ | _O(1)_ | Medium | | `Tip` [Permutation](http://eudiwffe.cnblogs.com/p/6260699.html) |
|52|[Next Permutation](http://lintcode.com/problem/next-permutation/)| [C++](./C++/next-permutation.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` [Permutation](http://eudiwffe.cnblogs.com/p/6260699.html) |
|57|[3 Sum](http://lintcode.com/problem/3sum/)| [C++](./C++/3sum.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Medium | LeetCode | `Tip` [Two Pointers](http://eudiwffe.cnblogs.com/p/6282635.html) |
|58|[4 Sum](http://lintcode.com/problem/4sum/)| [C++](./C++/4sum.cpp)| _O(n<sup>3</sup>)_ | _O(1)_ | Medium | LeetCode | `Tip` [HashMap](http://eudiwffe.cnblogs.com/p/6282635.html) |
|59|[3 Sum Closest](http://lintcode.com/problem/3sum-closest/)| [C++](./C++/3sum-closest.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Medium | LeetCode | `Tip` [Two Pointers](http://eudiwffe.cnblogs.com/p/6282635.html) |
|64|[Merge Two Sorted Arrays](http://lintcode.com/problem/merge-two-sorted-arrays/)| [C++](./C++/merge-two-sorted-arrays.cpp)| _O(m+n)_ | _O(1)_ | Easy | LeetCode | `Tip` [Merge](http://eudiwffe.cnblogs.com/p/6254394.html) |
|100|[Remove Duplicates from Sorted Array](http://lintcode.com/problem/remove-duplicates-from-sorted-array/)| [C++](./C++/remove-duplicates-from-sorted-array.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` Two Pointers |
|101|[Remove Duplicates from Sorted Array II](http://lintcode.com/problem/remove-duplicates-from-sorted-array-ii/)| [C++](./C++/remove-duplicates-from-sorted-array-ii.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` Two Pointers |
|133|[Longest Words](http://lintcode.com/problem/longest-words/)| [C++](./C++/longest-words.cpp)| _O(n)_ | _O(n)_ | Easy | | `Tip` Greed |
|144|[Interleaving Positive and Negative Numbers](http://lintcode.com/problem/interleaving-positive-and-negative-numbers/)| [C++](./C++/interleaving-positive-and-negative-numbers.cpp)| _O(n)_ | _O(1)_ | Medium | | `Tip` Two Pointers |
|161|[Rotate Image](http://lintcode.com/problem/rotate-image/)| [C++](./C++/rotate-image.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Medium | LeetCode | `Tip` Matrix |
|162|[Set Matrix Zeroes](http://lintcode.com/problem/set-matrix-zeroes/)| [C++](./C++/set-matrix-zeroes.cpp)| _O(m*n)_ | _O(1)_ | Medium | LeetCode | `Tip` [State Transition](http://eudiwffe.cnblogs.com/p/6298027.html) |
|172|[Remove Element](http://lintcode.com/problem/remove-element/)| [C++](./C++/remove-element.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` Two Pointers |
|185|[Matrix Zigzag Traversal](http://lintcode.com/problem/matrix-zigzag-traversal/)| [C++](./C++/matrix-zigzag-traversal.cpp)| _O(m*n)_ | _O(1)_ | Easy | | `Tip` Matrix |
|189|[First Missing Positive](http://lintcode.com/problem/first-missing-positive/)| [C++](./C++/first-missing-positive.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode, EPI | `Tip` Hash |
|190|[Next Permutation II](http://lintcode.com/problem/next-permutation-ii/)| [C++](./C++/next-permutation-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` [Permutation](http://eudiwffe.cnblogs.com/p/6260699.html) |
|200|[Longest Palindromic Substring](http://lintcode.com/problem/longest-palindromic-substring/)| [C++](./C++/longest-palindromic-substring.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | `Manacher's Algorithm` |
|363|[Trapping Rain Water](http://lintcode.com/problem/trapping-rain-water/)| [C++](./C++/trapping-rain-water.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` Two Pointers |
|373|[Partition Array by Odd and Even](http://lintcode.com/problem/partition-array-by-odd-and-even/)| [C++](./C++/partition-array-by-odd-and-even.cpp)| _O(n)_ | _O(1)_ | Easy | | `Tip` Partition |
|374| [Spiral Matrix](http://lintcode.com/problem/spiral-matrix/) | [C++](./C++/spiral-matrix.cpp) | _O(m*n)_    | O(1) | Medium | LeetCode | `Tip` Matrix |
|381| [Spiral Matrix II](http://lintcode.com/problem/spiral-matrix-ii/) | [C++](./C++/spiral-matrix-ii.cpp) | _O(n<sup>2</sup>)_ | _O(1)_ | Medium | LeetCode | `Tip` Matrix |
|382|[Triangle Count](http://lintcode.com/problem/triangle-count/)| [C++](./C++/triangle-count.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Medium | | Todo:jiuzhang |
|383|[Container With Most Water](http://lintcode.com/problem/container-with-most-water/)| [C++](./C++/container-with-most-water.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode, EPI | `Tip` Two Pointers |
|388|[Permutation Sequence](http://lintcode.com/problem/permutation-sequence/)| [C++](./C++/permutation-sequence.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Medium | LeetCode | `Tip` [Permutation](http://eudiwffe.cnblogs.com/p/6260699.html) |
|389|[Valid Sudoku](http://lintcode.com/problem/valid-sudoku/)| [C++](./C++/valid-sudoku.cpp)| _O(9<sup>2</sup>)_ | _O(9)_ | Easy | LeetCode | `Tip` Sudoku |
|404|[Subarray Sum II](http://lintcode.com/problem/subarray-sum-ii/)| [C++](./C++/subarray-sum-ii.cpp)| _O(nlogn)_ | _O(n)_ | Hard | | todo |
|405|[Submatrix Sum](http://lintcode.com/problem/submatrix-sum/)| [C++](./C++/submatrix-sum.cpp)| _O(m*n<sup>2</sup>)_ | _O(m)_ | Hard | | todo |
|406|[Minimum Size Subarray Sum](http://lintcode.com/problem/minimum-size-subarray-sum/)| [C++](./C++/minimum-size-subarray-sum.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` Two Pointers, Binary Search |
|539|[Move Zeroes](http://lintcode.com/problem/move-zeroes/)| [C++](./C++/move-zeroes.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` Two Pointers |
## Backtracking
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|15|[Permutations](http://lintcode.com/problem/permutations/)| [C++](./C++/permutations.cpp)| _O(n*n!)_ | _O(n)_ | Medium | LeetCode, EPI | `Tip` [Permutation](http://eudiwffe.cnblogs.com/p/6260699.html) |
|16|[Permutations II](http://lintcode.com/problem/permutations-ii/)| [C++](./C++/permutations-ii.cpp)| _O(n*n!)_ | _O(n)_ | Medium | LeetCode, EPI | `Tip` [Permutation](http://eudiwffe.cnblogs.com/p/6260699.html) |
|17|[Subsets](http://lintcode.com/problem/subsets/)| [C++](./C++/subsets.cpp)| _O(n*2<sup>n</sip>)_ | _O(1)_ | Medium | LeetCode | `Tip` Backtracking |
|18|[Subsets II](http://lintcode.com/problem/subsets-ii/)| [C++](./C++/subsets-ii.cpp)| _O(n*2<sup>n</sup>)_ | _O(1)_ | Medium | LeetCode | `Tip` Subset |
|33|[N-Queens](http://lintcode.com/problem/n-queens/)| [C++](./C++/n-queens.cpp)| _O(n*n!)_ | _O(n)_ | Medium | LeetCode, EPI | `Tip` N-Queens |
|34|[N-Queens II](http://lintcode.com/problem/n-queens-ii/)| [C++](./C++/n-queens-ii.cpp)| _O(n*n!)_ | _O(n)_ | Medium | LeetCode, EPI | `Tip` N-Queens |
|123|[Word Search](http://lintcode.com/problem/word-search/)| [C++](./C++/word-search.cpp)| _O(m*n*l)_ | _O(l)_ | Medium | LeetCode | `Tip` Backtracking |
|132|[Word Search II](http://lintcode.com/problem/word-search-ii/)| [C++](./C++/word-search-ii.cpp)| _O(m*n*l)_ | _O(l)_ | Hard | | `Tip` Trie, DFS |
|135|[Combination Sum](http://lintcode.com/problem/combination-sum/)| [C++](./C++/combination-sum.cpp)| _O(k*n<sup>k</sup>)_ | _O(k)_ | Medium | LeetCode | `Tip` DFS |
|136|[Palindrome Partitioning](http://lintcode.com/problem/palindrome-partitioning/)| [C++](./C++/palindrome-partitioning.cpp)| _O(2<sup>n</sup>)_ | _O(n)_ | Easy | LeetCode, EPI | `Tip` Substring |
|152|[Combinations](http://lintcode.com/problem/combinations/)| [C++](./C++/combinations.cpp)| _O(k*n<sup>k</sup>)_ | _O(k)_ | Medium | LeetCode, EPI | `Tip` Combination |
|153|[Combination Sum II](http://lintcode.com/problem/combination-sum-ii/)| [C++](./C++/combination-sum-ii.cpp)| _O(k*C(n,k))_ | _O(k)_ | Medium | LeetCode | `Tip` DFS |
|425|[Letter Combinations of a Phone Number](http://lintcode.com/problem/letter-combinations-of-a-phone-number/) | [C++](./C++/letter-combinations-of-a-phone-number.cpp)| _O(n*4<sup>n</sup>)_ | _O(n)_ | Medium | LeetCode | `Tip` Enumeration |
|426| [Restore IP Addresses](http://lintcode.com/problem/restore-ip-addresses/) | [C++](./C++/restore-ip-addresses.cpp) | _O(1)_ | _O(1)_ | Medium | LeetCode | `Tip` Backtracking |
|427| [Generate Parentheses](http://lintcode.com/problem/generate-parentheses/)| [C++](./C++/generate-parentheses.cpp)| _O(4<sup>n</sup>/n<sup>3/2</sup>)_ | _O(n)_ | Medium | LeetCode | todo |
## Binary Search
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|14|[First Position of Target](http://lintcode.com/problem/first-position-of-target/)| [C++](./C++/first-position-of-target.cpp)| _O(logn)_ | _O(1)_ | Easy | | `Tip` Binary Search |
|28|[Search a 2D Matrix](http://lintcode.com/problem/search-a-2d-matrix/)| [C++](./C++/search-a-2d-matrix.cpp)| _O(logm+logn)_ | _O(1)_ | Easy | LeetCode | `Tip` Matrix |
|60|[Search Insert Position](http://lintcode.com/problem/search-insert-position/)| [C++](./C++/search-insert-position.cpp)| _O(logn)_ | _O(1)_ | Easy | LeetCode | `Tip` Lower Bound |
|61|[Search for a Range](http://lintcode.com/problem/search-for-a-range/)| [C++](./C++/search-for-a-range.cpp)| _O(logn)_ | _O(1)_ | Medium | LeetCode | `Tip` Lower/Upper Bound |
|62|[Search in Rotated Sorted Array](http://lintcode.com/problem/search-in-rotated-sorted-array/)| [C++](./C++/search-in-rotated-sorted-array.cpp)| _O(logn)_ | _O(1)_ | Medium | LeetCode | `Tip` only ascending |
|63|[Search in Rotated Sorted Array II](http://lintcode.com/problem/search-in-rotated-sorted-array-ii/)| [C++](./C++/search-in-rotated-sorted-array-ii.cpp)| _O(logn)_ | _O(1)_ | Medium | LeetCode | `Tip` only ascending |
|65|[Median of two Sorted Arrays](http://lintcode.com/problem/median-of-two-sorted-arrays/)| [C++](./C++/median-of-two-sorted-arrays.cpp)| _O(log(min(m,n)))_ | _O(1)_ | Hard | LeetCode, EPI | todo |
|74|[First Bad Version](http://lintcode.com/problem/first-bad-version/)| [C++](./C++/first-bad-version.cpp)| _O(logn)_ | _O(1)_ | Medium | | `Tip` Binary Search |
|75|[Find Peak Element](http://lintcode.com/problem/find-peak-element/)| [C++](./C++/find-peak-element.cpp)| _O(logn)_ | _O(1)_ | Medium | LeetCode | `Tip` |
|76|[Longest Increasing Subsequence](http://lintcode.com/problem/longest-increasing-subsequence/)| [C++](./C++/longest-increasing-subsequence.cpp)| _O(nlogn)_ | _O(n)_ | Medium | CTCI | `Tip` |
|141|[Sqrt(x)](http://lintcode.com/problem/sqrtx/)| [C++](./C++/sqrtx.cpp)| <<_O(logn)_ | _O(1)_ | Easy | LeetCode | `Tip` Newton Iteration |
|159|[Find Minimum in Rotated Sorted Array](http://lintcode.com/problem/find-minimum-in-rotated-sorted-array/)| [C++](./C++/find-minimum-in-rotated-sorted-array.cpp)| _O(logn)_ | _O(1)_ | Medium | LeetCode | `Tip` only ascending |
|160|[Find Minimum in Rotated Sorted Array II](http://lintcode.com/problem/find-minimum-in-rotated-sorted-array-ii/)| [C++](./C++/find-minimum-in-rotated-sorted-array-ii.cpp)| _O(logn)_ | _O(1)_ | Medium | LeetCode | only ascending |
|183|[Wood Cut](http://lintcode.com/problem/wood-cut/)| [C++](./C++/wood-cut.cpp)| _O(nlogL)_ | _O(1)_ | Medium | | `Tip` |
|248|[Count of Smaller Number](http://lintcode.com/problem/count-of-smaller-number/)| [C++](./C++/count-of-smaller-number.cpp)| _O(n+klogn)_,_O((n+k)logn)_ | _O(h)_ | Medium | | `Tip` Segment Tree, Binary Search |
|390|[Find Peak Element II](http://lintcode.com/problem/find-peak-element-ii/)| [C++](./C++/find-peak-element-ii.cpp) | _O(m+n)_ | _O(1)_ | Hard | | todo:jiuzhang |
|437|[Copy Books](http://lintcode.com/problem/copy-books/)| [C++](./C++/copy-books.cpp) | _O(nlogp)_ | _O(1)_ | Hard | UVa 714 | todo |
|457|[Classical Binary Search](http://lintcode.com/problem/classical-binary-search/)|[C++](./C++/classical-binary-search.cpp)| _O(logn)_ | _O(1)_ | Easy | | `Tip` Binary Search |
## Binary Search Trees
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|11|[Search Range in Binary Search Tree](http://lintcode.com/problem/search-range-in-binary-search-tree/)| [C++](./C++/search-range-in-binary-search-tree.cpp)| _O(n)_ | _O(h)_ | Medium | EPI | `Tip` Branch Bound |
|86|[Binary Search Tree Iterator](http://lintcode.com/problem/binary-search-tree-iterator/)| [C++](./C++/binary-search-tree-iterator.cpp)| _O(1)_ | _O(h)_ | Hard | LeetCode | `Tip` Stack |
|87|[Remove Node in Binary Search Tree](http://lintcode.com/problem/remove-node-in-binary-search-tree/)| [C++](./C++/remove-node-in-binary-search-tree.cpp)| _O(h)_ | _O(h)_ | Hard | | `Tip` [BST](http://eudiwffe.cnblogs.com/p/6207196.html) |
|249|[Count of Smaller Number before itself](http://lintcode.com/problem/count-of-smaller-number-before-itself/)| [C++](./C++/count-of-smaller-number-before-itself.cpp)| _O(nlogn)_ | _O(n)_ | Hard | | `Tip` Segment Tree |
|360|[Sliding Window Median](http://lintcode.com/problem/sliding-window-median/)| [C++](./C++/sliding-window-median.cpp)| _O(nlogw)_ | _O(w)_ | Hard | | `Tip` BST |
|391|[Number of Airplanes in the Sky](http://lintcode.com/problem/number-of-airplanes-in-the-sky/)| [C++](./C++/number-of-airplanes-in-the-sky.cpp)| _O(nlogn)_ | _O(n)_ | Easy | | `Tip` BST, Heap, Sort |
|401|[Kth Smallest Number in Sorted Matrix](http://lintcode.com/problem/kth-smallest-number-in-sorted-matrix/)| [C++](./C++/kth-smallest-number-in-sorted-matrix.cpp)| _O(klog(min(m,n,k)))_ | _O(min(m,n,k))_ | Medium | | `Tip` Heap |
## Bit Manipulation
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|1|[A + B Problem](http://lintcode.com/problem/a-b-problem/)| [C++](./C++/a-b-problem.cpp)| _O(1)_ | _O(1)_ | Medium | | `Tip` Bit Operator |
|82|[Single Number](http://lintcode.com/problem/single-number/)| [C++](./C++/single-number.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` XOR |
|83|[Single Number II](http://lintcode.com/problem/single-number-ii/)| [C++](./C++/single-number-ii.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` Bit Operator, HashMap |
|84|[Single Number III](http://lintcode.com/problem/single-number-iii/)| [C++](./C++/single-number-iii.cpp)| _O(n)_ | _O(1)_ | Medium | CTCI | `Tip` XOR, Bit|
|142|[O(1) Check Power of 2](http://lintcode.com/problem/o1-check-power-of-2/)| [C++](./C++/o1-check-power-of-2.cpp)| _O(1)_ | _O(1)_ | Easy | | `Tip` Bit |
|179|[Update Bits](http://lintcode.com/problem/update-bits/)| [C++](./C++/update-bits.cpp)| _O(1)_ | _O(1)_ | Medium | CTCI | `Tip` Bit |
|181|[Flip Bits](http://lintcode.com/problem/flip-bits/)| [C++](./C++/flip-bits.cpp)| _O(1)_ | _O(1)_ | Easy | CTCI | `Tip` |
|196|[Find the Missing Number](http://lintcode.com/problem/find-the-missing-number/)| [C++](./C++/find-the-missing-number.cpp)| _O(n)_ | _O(1)_ | Medium | | `Tip` XOR |
|365|[Count 1 in Binary](http://lintcode.com/problem/count-1-in-binary/)| [C++](./C++/count-1-in-binary.cpp)| _O(1)_ | _O(1)_ | Easy | CTCI | `Tip` |
## Breadth-First Search
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|69|[Binary Tree Level Order Traversal](http://lintcode.com/problem/binary-tree-level-order-traversal/)| [C++](./C++/binary-tree-level-order-traversal.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | `Tip` BFS, Queue |
|70|[Binary Tree Level Order Traversal II](http://lintcode.com/problem/binary-tree-level-order-traversal-ii/)| [C++](./C++/binary-tree-level-order-traversal-ii.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | `Tip` BFS, Queue |
|71|[Binary Tree Zigzag Level Order Traversal](http://lintcode.com/problem/binary-tree-zigzag-level-order-traversal/)| [C++](./C++/binary-tree-zigzag-level-order-traversal.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | `Tip` BFS, Queue |
|120|[Word Ladder](http://lintcode.com/problem/word-ladder/)| [C++](./C++/word-ladder.cpp)| _O(n*d)_ | _O(d)_ | Medium | LeetCode | `Tip` BFS, Queue |
|121|[Word Ladder II](http://lintcode.com/problem/word-ladder-ii/)| [C++](./C++/word-ladder-ii.cpp)| _O(n*d)_ | _O(d)_ | Hard | LeetCode | `Tip` BFS, Multi-Tree, DFS |
|127|[Topological Sorting](http://lintcode.com/problem/topological-sorting/)| [C++](./C++/topological-sorting.cpp)| _O(V+E)_ | _O(E)_ | Medium | | `Tip` BFS, Queue |
|137|[Clone Graph](http://lintcode.com/problem/clone-graph/)| [C++](./C++/clone-graph.cpp)| _O(V+E)_ | _O(V)_ | Medium | | `Tip` BFS or DFS |
|176|[Route Between Two Nodes in Graph](http://lintcode.com/problem/route-between-two-nodes-in-graph/)| [C++](./C++/route-between-two-nodes-in-graph.cpp)| _O(n)_ | _O(n)_ | Medium | | `Tip` DFS, BFS |
|178| [Graph Valid Tree](http://lintcode.com/problem/graph-valid-tree/)| [C++](./C++/graph-valid-tree.cpp) | _O(V+E)_ | _O(V+E)_ | Medium | LeetCode | `Tip` BFS, Graph |
|431|[Find the Connected Component in the Undirected Graph](http://lintcode.com/problem/find-the-connected-component-in-the-undirected-graph/)| [C++](./C++/find-the-connected-component-in-the-undirected-graph.cpp)| _O(n)_ | _O(n)_ | Medium | | todo:jiuzhang |
|477|[Surrounded Regions](http://lintcode.com/problem/surrounded-regions/)|[C++](./C++/surrounded-regions.cpp)| _O(m*n)_ | _O(1)_ | Medium | LeetCode | `Tip` DFS, BFS |
## Data Structure
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|134|[LRU Cache](http://lintcode.com/problem/lru-cache/)| [C++](./C++/lru-cache.cpp)| _O(1)_ | _O(k)_ | Hard | LeetCode, EPI | `Tip` List(User-Defined), HashMap |
## Depth-First Search
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|90|[K Sum II](http://lintcode.com/problem/k-sum-ii/)| [C++](./C++/k-sum-ii.cpp)| _O(k*C(n,k))_ | _O(k)_ | Medium | | `Tip` DFS |
|376|[Binary Tree Path Sum](http://lintcode.com/problem/binary-tree-path-sum/)| [C++](./C++/binary-tree-path-sum.cpp)| _O(n)_ | _O(h)_ | Easy | LeetCode | `Tip` DFS |
|433|[Number of Islands](http://lintcode.com/problem/number-of-islands/)| [C++](./C++/number-of-islands.cpp)| _O(m*n)_ | _O(1)_ | Easy | LeetCode | `Tip` DFS |
|480| [Binary Tree Paths](http://lintcode.com/problem/binary-tree-paths/) | [C++](./C++/binary-tree-paths.cpp) | _O(n*h)_ | _O(h)_ | Easy | LeetCode | `Tip` DFS |
## Dynamic Programming
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|20|[Dices Sum](http://lintcode.com/problem/dices-sum/)| [C++](./C++/dices-sum.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Hard | | todo |
|29|[Interleaving String](http://lintcode.com/problem/interleaving-string/)| [C++](./C++/interleaving-string.cpp)| _O(m*n)_ | _O(m*n)_, _O(1)_ | Medium | EPI | `Tip` DP, DFS|
|43|[Maximum Subarray III](http://lintcode.com/problem/maximum-subarray-iii/)| [C++](./C++/maximum-subarray-iii.cpp)| _O(k*n)_ | _O(k*n)_ | Hard | | |
|77|[Longest Common Subsequence](http://lintcode.com/problem/longest-common-subsequence/)| [C++](./C++/longest-common-subsequence.cpp)| _O(m*n)_ | _O(min(m,n))_ | Medium | | |
|79|[Longest Common Substring](http://lintcode.com/problem/longest-common-substring/)| [C++](./C++/longest-common-substring.cpp)| _O(m*n)_ | _O(min(m,n))_ | Medium | | |
|89|[K Sum](http://lintcode.com/problem/k-sum/)| [C++](./C++/k-sum.cpp)| _O(k*n*t)_ | _O(n*t)_ | Hard | | |
|91|[Minimum Adjustment Cost](http://lintcode.com/problem/minimum-adjustment-cost/)| [C++](./C++/minimum-adjustment-cost.cpp)| _O(k*n*t)_ | _O(k)_ | Medium | | |
|92|[Backpack](http://lintcode.com/problem/backpack/)| [C++](./C++/backpack.cpp)| _O(m*n)_ | _O(m)_ | Easy | | |
|107|[Word Break](http://lintcode.com/problem/word-break/)| [C++](./C++/word-break.cpp)| _O(n*l<sup>2</sup>)_ | _O(n)_ | Medium | LeetCode, EPI | todo |
|108|[Palindrome Partitioning II](http://lintcode.com/problem/palindrome-partitioning-ii/)| [C++](./C++/palindrome-partitioning-ii.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Medium | LeetCode, EPI | |
|109|[Triangle](http://lintcode.com/problem/triangle/)| [C++](./C++/triangle.cpp)| _O(n)_ | _O(n)_ | Easy | LeetCode, EPI | |
|110|[Minimum Path Sum](http://lintcode.com/problem/minimum-path-sum/)| [C++](./C++/minimum-path-sum.cpp)| _O(m*n)_ | _O(min(m,n))_ | Easy | LeetCode, EPI | |
|111|[Climbing Stairs](http://lintcode.com/problem/climbing-stairs/)| [C++](./C++/climbing-stairs.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|115|[Unique Paths II](http://lintcode.com/problem/unique-paths-ii/)| [C++](./C++/unique-paths-ii.cpp)| _O(m*n)_ | _O(min(m,n))_ | Easy | LeetCode, CTCI | DP, Math |
|118|[Distinct Subsequences](http://lintcode.com/problem/distinct-subsequences/)| [C++](./C++/distinct-subsequences.cpp)| _O(m*n)_ | _O(m)_ | Medium | LeetCode | todo |
|119|[Edit Distance](http://lintcode.com/problem/edit-distance/)| [C++](./C++/edit-distance.cpp)| _O(m*n)_ | _O(min(m,n))_ | Medium | LeetCode, CTCI | DP |
|125|[Backpack II](http://lintcode.com/problem/backpack-ii/)| [C++](./C++/backpack-ii.cpp)| _O(m*n)_ | _O(m)_ | Medium | | |
|149|[Best Time to Buy and Sell Stock](http://lintcode.com/problem/best-time-to-buy-and-sell-stock/)| [C++](./C++/best-time-to-buy-and-sell-stock.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode, EPI | |
|150|[Best Time to Buy and Sell Stock II](http://lintcode.com/problem/best-time-to-buy-and-sell-stock-ii/)| [C++](./C++/best-time-to-buy-and-sell-stock-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode, EPI | |
|151|[Best Time to Buy and Sell Stock III](http://lintcode.com/problem/best-time-to-buy-and-sell-stock-iii/)| [C++](./C++/best-time-to-buy-and-sell-stock-iii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode, EPI | |
|154|[Regular Expression Matching](http://lintcode.com/problem/regular-expression-matching/)| [C++](./C++/regular-expression-matching.cpp)| _O(m*n)_ | _O(m)_ | Hard | LeetCode | todo |
|168|[Burst Balloons](http://lintcode.com/problem/burst-balloons/)| [C++](./C++/burst-balloons.cpp)| _O(n<sup>3</sup>)_ | _O(n<sup>2</sup>)_ | Medium | LeetCode | todo |
|191|[Maximum Product Subarray](http://lintcode.com/problem/maximum-product-subarray/)| [C++](./C++/maximum-product-subarray.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | |
|392|[House Robber](http://lintcode.com/problem/house-robber/)| [C++](./C++/house-robber.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | |
|393|[Best Time to Buy and Sell Stock IV](http://lintcode.com/problem/best-time-to-buy-and-sell-stock-iv/)| [C++](./C++/best-time-to-buy-and-sell-stock-iv.cpp)| _O(k*n)_ | _O(k)_ | Hard | LeetCode, EPI | |
|395|[Coins in a Line II](http://lintcode.com/problem/coins-in-a-line-ii/)| [C++](./C++/coins-in-a-line-ii.cpp)| _O(n)_ | _O(1)_ | Medium | | |
|396|[Coins in a Line III](http://lintcode.com/problem/coins-in-a-line-iii/)| [C++](./C++/coins-in-a-line-iii.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Hard | | todo |
|397|[Longest Increasing Continuous subsequence](http://lintcode.com/problem/longest-increasing-continuous-subsequence/)| [C++](./C++/longest-increasing-continuous-subsequence.cpp)| _O(n)_ | _O(1)_ | Easy | | `Tip` |
|398|[Longest Increasing Continuous subsequence II](http://lintcode.com/problem/longest-increasing-continuous-subsequence-ii/)| [C++](./C++/longest-increasing-continuous-subsequence-ii.cpp)| _O(m*n)_ | _O(m*n)_ | Hard | | todo |
|403|[Continuous Subarray Sum II](http://lintcode.com/problem/continuous-subarray-sum-ii/)| [C++](./C++/continuous-subarray-sum-ii.cpp)| _O(n)_ | _O(1)_ | Medium | EPI | todo |
|430|[Scramble String](http://lintcode.com/problem/scramble-string/)| [C++](./C++/scramble-string.cpp)| _O(n<sup>4</sup>)_ | _O(n<sup>3</sup>)_ | Hard | LeetCode | todo |
|435|[Post Office Problem](http://lintcode.com/problem/post-office-problem/)| [C++](./C++/post-office-problem.cpp)| _O(k*n<sup>2</sup>)_ | _O(n)_ | Hard | PKU 1160 | todo |
|436|[Maximal Square](http://lintcode.com/problem/maximal-square/)| [C++](./C++/maximal-square.cpp)| _O(m*n)_ | _O(n)_ | Medium | LeetCode | todo |
|512|[Decode Ways](http://lintcode.com/problem/decode-ways/)| [C++](./C++/decode-ways.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | todo |
|513|[Perfect Squares](http://lintcode.com/problem/perfect-squares/)| [C++](./C++/perfect-squares.cpp)| _O(n*sqrt(n))_ | _O(n)_ | Medium | LeetCode | todo |
|514|[Paint Fence](http://lintcode.com/problem/paint-fence/)| [C++](./C++/paint-fence.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | todo |
|515|[Paint House](http://lintcode.com/problem/paint-house/)| [C++](./C++/paint-house.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | todo |
|516|[Paint House II](http://lintcode.com/problem/paint-house-ii/)| [C++](./C++/paint-house-ii.cpp)| _O(n*k)_ | _O(k)_ | Hard | LeetCode | todo |
|534|[House Robber II](http://lintcode.com/problem/house-robber-ii/)| [C++](./C++/house-robber-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | todo |
|564|[Backpack VI](http://lintcode.com/problem/backpack-vi/)| [C++](./C++/backpack-vi.cpp)| _O(n*t)_ | _O(t)_ | Medium | | |
## Greedy
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|41|[Maximum Subarray](http://lintcode.com/problem/maximum-subarray/)| [C++](./C++/maximum-subarray.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` |
|42|[Maximum Subarray II](http://lintcode.com/problem/maximum-subarray-ii/)| [C++](./C++/maximum-subarray-ii.cpp)| _O(n)_ | _O(n)_ | Medium | | `Tip` Two Pointers |
|44|[Minimum Subarray](http://lintcode.com/problem/minimum-subarray/)| [C++](./C++/minimum-subarray.cpp)| _O(n)_ | _O(1)_ | Easy | | `Tip` |
|45|[Maximum Subarray Difference](http://lintcode.com/problem/maximum-subarray-difference/)| [C++](./C++/maximum-subarray-difference.cpp)| _O(n)_ | _O(n)_ | Medium | | `Tip` Two Pointers |
|116|[Jump Game](http://lintcode.com/problem/jump-game/)| [C++](./C++/jump-game.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` |
|117|[Jump Game II](http://lintcode.com/problem/jump-game-ii/)| [C++](./C++/jump-game-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` |
|182|[Delete Digits](http://lintcode.com/problem/delete-digits/)| [C++](./C++/delete-digits.cpp)| _O(n)_ | _O(n)_ | Medium | | `Tip` |
|187|[Gas Station](http://lintcode.com/problem/gas-station/)| [C++](./C++/gas-station.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` |
|192|[Wildcard Matching](http://lintcode.com/problem/wildcard-matching/)| [C++](./C++/wildcard-matching.cpp)| _O(m+n)_ | _O(1)_ | Hard | LeetCode | todo |
|402|[Continuous Subarray Sum](http://lintcode.com/problem/continuous-subarray-sum/)| [C++](./C++/continuous-subarray-sum.cpp)| _O(n)_ | _O(1)_ | Medium | EPI | `Tip` |
|412|[Candy](http://lintcode.com/problem/candy/)| [C++](./C++/candy.cpp)| _O(n)_ | _O(n)_ | Hard | LeetCode | `Tip` Greedy |
|552| [Create Maximum Number](http://lintcode.com/problem/create-maximum-number/)| [C++](./C++/create-maximum-number.cpp) | _O(k*(m+n+k))_~_O(k*(m+n+k<sup>2</sup>))_| _O(m+n+k<sup>2</sup>)_ | Hard | LeetCode | todo |
## Hash Tables
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|56|[Two Sum](http://lintcode.com/problem/two-sum/)| [C++](./C++/two-sum.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | `Tip` [HashMap](http://eudiwffe.cnblogs.com/p/6282635.html/) |
|124|[Longest Consecutive Sequence](http://lintcode.com/problem/longest-consecutive-sequence/)| [C++](./C++/longest-consecutive-sequence.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode, EPI | `Tip` HashSet |
|128|[Hash Function](http://lintcode.com/problem/hash-function/)| [C++](./C++/hash-function.cpp)| _O(n)_ | _O(1)_ | Easy | | `Tip` |
|129|[Rehashing](http://lintcode.com/problem/rehashing/)| [C++](./C++/rehashing.cpp)| _O(n)_ | _O(n)_ | Medium | | `Tip` |
|138|[Subarray Sum](http://lintcode.com/problem/subarray-sum/)| [C++](./C++/subarray-sum.cpp)| _O(n)_ | _O(n)_ | Easy | | `Tip` HashMap |
|186|[Max Points on a Line](http://lintcode.com/problem/max-points-on-a-line/)| [C++](./C++/max-points-on-a-line.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Medium | LeetCode | `Tip` HashMap |
|211|[String Permutation](http://lintcode.com/problem/string-permutation/)| [C++](./C++/string-permutation.cpp)| _O(n)_ | _O(1)_ | Easy | | `Tip` |
|384|[Longest Substring Without Repeating Characters](http://lintcode.com/problem/longest-substring-without-repeating-characters/)| [C++](./C++/longest-substring-without-repeating-characters.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode, EPI | `Tip` |
|386|[Longest Substring with At Most K Distinct Characters](http://lintcode.com/problem/longest-substring-with-at-most-k-distinct-characters/)| [C++](./C++/longest-substring-with-at-most-k-distinct-characters.cpp)| _O(n)_ | _O(n)_ | Medium | | todo:jiuzhang |
|432|[Find the Weak Connected Component in the Directed Graph](http://lintcode.com/problem/find-the-weak-connected-component-in-the-directed-graph/)| [C++](./C++/find-the-weak-connected-component-in-the-directed-graph.cpp)| _O(nlogn)_ | _O(n)_ | Medium | | todo:jiuzhang |
|434|[Number of Islands II](http://lintcode.com/problem/number-of-islands-ii/)| [C++](./C++/number-of-islands-ii.cpp)| _O(k)_ | _O(k)_ | Hard | | todo:jiuzhang |
|488| [Happy Number](http://lintcode.com/problem/happy-number/) | [C++](./C++/happy-number.cpp) | _O(k)_ | _O(k)_ | Easy | LeetCode | `Tip` |
|547| [Intersection of Two Arrays](http://lintcode.com/problem/intersection-of-two-arrays/) | [C++](./C++/intersection-of-two-arrays.cpp) | _O(m+n)_ | _O(min(m,n))_ | Easy | EPI, LeetCode | `Tip` HashSet |
|548| [Intersection of Two Arrays II](http://lintcode.com/problem/intersection-of-two-arrays-ii/) | [C++](./C++/intersection-of-two-arrays-ii.cpp) | _O(m+n)_ | _O(min(m,n))_ | Easy | EPI, LeetCode | `Tip` HashMap |
## Heap
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|4|[Ugly Number II](http://lintcode.com/problem/ugly-number-ii/)| [C++](./C++/ugly-number-ii.cpp)| _O(n)_ | _O(1)_ | Medium | CTCI | `Tip` DP, Heap |
|81|[Data Stream Median](http://lintcode.com/problem/data-stream-median/)| [C++](./C++/data-stream-median.cpp)| _O(nlogn)_ | _O(n)_ | Hard | EPI | `Tip` Heap |
|130|[Heapify](http://lintcode.com/problem/heapify/)| [C++](./C++/heapify.cpp)| _O(n)_ | _O(1)_ | Medium | | `Tip` [Heap](http://eudiwffe.cnblogs.com/p/6202111.html) |
|364|[Trapping Rain Water II](http://lintcode.com/problem/trapping-rain-water-ii/)| [C++](./C++/trapping-rain-water-ii.cpp)| _O(m*n*(logm+logn))_ | _O(m*n)_ | Hard | | todo |
|518|[Super Ugly Number](http://lintcode.com/problem/super-ugly-number/)| [C++](./C++/super-ugly-number.cpp)| _O(n*k)_ | _O(n+k)_ | Medium | LeetCode | `Tip` Heap |
## Linked List
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|16|[Merge Two Sorted Lists](http://lintcode.com/problem/merge-two-sorted-lists/)|[C++](./C++/merge-two-sorted-lists.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode, EPI | `Tip` [Merge Sort](http://eudiwffe.cnblogs.com/p/6254394.html) |
|35|[Reverse Linked List](http://lintcode.com/problem/reverse-linked-list/)|[C++](./C++/reverse-linked-list.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode, EPI | `Tip` |
|36|[Reverse Linked List II](http://lintcode.com/problem/reverse-linked-list-ii/)|[C++](./C++/reverse-linked-list-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode, EPI | `Tip` |
|96|[Partition List](http://lintcode.com/problem/partition-list/)|[C++](./C++/partition-list.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` |
|98|[Sort List](http://lintcode.com/problem/sort-list/)|[C++](./C++/sort-list.cpp)| _O(nlogn)_ | _O(logn)_ | Medium | LeetCode, EPI | `Tip` [Merge Sort](http://eudiwffe.cnblogs.com/p/6254394.html) [Quick Sort](http://eudiwffe.cnblogs.com/p/6202996.html) |
|99|[Reorder List](http://lintcode.com/problem/reorder-list/)|[C++](./C++/reorder-list.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` Two pointers |
|102|[Linked List Cycle](http://lintcode.com/problem/linked-list-cycle/)|[C++](./C++/linked-list-cycle.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` Fast/Slow Pointers |
|103|[Linked List Cycle II](http://lintcode.com/problem/linked-list-cycle-ii/)|[C++](./C++/linked-list-cycle-ii.cpp)| _O(n)_ | _O(1)_ | Hard | LeetCode | `Tip` Fast/Slow Pointers |
|104|[Merge k Sorted Lists](http://lintcode.com/problem/merge-k-sorted-lists/)| [C++](./C++/merge-k-sorted-lists.cpp)| _O(n*logk)_ | _O(1)_ | Medium | LeetCode | `Tip` Merge |
|105|[Copy List with Random Pointer](http://lintcode.com/problem/copy-list-with-random-pointer/)|[C++](./C++/copy-list-with-random-pointer.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` InPlace, HashMap |
|106|[Convert Sorted List to Balanced Binary Search Tree](http://lintcode.com/problem/convert-sorted-list-to-balanced-bst/)|[C++](./C++/convert-sorted-list-to-balanced-bst.cpp)| _O(n)_ | _O(logn)_ | Medium | LeetCode, EPI | `Tip` |
|112|[Remove Duplicates from Sorted List](http://lintcode.com/problem/remove-duplicates-from-sorted-list/)|[C++](./C++/remove-duplicates-from-sorted-list.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode, EPI | `Tip` |
|113|[Remove Duplicates from Sorted List II](http://lintcode.com/problem/remove-duplicates-from-sorted-list-ii/)|[C++](./C++/remove-duplicates-from-sorted-list-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode, EPI | `Tip` |
|166|[Nth to Last Node in List](http://lintcode.com/problem/nth-to-last-node-in-list/)|[C++](./C++/nth-to-last-node-in-list.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` |
|167|[Add Two Numbers](http://lintcode.com/problem/add-two-numbers/)|[C++](./C++/add-two-numbers.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` |
|170|[Rotate List](http://lintcode.com/problem/rotate-list/)|[C++](./C++/rotate-list.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` |
|173|[Insertion Sort List](http://lintcode.com/problem/insertion-sort-list/)|[C++](./C++/insertion-sort-list.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Easy | LeetCode | `Tip` |
|174|[Remove Nth Node From End of List](http://lintcode.com/problem/remove-nth-node-from-end-of-list/)|[C++](./C++/remove-nth-node-from-end-of-list.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` Two Pointers |
|223|[Palindrome Linked List](http://lintcode.com/problem/palindrome-linked-list/)|[C++](./C++/palindrome-linked-list.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` Reverse List |
|372|[Delete Node in the Middle of Singly Linked List](http://lintcode.com/problem/delete-node-in-the-middle-of-singly-linked-list/)|[C++](./C++/delete-node-in-the-middle-of-singly-linked-list.cpp)| _O(1)_ | _O(1)_ | Easy | CTCI | `Tip` |
|380|[Intersection of Two Linked Lists](http://lintcode.com/problem/intersection-of-two-linked-lists/)|[C++](./C++/intersection-of-two-linked-lists.cpp)| _O(m+n)_ | _O(1)_ | Easy | LeetCode | `Tip` |
|450|[Reverse Nodes in k-Group](http://lintcode.com/problem/reverse-nodes-in-k-group/)|[C++](./C++/reverse-nodes-in-k-group.cpp)| _O(n)_ | _O(1)_ | Hard | LeetCode | `Tip` Reverse List |
|451|[Swap Nodes in Pairs](http://lintcode.com/problem/swap-nodes-in-pairs/)|[C++](./C++/swap-nodes-in-pairs.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | `Tip` Two Pointers |
|452|[Remove Linked List Elements](http://lintcode.com/problem/remove-linked-list-elements/)|[C++](./C++/remove-linked-list-elements.cpp)| _O(n)_ | _O(1)_ | Naive | LeetCode | `Tip` |
|511|[Swap Two Nodes in Linked List](http://lintcode.com/problem/swap-two-nodes-in-linked-list/)|[C++](./C++/swap-two-nodes-in-linked-list.cpp)| _O(n)_ | _O(1)_ | Medium | | `Tip` |
## Math
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|2|[Trailing Zeros](http://lintcode.com/problem/trailing-zeros/)| [C++](./C++/trailing-zeros.cpp)| _O(logn)_ | _O(1)_ | Easy | LeetCode | `Tip` |
|3|[Digit Counts](http://lintcode.com/problem/digit-counts/)| [C++](./C++/digit-counts.cpp)| _O(logn)_ | _O(1)_ | Medium | CTCI | `Tip` |
|114|[Unique Paths](http://lintcode.com/problem/unique-paths/)| [C++](./C++/unique-paths.cpp)| _O(min(m,n))_ | _O(1)_ | Easy | LeetCode, CTCI | `Tip` DP, Math |
|163|[Unique Binary Search Trees](http://lintcode.com/problem/unique-binary-search-trees/)| [C++](./C++/unique-binary-search-trees.cpp)| _O(n)_ | _O(1)_ | Medium | CTCI | `Tip` Catalan Number |
|180|[Binary Represention](http://lintcode.com/problem/binary-representation/)| [C++](./C++/binary-representation.cpp)| _O(n<sup>2</sup>)_ | _O(n+m)_ | Hard | CTCI | `Tip`Big Integer Division |
|197|[Permutation Index](http://lintcode.com/problem/permutation-index/)| [C++](./C++/permutation-index.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Easy | | |
|198|[Permutation Index II](http://lintcode.com/problem/permutation-index-ii/)| [C++](./C++/permutation-index-ii.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Medium | | todo |
|394|[Coins in a Line](http://lintcode.com/problem/coins-in-a-line/)| [C++](./C++/coins-in-a-line.cpp)| _O(1)_ | _O(1)_ | Easy | | `Tip` |
|411|[Gray Code](http://lintcode.com/problem/gray-code/)| [C++](./C++/gray-code.cpp)| _O(2<sup>n</sup>)_ | _O(1)_ | Medium | LeetCode | `Tip` XOR |
|413|[Reverse Integer](http://lintcode.com/problem/reverse-integer/)| [C++](./C++/reverse-integer.cpp)| _O(1)_ | _O(1)_ | Medium | LeetCode | `Tip` |
|414|[Divide Two Integer](http://lintcode.com/problem/divide-two-integers/)| [C++](./C++/divide-two-integers.cpp)| _O(1)_ | _O(1)_ | Medium | LeetCode | `Tip` |
|418|[Integer to Roman](http://lintcode.com/problem/integer-to-roman/)| [C++](./C++/integer-to-roman.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` [Roman Number](http://baike.baidu.com/view/42061.htm) |
|419|[Roman to Integer](http://lintcode.com/problem/roman-to-integer/)| [C++](./C++/roman-to-integer.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` [Roman Number](http://baike.baidu.com/view/42061.htm) |
|428| [Pow(x, n)](http://lintcode.com/problem/powx-n/) | [C++](./C++/powx-n.cpp) | _O(1)_ | _O(1)_ | Medium | LeetCode | `Tip` Fast Pow |
|445|[Cosine Similarity](http://lintcode.com/problem/cosine-similarity/)| [C++](./C++/cosine-similarity.cpp) | _O(n)_ | _O(1)_ | Easy | | `Tip` |
|517|[Ugly Number](http://lintcode.com/problem/ugly-number/)| [C++](./C++/ugly-number.cpp)| _O(1)_ | _O(1)_ | Easy | CTCI, LeetCode | `Tip` |
|569|[Add Digits](http://lintcode.com/problem/add-digits/)|[C++](./C++/add-digits.cpp)| _O(1)_ | _O(1)_ | Easy | | `Tip` |
## OO Design
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|204|[Singleton](http://lintcode.com/problem/singleton/)| [C++](./C++/singleton.cpp)| _O(1)_ | _O(1)_ | Easy | | `Tip` |
|208|[Assignment Operator Overloading (C++ Only)](http://lintcode.com/problem/assignment-operator-overloading-c-only/)| [C++](./C++/assignment-operator-overloading-c-only.cpp)| _O(n)_ | _O(1)_ | Medium | | `Tip` |
|496|[Toy Factory](http://lintcode.com/problem/toy-factory/)| [C++](./C++/toy-factory.cpp)| _O(1)_ | _O(1)_ | Easy | | `Tip` |
|497|[Shape Factory](http://lintcode.com/problem/shape-factory/)| [C++](./C++/shape-factory.cpp)| _O(1)_ | _O(1)_ | Easy | | todo:jiuzhang |
|498|[Parking Lot](http://lintcode.com/problem/parking-lot/)| [C++](./C++/parking-lot.cpp)| _O(n*m*k)_ | _O(n*m*k)_ | Hard | CTCI | todo:jiuzhang |
## Queue
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|362|[Sliding Window Maximum](http://lintcode.com/problem/sliding-window-maximum/)| [C++](./C++/sliding-window-maximum.cpp)| _O(n)_ | _O(k)_ | Hard | EPI | Deque, Tricky |
## Recursion
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|22|[Flatten List](http://lintcode.com/problem/flatten-list/)| [C++](./C++/flatten-list.cpp)| _O(n)_ | _O(h)_ | Easy | | `Tip` |
|72|[Construct Binary Tree from Inorder and Postorder Traversal](http://lintcode.com/problem/construct-binary-tree-from-inorder-and-postorder-traversal/)| [C++](./C++/construct-binary-tree-from-inorder-and-postorder-traversal.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode, EPI | `Tip` |
|73|[Construct Binary Tree from Preorder and Inorder Traversal](http://lintcode.com/problem/construct-binary-tree-from-preorder-and-inorder-traversal/)| [C++](./C++/construct-binary-tree-from-preorder-and-inorder-traversal.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode, EPI | `Tip` [Binary Tree](http://eudiwffe.cnblogs.com/p/6207196.html) |
|93|[Balanced Binary Tree](http://lintcode.com/problem/balanced-binary-tree/)| [C++](./C++/balanced-binary-tree.cpp)| _O(n)_ | _O(h)_ | Easy | LeetCode | |
|94|[Binary Tree Maximum Path Sum](http://lintcode.com/problem/binary-tree-maximum-path-sum/)| [C++](./C++/binary-tree-maximum-path-sum.cpp)| _O(n)_ | _O(h)_ | Medium | LeetCode | |
|95|[Validate Binary Search Tree](http://lintcode.com/problem/validate-binary-search-tree/)| [C++](./C++/validate-binary-search-tree.cpp)| _O(n)_ | _O(h)_ | Medium | LeetCode | |
|97|[Maximum Depth of Binary Tree](http://lintcode.com/problem/maximum-depth-of-binary-tree/)| [C++](./C++/maximum-depth-of-binary-tree.cpp)| _O(n)_ | _O(h)_ | Easy | LeetCode | |
|131|[Building Outline](http://lintcode.com/problem/building-outline/)| [C++](./C++/building-outline.cpp) | _O(nlogn)_ | _O(n)_ | Hard | EPI | Sort, BST |
|140|[Fast Power](http://lintcode.com/problem/fast-power/)| [C++](./C++/fast-power.cpp)| _O(logn)_ | _O(1)_ | Medium | | |
|155|[Minimum Depth of Binary Tree](http://lintcode.com/problem/minimum-depth-of-binary-tree/)| [C++](./C++/minimum-depth-of-binary-tree.cpp)| _O(n)_ | _O(h)_ | Easy | LeetCode | |
|164|[Unique Binary Search Trees II](http://lintcode.com/problem/unique-binary-search-trees-ii/)| [C++](./C++/unique-binary-search-trees-ii.cpp)| _O(n*4<sup>n</sup> / n<sup>3/2</sup>)_ | _O(n)_ | Medium | LeetCode | |
|177|[Convert Sorted Array to Binary Search Tree With Minimal Height](http://lintcode.com/problem/convert-sorted-array-to-binary-search-tree-with-minimal-height/)| [C++](./C++/convert-sorted-array-to-binary-search-tree-with-minimal-height.cpp)| _O(n)_ | _O(logn)_ | Easy | LeetCode | |
|201|[Segment Tree Build](http://lintcode.com/problem/segment-tree-build/)| [C++](./C++/segment-tree-build.cpp)| _O(n)_ | _O(h)_ | Medium | | Segment Tree, BST |
|202|[Segment Tree Query](http://lintcode.com/problem/segment-tree-query/)| [C++](./C++/segment-tree-query.cpp)| _O(h)_ | _O(h)_ | Medium | | Segment Tree, BST |
|203|[Segment Tree Modify](http://lintcode.com/problem/segment-tree-modify/)| [C++](./C++/segment-tree-modify.cpp)| _O(h)_ | _O(h)_ | Medium | | Segment Tree, BST |
|205|[Interval Minimum Number](http://lintcode.com/problem/interval-minimum-number/)| [C++](./C++/interval-minimum-number.cpp)| _O(n+klogh)_| _O(h)_ | Hard | | Segment Tree, BST |
|206|[Interval Sum](http://lintcode.com/problem/interval-sum/)| [C++](./C++/interval-sum.cpp)| _O(n+klogn)_ | _O(n)_ | Hard | | Segment Tree, BIT |
|207|[Interval Sum II](http://lintcode.com/problem/interval-sum-ii/)| [C++](./C++/interval-sum-ii.cpp)| _O(n+klogn)_ | _O(n)_ | Hard | | Segment Tree, BIT |
|245|[Subtree](http://lintcode.com/problem/subtree/)| [C++](./C++/subtree.cpp)| _O(m*n)_ | _O(1)_ | Easy | | `Morris Traversal` |
|247|[Segment Tree Query II](http://lintcode.com/problem/segment-tree-query-ii/)| [C++](./C++/segment-tree-query-ii.cpp)| _O(h)_ | _O(h)_ | Hard | | Segment Tree, BST |
|371|[Print Numbers by Recursion](http://lintcode.com/problem/print-numbers-by-recursion/)| [C++](./C++/print-numbers-by-recursion.cpp)| _O(n)_ | _O(n)_ | Medium | | |
|375|[Clone Binary Tree](http://lintcode.com/problem/clone-binary-tree/)| [C++](./C++/clone-binary-tree.cpp)| _O(n)_ | _O(h)_ | Easy | | |
|378|[Convert Binary Search Tree to Doubly Linked List](http://lintcode.com/problem/convert-binary-search-tree-to-doubly-linked-list/)| [C++](./C++/convert-binary-search-tree-to-doubly-linked-list.cpp)| _O(n)_ | _O(h)_ | Medium | | |
|439|[Segment Tree Build II](http://lintcode.com/problem/segmemt-tree-build-ii/)| [C++](./C++/segment-tree-build-ii.cpp)| _O(n)_ | _O(h)_ | Medium | | Segment Tree, BST |
|453|[Flatten Binary Tree to Linked List](http://lintcode.com/problem/flatten-binary-tree-to-linked-list/)|[C++](./C++/flatten-binary-tree-to-linked-list.cpp)| _O(n)_ | _O(h)_ | Easy | LeetCode | |
|469| [Identical Binary Tree](http://lintcode.com/problem/problems/identical-binary-tree/)| [C++](./C++/identical-binary-tree.cpp)| _O(n)_ | _O(h)_ | Easy | | |
|532|[Reverse Pairs](http://lintcode.com/problem/reverse-pairs/)| [C++](./C++/reverse-pairs.cpp)| _O(nlogn)_ | _O(n)_ | Medium | [See 249](http://lintcode.com/problem/count-of-smaller-number-before-itself/) | BIT, Merge Sort |
|535|[House Robber III](http://lintcode.com/problem/house-robber-iii/)| [C++](./C++/house-robber-iii.cpp)| _O(n)_ | _O(h)_ | Medium | LeetCode | |
## Sort
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|5|[Kth Largest Element](http://lintcode.com/problem/kth-largest-element/)| [C++](./C++/kth-largest-element.cpp)| _O(n)_ ~ _O(n^2 )_ | _O(1)_ | Medium | EPI | `Tip` [Partition](http://eudiwffe.cnblogs.com/p/6202996.html) |
|80|[Median](http://lintcode.com/problem/median/)| [C++](./C++/median.cpp)| _O(n)_ | _O(1)_ | Easy | EPI | `Tip` Partition |
|139|[Subarray Sum Closest](http://lintcode.com/problem/subarray-sum-closest/)| [C++](./C++/subarray-sum-closest.cpp)| _O(nlogn)_ | _O(n)_ | Medium | | `Tip` Prefix Sum |
|143|[Sort Colors II](http://lintcode.com/problem/sort-colors-ii/)| [C++](./C++/sort-colors-ii.cpp)| _O(n)_ | _O(1)_ | Medium | | `Tip` Radix Sort |
|148|[Sort Colors](http://lintcode.com/problem/sort-colors/)| [C++](./C++/sort-colors.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | `Tip` Radix Sort |
|156|[Merge Intervals](http://lintcode.com/problem/merge-intervals/)| [C++](./C++/merge-intervals.cpp)| _O(nlogn)_ | _O(1)_ | Easy | LeetCode, EPI | `Tip` |
|184|[Largest Number](http://lintcode.com/problem/largest-number/)| [C++](./C++/largest-number.cpp)| _O(nlogn)_ | _O(1)_ | Medium | LeetCode | `Tip` Sort |
|366|[Fibonacci](http://lintcode.com/problem/fibonacci/)| [C++](./C++/fibonacci.cpp)| _O(n)_ | _O(1)_ | Easy | | `Tip` |
|379|[Reorder array to construct the minimum number](http://lintcode.com/problem/reorder-array-to-construct-the-minimum-number/)| [C++](./C++/reorder-array-to-construct-the-minimum-number.cpp)| _O(nlogn)_ | _O(1)_ | Medium | LeetCode | |
|387|[The Smallest Difference](http://lintcode.com/problem/the-smallest-difference/)| [C++](./C++/the-smallest-difference.cpp)| _O(max(m,n) * log(min(m,n)))_ | _O(1)_ | Medium | | Two Pointers, Binary Search |
|399|[Nuts & Bolts Problem](http://lintcode.com/problem/nuts-bolts-problem/)| [C++](./C++/nuts-bolts-problem.cpp)| _O(nlogn)_ | _O(logn)_ | Medium | | Quick Sort |
|400|[Maximum Gap](http://lintcode.com/problem/maximum-gap/)| [C++](./C++/maximum-gap.cpp) | _O(n)_ | _O(n)_ | Hard | LeetCode | Bucket Sort |
|463|[Sort Integers](http://lintcode.com/problem/sort-integers/)| [C++](./C++/sort-integers.cpp)| _O(n^2 )_ | _O(1)_ | Easy | | Insertion Sort, Selection Sort, Bubble Sort |
|464|[Sort Integers II](http://lintcode.com/problem/sort-integers-ii/)| [C++](./C++/sort-integers-ii.cpp)| _O(nlogn)_ | _O(n)_ | Easy | | `Tip` [Merge Sort](http://eudiwffe.cnblogs.com/p/6254394.html), [Heap Sort](http://eudiwffe.cnblogs.com/p/6202111.html), [Quick Sort](http://eudiwffe.cnblogs.com/p/6202996.html) |
|507|[Wiggle Sort II](http://lintcode.com/problem/wiggle-sort-ii/)| [C++](./C++/wiggle-sort-ii.cpp)|  _O(n)_ | _O(1)_ | Medium | LeetCode | Tri Partition |
|508|[Wiggle Sort](http://lintcode.com/problem/wiggle-sort/)| [C++](./C++/wiggle-sort.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | |
## Stack
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|12|[Min Stack](http://lintcode.com/problem/min-stack/)| [C++](./C++/min-stack.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode, EPI | `Tip` |
|40|[Implement Queue by Two Stacks](http://lintcode.com/problem/implement-queue-by-two-stacks/)| [C++](./C++/implement-queue-by-two-stacks.cpp)| _O(1)_ | _O(n)_ | Medium | EPI | `Tip` |
|66|[Binary Tree Preorder Traversal](http://lintcode.com/problem/binary-tree-preorder-traversal/)| [C++](./C++/binary-tree-preorder-traversal.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode, EPI | `Tip` |
|67|[Binary Tree Inorder Traversal](http://lintcode.com/problem/binary-tree-inorder-traversal/)| [C++](./C++/binary-tree-inorder-traversal.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode, EPI | `Tip` |
|68|[Binary Tree Postorder Traversal](http://lintcode.com/problem/binary-tree-postorder-traversal/)| [C++](./C++/binary-tree-postorder-traversal.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode, EPI | `Tip` |
|122|[Largest Rectangle in Histogram](http://lintcode.com/problem/largest-rectangle-in-histogram/)| [C++](./C++/largest-rectangle-in-histogram.cpp)| _O(n)_ | _O(n)_ | Hard | LeetCode, EPI | `Tip` Ascending Stack |
|126|[Max Tree](http://lintcode.com/problem/max-tree/)| [C++](./C++/max-tree.cpp)| _O(n)_ | _O(n)_ | Hard | | todo:jiuzhang |
|367|[Expression Tree Build](http://lintcode.com/problem/expression-tree-build/)| [C++](./C++/expression-tree-build.cpp)| _O(n)_ | _O(n)_ | Hard | | todo |
|368|[Expression Evaluation](http://lintcode.com/problem/expression-evaluation/)| [C++](./C++/expression-evaluation.cpp)| _O(n)_ | _O(n)_ | Hard | | |
|369|[Convert Expression to Polish Notation](http://lintcode.com/problem/convert-expression-to-reverse-notation/)| [C++](./C++/convert-expression-to-polish-notation.cpp)| _O(n)_ | _O(n)_ | Hard | | |
|370|[Convert Expression to Reverse Polish Notation](http://lintcode.com/problem/convert-expression-to-reverse-polish-notation/)| [C++](./C++/convert-expression-to-reverse-polish-notation.cpp)| _O(n)_ | _O(n)_ | Hard | | |
|421|[Simplify Path](http://lintcode.com/problem/simplify-path/)| [C++](./C++/simplify-path.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | `Tip` |
|423|[Valid Parentheses](http://lintcode.com/problem/valid-parentheses.cpp/)| [C++](./C++/valid-parentheses.cpp.cpp)| _O(n)_ | _O(n)_ | Easy | LeetCode | `Tip` |
|424|[Evaluate Reverse Polish Notation](http://lintcode.com/problem/evaluate-reverse-polish-notation/)| [C++](./C++/evaluate-reverse-polish-notation.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | |
|473|[Add and Search Word](http://lintcode.com/problem/add-and-search-word/)| [C++](./C++/add-and-search-word.cpp)| _O(min(n,h))_ | _O(min(n,h)_ | Medium | LeetCode | Trie |
|510|[Maximal Rectangle](http://lintcode.com/problem/maximal-rectangle/)| [C++](./C++/maximal-rectangle.cpp)| _O(m*n)_ | _O(n)_ | Hard | LeetCode | Ascending Stack |
|528|[Flatten Nested List Iterator](http://lintcode.com/problem/flatten-nested-list-iterator/)| [C++](./C++/flatten-nested-list-iterator.cpp)| _O(n)_ | _O(h)_ | Medium | LeetCode | |
## String
| PID# | Title | Source | Time | Space | Difficulty | Tag | Note |
|---| ----- | -------- | ---- | ----- | ---------- | --- | ---- |
|13|[strStr](http://lintcode.com/problem/strstr/)|[C++](./C++/strstr.cpp)| _O(n+k)_ | _O(k)_ | Easy | LeetCode | `Tip` KMP |
|53|[Reverse Words in a String](http://lintcode.com/problem/reverse-words-in-a-string/)|[C++](./C++/reverse-words-in-a-string.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode, EPI | |
|54|[String to Integer(atoi)](http://lintcode.com/problem/string-to-integeratoi/)|[C++](./C++/string-to-integeratoi.cpp)| _O(n)_ | _O(1)_ | Hard | LeetCode | |
|55|[Compare Strings](http://lintcode.com/problem/compare-strings/)|[C++](./C++/compare-strings.cpp)| _O(n)_ | _O(c)_ | Easy | | |
|78|[Longest Common Prefix](http://lintcode.com/problem/longest-common-prefix/)|[C++](./C++/longest-common-prefix.cpp)| _O(n)_ | _O(1)_ | Medium | | |
|157|[Unique Characters](http://lintcode.com/problem/unique-characters/)|[C++](./C++/unique-characters.cpp)| _O(n)_ | _O(1)_ | Easy | CTCI | |
|158|[Two Strings Are Anagrams](http://lintcode.com/problem/two-strings-are-anagrams/)|[C++](./C++/two-strings-are-anagrams.cpp)| _O(n)_ | _O(1)_ | Easy | | |
|171|[Anagrams](http://lintcode.com/problem/anagrams/)|[C++](./C++/anagrams.cpp)| _O(n*klogk)_ | _O(m)_ | Easy | LeetCode, EPI | |
|212|[Space Replacement](http://lintcode.com/problem/space-replacement/)|[C++](./C++/space-replacement.cpp)| _O(n)_ | _O(1)_ | Easy | | `Tip` |
|407|[Plus One](http://lintcode.com/problem/plus-one.cpp/)|[C++](./C++/plus-one.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|408|[Add Binary](http://lintcode.com/problem/add-binary/)|[C++](./C++/add-binary.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|415|[Valid Palindrome](http://lintcode.com/problem/valid-palindrome/)|[C++](./C++/valid-palindrome.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|417|[Valid Number](http://lintcode.com/problem/valid-number/)|[C++](./C++/valid-number.cpp)| _O(n)_ | _O(1)_ | Hard | LeetCode | Automata |
|420|[Count and Say](http://lintcode.com/problem/count-and-say/)|[C++](./C++/count-and-say.cpp)| _O(n*2<sup>n</sup>)_ | _O(2<sup>n</sup>)_ | Easy | LeetCode | |
|422|[Length of Last Word](http://lintcode.com/problem/length-of-last-word/)|[C++](./C++/length-of-last-word.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|524|[Left Pad](http://lintcode.com/problem/left-pad/)|[C++](./C++/left-pad.cpp)| _O(p+n)_ | _O(1)_ | Easy | LeetCode | |
## System Design
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|501|[Mini Twitter](http://lintcode.com/problem/mini-twitter/)| [C++](./C++/mini-twitter.cpp)| _O(klogu)_ | _O(t+f)_ | Medium | | |
## Tree
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|7|[Binary Tree Serialization](http://lintcode.com/problem/binary-tree-serialization/)| [C++](./C++/binary-tree-serialization.cpp)| _O(n)_ | _O(h)_ | Medium | | |
|85|[Insert Node in a Binary Search Tree](http://lintcode.com/problem/insert-node-in-a-binary-search-tree/)| [C++](./C++/insert-node-in-a-binary-search-tree.cpp)| _O(h)_ | _O(1)_ | Easy | | |
|88|[Lowest Common Ancestor](http://lintcode.com/problem/lowest-common-ancestor/)| [C++](./C++/lowest-common-ancestor.cpp)| _O(n)_ | _O(h)_ | Medium | EPI | |
|175|[Invert Binary Tree](http://lintcode.com/problem/invert-binary-tree/)| [C++](./C++/invert-binary-tree.cpp)| _O(n)_ | _O(h)_ | Easy | LeetCode | |
|442|[Implement Trie](http://lintcode.com/problem/implement-trie/)| [C++](./C++/implement-trie.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | Trie |
|632|[Binary Tree Maximum Node](http://lintcode.com/problem/binary-tree-maximum-node/)|[C++](./C++/binary-tree-maximum-node.cpp)| _O(n)_ | _O(1)_ | Easy | | `Tip` DFS |