A complete repository containing data structure implementations and LeetCode solutions. This can be used as a handbook to reference and learn these implementations in depth and a guide to study for interviews. Each python file follows the pycodestyle style guide.
Please feel free to reference and star to support this repo, thank you!
LeetCode is an online algorithm judging platform for engineers and mathmatcians to practice their problem solving abilities. Practicing LeetCode is known to help with passing technical interviews and can greatly increase algorithmic skills. Each solution is paired with a test file and README to understand the solution and overall problem. See below for an updated list of the solved problems in this repo.
| No. | Title | Solution | Complexity | Difficulty |
|---|---|---|---|---|
| 0001 | Two Sum | Py | O(N) | Easy |
| 0003 | Longest Substring without Repeating Characters | Py | O(N) | Medium |
| 0004 | Median of two Sorted Arrays | Py | O(log(M+N)) | Hard |
| 0011 | Container with Most Water | Py | O(N) | Medium |
| 0014 | Longest Common Prefix | Py | O(Nlog(N)) | Easy |
| 0028 | Implement strStr() | Py | O(N) | Easy |
| 0049 | Group Anagrams | Py | (Nlog(N)) | Medium |
| 0051 | N-Queens | Py | O(N^2) | Hard |
| 0053 | Maximum Subarray | Py | O(N) | Easy |
| 0054 | Spiral Matrix | Py | O(M+N) | Medium |
| 0056 | Merge Intervals | Py | O(Nlog(N)) | Medium |
| 0058 | Length of Last Word | Py | O(N) | Easy |
| 0094 | Binary Tree Inorder Traversal | Py | O(N) | Easy |
| 0125 | Valid Palindrome | Py | O(N) | Easy |
| 0155 | Min Stack | Py | O(1) | Medium |
| 0198 | House Robber | Py | O(N) | Medium |
| 0207 | Course Schedule | Py | O(V+E) | Medium |
| 0217 | Contains Duplicate | Py | O(N) | Easy |
| 0240 | Search in a 2D Matrix II | Py | O(M+N) | Medium |
| 0257 | Binary Tree Paths | Py | O(N) | Easy |
Data Structures or DS are key to understanding the fundmentals of programming. They teach us how data is stored, retrieved, and updated. Each data structure implementation comes with a test file as well as a README to reinforce the learnings.
In this repository, the following data structures are implemented:
Python comes pack with various cool methods and operations that all time different amounts of time. Here is a list of all of the standard python method's and their respective time complexities. Refer to this to brush up on your knowledge of python's standard library.
| Operation | Example | Class | Notes |
|---|---|---|---|
| Index | l[i] | O(1) | |
| Store | l[i] = 0 | O(1) | |
| Length | len(l) | O(1) | |
| Append | l.append(5) | O(1) | mostly: ICS-46 covers details |
| Pop | l.pop() | O(1) | same as l.pop(-1), popping at end |
| Clear | l.clear() | O(1) | similar to l = [] |
| Slice | l[a:b] | O(b-a) | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N) |
| Extend | l.extend(...) | O(len(...)) | depends only on len of extension |
| Construction | list(...) | O(len(...)) | depends on length of ... iterable |
| check ==, != | l1 == l2 | O(N) | |
| Insert | l[a:b] = ... | O(N) | |
| Delete | del l[i] | O(N) | depends on i; O(N) in worst case |
| Containment | x in/not in l | O(N) | linearly searches list |
| Copy | l.copy() | O(N) | Same as l[:] which is O(N) |
| Remove | l.remove(...) | O(N) | |
| Pop | l.pop(i) | O(N) | O(N-i): l.pop(0):O(N) (see above) |
| Extreme value | min(l)/max(l) | O(N) | linearly searches list for value |
| Reverse | l.reverse() | O(N) | |
| Iteration | for v in l: | O(N) | Worst: no return/break in loop |
| Sort | l.sort() | O(N Log N) | key/reverse mostly doesn't change |
| Multiply | k*l | O(k N) | 5*l is O(N): len(l)*l is O(N**2) |
| Operation | Example | Class | Notes |
|---|---|---|---|
| Length | len(s) | O(1) | |
| Add | s.add(5) | O(1) | |
| Containment | x in/not in s | O(1) | compare to list/tuple - O(N) |
| Remove | s.remove(..) | O(1) | compare to list/tuple - O(N) |
| Discard | s.discard(..) | O(1) | |
| Pop | s.pop() | O(1) | popped value "randomly" selected |
| Clear | s.clear() | O(1) | similar to s = set() |
| Construction | set(...) | O(len(...)) | depends on length of ... iterable |
| check ==, != | s != t | O(len(s)) | same as len(t); False in O(1) if the lengths are different |
| <=/< | s <= t | O(len(s)) | issubset |
| >=/> | s >= t | O(len(t)) | issuperset s <= t == t >= s |
| Union | s | t | O(len(s)+len(t)) |
| Intersection | s & t | O(len(s)+len(t)) | |
| Difference | s - t | O(len(s)+len(t)) | |
| Symmetric Diff | s ^ t | O(len(s)+len(t)) | |
| Iteration | for v in s: | O(N) | Worst: no return/break in loop |
| Copy | s.copy() | O(N) |
| Operation | Example | Class | Notes |
|---|---|---|---|
| Index | d[k] | O(1) | |
| Store | d[k] = v | O(1) | |
| Length | len(d) | O(1) | |
| Delete | del d[k] | O(1) | |
| get/setdefault | d.get(k) | O(1) | |
| Pop | d.pop(k) | O(1) | |
| Pop item | d.popitem() | O(1) | popped item "randomly" selected |
| Clear | d.clear() | O(1) | similar to s = {} or = dict() |
| View | d.keys() | O(1) | same for d.values() |
| Construction | dict(...) | O(len(...)) | depends # (key,value) 2-tuples |
| Iteration | for k in d: | O(N) | all forms: keys, values, items, Worst: no return/break in loop |