Skip to content

Latest commit

 

History

History
734 lines (656 loc) · 56.5 KB

README.md

File metadata and controls

734 lines (656 loc) · 56.5 KB

LeetCode

Up to date (2015-01-13), there are total 180 problems on LeetCode Online Judge. The number of problems is increasing recently. Here is the classification of all 180 problems. I'll keep updating for full summary and better solutions. Stay tuned for updates.


Algorithm

Database


##Bit Manipulation

Problem Solution Time Space Difficulty Notes
Single Number single-number.py O(n) O(1) Medium
Single Number II single-number-ii.py O(n) O(1) Medium

##Array

Problem Solution Time Space Difficulty Notes
3 Sum 3sum.py O(n^2) O(1) Medium
3 Sum Closest 3sum-closest.py O(n^2) O(1) Medium
Best Time to Buy and Sell Stock best-time-to-buy-and-sell-stock.py O(n) O(1) Medium
First Missing Positive first-missing-positive.py O(n) O(1) Hard Tricky
Longest Consecutive Sequence longest-consecutive-sequence.py O(n) O(n) Hard Tricky
Majority Element majority-element.py O(n) O(1) Easy
Missing Ranges missing-ranges.py O(n) O(1) Medium
Next Permutation next-permutation.py O(n) O(1) Medium Tricky
Pascal's Triangle pascals-triangle.py O(n^2) O(n) Easy
Pascal's Triangle II pascals-triangle-ii.py O(n^2) O(n) Easy
Plus One plus-one.py O(n) O(1) Easy
Read N Characters Given Read4 read-n-characters-given-read4.py O(n) O(1) Easy
Read N Characters Given Read4 II - Call multiple times read-n-characters-given-read4-ii-call-multiple-times.py O(n) O(1) Hard
Remove Duplicates from Sorted Array remove-duplicates-from-sorted-array.py O(n) O(1) Easy
Remove Duplicates from Sorted Array II remove-duplicates-from-sorted-array-ii.py O(n) O(1) Medium
Remove Element remove-element.py O(n) O(1) Easy
Rotate Image rotate-image.py O(n^2) O(1) Medium
Set Matrix Zeroes set-matrix-zeroes.py O(m * n) O(1) Medium
Spiral Matrix spiral-matrix.py O(m * n) O(1) Medium
Spiral Matrix II spiral-matrix-ii.py O(m * n) O(1) Medium

##String

Problem Solution Time Space Difficulty Notes
Add Binary add-binary.py O(n) O(1) Easy
Anagrams anagrams.py O(n) O(n) Medium
Compare Version Numbers compare-version-numbers.py O(n) O(1) Easy
Count and Say count-and-say.py O(n^2) O(n) Easy
Implement strStr() implement-strstr.py O(n + m) O(m) Easy KMP Algorithm
Length of Last Word length-of-last-word.py O(n) O(1) Easy
Longest Common Prefix longest-common-prefix.py O(n1 + n2 + ...) O(1) Easy
Longest Palindromic Substring longest-palindromic-substring.py O(n) O(n) Medium Manacher's Algorithm
Multiply Strings multiply-strings.py O(m * n) O(m + n) Medium
One Edit Distance one-edit-distance.py O(m + n) O(1) Medium
Reverse Words in a String reverse-words-in-a-string.py O(n) O(n) Medium
String to Integer (atoi) string-to-integer-atoi.py O(n) O(1) Easy
Text Justification text-justification.py O(n) O(1) Hard
Valid Palindrome valid-palindrome.py O(n) O(1) Easy
ZigZag Conversion zigzag-conversion.py O(n) O(1) Easy

##Linked List

Problem Solution Time Space Difficulty Notes
Add Two Numbers add-two-numbers.py O(n) O(1) Medium
Copy List with Random Pointer copy-list-with-random-pointer.py O(n) O(1) Hard
Intersection of Two Linked Lists intersection-of-two-linked-lists.py O(m + n) O(1) Easy
Remove Duplicates from Sorted List remove-duplicates-from-sorted-list.py O(n) O(1) Easy
Remove Duplicates from Sorted List II remove-duplicates-from-sorted-list-ii.py O(n) O(1) Medium
Reverse Linked List II reverse-linked-list-ii.py O(n) O(1) Medium
Reverse Nodes in k-Group reverse-nodes-in-k-group.py O(n) O(1) Hard
Rotate List rotate-list.py O(n) O(1) Medium
Swap Nodes in Pairs swap-nodes-in-pairs.py O(n) O(1) Medium

