# lintcode

**Repository Path**: eudiwffe/lintcode

## Basic Information

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

## Statistics

- **Stars**: 8
- **Forks**: 2
- **Created**: 2017-01-06
- **Last Updated**: 2025-06-27

## Categories & Tags

**Categories**: sample-code

**Tags**: None

## README

# Yet Another Source Code for [LintCode](http://lintcode.com/problem/)
Current Status : 613`AC` / 1211`ALL` in Language `C++`, Up to date (2020-01-19)
For more problems and solutions, you can see my [LintCode Git](https://gitee.com/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. \* means has note at cnblogs.
This context template fork from [kamyu104](https://github.com/kamyu104/LintCode) , thanks them very much!
# Notice
## This Repository Was Merged in My [Online Judge Collection](https://gitee.com/eudiwffe/ojc) and It Will Be Closed.
## 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 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 | [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 | |
|9|[Fizz Buzz](http://lintcode.com/problem/fizz-buzz/)| [C++](./C++/fizz-buzz.cpp)| _O(n)_ | _O(1)_ | Easy | | Logic |
|30|[Insert Interval](http://lintcode.com/problem/insert-interval/)| [C++](./C++/insert-interval.cpp)| _O(logn)_ | _O(1)_ | Medium | LeetCode | Binary Search |
|31|[Partition Array](http://lintcode.com/problem/partition-array/)| [C++](./C++/partition-array.cpp)| _O(n)_ | _O(1)_ | Medium | | Partition |
|32|[Minimum Window Substring](http://lintcode.com/problem/minimum-window-substring/)| [C++](./C++/minimum-window-substring.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | HashMap |
|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 | 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 | | |
|46|[Majority Number](http://lintcode.com/problem/majority-number/)| [C++](./C++/majority-number.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|47|[Majority Number II](http://lintcode.com/problem/majority-number-ii/)| [C++](./C++/majority-number-ii.cpp)| _O(n)_ | _O(1)_ | Medium | EPI | HashMap |
|48|[Majority Number III](http://lintcode.com/problem/majority-number-iii/)| [C++](./C++/majority-number-iii.cpp)| _O(n)_ | _O(k)_ | Medium | EPI | 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 | | 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 | LintCode | State Store |
|51|[Previous Permutation](http://lintcode.com/problem/previous-permutation/)| [C++](./C++/previous-permutation.cpp)| _O(n)_ | _O(1)_ | Medium | | [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 | [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 | [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 | [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 | [Two Pointers](http://eudiwffe.cnblogs.com/p/6282635.html) |
|64|[Merge Sorted Array](http://lintcode.com/problem/merge-sorted-array/)| [C++](./C++/merge-sorted-array.cpp)| _O(m+n)_ | _O(1)_ | Easy | LeetCode | [Merge](http://eudiwffe.cnblogs.com/p/6254394.html) |
|100|[Remove Duplicates from <br>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 | Two Pointers |
|101|[Remove Duplicates from <br>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 | Two Pointers |
|133|[Longest Words](http://lintcode.com/problem/longest-words/)| [C++](./C++/longest-words.cpp)| _O(n)_ | _O(n)_ | Easy | | Greed |
|144|[Interleaving Positive <br>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 | | 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 | Matrix |
|162|[Set Matrix Zeroes](http://lintcode.com/problem/set-matrix-zeroes/)| [C++](./C++/set-matrix-zeroes.cpp)| _O(mn)_ | _O(1)_ | Medium | LeetCode | [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 | Two Pointers |
|185|[Matrix Zigzag Traversal](http://lintcode.com/problem/matrix-zigzag-traversal/)| [C++](./C++/matrix-zigzag-traversal.cpp)| _O(mn)_ | _O(1)_ | Easy | | Matrix |
|189|[First Missing Positive](http://lintcode.com/problem/first-missing-positive/)| [C++](./C++/first-missing-positive.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | Hash |
|190|[Next Permutation II](http://lintcode.com/problem/next-permutation-ii/)| [C++](./C++/next-permutation-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | [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, <br>Center Expand |
|278|[Paint Fill](http://lintcode.com/problem/paint-fill/)| [C++](./C++/paint-fill.cpp)| _O(1)_ | _O(1)_ | Easy | | |
|363|[Trapping Rain Water](http://lintcode.com/problem/trapping-rain-water/)| [C++](./C++/trapping-rain-water.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | Two Pointers |
|373|[Partition Array by Odd <br>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 | | Partition |
|374| [Spiral Matrix](http://lintcode.com/problem/spiral-matrix/) | [C++](./C++/spiral-matrix.cpp) | _O(mn)_ | O(1) | Medium | LeetCode | 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 | Matrix |
|382|[Triangle Count](http://lintcode.com/problem/triangle-count/)| [C++](./C++/triangle-count.cpp)| | | Medium | LintCode| Two Points|
|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 | 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 | [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 | Sudoku |
|405|[Submatrix Sum](http://lintcode.com/problem/submatrix-sum/)| [C++](./C++/submatrix-sum.cpp)| _O(mn<sup>2</sup>)_ | _O(m)_ | Hard | LintCode | HashMap |
|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 | Two Pointers, <br>Binary Search |
|479|[Second Max of Array](http://lintcode.com/problem/second-max-of-array/)| [C++](./C++/second-max-of-array.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|484|[Swap Two Integers in Array](http://lintcode.com/problem/swap-two-integers-in-array/)| [C++](./C++/swap-two-ingtegers-in-array.cpp)| _O(1)_ | _O(1)_ | Naive | LeetCode | |
|539|[Move Zeroes](http://lintcode.com/problem/move-zeroes/)| [C++](./C++/move-zeroes.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | Two Pointers |
|540|[Zigzag Iterator](http://lintcode.com/problem/zigzag-iterator/)| [C++](./C++/zigzag-iterator.cpp)| _O(n)_ | _O(1)_ | Medium | Google | |
|541|[Zigzag Iterator II](http://lintcode.com/problem/zigzag-iterator-ii/)| [C++](./C++/zigzag-iterator-ii.cpp)| _O(n)_ | _O(1)_ | Medium | Google | |
|601|[Flatten 2D Vector](http://lintcode.com/problem/flatten-2d-vector/)| [C++](./C++/flatten-2d-vector.cpp)| _O(n)_ | _O(1)_ | Medium | Google | Two Pointers |
|608|[Two Sum II Input Array <br>Is Sorted](http://lintcode.com/problem/two-sum-ii-input-array-is-sorted/)| [C++](./C++/two-sum-ii-input-array-is-sorted.cpp)| _O(n)_ | _O(1)_ | Easy | Amazon | Two Pointers |
|633|[Find The Duplicate Number](http://lintcode.com/problem/find-the-duplicate-number/)| [C++](./C++/find-the-duplicate-number.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Hard | Bloomberg | |
|645|[Find The Celebrity](http://lintcode.com/problem/find-the-celebrity/)| [C++](./C++/find-the-celebrity.cpp)| _O(n)_ | _O(1)_ | Medium | LinkedIn, <br>Facebook | |
|654|[Sparse Matrix Multiplication](http://lintcode.com/problem/sparse-matrix-multiplication/)| [C++](./C++/sparse-matrix-multiplication.cpp)| _O(mn<sup>2</sup>)_ | _O(1)_ | Medium | LinkedIn, <br>Facebook | |
|665|[Range Sum Query 2D <br>Immutable](http://lintcode.com/problem/range-sum-query-2d-immutable/)| [C++](./C++/range-sum-query-2d-immutable.cpp)| _O(mn)_ | _O(mn)_ | Medium | LintCode | PrefixSum|
|692|[Sliding Window Unique <br>Elements Sum](http://lintcode.com/problem/sliding-window-unique-elements-sum/)| [C++](./C++/sliding-window-unique-elements-sum.cpp)| _O(n)_ | _O(n)_ | Medium | LintCode | |
|698|[Maximum Distance in <br>Arrays](http://lintcode.com/problem/maximum-distance-in-arrays/)| [C++](./C++/maximum-distance-in-arrays.cpp)| _O(m)_ | _O(1)_ | Medium | LintCode | |
|745|[Palindromic Ranges](http://lintcode.com/problem/palindromic-ranges/)| [C++](./C++/palindromic-ranges.cpp)| _O(n)_ | _O(n)_ | Easy | LeetCode | Two Pointers |
|767|[Reverse Array](http://lintcode.com/problem/reverse-array/)| [C++](./C++/reverse-array.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | Two Pointers |
|769|[Spiral Array](http://lintcode.com/problem/spiral-array/)| [C++](./C++/spiral-array.cpp)| _O(n<sup>2</sup>)_ | _O(n<sup>2</sup>)_ | Easy | LeetCode | |
|770|[Maximum and Minimum](http://lintcode.com/problem/maximum-and-minimum/)| [C++](./C++/maximum-and-minimum.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Easy | LintCode | |
|807|[Palindrome Number II](http://lintcode.com/problem/palindrome-number-ii/)| [C++](./C++/palindrome-number-ii.cpp)| _O(1)_ | _O(1)_ | Easy | Amazon | Two Pointers |
|817|[Range Sum Query 2D Mutable](http://lintcode.com/problem/range-sum-query-2d-mutable/)| [C++](./C++/range-sum-query-2d-mutable.cpp)| _O(mn)_ | _O(mn)_ | Medium | Google | PrefixSum|
|839|[Merge Two Sorted Interval Lists](http://lintcode.com/problem/merge-two-sorted-interval-lists/)| [C++](./C++/merge-two-sorted-interval-lists.cpp)| _O(m+n)_ | _O(1)_ | Easy | LintCode | [Merge](http://eudiwffe.cnblogs.com/p/6254394.html)|
|840|[Range Sum Query Mutable](http://lintcode.com/problem/range-sum-query-mutable/)| [C++](./C++/range-sum-query-mutable.cpp)| _O(nlogn)_ | _O(n)_ | Medium | Google | BIT |
|846|[Multi Keyword Sort](http://lintcode.com/problem/multi-keyword-sort/)| [C++](./C++/multi-keyword-sort.cpp)| _O(nlogn)_ | _O(1)_ | Easy | LintCode | Sort|
|868|[Maximum Average Subarray](http://lintcode.com/problem/maximum-average-subarray/)| [C++](./C++/maximum-average-subarray.cpp)| _O(n)_ | _O(1)_ | Easy | Google | |
|888|[Valid Word Square](http://lintcode.com/problem/valid-word-square/)| [C++](./C++/valid-word-square.cpp)| _O(mn)_ | _O(1)_ | Easy | Google | |
|903|[Range Addition](http://lintcode.com/problem/range-addition/)| [C++](./C++/range-addition.cpp)| _O(n)_ | _O(1)_ | Medium | Google | |
|943|[Range Sum Query Immutable](http://lintcode.com/problem/range-sum-query-immutable/)| [C++](./C++/range-sum-query-immutable.cpp)| _O(n)_ | _O(n)_ | Easy | Palantir | PrefixSum|
|1001|[Asteroid Collision](http://lintcode.com/problem/asteroid-collision/)| [C++](./C++/asteroid-collision.cpp)| _O(n)_ | _O(1)_ | Medium | Uber | Stack|
|1042|[Toeplitz Matrix](http://lintcode.com/problem/toeplitz-matrix/)| [C++](./C++/toeplitz-matrix.cpp)| _O(mn)_ | _O(1)_ | Easy | Google | |
|1068|[Find Pivot Index](http://lintcode.com/problem/find-pivot-index/)| [C++](./C++/find-pivot-index.cpp)| _O(n)_ | _O(1)_ | Easy | Radius | PrefixSum|
|1099|[Non Decreasing Array](http://lintcode.com/problem/non-decreasing-array/)| [C++](./C++/non-decreasing-array.cpp)| _O(n)_ | _O(1)_ | Easy | Google | |
|1138|[Can Place Flowers](http://lintcode.com/problem/can-place-flowers/)| [C++](./C++/can-place-flowers.cpp)| _O(n)_ | _O(1)_ | Easy | LinkedIn | |
|1144|[Range Addition II](http://lintcode.com/problem/range-addition-ii/)| [C++](./C++/range-addition-ii.cpp)| _O(n)_ | _O(1)_ | Easy | IXL | |
|1157|[Shortest Unsorted <br>Continuous Subarray](http://lintcode.com/problem/shortest-unsorted-continuous-subarray/)| [C++](./C++/shortest-unsorted-continuous-subarray.cpp)| _O(n)_ | _O(1)_ | Easy | Google | |
|1170|[Reshape The Matrix](http://lintcode.com/problem/reshape-the-matrix/)| [C++](./C++/reshape-the-matrix.cpp)| _O(mn)_ | _O(mn)_ | Easy | Mathworks | |
|1174|[Next Greater Element III](http://lintcode.com/problem/next-greater-element-iii/)| [C++](./C++/next-greater-element-iii.cpp)| _O(1)_ | _O(1)_ | Medium | Bloomberg | Permutation |
|1207|[Teemo Attacking](http://lintcode.com/problem/teemo-attacking/)| [C++](./C++/teemo-attacking.cpp)| _O(n)_ | _O(1)_ | Medium | Riot | |
|1225|[Island Perimeter](http://lintcode.com/problem/island-perimeter/)| [C++](./C++/island-perimeter.cpp)| _O(mn)_ | _O(1)_ | Easy | Google | |
|1282|[Reverse Vowels of A String](http://lintcode.com/problem/reverse-vowels-of-a-string/)| [C++](./C++/reverse-vowels-of-a-string.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | Two Pointers |
|1310|[Product of Array Except Itself](http://lintcode.com/problem/product-of-array-except-itself/)| [C++](./C++/product-of-array-except-itself.cpp)| _O(n)_ | _O(1)_ | Easy | Apple, Microsoft, <br>Facebook| |
|1334|[Rotate Array](http://lintcode.com/problem/rotate-array/)| [C++](./C++/rotate-array.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
## 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 | [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 | [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 | 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 | Subset |
|33|[N-Queens](http://lintcode.com/problem/n-queens/)| [C++](./C++/n-queens.cpp)| _O(n*n!)_ | _O(n)_ | Medium | LeetCode | 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 | N-Queens |
|123|[Word Search](http://lintcode.com/problem/word-search/)| [C++](./C++/word-search.cpp)| _O(mnl)_ | _O(l)_ | Medium | LeetCode | Backtracking |
|132|[Word Search II](http://lintcode.com/problem/word-search-ii/)| [C++](./C++/word-search-ii.cpp)| _O(mnl)_ | _O(l)_ | Hard | | Trie, DFS |
|135|[Combination Sum](http://lintcode.com/problem/combination-sum/)| [C++](./C++/combination-sum.cpp)| _O(kn<sup>k</sup>)_ | _O(k)_ | Medium | LeetCode | DFS |
|136|[Palindrome Partitioning](http://lintcode.com/problem/palindrome-partitioning/)| [C++](./C++/palindrome-partitioning.cpp)| _O(2<sup>n</sup>)_ | _O(n)_ | Easy | LeetCode | Substring |
|152|[Combinations](http://lintcode.com/problem/combinations/)| [C++](./C++/combinations.cpp)| _O(kn<sup>k</sup>)_ | _O(k)_ | Medium | LeetCode | Combination |
|153|[Combination Sum II](http://lintcode.com/problem/combination-sum-ii/)| [C++](./C++/combination-sum-ii.cpp)| _O(kC(n,k))_ | _O(k)_ | Medium | LeetCode | DFS |
|169|[Tower of Hanoi](http://lintcode.com/problem/tower-of-hanoi/)| [C++](./C++/tower-of-hanoi.cpp)| _O(2<sup>n</sup>)_ | _O(2<sup>n</sup>)_ | Medium | LeetCode | |
|425|[Letter Combinations <br>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 | Enumeration |
|426| [Restore IP Addresses](http://lintcode.com/problem/restore-ip-addresses/) | [C++](./C++/restore-ip-addresses.cpp) | _O(1)_ | _O(1)_ | Medium | LeetCode | 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 | Backtracking |
|582|[Word Break II](http://lintcode.com/problem/word-break-ii/)| [C++](./C++/word-break-ii.cpp)| _O(nl<sup>2</sup>)_ | _O(n)_ | Hard | Google, Twitter, <br>Uber, Snapchat | Backtrack|
|680| [Split String](http://lintcode.com/problem/split-string/)| [C++](./C++/split-string.cpp)| _O(2<sup>n</sup>)_ | _O(2<sup>n</sup>)_ | Medium | LeetCode | Backtracking |
|634| [Word Squares](http://lintcode.com/problem/word-squares/)| [C++](./C++/word-squares.cpp)| _O(2<sup>n</sup>)_ | _O(nk)_ | Hard | Google | Backtracking, <br>HashMap |
|749| [Johns Backyard Garden](http://lintcode.com/problem/johns-backyard-garden/)| [C++](./C++/johns-backyard-garden.cpp)| _O(2<sup>n</sup>)_ | _O(2<sup>n</sup>)_ | Easy | LintCode | Backtracking |
|836| [Partition to K Equal <br>Sum Subsets](http://lintcode.com/problem/partition-to-k-equal-sum-subsets/)| [C++](./C++/partition-to-k-equal-sum-subsets.cpp)| _O(2<sup>n</sup>)_ | _O(n)_ | Easy | LinkedIn | Backtracking |
|913|[Flip Game II](http://lintcode.com/problem/flip-game-ii/)|[C++](./C++/flip-game-ii.cpp)| _O(2<sup>n</sup>)_ | _O(2<sup>n</sup>)_ | Medium | Google | |
|1032| [Letter Case Permutation](http://lintcode.com/problem/letter-case-permutation/)| [C++](./C++/letter-case-permutation.cpp)| _O(2<sup>k</sup>)_ | _O(2<sup>k</sup>)_ | Easy | Yelp, Facebook | Backtracking |
## 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 | | 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 | Matrix |
|60|[Search Insert Position](http://lintcode.com/problem/search-insert-position/)| [C++](./C++/search-insert-position.cpp)| _O(logn)_ | _O(1)_ | Easy | LeetCode | 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 | Lower Bound |
|62|[Search in Rotated <br>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 | only ascending |
|63|[Search in Rotated <br>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 | 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(logm)_ | _O(1)_ | Hard | LeetCode | kth-element, <br>merge |
|74|[First Bad Version](http://lintcode.com/problem/first-bad-version/)| [C++](./C++/first-bad-version.cpp)| _O(logn)_ | _O(1)_ | Medium | | 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 | |
|76|[Longest Increasing <br>Subsequence](http://lintcode.com/problem/longest-increasing-subsequence/)| [C++](./C++/longest-increasing-subsequence.cpp)| _O(nlogn)_ | _O(n)_ | Medium | CTCI | BS, DP|
|141|[Sqrt(x)](http://lintcode.com/problem/sqrtx/)| [C++](./C++/sqrtx.cpp)| _O(logn)_ | _O(1)_ | Easy | LeetCode | Newton Iteration |
|159|[Find Minimum in Rotated <br>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 | only ascending |
|160|[Find Minimum in Rotated <br>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 | | |
|248|[Count of Smaller Number](http://lintcode.com/problem/count-of-smaller-number/)| [C++](./C++/count-of-smaller-number.cpp)| _O(n+klogn)_ | _O(h)_ | Medium | | Segment Tree, <br>Binary Search |
|437|[Copy Books](http://lintcode.com/problem/copy-books/)| [C++](./C++/copy-books.cpp) | _O(nk)_ | _O(1)_ | Hard | UVa 714 | Binary Search|
|457|[Classical Binary Search](http://lintcode.com/problem/classical-binary-search/)|[C++](./C++/classical-binary-search.cpp)| _O(logn)_ | _O(1)_ | Easy | | Binary Search |
|460|[Find K Closest Elements](http://lintcode.com/problem/find-k-closest-elements/)|[C++](./C++/find-k-closest-elements.cpp)| _O(nlogk)_ | _O(k)_ | Medium | Google | Binary Search |
|641|[Missing Ranges](http://lintcode.com/problem/missing-ranges/)|[C++](./C++/missing-ranges.cpp)| _O(logn)_ | _O(1)_ | Medium | Google | Binary Search |
|662|[Guess Number Higher <br>or Lower](http://lintcode.com/problem/guess-number-higher-or-lower/)|[C++](./C++/guess-number-higher-or-lower.cpp)| _O(logn)_ | _O(1)_ | Easy | Google | Binary Search |
|1219|[Heaters](http://lintcode.com/problem/heaters/)|[C++](./C++/heaters.cpp)| _O(nlogn)_ | _O(1)_ | Easy | Google | Binary Search |
## Binary Search Trees
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|11|[Search Range in Binary <br>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 | 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 | Stack |
|87|[Remove Node in Binary <br>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 | | [BST](http://eudiwffe.cnblogs.com/p/6207196.html) |
|249|[Count of Smaller Number <br>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 | | Segment Tree, <br>Binary Search |
|360|[Sliding Window Median](http://lintcode.com/problem/sliding-window-median/)| [C++](./C++/sliding-window-median.cpp)| _O(nlogw)_ | _O(w)_ | Hard | | BST |
|391|[Number of Airplanes <br>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 | | BST, <br>Heap, Sort |
|401|[Kth Smallest Number in <br>Sorted Matrix](http://lintcode.com/problem/kth-smallest-number-in-sorted-matrix/)| [C++](./C++/kth-smallest-number-in-sorted-matrix.cpp)| _O(klogm)_ | _O(m))_ | Medium | | Heap |
|448|[Inorder Successor in BST](http://lintcode.com/problem/inorder-successor-in-bst/)| [C++](./C++/inorder-successor-in-bst.cpp)| _O(h)_ | _O(1)_ | Medium | LintCode | BST |
|661|[Convert BST to Greater <br>Tree](http://lintcode.com/problem/convert-bst-to-greater-tree/)| [C++](./C++/convert-bst-to-greater-tree.cpp)| _O(n)_ | _O(1)_ | Easy | Amazon | BST |
|689|[Two Sum IV Input Is A <br>BST](http://lintcode.com/problem/two-sum-iv-input-is-a-bst/)| [C++](./C++/two-sum-iv-input-is-a-bst.cpp)| _O(nh)_ | _O(n)_ | Medium | Google, Samsung, <br>Facebook | BST |
|691|[Recover Binary Search <br>Tree](http://lintcode.com/problem/recover-binary-search-tree/)| [C++](./C++/recover-binary-search-tree.cpp)| _O(n)_ | _O(1)_ | Medium | LintCode | BST |
|701|[Trim A Binary Search <br>Tree](http://lintcode.com/problem/trim-a-binary-search-tree/)| [C++](./C++/trim-a-binary-search-tree.cpp)| _O(h)_ | _O(1)_ | Medium | LintCode | BST |
|900|[Closest Binary Search <br>Tree Value](http://lintcode.com/problem/closest-binary-search-tree-value/)| [C++](./C++/closest-binary-search-tree-value.cpp)| _O(h)_ | _O(1)_ | Easy | Google | BST |
|901|[Closest Binary Search <br>Tree Value II](http://lintcode.com/problem/closest-binary-search-tree-value-ii/)| [C++](./C++/closest-binary-search-tree-value-ii.cpp)| _O(n)_ | _O(n)_ | Hard | Google | BST, <br>BinarySearch |
|902|[Kth Smallest Element <br>in A BST](http://lintcode.com/problem/kth-smallest-element-in-a-bst/)| [C++](./C++/kth-smallest-element-in-a-bst.cpp)| _O(n)_ | _O(1)_ | Medium | Google | BST |
|1033|[Minimum Difference <br>Between BST Nodes](http://lintcode.com/problem/minimum-difference-between-bst-nodes/)| [C++](./C++/minimum-difference-between-bst-nodes.cpp)| _O(n)_ | _O(1)_ | Easy | Google | BST, <br>BinarySearch |
|1188|[Minimum Absolute <br>Difference in BST](http://lintcode.com/problem/minimum-absolute-difference-in-bst/)| [C++](./C++/minimum-absolute-difference-in-bst.cpp)| _O(n)_ | _O(n)_ | Easy | Google | BST|
## 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 | | Bit Operator |
|82|[Single Number](http://lintcode.com/problem/single-number/)| [C++](./C++/single-number.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | XOR |
|83|[Single Number II](http://lintcode.com/problem/single-number-ii/)| [C++](./C++/single-number-ii.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | Bit Operator, <br>HashMap |
|84|[Single Number III](http://lintcode.com/problem/single-number-iii/)| [C++](./C++/single-number-iii.cpp)| _O(n)_ | _O(1)_ | Medium | CTCI | 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 | | Bit |
|179|[Update Bits](http://lintcode.com/problem/update-bits/)| [C++](./C++/update-bits.cpp)| _O(1)_ | _O(1)_ | Medium | CTCI | Bit |
|181|[Flip Bits](http://lintcode.com/problem/flip-bits/)| [C++](./C++/flip-bits.cpp)| _O(1)_ | _O(1)_ | Easy | CTCI | |
|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 | | 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 | |
|664|[Counting Bits](http://lintcode.com/problem/counting-bits/)| [C++](./C++/counting-bits.cpp)| _O(n)_ | _O(n)_ | Medium | LintCode | |
|723|[Rotate Bits Left](http://lintcode.com/problem/rotate-bits-left/)| [C++](./C++/rotate-bits-left.cpp)| _O(1)_ | _O(1)_ | Medium | Facebook | |
|782|[And And Or](http://lintcode.com/problem/and-and-or/)| [C++](./C++/and-and-or.cpp)| _O(n)_ | _O(1)_ | Medium | Uber | |
|1046|[Prime Number of Set Bits <br>in Binary Representation](http://lintcode.com/problem/prime-number-of-set-bits-in-binary-representation/)| [C++](./C++/prime-number-of-set-bits-in-binary-representation.cpp)| _O(n)_ | _O(1)_ | Easy | Amazon | |
|1112|[Set Mismatch](http://lintcode.com/problem/set-mismatch/)| [C++](./C++/set-mismatch.cpp)| _O(n)_ | _O(n)_ | Easy | Amazon | |
|1218|[Number Complement](http://lintcode.com/problem/number-complement/)| [C++](./C++/number-complement.cpp)| _O(n)_ | _O(1)_ | Easy | Cloudera | |
|1253|[Convert A Number to <br>Hexadecimal](http://lintcode.com/problem/convert-a-number-to-hexadecimal/)| [C++](./C++/convert-a-number-to-hexadecimal.cpp)| _O(n)_ | _O(1)_ | Easy | LintCode | |
|1266|[Find The Difference](http://lintcode.com/problem/find-the-difference/)| [C++](./C++/find-the-difference.cpp)| _O(n)_ | _O(1)_ | Easy | Google | |
|1332|[Number of 1 Bits](http://lintcode.com/problem/number-of-1-bits/)| [C++](./C++/number-of-1-bits.cpp)| _O(1)_ | _O(1)_ | Easy | Apple, Microsoft | |
## Breadth-First Search
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|69|[Binary Tree Level Order <br>Traversal](http://lintcode.com/problem/binary-tree-level-order-traversal/)| [C++](./C++/binary-tree-level-order-traversal.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | BFS, <br>Queue |
|70|[Binary Tree Level Order <br>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 | BFS, <br>Queue |
|71|[Binary Tree Zigzag Level <br>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 | BFS, <br>Queue |
|120|[Word Ladder](http://lintcode.com/problem/word-ladder/)| [C++](./C++/word-ladder.cpp)| _O(nd)_ | _O(d)_ | Medium | LeetCode | BFS, Queue |
|121|[Word Ladder II](http://lintcode.com/problem/word-ladder-ii/)| [C++](./C++/word-ladder-ii.cpp)| _O(nd)_ | _O(d)_ | Hard | LeetCode | BFS, DFS, <br>Multi-Tree |
|127|[Topological Sorting](http://lintcode.com/problem/topological-sorting/)| [C++](./C++/topological-sorting.cpp)| _O(V+E)_ | _O(E)_ | Medium | | BFS, Queue |
|137|[Clone Graph](http://lintcode.com/problem/clone-graph/)| [C++](./C++/clone-graph.cpp)| _O(V+E)_ | _O(V)_ | Medium | | BFS, DFS |
|176|[Route Between Two Nodes <br>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 | | 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 | BFS, Graph |
|477|[Surrounded Regions](http://lintcode.com/problem/surrounded-regions/)|[C++](./C++/surrounded-regions.cpp)| _O(mn)_ | _O(1)_ | Medium | LeetCode | DFS, BFS |
|573|[Build Post Office II](http://lintcode.com/problem/build-post-office-ii/)|[C++](./C++/build-post-office-ii.cpp)| _O(n<sup>3</sup>)_ | _O(n)_ | Hard | Google, Zenefits | BFS |
|605|[Sequence Reconstruction](http://lintcode.com/problem/sequence-reconstruction/)|[C++](./C++/sequence-reconstruction.cpp)| _O(m+n)_ | _O(n)_ | Medium | Google, Airbnb | BFS |
|615|[Course Schedule](http://lintcode.com/problem/course-schedule/)|[C++](./C++/course-schedule.cpp)| _O(n)_ | _O(n)_ | Medium | Apple, Amazon | BFS |
|663|[Walls and Gates](http://lintcode.com/problem/walls-and-gates/)|[C++](./C++/walls-and-gates.cpp)| _O(mn)_ | _O(n)_ | Medium | Google, Facebook | BFS |
|677|[Number of Big Islands](http://lintcode.com/problem/number-of-big-islands/)|[C++](./C++/number-of-big-islands.cpp)| _O(mn)_ | _O(1)_ | Medium | | BFS |
|698|[Maximum Distance in <br>Arrays](http://lintcode.com/problem/maximum-distance-in-arrays/)| [C++](./C++/maximum-distance-in-arrays.cpp)| _O(m)_ | _O(1)_ | Medium | LintCode | |
|750|[Portal](http://lintcode.com/problem/portal/)| [C++](./C++/portal.cpp)| _O(mn)_ | _O(k)_ | Medium | LintCode | BFS |
|787|[The Maze](http://lintcode.com/problem/the-maze/)| [C++](./C++/the-maze.cpp)| _O(mn)_ | _O(k)_ | Medium | Google | BFS |
|788|[The Maze II](http://lintcode.com/problem/the-maze-ii/)| [C++](./C++/the-maze-ii.cpp)| _O(mn)_ | _O(k)_ | Medium | NetEase, Google | BFS |
|796|[Open The Lock](http://lintcode.com/problem/open-the-lock/)|[C++](./C++/open-the-lock.cpp)| _O(10<sup>4</sup>)_ | _O(10<sup>4</sup>)_ | Hard | | BFS |
|803|[Shortest Distance <br>from All Buildings](http://lintcode.com/problem/shortest-distance-from-all-buildings/)|[C++](./C++/shortest-distance-from-all-buildings.cpp)| _O(n<sup>3</sup>)_ | _O(n)_ | Hard | Google, <br>Zenefits | BFS |
|804|[Number of Distinct <br>Islands II](http://lintcode.com/problem/number-of-distinct-islands-ii/)| [C++](./C++/number-of-distinct-islands-ii.cpp)| _O(mn)_ | _O(k)_ | Hard | Amazon | BFS |
|814|[Shortest Path in Undirected <br>Graph](http://lintcode.com/problem/shortest-path-in-undirected-graph/)| [C++](./C++/shortest-path-in-undirected-graph.cpp)| _O(mn)_ | _O(k)_ | Medium | LintCode | BFS |
|860|[Number of Distinct Islands](http://lintcode.com/problem/number-of-distinct-islands/)| [C++](./C++/number-of-distinct-islands.cpp)| _O(mn)_ | _O(k)_ | Medium | Amazon | BFS |
|872|[Kill Process](http://lintcode.com/problem/kill-process/)|[C++](./C++/kill-process.cpp)| _O(n)_ | _O(n)_ | Easy | Bloomberg| BFS |
|1062|[Flood Fill](http://lintcode.com/problem/flood-fill/)|[C++](./C++/flood-fill.cpp)| _O(mn)_ | _O(mn)_ | Easy | Uber | BFS |
|1071|[Longest Word in Dictionary](http://lintcode.com/problem/longest-word-in-dictionary/)|[C++](./C++/longest-word-in-dictionary.cpp)| _O(nlogn)_ | _O(n)_ | Easy | Pinterest | BFS |
|1080|[Max Area of Island](http://lintcode.com/problem/max-area-of-island/)|[C++](./C++/max-area-of-island.cpp)| _O(mn)_ | _O(n)_ | Easy | Intuit | BFS |
## Data Structure
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|24|[LFU Cache](http://lintcode.com/problem/lfu-cache/)| [C++](./C++/lfu-cache.cpp)| _O(n)_ | _O(k)_ | Hard | Google | HashMap, MultiMap |
|134|[LRU Cache](http://lintcode.com/problem/lru-cache/)| [C++](./C++/lru-cache.cpp)| _O(1)_ | _O(k)_ | Hard | LeetCode | List, HashMap |
|657|[Insert Delete <br>Getrandom O1](http://lintcode.com/problem/insert-delete-getrandom-o1/)| [C++](./C++/insert-delete-getrandom-o1.cpp)| _O(1)_ | _O(n)_ | Medium | Twitter, Facebook, <br>Amazon, Google | 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(kC(n,k))_ | _O(k)_ | Medium | | 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 | DFS |
|430|[Scramble String](http://lintcode.com/problem/scramble-string/)| [C++](./C++/scramble-string.cpp)| _O(n^3)_ | _O(n^3)_ | Hard | | DFS |
|433|[Number of Islands](http://lintcode.com/problem/number-of-islands/)| [C++](./C++/number-of-islands.cpp)| _O(mn)_ | _O(1)_ | Easy | LeetCode | DFS |
|480| [Binary Tree Paths](http://lintcode.com/problem/binary-tree-paths/) | [C++](./C++/binary-tree-paths.cpp) | _O(nh)_ | _O(h)_ | Easy | LeetCode | DFS |
|551| [Nested List Weight Sum](http://lintcode.com/problem/nested-list-weight-sum/) | [C++](./C++/nested-list-weight-sum.cpp) | _O(n)_ | _O(h)_ | Easy | LeetCode | DFS |
|570|[Find The Missing Number II](http://lintcode.com/problem/find-the-missing-number-ii/)| [C++](./C++/find-the-missing-number-ii.cpp)| _O(n!)_ | _O(1)_ | Medium | LintCode| |
|790|[Parser](http://lintcode.com/problem/parser/)| [C++](./C++/parser.cpp)| _O(2<sup>n</sup>)_ | _O(1)_ | Medium | LintCode| |
|1795| [Is Possible](http://lintcode.com/problem/is-possible/) | [C++](./C++/is-possible.cpp) | _O(n)_ | _O(1)_ | Medium | LintCode | 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 | | |
|29|[Interleaving String](http://lintcode.com/problem/interleaving-string/)| [C++](./C++/interleaving-string.cpp)| _O(mn)_ | _O(1)_ | Medium | EPI | DP, DFS|
|43|[Maximum Subarray III](http://lintcode.com/problem/maximum-subarray-iii/)| [C++](./C++/maximum-subarray-iii.cpp)| _O(kn)_ | _O(kn)_ | Hard | LintCode | DP|
|77|[Longest Common Subsequence](http://lintcode.com/problem/longest-common-subsequence/)| [C++](./C++/longest-common-subsequence.cpp)| _O(mn)_ | _O(m)_ | Medium | LintCode | LCS, DP |
|79|[Longest Common Substring](http://lintcode.com/problem/longest-common-substring/)| [C++](./C++/longest-common-substring.cpp)| _O(mn)_ | _O(m)_ | Medium | LintCode | LCS, DP|
|89|[K Sum](http://lintcode.com/problem/k-sum/)| [C++](./C++/k-sum.cpp)| _O(knt)_ | _O(nt)_ | Hard | | DP|
|91|[Minimum Adjustment Cost](http://lintcode.com/problem/minimum-adjustment-cost/)| [C++](./C++/minimum-adjustment-cost.cpp)| _O(knt)_ | _O(k)_ | Medium | LintCode | DP|
|92|[Backpack](http://lintcode.com/problem/backpack/)| [C++](./C++/backpack.cpp)| _O(mn)_ | _O(m)_ | Easy | | DP |
|107|[Word Break](http://lintcode.com/problem/word-break/)| [C++](./C++/word-break.cpp)| _O(nl<sup>2</sup>)_ | _O(n)_ | Medium | LeetCode | |
|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 | DP|
|109|[Triangle](http://lintcode.com/problem/triangle/)| [C++](./C++/triangle.cpp)| _O(n)_ | _O(n)_ | Easy | LeetCode | DP|
|110|[Minimum Path Sum](http://lintcode.com/problem/minimum-path-sum/)| [C++](./C++/minimum-path-sum.cpp)| _O(mn)_ | _O(1)_ | Easy | LeetCode | DP|
|111|[Climbing Stairs](http://lintcode.com/problem/climbing-stairs/)| [C++](./C++/climbing-stairs.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | Fibonacci |
|115|[Unique Paths II](http://lintcode.com/problem/unique-paths-ii/)| [C++](./C++/unique-paths-ii.cpp)| _O(mn)_ | _O(m)_ | Easy | LeetCode | DP |
|118|[Distinct Subsequences](http://lintcode.com/problem/distinct-subsequences/)| [C++](./C++/distinct-subsequences.cpp)| _O(mn)_ | _O(m)_ | Medium | LeetCode | DP |
|119|[Edit Distance](http://lintcode.com/problem/edit-distance/)| [C++](./C++/edit-distance.cpp)| _O(mn)_ | _O(m))_ | Medium | LeetCode | DP |
|125|[Backpack II](http://lintcode.com/problem/backpack-ii/)| [C++](./C++/backpack-ii.cpp)| _O(mn)_ | _O(m)_ | Medium | | DP|
|149|[Best Time to Buy and <br>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 | Greedy|
|150|[Best Time to Buy and <br>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 | Greedy|
|151|[Best Time to Buy and <br>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 | |
|154|[Regular Expression Matching](http://lintcode.com/problem/regular-expression-matching/)| [C++](./C++/regular-expression-matching.cpp)| _O(mn)_ | _O(m)_ | Hard | LeetCode | Recursion, <br>DP, Regex |
|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 | DP |
|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 | DP|
|393|[Best Time to Buy and <br>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(kn)_ | _O(k)_ | Hard | LeetCode | DP|
|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 | | DP|
|397|[Longest Continuous <br>Increasing Subsequence](http://lintcode.com/problem/longest-continuous-increasing-subsequence/)| [C++](./C++/longest-continuous-increasing-subsequence.cpp)| _O(n)_ | _O(1)_ | Easy | | DP|
|398|[Longest Increasing <br>Continuous subsequence II](http://lintcode.com/problem/longest-increasing-continuous-subsequence-ii/)| [C++](./C++/longest-increasing-continuous-subsequence-ii.cpp)| _O(mn)_ | _O(mn)_ | 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(kn<sup>2</sup>)_ | _O(n)_ | Hard | PKU 1160 | todo |
|436|[Maximal Square](http://lintcode.com/problem/maximal-square/)| [C++](./C++/maximal-square.cpp)| _O(mn)_ | _O(n)_ | Medium | Apple, <br>Facebook | |
|476|[Stone Game](http://lintcode.com/problem/stone-game/)| [C++](./C++/stone-game.cpp)| _O(n<sup>3</sup>)_ | _O(n<sup>2</sup>)_ | Medium | LeetCode | DP|
|512|[Decode Ways](http://lintcode.com/problem/decode-ways/)| [C++](./C++/decode-ways.cpp)| _O(n)_ | _O(1)_ | Medium | Microsoft,<br>Google,<br>Facebook | |
|513|[Perfect Squares](http://lintcode.com/problem/perfect-squares/)| [C++](./C++/perfect-squares.cpp)| _O(n<sup>1.5</sup>)_ | _O(n)_ | Medium | Google | DP|
|515|[Paint House](http://lintcode.com/problem/paint-house/)| [C++](./C++/paint-house.cpp)| _O(n)_ | _O(1)_ | Medium | LinkedIn | |
|516|[Paint House II](http://lintcode.com/problem/paint-house-ii/)| [C++](./C++/paint-house-ii.cpp)| _O(nk)_ | _O(k)_ | Hard | Facebook | |
|534|[House Robber II](http://lintcode.com/problem/house-robber-ii/)| [C++](./C++/house-robber-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | |
|553|[Bomb Enemy](http://lintcode.com/problem/bomb-enemy/)| [C++](./C++/bomb-enemy.cpp)| _O(mn)_ | _O(n)_ | Medium | Google | |
|562|[Backpack IV](http://lintcode.com/problem/backpack-iv/)| [C++](./C++/backpack-iv.cpp)| _O(mn)_ | _O(m)_ | Medium | | DP|
|563|[Backpack V](http://lintcode.com/problem/backpack-v/)| [C++](./C++/backpack-v.cpp)| _O(mn)_ | _O(m)_ | Medium | | DP|
|564|[Combination Sum <br>IV(Backpack VI)](http://lintcode.com/problem/combination-sum-iv/)| [C++](./C++/combination-sum-iv.cpp)| _O(nt)_ | _O(t)_ | Medium | Google, <br>Facebook| |
|588|[Partition Equal Subset Sum](http://lintcode.com/problem/partition-equal-subset-sum/)| [C++](./C++/partition-equal-subset-sum.cpp)| _O(n*sum)_ | _O(sum)_ | Medium | eBuy, Amazon| DP |
|603|[Largest Divisible Subset](http://lintcode.com/problem/largest-divisible-subset/)| [C++](./C++/largest-divisible-subset.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Medium | LintCode | |
|666|[Guess Number Higher or <br>Lower II](http://lintcode.com/problem/guess-number-higher-or-lower-ii/)|[C++](./C++/guess-number-higher-or-lower-ii.cpp)| _O(n<sup>2</sup>)_ | _O(n<sup>2</sup>)_ | Medium | Google | DP |
|667|[Longest Palindromic <br>Subsequence](http://lintcode.com/problem/longest-palindromic-subsequence/)| [C++](./C++/longest-palindromic-subsequence.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Medium | Amazon, Uber | DP, Memorized <br>Search |
|669|[Coin Change](http://lintcode.com/problem/coin-change/)| [C++](./C++/coin-change.cpp)| _O(nk)_ | _O(k)_ | Medium | LintCode | |
|670|[Predict The Winner](http://lintcode.com/problem/predict-the-winner/)| [C++](./C++/predict-the-winner.cpp)| _O(n<sup>2</sup>)_ | _O(n<sup>2</sup>)_ | Medium | Google | DP|
|676|[Decode Ways II](http://lintcode.com/problem/decode-ways-ii/)| [C++](./C++/decode-ways-ii.cpp)| _O(1)_ | _O(1)_ | Hard | Facebook | |
|679|[Unique Paths III](http://lintcode.com/problem/unique-paths-iii/)| [C++](./C++/unique-paths-iii.cpp)| _O(mn)_ | _O(m)_ | Hard | Amazon | DP,HashSet |
|683|[Word Break III](http://lintcode.com/problem/word-break-iii/)| [C++](./C++/word-break-iii.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Medium | LintCode | DP|
|734|[Number of Subsquences of <br>Form Ai Bj Ck](http://lintcode.com/problem/number-of-subsquences-of-form-ai-bj-ck/)| [C++](./C++/number-of-subsquences-of-form-ai-bj-ck.cpp)| _O(n)_ | _O(n)_ | Medium | Amazon| DP |
|740|[Coin Change 2](http://lintcode.com/problem/coin-change-2/)| [C++](./C++/coin-change-2.cpp)| _O(nk)_ | _O(k)_ | Medium | LintCode | |
|866|[Coin Path](http://lintcode.com/problem/coin-path/)| [C++](./C++/coin-path.cpp)| _O(nB)_ | _O(n)_ | Hard | Google | DP|
|885|[Encode String with Shortest <br>Length](http://lintcode.com/problem/encode-string-with-shortest-length/)| [C++](./C++/encode-string-with-shortest-length.cpp)| _O(n<sup>3</sup>)_ | _O(n<sup>2</sup>)_ | Hard | Google | DP|
|1044|[Largest Plus Sign](http://lintcode.com/problem/largest-plus-sign/)| [C++](./C++/largest-plus-sign.cpp)| _O(n<sup>2</sup>)_ | _O(n<sup>2</sup>)_ | Medium | Facebook | DP|
|1054|[Min Cost Climbing Stairs](http://lintcode.com/problem/min-cost-climbing-stairs/)| [C++](./C++/min-cost-climbing-stairs.cpp)| _O(n)_ | _O(n)_ | Easy | Amazon | DP|
## 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 | |
|42|[Maximum Subarray II](http://lintcode.com/problem/maximum-subarray-ii/)| [C++](./C++/maximum-subarray-ii.cpp)| _O(n)_ | _O(n)_ | Medium | | Two Pointers |
|44|[Minimum Subarray](http://lintcode.com/problem/minimum-subarray/)| [C++](./C++/minimum-subarray.cpp)| _O(n)_ | _O(1)_ | Easy | | |
|45|[Maximum Subarray Difference](http://lintcode.com/problem/maximum-subarray-difference/)| [C++](./C++/maximum-subarray-difference.cpp)| _O(n)_ | _O(n)_ | Medium | | Two Pointers |
|116|[Jump Game](http://lintcode.com/problem/jump-game/)| [C++](./C++/jump-game.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | |
|117|[Jump Game II](http://lintcode.com/problem/jump-game-ii/)| [C++](./C++/jump-game-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | |
|182|[Delete Digits](http://lintcode.com/problem/delete-digits/)| [C++](./C++/delete-digits.cpp)| _O(n)_ | _O(n)_ | Medium | | |
|187|[Gas Station](http://lintcode.com/problem/gas-station/)| [C++](./C++/gas-station.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|192|[Wildcard Matching](http://lintcode.com/problem/wildcard-matching/)| [C++](./C++/wildcard-matching.cpp)| _O(m+n)_ | _O(1)_ | Hard | LeetCode | Backtracking, DP |
|402|[Continuous Subarray Sum](http://lintcode.com/problem/continuous-subarray-sum/)| [C++](./C++/continuous-subarray-sum.cpp)| _O(n)_ | _O(1)_ | Medium | EPI | |
|412|[Candy](http://lintcode.com/problem/candy/)| [C++](./C++/candy.cpp)| _O(n)_ | _O(n)_ | Hard | LeetCode | Greedy |
|761|[Smallest Subset](http://lintcode.com/problem/smallest-subset/)| [C++](./C++/smallest-subset.cpp)| _O(n)_ | _O(1)_ | Medium | LintCode | Greedy |
|797|[Reach A Number](http://lintcode.com/problem/reach-a-number/)| [C++](./C++/reach-a-number.cpp)| _O(n)_ | _O(1)_ | Easy | inmobi| Greedy |
|1230| [Assign Cookies](http://lintcode.com/problem/assign-cookies/)| [C++](./C++/assign-cookies.cpp) | _O(nlogn)_ | _O(1)_ | Easy | LintCode | |
## 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 | [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 | HashSet |
|128|[Hash Function](http://lintcode.com/problem/hash-function/)| [C++](./C++/hash-function.cpp)| _O(n)_ | _O(1)_ | Easy | | |
|129|[Rehashing](http://lintcode.com/problem/rehashing/)| [C++](./C++/rehashing.cpp)| _O(n)_ | _O(n)_ | Medium | | |
|131|[The Skyline Problem](http://lintcode.com/problem/the-skyline-problem/)| [C++](./C++/the-skyline-problem.cpp)| _O(nlogn)_ | _O(n)_ | Hard | LeetCode | HashSet|
|138|[Subarray Sum](http://lintcode.com/problem/subarray-sum/)| [C++](./C++/subarray-sum.cpp)| _O(n)_ | _O(n)_ | Easy | | 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 | HashMap |
|209|[First Unique Character in <br>A String](http://lintcode.com/problem/first-unique-character-in-a-string/)| [C++](./C++/first-unique-character-in-a-string.cpp)| _O(n)_ | _O(n)_ | Easy | | HashMap |
|211|[String Permutation](http://lintcode.com/problem/string-permutation/)| [C++](./C++/string-permutation.cpp)| _O(n)_ | _O(1)_ | Easy | | |
|384|[Longest Substring Without <br>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 | |
|386|[Longest Substring with At <br>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 | | HashMap|
|434|[Number of Islands II](http://lintcode.com/problem/number-of-islands-ii/)| [C++](./C++/number-of-islands-ii.cpp)| _O(k)_ | _O(mn)_ | Hard | | UFS |
|488| [Happy Number](http://lintcode.com/problem/happy-number/) | [C++](./C++/happy-number.cpp) | _O(k)_ | _O(k)_ | Easy | LeetCode | |
|547| [Intersection of Two Arrays](http://lintcode.com/problem/intersection-of-two-arrays/) | [C++](./C++/intersection-of-two-arrays.cpp) | _O(m+n)_ | _O(m)_ | Easy | LeetCode | 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(m)_ | Easy | LeetCode | HashMap |
|550| [Top K Frequent Words II](http://lintcode.com/problem/top-k-frequent-words-ii/) | [C++](./C++/top-k-frequent-words-ii.cpp) | _O(n+k)_ | _O(nlogk)_ | Hard | LintCode | HashMap |
|627| [Longest Palindrome](http://lintcode.com/problem/longest-palindrome/) | [C++](./C++/longest-palindrome.cpp) | _O(n)_ | _O(1)_ | Easy | | HashMap |
|638| [Isomorphic Strings](http://lintcode.com/problem/isomorphic-strings/)|[C++](./C++/isomorphic-strings.cpp)| _O(n)_ | _O(n)_ | Easy | LinkedIn | HashMap|
|639| [Word Abbreviation](http://lintcode.com/problem/word-abbreviation/)|[C++](./C++/word-abbreviation.cpp)| _O(n)_ | _O(n)_ | Hard | Google, <br>Snapchat | HashMap|
|646| [First Position Unique <br>Character](http://lintcode.com/problem/first-position-unique-character/) | [C++](./C++/first-position-unique-character.cpp) | _O(n)_ | _O(n)_ | Easy | | HashMap |
|647|[Find All Anagrams in A <br>String](http://lintcode.com/problem/find-all-anagrams-in-a-string/)|[C++](./C++/find-all-anagrams-in-a-string.cpp)| _O(mn)_ | _O(m)_ | Easy |Amazon | HashMap|
|648| [Unique Word Abbreviation](http://lintcode.com/problem/unique-word-abbreviation/)|[C++](./C++/unique-word-abbreviation.cpp)| _O(n)_ | _O(n)_ | Medium | Google | HashMap|
|671| [Rotate Words](http://lintcode.com/problem/rotate-words/) | [C++](./C++/rotate-words.cpp) | _O(nk)_ | _O(n)_ | Easy | LintCode | HashCode |
|684| [Missing String](http://lintcode.com/problem/missing-string/) | [C++](./C++/missing-string.cpp) | _O(m)_ | _O(m+n)_ | Easy | Twitter | HashMap |
|685| [First Unique Number in <br>Data Stream](http://lintcode.com/problem/first-unique-number-in-data-stream/) | [C++](./C++/first-unique-number-in-data-stream.cpp) | _O(n)_ | _O(n)_ | Medium | LintCode | HashMap |
|702|[Concatenated String with Uncommon <br>Characters of Two Strings](http://lintcode.com/problem/concatenated-string-with-uncommon-characters-of-two-strings/)|[C++](./C++/concatenated-string-with-uncommon-characters-of-two-strings.cpp)| _O(n)_ | _O(n)_ | Easy | Microsoft | HashMap|
|720|[Rearrange A String with Integers](http://lintcode.com/problem/rearrange-a-string-with-integers/)|[C++](./C++/rearrange-a-string-with-integers.cpp)| _O(n)_ | _O(n)_ | Easy | Facebook | HashMap|
|737|[Find Elements in Matrix](http://lintcode.com/problem/find-elements-in-matrix/)|[C++](./C++/find-elements-in-matrix.cpp)| _O(mn)_ | _O(n)_ | Easy | LintCode | HashMap|
|772|[Group Anagrams](http://lintcode.com/problem/group-anagrams/)|[C++](./C++/group-anagrams.cpp)| _O(nklogk)_ | _O(n)_ | Easy |Amazon | HashMap|
|774|[Repeated DNA](http://lintcode.com/problem/repeated-dna/)|[C++](./C++/repeated-dna.cpp)| _O(n)_ | _O(n)_ | Medium | LinkedIn | HashMap|
|775|[Palindrome Pairs](http://lintcode.com/problem/palindrome-pairs/)|[C++](./C++/palindrome-pairs.cpp)| _O(nk)_ | _O(n)_ | Hard |Google, Airbnb | HashMap|
|813|[Find Anagram Mappings](http://lintcode.com/problem/find-anagram-mappings/)|[C++](./C++/find-anagram-mappings.cpp)| _O(n)_ | _O(n)_ | Easy | Google | HashMap|
|828|[Word Pattern](http://lintcode.com/problem/word-pattern/)|[C++](./C++/word-pattern.cpp)| _O(n)_ | _O(n)_ | Easy | Uber | HashMap|
|838|[Subarray Sum Equals K](http://lintcode.com/problem/subarray-sum-equals-k/)|[C++](./C++/subarray-sum-equals-k.cpp)| _O(n)_ | _O(n)_ | Easy | Google | HashMap|
|856|[Sentence Similarity](http://lintcode.com/problem/sentence-similarity/)|[C++](./C++/sentence-similarity.cpp)| _O(n)_ | _O(n)_ | Easy | Google | HashMap|
|908|[Line Reflection](http://lintcode.com/problem/line-reflection/)|[C++](./C++/line-reflection.cpp)| _O(n)_ | _O(n)_ | Easy | Google | HashMap|
|960| [First Unique Number in <br>Data Stream II](http://lintcode.com/problem/first-unique-number-in-data-stream-ii/) | [C++](./C++/first-unique-number-in-data-stream-ii.cpp) | _O(n)_ | _O(n)_ | Medium | LintCode | HashMap |
|1006| [Subdomain Visit Count](http://lintcode.com/problem/subdomain-visit-count/) | [C++](./C++/subdomain-visit-count.cpp) | _O(n)_ | _O(n)_ | Easy | Roblox | HashMap |
|1038| [Jewels and Stones](http://lintcode.com/problem/jewels-and-stones/) | [C++](./C++/jewels-and-stones.cpp) | _O(n)_ | _O(n)_ | Easy | Amazon | HashMap |
|1078| [Degree of An Array](http://lintcode.com/problem/degree-of-an-array/) | [C++](./C++/degree-of-an-array.cpp) | _O(nlogn)_ | _O(n)_ | Easy | Amazon | HashMap |
|1143|[Minimum Index Sum of <br>Two Lists](http://lintcode.com/problem/minimum-index-sum-of-two-lists/)|[C++](./C++/minimum-index-sum-of-two-lists.cpp)| _O(m+n)_ | _O(m)_ | Easy | Yelp | HashMap|
|1148|[Longest Harmonious Subsequence](http://lintcode.com/problem/longest-harmonious-subsequence/)|[C++](./C++/longest-harmonious-subsequence.cpp)| _O(n)_ | _O(n)_ | Easy | LiveRamp | HashMap|
|1163|[Distribute Candies](http://lintcode.com/problem/distribute-candies/)|[C++](./C++/distribute-candies.cpp)| _O(n)_ | _O(n)_ | Easy | LiveRamp | HashMap|
|1169|[Permutation in String](http://lintcode.com/problem/permutation-in-string/)|[C++](./C++/permutation-in-string.cpp)| _O(mn)_ | _O(m)_ | Medium | Microsoft | HashMap|
|1187|[K Diff Pairs in An Array](http://lintcode.com/problem/k-diff-paris-in-an-array/)|[C++](./C++/k-diff-pairs-in-an-array.cpp)| _O(n)_ | _O(n)_ | Easy | Amazon | HashMap|
|1237|[Number of Boomerangs](http://lintcode.com/problem/number-of-boomerangs/)|[C++](./C++/number-of-boomerangs.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Easy | Google | HashMap|
|1270|[Ransom Note](http://lintcode.com/problem/ransom-note/)|[C++](./C++/ransom-note.cpp)| _O(n)_ | _O(128)_ | Easy | Apple | HashMap|
|1319|[Contains Duplicate II](http://lintcode.com/problem/contains-duplicate-ii/)|[C++](./C++/contains-duplicate-ii.cpp)| _O(n)_ | _O(n)_ | Easy |Airbnb, Yahoo | HashMap|
|1320|[Contains Duplicate](http://lintcode.com/problem/contains-duplicate/)|[C++](./C++/contains-duplicate.cpp)| _O(n)_ | _O(n)_ | Easy |Airbnb, Yahoo | HashMap|
|1369|[Most Common Word](http://lintcode.com/problem/most-common-word/)|[C++](./C++/most-common-word.cpp)| _O(n)_ | _O(n)_ | Easy | Amazon | HashMap|
|1443|[Longest AB Substring](http://lintcode.com/problem/longest-ab-substring/)| [C++](./C++/longest-ab-substring.cpp)| _O(n)_ | _O(n)_ | Easy | Alibaba | HashMap |
|1713| [Unique Email Addresses](http://lintcode.com/problem/unique-email-addresses/) | [C++](./C++/unique-email-addresses.cpp) | _O(m)_ | _O(m)_ | Easy | Google | HashMap |
|1728| [X of A Kind in A Deck <br>of Cards](http://lintcode.com/problem/x-of-a-kind-in-a-deck-of-cards/) | [C++](./C++/x-of-a-kind-in-a-deck-of-cards.cpp) | _O(n)_ | _O(n)_ | Easy | LeetCode | HashMap |
|1779| [Shortest Duplicate Subarray](http://lintcode.com/problem/shortest-duplicate-subarray/) | [C++](./C++/shortest-duplicate-subarray.cpp) | _O(m)_ | _O(m)_ | Easy | Google | 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 | DP, Heap |
|81|[Find Median from Data Stream](http://lintcode.com/problem/find-median-from-data-stream/)| [C++](./C++/find-median-from-data-stream.cpp)| _O(nlogn)_ | _O(n)_ | Hard | EPI | Heap |
|130|[Heapify](http://lintcode.com/problem/heapify/)| [C++](./C++/heapify.cpp)| _O(n)_ | _O(1)_ | Medium | | [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(mnlogmn))_ | _O(mn)_ | Hard | | BFS, Heap |
|471|[Top K Frequent Words](http://lintcode.com/problem/top-k-frequent-words/)| [C++](./C++/top-k-frquent-words.cpp)| _O(nlogk)_ | _O(n)_ | Medium | | Heap |
|486|[Merge K Sorted Arrays](http://lintcode.com/problem/merge-k-sorted-arrays/)| [C++](./C++/merge-k-sorted-arrays.cpp)| _O(nlogk)_ | _O(n)_ | Medium | | Heap |
|518|[Super Ugly Number](http://lintcode.com/problem/super-ugly-number/)| [C++](./C++/super-ugly-number.cpp)| _O(nk)_ | _O(n+k)_ | Medium | LeetCode | Heap |
|549|[Top K Frequent Words <br>Map Reduce](http://lintcode.com/problem/top-k-frequent-words-map-reduce/)| [C++](./C++/top-k-frequent-words-map-reduce.cpp)| _O(nlogk)_ | _O(k)_ | Medium | LeetCode | Heap,<br>Set |
|577|[Merge K Sorted Interval Lists](http://lintcode.com/problem/merge-k-sorted-interval-lists/)| [C++](./C++/merge-k-sorted-interval-lists.cpp)| _O(nlogk)_ | _O(n)_ | Medium | Airbnb | Heap |
|612|[K Closest Points](http://lintcode.com/problem/k-closest-points/)| [C++](./C++/k-closest-points.cpp)| _O(nlogk)_ | _O(k)_ | Medium | LinkedIn, <br>Amazon | Heap |
## Linked List
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|165|[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 | [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 | |
|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 | |
|96|[Partition List](http://lintcode.com/problem/partition-list/)|[C++](./C++/partition-list.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|98|[Sort List](http://lintcode.com/problem/sort-list/)|[C++](./C++/sort-list.cpp)| _O(nlogn)_ | _O(logn)_ | Medium | LeetCode | [Merge Sort](http://eudiwffe.cnblogs.com/p/6254394.html), <br>[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 | 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 | Two 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 | Tow Pointers |
|104|[Merge k Sorted Lists](http://lintcode.com/problem/merge-k-sorted-lists/)| [C++](./C++/merge-k-sorted-lists.cpp)| _O(nlogk)_ | _O(1)_ | Medium | LeetCode | 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 | InPlace, <br>HashMap |
|106|[Convert Sorted List to <br>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 | |
|112|[Remove Duplicates from <br>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 | |
|113|[Remove Duplicates from <br>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 | |
|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 | |
|167|[Add Two Numbers](http://lintcode.com/problem/add-two-numbers/)|[C++](./C++/add-two-numbers.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|170|[Rotate List](http://lintcode.com/problem/rotate-list/)|[C++](./C++/rotate-list.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | |
|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 | |
|174|[Remove Nth Node From <br>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 | Two Pointers |
|219|[Insert Node in Sorted <br>Linked List](http://lintcode.com/problem/insert-node-in-sorted-linked-list/)|[C++](./C++/insert-node-in-sorted-linked-list.cpp)| _O(n)_ | _O(1)_ | Easy | LintCode | |
|221|[Add Two Numbers ii](http://lintcode.com/problem/add-two-numbers-ii/)|[C++](./C++/add-two-numbers-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | |
|223|[Palindrome Linked List](http://lintcode.com/problem/palindrome-linked-list/)|[C++](./C++/palindrome-linked-list.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | Reverse List |
|372|[Delete Node in the Middle <br>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 | |
|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 | |
|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 | 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 | 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 | |
|466|[Count Linked List Nodes](http://lintcode.com/problem/count-linked-list-nodes/)|[C++](./C++/count-linked-list-nodes.cpp)| _O(n)_ | _O(1)_ | Naive | LeetCode | |
|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 | | |
|599|[Insert into A Cyclic Sorted List](http://lintcode.com/problem/insert-into-a-cyclic-sorted-list/)|[C++](./C++/insert-into-a-cyclic-sorted-list.cpp)| _O(n)_ | _O(n)_ | Medium | Alibaba | HashSet |
|822|[Reverse Order Storage](http://lintcode.com/problem/reverse-order-storage/)|[C++](./C++/reverse-order-storage.cpp)| _O(n)_ | _O(n)_ | Easy | LintCode | |
## 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 | |
|3|[Digit Counts](http://lintcode.com/problem/digit-counts/)| [C++](./C++/digit-counts.cpp)| _O(logn)_ | _O(1)_ | Medium | CTCI | |
|37|[Reverse 3 Digit Integer](http://lintcode.com/problem/reverse-3-digit-integer/)| [C++](./C++/reverse-3-digit-integer.cpp)| _O(1)_ | _O(1)_ | Naive | LintCode | |
|114|[Unique Paths](http://lintcode.com/problem/unique-paths/)| [C++](./C++/unique-paths.cpp)| _O(m)_ | _O(1)_ | Easy | LeetCode | 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 | Catalan |
|180|[Binary Represention](http://lintcode.com/problem/binary-representation/)| [C++](./C++/binary-representation.cpp)| _O(n<sup>2</sup>)_ | _O(n+m)_ | Hard | CTCI | Math |
|197|[Permutation Index](http://lintcode.com/problem/permutation-index/)| [C++](./C++/permutation-index.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Easy | | Cantor Expand|
|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 | | Cantor Expand |
|254|[Drop Eggs](http://lintcode.com/problem/drop-eggs/)| [C++](./C++/drop-eggs.cpp)| _O(1)_ | _O(1)_ | Easy | Tencent | Math |
|283|[Max of 3 Numbers](http://lintcode.com/problem/max-of-3-numbers/)| [C++](./C++/max-of-3-numbers.cpp)| _O(1)_ | _O(1)_ | Naive | | |
|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 | | |
|411|[Gray Code](http://lintcode.com/problem/gray-code/)| [C++](./C++/gray-code.cpp)| _O(2<sup>n</sup>)_ | _O(1)_ | Medium | LeetCode | XOR |
|413|[Reverse Integer](http://lintcode.com/problem/reverse-integer/)| [C++](./C++/reverse-integer.cpp)| _O(1)_ | _O(1)_ | Medium | LeetCode | |
|414|[Divide Two Integer](http://lintcode.com/problem/divide-two-integers/)| [C++](./C++/divide-two-integers.cpp)| _O(1)_ | _O(1)_ | Medium | LeetCode | |
|418|[Integer to Roman](http://lintcode.com/problem/integer-to-roman/)| [C++](./C++/integer-to-roman.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | [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 | [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 | Fast Pow |
|454|[Rectangle Area](http://lintcode.com/problem/rectangle-area/) | [JAVA](./JAVA/rectangle-area.java) | _O(1)_ | _O(1)_ | Naive | LeetCode | |
|445|[Cosine Similarity](http://lintcode.com/problem/cosine-similarity/)| [C++](./C++/cosine-similarity.cpp) | _O(n)_ | _O(1)_ | Easy | | |
|514|[Paint Fence](http://lintcode.com/problem/paint-fence/)| [C++](./C++/paint-fence.cpp)| _O(n)_ | _O(1)_ | Easy | Google | DP|
|517|[Ugly Number](http://lintcode.com/problem/ugly-number/)| [C++](./C++/ugly-number.cpp)| _O(1)_ | _O(1)_ | Easy | LeetCode | |
|569|[Add Digits](http://lintcode.com/problem/add-digits/)|[C++](./C++/add-digits.cpp)| _O(1)_ | _O(1)_ | Easy | | |
|626|[Rectangle Overlap](http://lintcode.com/problem/rectangle-overlap/)|[C++](./C++/rectangle-overlap.cpp)| _O(1)_ | _O(1)_ | Easy | LintCode| |
|681|[First Missing Prime Number](http://lintcode.com/problem/first-missing-prime-number/)|[C++](./C++/first-missing-prime-number.cpp)| _O(nlogn)_ | _O(1)_ | Easy | LintCode| |
|690|[Factorial](http://lintcode.com/problem/factorial/)| [C++](./C++/factorial.cpp)| _O(n)_ | _O(n)_ | Hard | | Fast Factorial|
|697|[Sum of Square Numbers](http://lintcode.com/problem/sum-of-square-numbers/)|[C++](./C++/sum-of-square-numbers.cpp)| _O(n)_ | _O(1)_ | Easy | LinkedIn | Two Points|
|699|[Check Sum of K <br>Primes](http://lintcode.com/problem/check-sum-of-k-primes/)|[C++](./C++/check-sum-of-k-primes.cpp)| _O(1)_ | _O(1)_ | Hard | Goldbach Conjecture | Math |
|706|[Binary Watch](http://lintcode.com/problem/binary-watch/)| [C++](./C++/binary-watch.cpp)| _O(720*7)_ | _O(720)_ | Medium | Google | Bit |
|728|[Three Distinct Factors](http://lintcode.com/problem/three-distinct-factors/)| [C++](./C++/three-distinct-factors.cpp)| _O(n)_ | _O(1)_ | Medium | | Prime|
|729|[Last Digit by <br>Factorial Divide](http://lintcode.com/problem/last-digit-by-factorial-divide/)| [C++](./C++/last-digit-by-factorial-divide.cpp)| _O(n)_ | _O(1)_ | Meidum | Google | Math|
|730|[Sum of All Subsets](http://lintcode.com/problem/sum-of-all-subsets/)| [C++](./C++/sum-of-all-subsets.cpp)| _O(1)_ | _O(1)_ | Easy | Bloomberg | Math|
|739|[24 Game](http://lintcode.com/problem/24-game/)| [C++](./C++/24-game.cpp)| _O(n!)_ | _O(1)_ | Medium | Google | BFS|
|742|[Self Dividing Numbers](http://lintcode.com/problem/self-dividing-numbers/)| [C++](./C++/self-dividing-numbers.cpp)| _O(n)_ | _O(1)_ | Medium | | |
|744|[Sum of K Even Length <br>Palindrome Numbers](http://lintcode.com/problem/sum-of-k-even-length-palindrome-numbers/)| [C++](./C++/sum-of-k-even-length-palindrome-numbers.cpp)| _O(n)_ | _O(1)_ | Medium | Facebook| |
|763|[Hex Conversion](http://lintcode.com/problem/hex-conversion/)| [C++](./C++/hex-conversion.cpp)| _O(logn)_ | _O(1)_ | Easy | | |
|764|[Calculate Circumference <br>and Area](http://lintcode.com/problem/calculate-circumference-and-area/)| [C++](./C++/calculate-circumference-and-area.cpp)| _O(1)_ | _O(1)_ | Easy | LintCode | |
|765|[Valid Triangle](http://lintcode.com/problem/valid-triangle/)| [C++](./C++/valid-triangle.cpp)| _O(1)_ | _O(1)_ | Easy | | |
|766|[Leap Year](http://lintcode.com/problem/leap-year/)| [C++](./C++/leap-year.cpp)| _O(1)_ | _O(1)_ | Easy | | |
|768|[Yang Hui Triangle](http://lintcode.com/problem/yang-hui-triangle/)| [C++](./C++/yang-hui-triangle.cpp)| _O(n<sup>2</sup>)_ | _O(n<sup>2</sup>)_ | Easy | | |
|777|[Valid Perfect Square](http://lintcode.com/problem/valid-perfect-square/)| [C++](./C++/valid-perfect-square.cpp)| _O(1)_ | _O(1)_ | Easy | | |
|779|[Generalized Abbreviation](http://lintcode.com/problem/generalized-abbreviation/)| [C++](./C++/generalized-abbreviation.cpp)| _O(2<sup>k</sup>)_ | _O(2<sup>k</sup>)_ | Medium | Google| Binary |
|792|[Kth Prime Number](http://lintcode.com/problem/kth-prime-number/)| [C++](./C++/kth-prime-number.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Easy | | Math |
|835|[Hamming Distance](http://lintcode.com/problem/hamming-distance/)| [C++](./C++/hamming-distance.cpp)| _O(1)_ | _O(1)_ | Easy | Facebook | Math |
|845|[Greatest Common Divisor](http://lintcode.com/problem/greatest-common-divisor/)| [C++](./C++/greatest-common-divisor.cpp)| _O(k)_ | _O(1)_ | Easy | LintCode | Math |
|918|[3 Sum Smaller](http://lintcode.com/problem/3sum-smaller/)| [C++](./C++/3sum-smaller.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Medium | Google | Sort|
|949|[Fibonacci II](http://lintcode.com/problem/fibonacci-ii/)| [C++](./C++/fibonacci-ii.cpp)| _O(logn)_ | _O(1)_ | Medium | LintCode | MatrixCal|
|973|[1 Bit and 2 Bit Characters](http://lintcode.com/problem/1-bit-and-2-bit-characters/)| [C++](./C++/1-bit-and-2-bit-characters.cpp)| _O(1)_ | _O(1)_ | Easy | | |
|977|[Base 7](http://lintcode.com/problem/base-7/)| [C++](./C++/base-7.cpp)| _O(logn)_ | _O(logn)_ | Easy | LintCode | |
|983|[Baseball Game](http://lintcode.com/problem/baseball-game/)| [C++](./C++/baseball-game.cpp)| _O(n)_ | _O(n)_ | Easy | Amazon | Stack|
|987|[Binary Number with <br>Alternating Bits](http://lintcode.com/problem/binary-number-with-alternating-bits/)| [C++](./C++/binary-number-with-alternating-bits.cpp)| _O(logn)_ | _O(1)_ | Easy | Yahoo | |
|988|[Arranging Coins](http://lintcode.com/problem/arranging-coins/)| [C++](./C++/arranging-coins.cpp)| _O(1)_ | _O(1)_ | Easy | GoDaddy | Math|
|1005|[Largest Triangle Area](http://lintcode.com/problem/largest-triangle-area/)| [C++](./C++/largest-triangle-area.cpp)| _O(n<sup>3</sup>)_ | _O(1)_ | Easy | Google | Math|
|1017|[Similar RGB Color](http://lintcode.com/problem/similar-rgb-color/)| [C++](./C++/similar-rgb-color.cpp)| _O(16)_ | _O(1)_ | Easy | Google | |
|1023|[Preimage Size of Factorial <br>Zeroes Function](http://lintcode.com/problem/preimage-size-of-factorial-zeroes-function/)| [C++](./C++/preimage-size-of-factorial-zeroes-function.cpp)| _O(logK)_ | _O(1)_ | Hard | Adobe | Binary Search |
|1192|[Longest Uncommon <br>Subsequence I](http://lintcode.com/problem/longest-uncommon-subsequence-i/)| [C++](./C++/longest-uncommon-subsequence-i.cpp)| _O(1)_ | _O(1)_ | Easy | Google | |
|1199|[Perfect Number](http://lintcode.com/problem/perfect-number/)| [C++](./C++/perfect-number.cpp)| _O(sqrt(n))_ | _O(1)_ | Easy | Fallible | |
|1209|[Construct The Rectangle](http://lintcode.com/problem/construct-the-rectangle/)| [C++](./C++/construct-the-rectangle.cpp)| _O(sqrt(n))_ | _O(1)_ | Easy | LintCode | |
|1216|[Largest Palindrome Product](http://lintcode.com/problem/largest-palindrome-product/)| [C++](./C++/largest-palindrome-product.cpp)| _O(pow(n))_ | _O(1)_ | Easy | Yahoo | Math|
|1217|[Total Hamming Distance](http://lintcode.com/problem/total-hamming-distance/)| [C++](./C++/total-hamming-distance.cpp)| _O(1)_ | _O(1)_ | Medium | Facebook | Math |
|1228|[Poor Pigs](http://lintcode.com/problem/poor-pigs/)| [C++](./C++/poor-pigs.cpp)| _O(1)_ | _O(1)_ | Easy | LintCode | Math |
|1256|[Nth Digit](http://lintcode.com/problem/nth-digit/)| [C++](./C++/nth-digit.cpp)| _O(1)_ | _O(1)_ | Easy | Google | Math |
|1277|[Water and Jug Problem](http://lintcode.com/problem/water-and-jug-problem/)| [C++](./C++/water-and-jug-problem.cpp)| _O(n)_ | _O(1)_ | Medium | Microsoft | Math |
|1285|[Power of Four](http://lintcode.com/problem/power-of-four/)| [C++](./C++/power-of-four.cpp)| _O(1)_ | _O(1)_ | Easy | Two Sigma | Math |
|1286|[Self Crossing](http://lintcode.com/problem/self-crossing/)| [C++](./C++/self-crossing.cpp)| _O(n)_ | _O(1)_ | Hard | LintCode | Math |
|1294|[Power of Three](http://lintcode.com/problem/power-of-three/)| [C++](./C++/power-of-three.cpp)| _O(1)_ | _O(1)_ | Easy | Google | Math |
|1300|[Nim Game](http://lintcode.com/problem/nim-game/)| [C++](./C++/nim-game.cpp)| _O(1)_ | _O(1)_ | Easy | Adobe | |
|1314|[Power of Two](http://lintcode.com/problem/power-of-two/)| [C++](./C++/power-of-two.cpp)| _O(1)_ | _O(1)_ | Easy | Google | Bit |
|1324|[Count Primes](http://lintcode.com/problem/count-primes/)| [C++](./C++/count-primes.cpp)| _O(nloglogn)_ | _O(n)_ | Easy | Amazon, <br>Microsoft | |
|1347|[Factorial Trailing Zeroes](http://lintcode.com/problem/factorial-trailing-zeroes/)| [C++](./C++/factorial-trailing-zeroes.cpp)| _O(logn)_ | _O(1)_ | Easy | Bloomberg | |
|1348|[Excel Sheet Column Number](http://lintcode.com/problem/excel-sheet-column-number/)| [C++](./C++/excel-sheet-column-number.cpp)| _O(n)_ | _O(1)_ | Easy | Uber, <br>Microsoft | |
|1350|[Excel Sheet Column Title](http://lintcode.com/problem/excel-sheet-column-title/)| [C++](./C++/excel-sheet-column-title.cpp)| _O(n)_ | _O(1)_ | Easy | Fackbook, <br>Microsoft | |
|1354|[Pascals Triangle II](http://lintcode.com/problem/pascals-triangle-ii/)| [C++](./C++/pascals-triangle-ii.cpp)| _O(k)_ | _O(k)_ | Easy | LintCode | |
|1385|[Lucky Number Eight](http://lintcode.com/problem/lucky-number-eight/)| [C++](./C++/lucky-number-eight.cpp)| _O(n)_ | _O(1)_ | Easy | LintCode | |
## 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 | | |
|208|[Assignment Operator Overloading <br>(C++ Only)](http://lintcode.com/problem/assignment-operator-overloading-c-only/)| [C++](./C++/assignment-operator-overloading-c-only.cpp)| _O(n)_ | _O(1)_ | Medium | | |
|496|[Toy Factory](http://lintcode.com/problem/toy-factory/)| [C++](./C++/toy-factory.cpp)| _O(1)_ | _O(1)_ | Easy | | |
## 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, Multiset |
|642|[Moving Average from <br>Data Stream](http://lintcode.com/problem/moving-average-from-data-stream/)| [C++](./C++/moving-average-from-data-stream.cpp)| _O(n)_ | _O(n)_ | Easy | | Queue |
|791|[Merge Number](http://lintcode.com/problem/merge-number/)| [C++](./C++/merge-number.cpp)| _O(n)_ | _O(k)_ | Medium | LintCode | |
|1109|[Dota2 Senate](http://lintcode.com/problem/dota2-senate/)| [C++](./C++/dota2-senate.cpp)| _O(n<sup>2</sup>)_ | _O(n)_ | Medium | Valve | Queue |
## 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 | | |
|72|[Construct Binary Tree from <br>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 | |
|73|[Construct Binary Tree from <br>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 | [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|[The Skyline Problem <br>(Building Outline)](http://lintcode.com/problem/the-skyline-problem/)| [C++](./C++/the-skyline-problem.cpp) | _O(nlogn)_ | _O(n)_ | Hard | EPI | todo |
|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<sup>0.5</sup>*4<sup>n</sup>)_ | _O(n)_ | Medium | LeetCode | DFS |
|177|[Convert Sorted Array to Binary <br>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 |
|202|[Segment Tree Query](http://lintcode.com/problem/segment-tree-query/)| [C++](./C++/segment-tree-query.cpp)| _O(h)_ | _O(h)_ | Medium | | Segment Tree |
|203|[Segment Tree Modify](http://lintcode.com/problem/segment-tree-modify/)| [C++](./C++/segment-tree-modify.cpp)| _O(h)_ | _O(h)_ | Medium | | Segment Tree |
|205|[Interval Minimum Number](http://lintcode.com/problem/interval-minimum-number/)| [C++](./C++/interval-minimum-number.cpp)| _O(n+klogh)_| _O(h)_ | Medium | | Segment Tree |
|206|[Interval Sum](http://lintcode.com/problem/interval-sum/)| [C++](./C++/interval-sum.cpp)| _O(n+klogn)_ | _O(n)_ | Medium | | Segment Tree,<br> Prefix-sum |
|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 |
|227|[Mock Hanoi Tower by Stacks](http://lintcode.com/problem/mock-hanoi-tower-by-stacks/)| [C++](./C++/mock-hanoi-tower-by-stacks.cpp)| _O(2<sup>n</sup>)_ | _O(2<sup>n</sup>)_ | Easy | | Recursion, <br>Stack|
|245|[Subtree](http://lintcode.com/problem/subtree/)| [C++](./C++/subtree.cpp)| _O(mn)_ | _O(1)_ | Easy | | Pre-order |
|247|[Segment Tree Query II](http://lintcode.com/problem/segment-tree-query-ii/)| [C++](./C++/segment-tree-query-ii.cpp)| _O(h)_ | _O(h)_ | Medium | | Segment Tree |
|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 | | Pre-order|
|378|[Convert Binary Search Tree <br>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 | | In-order|
|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 |
|453|[Flatten Binary Tree to <br>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| [Same Tree(Identical Binary Tree)](http://lintcode.com/problem/same-tree/)| [C++](./C++/same-tree.cpp)| _O(n)_ | _O(h)_ | Easy | | Pre-order|
|532|[Reverse Pairs](http://lintcode.com/problem/reverse-pairs/)| [C++](./C++/reverse-pairs.cpp)| _O(nlogn)_ | _O(n)_ | Medium | LintCode | Binary Search |
|575|[Decode String](http://lintcode.com/problem/decode-string/)| [C++](./C++/decode-string.cpp)| _O(n)_ | _O(n)_ | Medium | Google, <br>Facebook | Recursion |
|535|[House Robber III](http://lintcode.com/problem/house-robber-iii/)| [C++](./C++/house-robber-iii.cpp)| _O(n)_ | _O(h)_ | Medium | LeetCode | Post-order|
|650|[Find Leaves of Binary Tree](http://lintcode.com/problem/find-leaves-of-binary-tree/)| [C++](./C++/find-leaves-of-binary-tree.cpp)| _O(n)_ | _O(1)_ | Medium | LinkedIn | Binary Tree|
## 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(1)_ | Medium | EPI | [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 | Partition |
|139|[Subarray Sum Closest](http://lintcode.com/problem/subarray-sum-closest/)| [C++](./C++/subarray-sum-closest.cpp)| _O(nlogn)_ | _O(n)_ | Medium | | Prefix Sum |
|143|[Sort Colors II](http://lintcode.com/problem/sort-colors-ii/)| [C++](./C++/sort-colors-ii.cpp)| _O(n)_ | _O(1)_ | Medium | | Radix Sort |
|148|[Sort Colors](http://lintcode.com/problem/sort-colors/)| [C++](./C++/sort-colors.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | Radix Sort |
|156|[Merge Intervals](http://lintcode.com/problem/merge-intervals/)| [C++](./C++/merge-intervals.cpp)| _O(nlogn)_ | _O(1)_ | Easy | LeetCode | |
|184|[Largest Number](http://lintcode.com/problem/largest-number/)| [C++](./C++/largest-number.cpp)| _O(nlogn)_ | _O(1)_ | Medium | LeetCode | Sort |
|366|[Fibonacci](http://lintcode.com/problem/fibonacci/)| [C++](./C++/fibonacci.cpp)| _O(n)_ | _O(1)_ | Easy | | |
|379|[Reorder Array to Construct <br>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 | Sort|
|387|[The Smallest Difference](http://lintcode.com/problem/the-smallest-difference/)| [C++](./C++/the-smallest-difference.cpp)| _O(mlogm)_ | _O(1)_ | Medium | LintCode | Two Pointers |
|399|[Nuts & Bolts Problem](http://lintcode.com/problem/nuts-bolts-problem/)| [C++](./C++/nuts-bolts-problem.cpp)| _O(nlogn)_ | _O(logn)_ | Medium | | Quick Sort, <br>Select Sort |
|400|[Maximum Gap](http://lintcode.com/problem/maximum-gap/)| [C++](./C++/maximum-gap.cpp) | _O(nlogn)_ | _O(n)_ | Hard | LeetCode | Quick Sort |
|463|[Sort Integers](http://lintcode.com/problem/sort-integers/)| [C++](./C++/sort-integers.cpp)| _O(n<sup>2</sup> )_ | _O(1)_ | Easy | | Insertion Sort, <br>Selection Sort, <br>Bubble Sort |
|464|[Sort Integers II](http://lintcode.com/problem/sort-integers-ii/)| [C++](./C++/sort-integers-ii.cpp)| _O(nlogn)_ | _O(n)_ | Easy | | [Merge Sort](http://eudiwffe.cnblogs.com/p/6254394.html), <br>[Heap Sort](http://eudiwffe.cnblogs.com/p/6202111.html), <br>[Quick Sort](http://eudiwffe.cnblogs.com/p/6202996.html) |
|503|[Anagram Map Reduce](http://lintcode.com/problem/anagram-map-reduce/)| [C++](./C++/anagram-map-reduce.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | Sort |
|506|[Movie Recommendation](http://lintcode.com/problem/movie-recommendation/)| [C++](./C++/movie-recommendation.cpp)| _O(n^2)_ | _O(n)_ | Medium | LeetCode | Set |
|507|[Wiggle Sort II](http://lintcode.com/problem/wiggle-sort-ii/)| [C++](./C++/wiggle-sort-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | todo |
|508|[Wiggle Sort](http://lintcode.com/problem/wiggle-sort/)| [C++](./C++/wiggle-sort.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | |
|554|[Sort Integers Map Reduce](http://lintcode.com/problem/sort-integers-map-reduce/)| [C++](./C++/sort-integers-map-reduce.cpp)| _O(nlogn)_ | _O(1)_ | Medium | LeetCode | |
|912|[Best Meeting Point](http://lintcode.com/problem/best-meeting-point/)| [C++](./C++/best-meeting-point.cpp)| _O(mn)_ | _O(m+n)_ | Hard | Twitter | Sort|
|919|[Meeting Rooms II](http://lintcode.com/problem/meeting-rooms-ii/)| [C++](./C++/meeting-rooms-ii.cpp)| _O(nlogn)_ | _O(n)_ | Medium | Facebook | Sort|
|920|[Meeting Rooms](http://lintcode.com/problem/meeting-rooms/)| [C++](./C++/meeting-rooms.cpp)| _O(nlogn)_ | _O(1)_ | Easy | Facebook | HashSet|
|993|[Array Partition I](http://lintcode.com/problem/array-partition-i/)| [C++](./C++/array-partition-i.cpp)| _O(nlogn)_ | _O(1)_ | Easy | | Sort|
|1119|[Maximum Product of Three <br>Numbers](http://lintcode.com/problem/maximum-product-of-three-numbers/)| [C++](./C++/maximum-product-of-three-numbers.cpp)| _O(nlogn)_ | _O(1)_ | Easy | Intuit| Sort|
|1200|[Relative Ranks](http://lintcode.com/problem/relative-ranks/)| [C++](./C++/relative-ranks.cpp)| _O(nlogn)_ | _O(n)_ | Easy | | Sort|
|1231|[Minimum Moves to Equal <br>Array Elements](http://lintcode.com/problem/minimum-moves-to-equal-array-elements/)| [C++](./C++/minimum-moves-to-equal-array-elements.cpp)| _O(nlogn)_ | _O(1)_ | Easy | Indeed | Sort|
|1236|[Find All Numbers Disappeared <br>in An Array](http://lintcode.com/problem/find-all-numbers-disappeared-in-an-array/)| [C++](./C++/find-all-numbers-disappeared-in-an-array.cpp)| _O(nlogn)_ | _O(1)_ | Easy | Google | Sort|
|1318|[Contains Duplicate III](http://lintcode.com/problem/contains-duplicate-iii/)| [C++](./C++/contains-duplicate-iii.cpp)| _O(nlogn)_ | _O(n)_ | Easy | Airbnb | Sort|
## 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 | |
|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 | |
|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 | |
|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 | |
|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 | |
|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 | MiniStack |
|367|[Expression Tree Build](http://lintcode.com/problem/expression-tree-build/)| [C++](./C++/expression-tree-build.cpp)| _O(n)_ | _O(n)_ | Hard | | Stack|
|368|[Expression Evaluation](http://lintcode.com/problem/expression-evaluation/)| [C++](./C++/expression-evaluation.cpp)| _O(n)_ | _O(n)_ | Hard | | Stack|
|370|[Convert Expression to <br>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 | | Stack|
|421|[Simplify Path](http://lintcode.com/problem/simplify-path/)| [C++](./C++/simplify-path.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | |
|423|[Valid Parentheses](http://lintcode.com/problem/valid-parentheses.cpp/)| [C++](./C++/valid-parentheses.cpp.cpp)| _O(n)_ | _O(n)_ | Easy | LeetCode | |
|424|[Evaluate Reverse Polish <br>Notation](http://lintcode.com/problem/evaluate-reverse-polish-notation/)| [C++](./C++/evaluate-reverse-polish-notation.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | Stack|
|473|[Add and Search Word Data <br>Structure Design](http://lintcode.com/problem/add-and-search-word-data-structure-design/)| [C++](./C++/add-and-search-word-data-structure-design.cpp)| _O(h)_ | _O(h)_ | Medium | LeetCode | Trie Tree|
|510|[Maximal Rectangle](http://lintcode.com/problem/maximal-rectangle/)| [C++](./C++/maximal-rectangle.cpp)| _O(mn)_ | _O(n)_ | Hard | LeetCode | MiniStack |
|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 | Stack|
|636|[132 Pattern](http://lintcode.com/problem/132-pattern/)| [C++](./C++/132-pattern.cpp)| _O(nk)_ | _O(k)_ | Medium | LeetCode | Stack|
|834|[Remove Duplicate Letters](http://lintcode.com/problem/remove-duplicate-letters/)| [C++](./C++/remove-duplicate-letters.cpp)| _O(n)_ | _O(n)_ | Easy | Google | Stack|
|1201|[Next Greater Element II](http://lintcode.com/problem/next-greater-element-ii/)| [C++](./C++/next-greater-element-ii.cpp)| _O(n)_ | _O(n)_ | Medium | Google | Stack|
|1206|[Next Greater Element I](http://lintcode.com/problem/next-greater-element-i/)| [C++](./C++/next-greater-element-i.cpp)| _O(n)_ | _O(n)_ | Easy | LintCode | Stack|
## String
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|13|[Implement strStr](http://lintcode.com/problem/implement-strstr/)|[C++](./C++/implement-strstr.cpp)| _O(n+k)_ | _O(k)_ | Easy | LeetCode | 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 | Stack |
|54|[String to Integer Atoi](http://lintcode.com/problem/string-to-integer-atoi/)|[C++](./C++/string-to-integer-atoi.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 | | Hash|
|78|[Longest Common Prefix](http://lintcode.com/problem/longest-common-prefix/)|[C++](./C++/longest-common-prefix.cpp)| _O(n)_ | _O(1)_ | Medium | | |
|145|[Lowercase to Uppercase](http://lintcode.com/problem/lowercase-to-uppercase/)|[C++](./C++/lowercase-to-uppercase.cpp)| _O(n)_ | _O(1)_ | Naive | LintCode | ASCII|
|157|[Unique Characters](http://lintcode.com/problem/unique-characters/)|[C++](./C++/unique-characters.cpp)| _O(n)_ | _O(1)_ | Easy | CTCI | Hash|
|158|[Valid Anagram <br>(Two Strings Are Anagrams)](http://lintcode.com/problem/valid-anagram/)|[C++](./C++/valid-anagram.cpp)| _O(n)_ | _O(1)_ | Easy | | Hash|
|171|[Anagrams](http://lintcode.com/problem/anagrams/)|[C++](./C++/anagrams.cpp)| _O(nklogk)_ | _O(m)_ | Easy | LeetCode | Sort,Hash|
|212|[Space Replacement](http://lintcode.com/problem/space-replacement/)|[C++](./C++/space-replacement.cpp)| _O(n)_ | _O(1)_ | Easy | | |
|213|[String Compression](http://lintcode.com/problem/string-compression/)|[C++](./C++/string-compression.cpp)| _O(n)_ | _O(n)_ | Easy | | |
|407|[Plus One](http://lintcode.com/problem/plus-one/)|[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)_ | Easy | LinkedIn | Regex |
|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 | |
|491|[Palindrome Number](http://lintcode.com/problem/palindrome-number/)|[C++](./C++/palindrome-number.cpp)| _O(1)_ | _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 | |
|594|[strStr II](http://lintcode.com/problem/strstr-ii/)|[C++](./C++/strstr-ii.cpp)| _O(n+k)_ | _O(k)_ | Easy | LeetCode | KMP |
|637|[Valid Word Abbreviation](http://lintcode.com/problem/valid-word-abbreviation/)|[C++](./C++/valid-word-abbreviation.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|640|[One Edit Distance](http://lintcode.com/problem/one-edit-distance/)|[C++](./C++/one-edit-distance.cpp)| _O(n)_ | _O(1)_ | Medium | Facebook | |
|643|[Longest Absolute File Path](http://lintcode.com/problem/longest-absolute-file-path/)|[C++](./C++/longest-absolute-file-path.cpp)| _O(n)_ | _O(n)_ | Medium | Google | |
|644|[Strobogrammatic Number](http://lintcode.com/problem/strobogrammatic-number/)|[C++](./C++/strobogrammatic-number.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|655|[Add Strings](http://lintcode.com/problem/add-strings/)|[C++](./C++/add-strings.cpp)| _O(n)_ | _O(1)_ | Easy | LeetCode | |
|656|[Multiply Strings](http://lintcode.com/problem/multiply-strings/)|[C++](./C++/multiply-strings.cpp)| _O(mn)_ | _O(1)_ | Medium | LeetCode | |
|659|[Encode and Decode Strings](http://lintcode.com/problem/encode-and-decode-strings/)|[C++](./C++/encode-and-decode-strings.cpp)| _O(n)_ | _O(n)_ | Medium | Google | |
|678|[Shortest Palindrome](http://lintcode.com/problem/shortest-palindrome/)|[C++](./C++/shortest-palindrome.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Medium | Google | |
|686|[Remove Arbitrary](http://lintcode.com/problem/remove-arbitrary/)|[C++](./C++/remove-arbitrary.cpp)| _O(n)_ | _O(1)_ | Easy | LintCode | |
|688|[The Number in Words](http://lintcode.com/problem/the-number-in-words/)|[C++](./C++/the-number-in-words.cpp)| _O(1)_ | _O(1)_ | Medium | LintCode | |
|719|[Calculate Maximum Value](http://lintcode.com/problem/calculate-maximum-value/)|[C++](./C++/calculate-maximum-value.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | |
|776|[Strobogrammatic Number II](http://lintcode.com/problem/strobogrammatic-number-ii/)|[C++](./C++/strobogrammatic-number-ii.cpp)| _O(n)_ | _O(n)_ | Medium | Google | Backtrack|
|784|[The Longest Common Prefix II](http://lintcode.com/problem/the-longest-common-prefix-ii/)|[C++](./C++/the-longest-common-prefix-ii.cpp)| _O(nk)_ | _O(1)_ | Easy | LintCode | |
|812|[Bold Words i String](http://lintcode.com/problem/bold-words-in-string/)|[C++](./C++/bold-words-in-string.cpp)| _O(nk)_ | _O(m)_ | Easy | LintCode | Hash |
|837|[Palindromic-Substrings](http://lintcode.com/problem/palindromic-substrings/)|[C++](./C++/palindromic-substrings.cpp)| _O(n<sup>2</sup>)_ | _O(1)_ | Easy | LintCode | |
|891|[Valid Palindrome II](http://lintcode.com/problem/valid-palindrome-ii/)|[C++](./C++/valid-palindrome-ii.cpp)| _O(n)_ | _O(1)_ | Medium | NetEase, <br>Facebook | |
|914|[Flip Game](http://lintcode.com/problem/flip-game/)|[C++](./C++/flip-game.cpp)| _O(n)_ | _O(1)_ | Easy | Google | |
|916|[Palindrome Permutation](http://lintcode.com/problem/palindrome-permutation/)|[C++](./C++/palindrome-permutation.cpp)| _O(n)_ | _O(1)_ | Easy | Google | HashMap|
|927|[Reverse Words in a String ii](http://lintcode.com/problem/reverse-words-in-a-string-ii/)|[C++](./C++/reverse-words-in-a-string-ii.cpp)| _O(n)_ | _O(1)_ | Medium | LeetCode | |
|936|[Capitalizes The First Letter](http://lintcode.com/problem/capitalizes-the-first-letter/)|[C++](./C++/capitalizes-the-first-letter.cpp)| _O(n)_ | _O(1)_ | Easy | LintCode | |
|1086|[Repeated String Match](http://lintcode.com/problem/repeated-string-match/)|[C++](./C++/repeated-string-match.cpp)| _O(n)_ | _O(1)_ | Easy | Google | KMP |
|1011|[Number of Lines to Write String](http://lintcode.com/problem/number-of-lines-to-write-string/)|[C++](./C++/number-of-lines-to-write-string.cpp)| _O(n)_ | _O(1)_ | Easy | LintCode | |
|1013|[Unique Morse Code Words](http://lintcode.com/problem/unique-morse-code-words/)|[C++](./C++/unique-morse-code-words.cpp)| _O(n)_ | _O(n)_ | Easy | LintCode | HashTable|
|1028|[Rotated Digits](http://lintcode.com/problem/rotated-digits/)|[C++](./C++/rotated-digits.cpp)| _O(n)_ | _O(1)_ | Easy | LintCode | |
|1056|[Find Smallest Letter <br>Greater Than Target](http://lintcode.com/problem/find-smallest-letter-greater-than-target/)|[C++](./C++/find-smallest-letter-greater-than-target.cpp)| _O(n)_ | _O(1)_ | Easy | LinkedIn | |
|1079|[Count Binary Substring](http://lintcode.com/problem/count-binary-substring/)|[C++](./C++/count-binary-substring.cpp)| _O(n)_ | _O(1)_ | Easy | Helix | |
|1104|[Judge Route Circle](http://lintcode.com/problem/judge-route-circle/)|[C++](./C++/judge-route-circle.cpp)| _O(n)_ | _O(1)_ | Easy | Google | |
|1173|[Reverse Words in A String III](http://lintcode.com/problem/reverse-words-in-a-string-iii/)|[C++](./C++/reverse-words-in-a-string.cpp)| _O(n)_ | _O(1)_ | Easy | Zappos | |
|1178|[Student Attendance Record I](http://lintcode.com/problem/student-attendance-record-i/)|[C++](./C++/student-attendance-record-i.cpp)| _O(n)_ | _O(1)_ | Easy | Google | |
|1193|[Detect Capital](http://lintcode.com/problem/detect-capital/)|[C++](./C++/detect-captial.cpp)| _O(n)_ | _O(1)_ | Easy | Google | |
|1204|[Keyboard Row](http://lintcode.com/problem/keyboard-row/)|[C++](./C++/keyboard-row.cpp)| _O(n)_ | _O(1)_ | Easy | Mathworks | |
|1214|[License Key Formatting](http://lintcode.com/problem/license-key-formatting/)|[C++](./C++/license-key-formatting.cpp)| _O(n)_ | _O(1)_ | Easy | Google | |
|1227|[Repeated Substring Pattern](http://lintcode.com/problem/repeated-substring-pattern/)|[C++](./C++/repeated-substring-pattern.cpp)| _O(n)_ | _O(n)_ | Easy | Google, <br>Amazon | |
|1243|[Number of Segments in A String](http://lintcode.com/problem/number-of-segments-in-a-string/)|[C++](./C++/number-of-segments-in-a-string.cpp)| _O(n)_ | _O(1)_ | Easy | LintCode | |
|1283|[Reverse String](http://lintcode.com/problem/reverse-string/)|[C++](./C++/reverse-string.cpp)| _O(n)_ | _O(1)_ | Easy | LintCode | |
|1394|[Goat Latin](http://lintcode.com/problem/goat-latin/)|[C++](./C++/goat-latin.cpp)| _O(n)_ | _O(n)_ | Easy | Facebook | |
|1510|[Buddy Strings](http://lintcode.com/problem/buddy-strings/)|[C++](./C++/buddy-strings.cpp)| _O(n)_ | _O(1)_ | Easy | Google | |
|1535|[To Lower Case](http://lintcode.com/problem/to-lower-case/)|[C++](./C++/to-lower-case.cpp)| _O(n)_ | _O(1)_ | Easy | LintCode | |
|1781|[Reverse ASCII Encoded Strings](http://lintcode.com/problem/reverse-ascii-encoded-strings/)|[C++](./C++/reverse-ascii-encoded-strings.cpp)| _O(n)_ | _O(n)_ | Easy | Twitter | |
## System Design
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|499|[Word Count Map Reduce](http://lintcode.com/problem/word-count-map-reduce/)| [C++](./C++/word-count-map-reduce.cpp)| _O(n)_ | _O(n)_ | Easy | LintCode | Map-Reduce|
|501|[Design Twitter(Mini Twitter)](http://lintcode.com/problem/design-twitter/)| [C++](./C++/design-twitter.cpp)| _O(klogu)_ | _O(t+f)_ | Medium | Twitter | HashMap|
|504|[Inverted Index Map Reduce](http://lintcode.com/problem/inverted-index-map-reduce/)| [C++](./C++/inverted-index-map-reduce.cpp)| _O(n)_ | _O(n)_ | Medium | LintCode | Map-Reduce|
|537|[N Gram Map Reduce](http://lintcode.com/problem/n-gram-map-reduce/)| [C++](./C++/n-gram-map-reduce.cpp)| _O(n)_ | _O(n)_ | Medium | LintCode | Map-Reduce|
|607|[Two Sum III Data Structure Design](http://lintcode.com/problem/two-sum-iii-data-structure-design/)| [C++](./C++/two-sum-iii-data-structure-design.cpp)| _O(n)_ | _O(n)_ | Easy | LinkedIn | HashMap|
|660|[Read N Charaters Given Read4 II <br>Call Multiple Times](http://lintcode.com/problem/read-n-characters-given-read4-ii-call-multiple-times/)| [C++](./C++/read-n-characters-given-read4-ii-call-multiple-times.cpp)| _O(n)_ | _O(4)_ | Medium | | |
## Tree
| PID# | Title | Source | Time | Space | Level | Tag | Note |
| ---- | ----- | ------ | ---- | ----- | ----- | --- | ---- |
|7|[Serialize and Deserialize Binary Tree](http://lintcode.com/problem/serialize-and-deserialzie-binary-tree/)| [C++](./C++/serialize-and-deserialize-binary-tree.cpp)| _O(n)_ | _O(h)_ | Medium | | Queue|
|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 | Deque |
|175|[Invert Binary Tree](http://lintcode.com/problem/invert-binary-tree/)| [C++](./C++/invert-binary-tree.cpp)| _O(n)_ | _O(h)_ | Easy | LeetCode | DFS|
|242|[Convert Binary Tree to <br>Linked Lists by Depth](http://lintcode.com/problem/convert-binary-tree-to-linked-lists-by-depth/)| [C++](./C++/convert-binary-tree-to-linked-lists-by-depth.cpp)| _O(n)_ | _O(h)_ | Easy | LintCode | BFS|
|442|[Implement Trie Prefix Tree](http://lintcode.com/problem/implement-trie-prefix-tree/)| [C++](./C++/implement-trie-prefix-tree.cpp)| _O(n)_ | _O(n)_ | Medium | LeetCode | Trie Tree |
|474|[Lowest Common Ancestor II](http://lintcode.com/problem/lowest-common-ancestor-ii/)| [C++](./C++/lowest-common-ancestor-ii.cpp)| _O(n)_ | _O(h)_ | Easy | | Stack |
|578|[Lowest Common Ancestor III](http://lintcode.com/problem/lowest-common-ancestor-iii/)| [C++](./C++/lowest-common-ancestor-iii.cpp)| _O(n)_ | _O(h)_ | Medium | | Deque |
|595|[Binary Tree Longest <br>Consecutive Sequence](http://lintcode.com/problem/binary-tree-longest-consecutive-sequence/)| [C++](./C++/binary-tree-longest-consecutive-sequence.cpp)| _O(n)_ | _O(1)_ | Easy | Google, <br>NetEase ||
|596|[Minimum Subtree](http://lintcode.com/problem/minimum-subtree/)| [C++](./C++/minimum-subtree.cpp)| _O(n)_ | _O(h)_ | Easy | | DFS |
|597|[Subtree with Maximum Average](http://lintcode.com/problem/subtree-with-maximum-average/)| [C++](./C++/subtree-with-maximum-average.cpp)| _O(n)_ | _O(h)_ | Easy | | DFS |
|614|[Binary Tree Longest <br>Consecutive Sequence II](http://lintcode.com/problem/binary-tree-longest-consecutive-sequence-ii/)| [C++](./C++/binary-tree-longest-consecutive-sequence-ii.cpp)| _O(n)_ | _O(1)_ | Easy | Google ||
|628|[Maximum Subtree](http://lintcode.com/problem/maximum-subtree/)| [C++](./C++/maximum-subtree.cpp)| _O(n)_ | _O(h)_ | Easy | | DFS |
|632|[Binary Tree Maximum Node](http://lintcode.com/problem/binary-tree-maximum-node/)|[C++](./C++/binary-tree-maximum-node.cpp)| _O(n)_ | _O(1)_ | Naive | | DFS |
|649|[Binary Tree Upside Down](http://lintcode.com/problem/binary-tree-upside-down/)|[C++](./C++/binary-tree-upside-down.cpp)| _O(n)_ | _O(1)_ | Medium | LinkedIn | |
|651|[Binary Tree Vertical Order <br>Traversal](http://lintcode.com/problem/binary-tree-vertical-order-traversal/)|[C++](./C++/binary-tree-vertical-order-traversal.cpp)| _O(n)_ | _O(n)_ | Medium | Google, <br>Facebook | Map |
|726|[Check Full Binary Tree](http://lintcode.com/problem/check-full-binary-tree/)|[C++](./C++/check-full-binary-tree.cpp)| _O(n)_ | _O(1)_ | Medium | Amazon| |
|921|[Count Univalue Subtrees](http://lintcode.com/problem/count-univalue-substrees/)|[C++](./C++/count-univalue-subtrees.cpp)| _O(n)_ | _O(1)_ | Medium | | Postorder |
|1003|[Binary Tree Pruning](http://lintcode.com/problem/binary-tree-pruning/)|[C++](./C++/binary-tree-pruning.cpp)| _O(n)_ | _O(1)_ | Easy | Hulu | DFS |
|1085|[Longest Univalue Path](http://lintcode.com/problem/longest-univalue-path/)|[C++](./C++/longest-univalue-path.cpp)| _O(n)_ | _O(1)_ | Easy | Google | DFS |
|1094|[Second Minimum Node in A <br>Binary Tree](http://lintcode.com/problem/second-minimum-node-in-a-binary-tree/)|[C++](./C++/second-minimum-node-in-a-binary-tree.cpp)| _O(n)_ | _O(1)_ | Easy | LinkedIn | DFS |
|1106|[Maximum Binary Tree](http://lintcode.com/problem/maximum-binary-tree/)|[C++](./C++/maximum-binary-tree.cpp)| _O(nlogn)_ | _O(n)_ | Easy | Microsoft | |
|1115|[Average of Levels in <br>Binary Tree](http://lintcode.com/problem/average-of-levels-in-binary-tree/)|[C++](./C++/average-of-levels-in-binary-tree.cpp)| _O(n)_ | _O(n)_ | Easy | Facebook | Queue|
|1126|[Merge Two Binary Trees](http://lintcode.com/problem/merge-two-binary-trees/)|[C++](./C++/merge-two-binary-trees.cpp)| _O(n)_ | _O(1)_ | Easy | Amazon | |
|1137|[Construct String from <br>Binary Tree](http://lintcode.com/problem/construct-string-from-binary-tree/)|[C++](./C++/construct-string-from-binary-tree.cpp)| _O(n)_ | _O(n)_ | Easy | Amazon | |
|1165|[Subtree of Another Tree](http://lintcode.com/problem/subtree-of-another-tree/)|[C++](./C++/subtree-of-another-tree.cpp)| _O(n)_ | _O(n)_ | Easy | eBay, <br>Facebook | |
|1172|[Binary Tree Tilt](http://lintcode.com/problem/binary-tree-tilt/)|[C++](./C++/binary-tree-tilt.cpp)| _O(n)_ | _O(1)_ | Easy | Indeed | Postorder|
|1181|[Diameter of Binary Tree](http://lintcode.com/problem/diameter-of-binary-tree/)|[C++](./C++/diameter-of-binary-tree.cpp)| _O(n)_ | _O(1)_ | Easy | Google, <br>Facebook | Postorder|
|1198|[Most Frequent Subtree Sum](http://lintcode.com/problem/most-frequent-subtree-sum/)|[C++](./C++/most-frequent-subtree-sum.cpp)| _O(n)_ | _O(n)_ | Medium | Amazon | HashMap |
|1254|[Sum of Left Leaves](http://lintcode.com/problem/sum-of-left-leaves/)|[C++](./C++/sum-of-left-leaves.cpp)| _O(n)_ | _O(1)_ | Easy | Facebook | postorder |
|1360|[Symmetric Tree](http://lintcode.com/problem/symmetric-tree/)|[C++](./C++/symmetric-tree.cpp)| _O(n)_ | _O(1)_ | Easy | LinkedIn, <br>Microsoft | postorder |