The Python3 solutions for LeetCode problems.
Back to Table of Contents
# |
Title |
Solutions |
Time |
Space |
Comments |
1 |
Two Sum |
Python3(40ms) |
O(N) |
O(N) |
|
2 |
Add Two Numbers |
Python3(112ms) |
O(Max(N, M)) |
O(1) |
|
3 |
Longest Substring Without Repeating Characters |
Python3(72ms) |
O(N) |
O(1) |
C# use array will slower |
4 |
Median of Two Sorted Arrays |
Python3(100ms) |
O(Log(N+M)) |
O(1) |
|
5 |
Longest Palindromic Substring |
Python3(120ms) |
O(N) |
O(N) |
Use Manacher's Algorithm |
6 |
ZigZag Conversion |
Python3(100ms) |
O(N) |
O(N) |
|
7 |
Reverse Integer |
Python3(32ms) |
O(1) |
O(1) |
|
8 |
String to Integer (atoi) |
Python3(40ms) |
O(1) |
O(1) |
|
9 |
Palindrome Number |
Python3(68ms) |
O(1) |
O(1) |
|
10 |
Regular Expression Matching |
Python3(48ms) |
O(N*M) |
O(N*M) |
|
11 |
Container With Most Water |
Python3(40ms) |
O(N) |
O(1) |
|
12 |
Integer to Roman |
Python3(44ms) |
O(N) |
O(1) |
|
13 |
Roman to Integer |
Python3(56ms) |
O(N) |
O(1) |
|
14 |
Longest Common Prefix |
Python3(32ms) |
O(N) |
O(1) |
|
15 |
3Sum |
Python3(400ms) |
O(N2) |
O(M) |
For Python solution, use count to reduce time to O(min(N, M2)) and space to O(M) |
16 |
3Sum Closest |
Python3(92ms) |
O(N2) |
O(1) |
|
17 |
Letter Combinations of a Phone Number |
Python3(36ms) |
O(4N) |
O(4N) |
|
18 |
4Sum |
Python3(64ms) |
O(N2) |
O(N2) |
|
19 |
Remove Nth Node From End of List |
Python3(32ms) |
O(N) |
O(1) |
|
20 |
Valid Parentheses |
Python3(36ms) |
O(N) |
O(N) |
|
21 |
Merge Two Sorted Lists |
Python3(40ms) |
O(N1+N2) |
O(1) |
|
22 |
Generate Parentheses |
Python3(36ms) |
O(N) |
O(?) |
|
23 |
Merge k Sorted Lists |
Python3(64ms) |
O(N*logk) |
O(1) |
Python solution use heap to compare the lists, so reduce time to O(N logK) but increase space to O(k) |
24 |
Swap Nodes in Pairs |
Python3(28ms) |
O(N) |
O(1) |
|
25 |
Reverse Nodes in k-Group |
Python3(48ms) |
O(N) |
O(1) |
|
26 |
Remove Duplicates from Sorted Array |
Python3(52ms) |
O(N) |
O(1) |
|
27 |
Remove Element |
Python3(28ms) |
O(N) |
O(1) |
|
28 |
Implement strStr() |
Python3(32ms) |
O(N+M) |
O(1) |
Use Knuth–Morris–Pratt Algorithm |
29 |
Divide Two Integers |
Python3(32ms) |
O(N) |
O(1) |
|
30 |
Substring with Concatenation of All Words |
Python3(56ms) |
O(N*M) |
O(M) |
|
31 |
Next Permutation |
Python3(36ms) |
O(N) |
O(1) |
|
32 |
Longest Valid Parentheses |
Python3(48ms) |
O(N) |
O(1) |
|
33 |
Search in Rotated Sorted Array |
Python3(28ms) |
O(N) |
O(1) |
|
34 |
Search for a Range |
Python3(32ms) |
O(LogN) |
O(1) |
|
35 |
Search Insert Position |
Python3(28ms) |
O(LogN) |
O(1) |
|
36 |
Valid Sudoku |
Python3(44ms) |
O(1) |
O(1) |
|
37 |
Sudoku Solver |
Python3(44ms) |
O(1) |
N(1) |
|
38 |
Count and Say |
Python3(32ms) |
O(N2) |
O(N) |
Python use an dictionary of answers |
39 |
Combination Sum |
Python3(52ms) |
O(N!) |
O(N) |
|
40 |
Combination Sum II |
Python3(48ms) |
O(N!) |
O(N) |
|
41 |
First Missing Positive |
Python3(36ms) |
O(N) |
O(1) |
|
42 |
Trapping Rain Water |
Python3(32ms) |
O(N) |
O(1) |
|
43 |
Multiply Strings |
Python3(84ms) |
O(N*M) |
O(N+M) |
|
44 |
Wildcard Matching |
Python3(60ms) |
O(N*M) |
O(1) |
Similar with Problem No. 10 |
45 |
Jump Game II |
Python3(40ms) |
O(N) |
O(1) |
Use Greedy Algorithm |
46 |
Permutations |
Python3(44ms) |
O(N!) |
(N) |
Get inspired by Heap's Algorithm |
47 |
Permutations II |
Python3(56ms) |
O(N!) |
(N) |
Get inspired by Heap's Algorithm |
48 |
Rotate Image |
Python3(32ms) |
O(N2) |
O(1) |
|
49 |
Group Anagrams |
Python3(108ms) |
O(N K log K) |
O(N K) |
Linear algorithm will slower and cost more memory |
50 |
Pow(x, n) |
Python3(32ms) |
O(LogN) |
O(1) |
|
Back to Table of Contents
# |
Title |
Solutions |
Time |
Space |
Comments |
51 |
N-Queens |
Python3(60ms) |
O(N!) |
O(N) |
|
52 |
N-Queens II |
Python3(44ms) |
O(N!) |
O(N) |
|
53 |
Maximum Subarray |
Python3(36ms) |
O(N) |
O(1) |
|
54 |
Spiral Matrix |
Python3(28ms) |
O(N) |
O(1) |
|
55 |
Jump Game |
Python3(32ms) |
O(N) |
O(1) |
Use Greedy Algorithm |
56 |
Merge Intervals |
Python3(40ms) |
O(NLogN) |
O(1) |
|
57 |
Insert Interval |
Python3(40ms) |
O(N) |
O(N) |
|
58 |
Length of Last Word |
Python3(32ms) |
O(N) |
O(1) |
|
59 |
Spiral Matrix II |
Python3(36ms) |
O(N2) |
O(N2) |
|
60 |
Permutation Sequence |
Python3(24ms) |
O(N) |
(N) |
Use Cantor Expansion (Introduction to Algorithms, MIT) |
61 |
Rotate List |
Python3(36ms) |
O(N) |
O(1) |
|
62 |
Unique Paths |
Python3(28ms) |
O(Min(M, N)) |
O(1) |
Use dynamic programing will cost O(M*N) time and O(Min(M, N)) space |
63 |
Unique Paths II |
Python3(32ms) |
O(M*N) |
O(Min(M, N)) |
|
64 |
Minimum Path Sum |
Python3(100ms) |
O(M*N) |
O(Min(M, N)) |
Update grid to not use new space |
65 |
Valid Number |
Python3(36ms) |
O(N) |
O(1) |
|
66 |
Plus One |
Python3(36ms) |
O(N) |
O(N) |
|
67 |
Add Binary |
Python3(40ms) |
O(N) |
O(N) |
|
68 |
Text Justification |
Python3(32ms) |
O(N) |
O(N) |
|
69 |
Sqrt(x) |
Python3(36ms) |
O(LogN) |
O(1) |
Use Newton–Raphson Method to computing square root |
70 |
Climbing Stairs |
Python3(28ms) |
O(N) |
O(1) |
|
71 |
Simplify Path |
Python3(32ms) |
O(N) |
O(N) |
|
72 |
Edit Distance |
Python3(128ms) |
O(N*M) |
O(Min(N,M)) |
|
73 |
Set Matrix Zeroes |
Python3(148ms) |
O(N*M) |
O(N+M) |
When use constant space, solution will slower |
74 |
Search a 2D Matrix |
Python3(76ms) |
O(Log(N+M)) |
O(1) |
|
75 |
Sort Colors |
Python3(32ms) |
O(N) |
O(1) |
|
Back to Table of Contents
# |
Title |
Solutions |
Time |
Space |
Comments |
222 |
Count Complete Tree Nodes |
Python3(80ms) |
O(log2N) |
O(1) |
|
Back to Table of Contents
# |
Title |
Solutions |
Time |
Space |
Comments |
410 |
Split Array Largest Sum |
Python3(40ms) |
O(N∗log(sum of array)) |
O(1) |
Binary Search |
Back to Table of Contents
# |
Title |
Solutions |
Time |
Space |
Comments |
482 |
License Key Formatting |
Python3(36ms) |
O(N) |
O(N) |
|
Back to Table of Contents
# |
Title |
Solutions |
Time |
Space |
Comments |
843 |
Guess the Word |
Python3(36ms) |
O(N2) |
O(N) |
|
Back to Table of Contents
# |
Title |
Solutions |
Time |
Space |
Comments |
1007 |
Minimum Domino Rotations For Equal Row |
Python3(1248ms) |
O(N) |
O(1) |
|
Back to Table of Contents
# |
Title |
Solutions |
Time |
Space |
Comments |
1057 |
Campus Bikes |
Python3(724ms) |
O(N*M) |
O(N*M) |
|
1096 |
Brace Expansion II |
Python3(48ms) |
O(N) |
? |
|
Back to Table of Contents
# |
Title |
Solutions |
Time |
Space |
Comments |
1197 |
Minimum Knight Moves |
Python3(36ms) |
O(N2) |
O(N2) |
|