##Stack

Problem Solution Time Space Difficulty Notes
Binary Search Tree Iterator binary-search-tree-iterator.py O(1) O(logn) Medium
Evaluate Reverse Polish Notation evaluate-reverse-polish-notation.py O(n) O(n) Medium
Longest Valid Parentheses longest-valid-parentheses.py O(n) O(1) Hard
Min Stack min-stack.py O(n) O(1) Easy
Simplify Path simplify-path.py O(n) O(n) Medium
Symmetric Tree symmetric-tree.py O(n) O(logn) Easy
Valid Parentheses valid-parentheses.py O(n) O(n) Easy

##Heap

Problem Solution Time Space Difficulty Notes
Merge k Sorted Lists merge-k-sorted-lists.py O(nlogk) O(1) Hard

##Tree

Problem Solution Time Space Difficulty Notes
Binary Tree Preorder Traversal binary-tree-preorder-traversal.py O(n) O(1) Medium Morris Traversal
Binary Tree Inorder Traversal binary-tree-inorder-traversal.py O(n) O(1) Medium Morris Traversal
Binary Tree Postorder Traversal binary-tree-postorder-traversal.py O(n) O(1) Hard Morris Traversal
Recover Binary Search Tree recover-binary-search-tree.py O(n) O(1) Hard Morris Traversal

##Hash Table

Problem Solution Time Space Difficulty Notes
4 Sum 4sum.py O(n^2) ~ O(n^4) O(n^2) Medium
Longest Substring with At Most Two Distinct Characters longest-substring-with-at-most-two-distinct-characters.py O(n^2) O(1) Hard
Longest Substring Without Repeating Characters longest-substring-without-repeating-characters.py O(n) O(1) Medium
Max Points on a Line max-points-on-a-line.py O(n^2) O(n) Hard
Minimum Window Substring minimum-window-substring.py O(n^2) O(n) Hard
Substring with Concatenation of All Words substring-with-concatenation-of-all-words.py O(m * n * k) O(n * k) Hard
Two Sum two-sum.py O(n) O(n) Medium
Two Sum III - Data structure design two-sum-iii-data-structure-design.py O(n) O(n) Easy
Valid Sudoku valid-sudoku.py O(n) O(n) Easy

##Data Structure

Problem Solution Time Space Difficulty Notes
LRU Cache lru-cache.py O(1) O(n) Hard

##Math

Problem Solution Time Space Difficulty Notes
Divide Two Integers divide-two-integers.py O(logn) O(1) Medium
Excel Sheet Column Title excel-sheet-column-title.py O(logn) O(1) Easy
Excel Sheet Column Number excel-sheet-column-number.py O(n) O(1) Easy
Factorial Trailing Zeroes factorial-trailing-zeroes.py O(logn) O(1) Easy
Fraction to Recurring Decimal fraction-to-recurring-decimal.py O(logn) O(1) Medium
Gray Code gray-code.py O(2^n) O(1) Medium
Integer to Roman integer-to-roman.py O(n) O(1) Medium
Palindrome Number palindrome-number.py O(1) O(1) Easy
Permutation Sequence permutation-sequence.py O(n) O(1) Medium Cantor Ordering
Reverse Integer reverse-integer.py O(logn) O(1) Easy
Roman to Integer roman-to-integer.py O(n) O(1) Easy
Valid Number valid-number.py O(n) O(1) Hard Automata

##Sort

Problem Solution Time Space Difficulty Notes
Insert Interval insert-interval.py O(n) O(1) Hard
Insertion Sort List insertion-sort-list.py O(n^2) O(1) Medium
Largest Number largest-number.py O(n^2) O(n) Medium
Maximum Gap maximum-gap.py O(n) O(n) Hard Tricky
Merge Intervals merge-intervals.py O(n^2) O(1) Hard
Merge Sorted Array merge-sorted-array.py O(n) O(1) Easy
Merge Two Sorted Lists merge-two-sorted-lists.py O(n) O(1) Easy
Sort Colors sort-colors.py O(n) O(1) Medium
Sort List sort-list.py O(nlogn) O(1) Medium

##Two Pointer

Problem Solution Time Space Difficulty Notes
Linked List Cycle linked-list-cycle.py O(n) O(1) Medium
Linked List Cycle II linked-list-cycle-ii.py O(n) O(1) Medium
Partition List partition-list.py O(n) O(1) Medium
Remove Nth Node From End of List remove-nth-node-from-end-of-list.py O(n) O(1) Easy
Reorder List reorder-list.py O(n) O(1) Medium
Two Sum II - Input array is sorted two-sum-ii-input-array-is-sorted.py O(n) O(1) Medium

##Brute Force Search

Problem Solution Time Space Difficulty Notes
Letter Combinations of a Phone Number letter-combinations-of-a-phone-number.py O(4^n) O(1) Medium
Permutations permutations.py O(n!) O(n) Medium
Permutations II permutations-ii.py O(n!) O(n) Hard
Subsets subsets.py O(2^n) O(1) Medium
Subsets II subsets-ii.py O(2^n) O(1) Medium

##Divide and Conquer

Problem Solution Time Space Difficulty Notes
Balanced Binary Tree balanced-binary-tree.py O(n) O(logn) Easy
Binary Tree Maximum Path Sum binary-tree-maximum-path-sum.py O(n) O(logn) Hard
Binary Tree Upside Down binary-tree-upside-down.py O(n) O(1) Medium
Construct Binary Tree from Inorder and Postorder Traversal construct-binary-tree-from-inorder-and-postorder-traversal.py O(n) O(n) Medium
Construct Binary Tree from Preorder and Inorder Traversal construct-binary-tree-from-preorder-and-inorder-traversal.py O(n) O(n) Medium
Convert Sorted Array to Binary Search Tree convert-sorted-array-to-binary-search-tree.py O(n) O(logn) Medium
Convert Sorted List to Binary Search Tree convert-sorted-list-to-binary-search-tree.py O(n) O(logn) Medium
Flatten Binary Tree to Linked List flatten-binary-tree-to-linked-list.py O(n) O(logn) Medium
Maximum Depth of Binary Tree maximum-depth-of-binary-tree.py O(n) O(logn) Easy
Minimum Depth of Binary Tree minimum-depth-of-binary-tree.py O(n) O(logn) Easy
Populating Next Right Pointers in Each Node populating-next-right-pointers-in-each-node.py O(n) O(logn) Medium
Same Tree same-tree.py O(n) O(logn) Easy
Sum Root to Leaf Numbers sum-root-to-leaf-numbers.py O(n) O(logn) Medium
Unique Binary Search Trees II unique-binary-search-trees-ii.py O(4^n / n^(3/2) O(4^n / n^(3/2) Medium
Validate Binary Search Tree validate-binary-search-tree.py O(n) O(logn) Medium

##Binary Search

Problem Solution Time Space Difficulty Notes
Find Minimum in Rotated Sorted Array find-minimum-in-rotated-sorted-array.py O(logn) O(1) Medium
Find Minimum in Rotated Sorted Array II find-minimum-in-rotated-sorted-array-ii.py O(logn) ~ O(n) O(1) Hard
Find Peak Element find-peak-element.py O(logn) O(1) Medium
Median of Two Sorted Arrays median-of-two-sorted-arrays.py O(log(m + n) O(log(m + n) Hard
Pow(x, n) powx-n.py O(logn) O(logn) Medium
Search a 2D Matrix search-a-2d-matrix.py O(log m + logn) O(1) Medium
Search for a Range search-for-a-range.py O(logn) O(1) Medium
Search in Rotated Sorted Array search-in-rotated-sorted-array.py O(logn) O(1) Hard
Search in Rotated Sorted Array II search-in-rotated-sorted-array-ii.py O(logn) O(1) Medium
Search Insert Position search-insert-position.py O(logn) O(1) Medium
Sqrt(x) sqrtx.py O(logn) O(1) Medium

##Breadth-First Search

Problem Solution Time Space Difficulty Notes
Binary Tree Level Order Traversal binary-tree-level-order-traversal.py O(n) O(n) Easy
Binary Tree Level Order Traversal II binary-tree-level-order-traversal-ii.py O(n) O(n) Easy
Binary Tree Zigzag Level Order Traversal binary-tree-zigzag-level-order-traversal.py O(n) O(n) Medium
Clone Graph clone-graph.py O(n) O(n) Medium
Populating Next Right Pointers in Each Node II populating-next-right-pointers-in-each-node-ii.py O(n) O(1) Hard
Surrounded Regions surrounded-regions.py O(m * n) O(m + n) Medium
Word Ladder word-ladder.py O((25n)^n) O((25n)^n) Medium

##Depth-First Search

Problem Solution Time Space Difficulty Notes
Combination Sum combination-sum.py O(n^m) O(m) Medium
Combination Sum II combination-sum-ii.py O(n! / m!(n-m)!) O(m) Medium
Combinations combinations.py O(n!) O(n) Medium
Generate Parentheses generate-parentheses.py O(4^n / n^(3/2) O(n) Medium
N-Queens n-queens.py O(n!) O(n) Hard
N-Queens-II n-queens-ii.py O(n!) O(n) Hard
Palindrome Partitioning palindrome-partitioning.py O(n^2) ~ O(2^n) O(n^2) Medium
Path Sum path-sum.py O(n) O(logn) Easy
Path Sum II path-sum-ii.py O(n) O(logn) Medium
Restore IP Addresses restore-ip-addresses.py O(n^m) ~ O(3^4) O(n * m) ~ O(3 * 4) Medium
Sudoku Solver sudoku-solver.py O((9!)^9) O(1) Hard
Word Search word-search.py O(m * n * 3^p) O(m * n * p) Medium

##Dynamic Programming

Problem Solution Time Space Difficulty Notes
Best Time to Buy and Sell Stock III best-time-to-buy-and-sell-stock-iii.py O(n) O(1) Hard
Climbing Stairs climbing-stairs.py O(n) O(1) Easy
Decode Ways decode-ways.py O(n) O(1) Medium
Distinct Subsequences distinct-subsequences.py O(n^2) O(n) Hard
Dungeon Game dungeon-game.py O(m * n) O(m + n) Hard
Edit Distance edit-distance.py O(m * n) O(m + n) Hard
Interleaving String interleaving-string.py O(m * n) O(m + n) Hard
Maximal Rectangle maximal-rectangle.py O(n^2) O(n) Hard
Maximum Product Subarray maximum-product-subarray.py O(n) O(1) Medium
Maximum Subarray maximum-subarray.py O(n) O(1) Medium
Minimum Path Sum minimum-path-sum.py O(m * n) O(m + n) Medium
Palindrome Partitioning II palindrome-partitioning-ii.py O(n^2) O(n^2) Hard
Regular Expression Matching regular-expression-matching.py O(m * n) O(n) Hard
Scramble String scramble-string.py O(n^4) O(n^3) Hard
Triangle triangle.py O(m * n) O(n) Medium
Unique Binary Search Trees unique-binary-search-trees.py O(n^2) O(n) Medium
Unique Paths unique-paths.py O(m * n) O(m + n) Medium
Unique Paths II unique-paths-ii.py O(m * n) O(m + n) Medium
Word Break word-break.py O(n^2) O(n) Medium
Word Break II word-break-ii.py O(n^2) O(n) Hard

##Backtracking

Problem Solution Time Space Difficulty Notes
Word Ladder II word-ladder-ii.py O((25n)^n) O((25n)^n) Hard

##Greedy

Problem Solution Time Space Difficulty Notes
Best Time to Buy and Sell Stock II best-time-to-buy-and-sell-stock-ii.py O(n) O(1) Medium
Candy candy.py O(n) O(n) Hard
Container With Most Water container-with-most-water.py O(n) O(1) Medium
Gas Station gas-station.py O(n) O(1) Medium
Jump Game jump-game.py O(n) O(1) Medium
Jump Game II jump-game-ii.py O(n^2) O(1) Hard
Largest Rectangle in Histogram largest-rectangle-in-histogram.py O(n) O(n) Hard Tricky
Trapping Rain Water trapping-rain-water.py O(n) O(1) Hard Tricky
Wildcard Matching wildcard-matching.py O(m + n) O(1) Hard Tricky

##SQL

Problem Solution Time Space Difficulty Notes
Combine Two Tables combine-two-tables.sql O(m + n) O(m + n) Easy
Consecutive Numbers consecutive-numbers.sql O(n) O(n) Medium
Nth Highest Salary nth-highest-salary.sql O(n^2) O(n) Medium
Rank Scores rank-scores.sql O(n^2) O(n) Medium
Second Highest Salary second-highest-salary.sql O(n) O(1) Easy