Data structures, algorithms and their applications to Leetcode most well known problems with a walkthrough explanation.
| # | Title |
|---|---|
| 1 | Algorithms |
| 2 | Data Structures |
| 3 | Leetcode solutions |
| 4 | Interface design |
| Technique | Algorithm | Solution | Time complexity | Space complexity |
|---|---|---|---|---|
| Recursion | Binary Search | Javascript | O(log n) | recursively: O(log n) / iteratively: O (1) |
| Recursion | Tail factorial | Javascript | O(n) | normal recursion: O(n) / tail recursion: O (1) |
| Recursion | 2d array BFS | Javascript | O(n) | O(n) |
| Recursion | Graph BFS | Javascript | using adjacency list: O(v + e) / using adjacency matrix: O(v ^ 2) | O(v) |
| Recursion | 2d array DFS | Javascript | O(n) | O(n) |
| Recursion | Graph DFS | Javascript | using adjacency list: O(v + e) / using adjacency matrix: O(v ^ 2) | O(v) |
| Sorting | Bubble Sort | Javascript | O(n ^ 2) | O(1) |
| Sorting | Insertion Sort | Javascript | O(n ^ 2) | O(1) |
| Sorting | Selection Sort | Javascript | O(n ^ 2) | O(1) |
| Sorting | Merge Sort | Javascript | O(n log n) | O(n) |
| Sorting | Quick Sort | Javascript | O(n ^ 2) | O(n) |
| Name | Description | Applications | Solution |
|---|---|---|---|
| Binary tree | A tree that has at most 2 children for any node | Binary search trees, Heaps, etc. | Javascript |
| AVL tree | Self balancing BST | in memory sorts of sets, dictionaries, lookups in databases | Typescript |
| Graph | Non-linear data structure consisting of nodes and edges | Network communication, Data organization, flow control, etc. | Javascript |
| Array | Data structure in which elements are located sequentially in memory | Ordering elements, Store colleciton of data, etc. | Typescript |
| Hash table | O (1) run time data structure that holds key value pairs for efficient data storage | Dictionaries, Databases, etc | Typescript |
| Linked List | Linear data structure consiting of a list of connected nodes | Queues, Doubly Linked Lists, Dynamic Memory Allocation, etc. | Typescript |
| Doubly Linked list | Variation of Linked List that allows back and forth navigation | front and back navigation, browsers, thread scheduler | Typescript |
| Stack | Linear data structure that holds linear, ordered sequence of elements (LIFO) | Evaluating expressions consisting of operators, backtracking, memory management | Typescript |
| Queue | Linear data structure that holds linear, ordered sequence of elements (FIFO) | Resource scheduling, Semaphores, Mail Queues | Typescript |
| Heap | Tree like Data structure for quick access to min or max values | Priority queues, Prim's algorithm, Dijkstra's algorithm, etc. | Typescript |
| Trie | Tree data structure based on the prefix of a string | Search engines, Autcomplete, etc. | Typescript |
| # | Category | Title | Solution | Dificulty | Time complexity | Space complexity |
|---|---|---|---|---|---|---|
| 1 | Arrays | Two Sum | Javascript | Easy | O(n) | O(n) |
| 2 | Arrays | Container with most water | Javascript | Medium | O(n) | O(1) |
| 3 | Arrays | Trapping Rain Water | Javascript | Hard | O(n) | O(1) |
| 4 | Strings | Valid Palindrome | Javascript | Easy | O(n) | O(1) |
| 5 | Strings | Valid Palindrome II | Javascript | Easy | O(n) | O(1) |
| 6 | Strings | Backspace String Compare | Javascript | Easy | O(n) | O(1) |
| 7 | Strings | First Unique Character in a String | Javascript | Easy | O(n) | O(n) |
| 8 | Strings | Longest Substring Without Repeating Characters | Javascript | Medium | O(n) | O(n) |
| 9 | Linked Lists | Reverse Linked List | Javascript | Easy | O(n) | O(1) |
| 10 | Linked Lists | Reverse Linked List II | Javascript | Medium | O(n) | O(1) |
| 11 | Linked Lists | Flatten a Multilevel Doubly Linked List | Javascript | Medium | O(n) | O(1) |
| 12 | Linked Lists | Linked List Cycle II | Javascript | Medium | O(n) | O(1) |
| 13 | Stacks and Queues | Valid Parentheses | Javascript | Easy | O(n) | O(n) |
| 14 | Stacks and Queues | Minimum Remove to Make Valid Parentheses | Javascript | Medium | O(n) | O(n) |
| 15 | Recursion | Find First and Last Position of Element in Sorted Array | Javascript | Medium | O(log n) | O(1) |
| 16 | Recursion | Kth Largest Element in an Array | Javascript | Medium | O(n log n) | O(1) |
| 17 | Binary trees | Maximum Depth of Binary Tree | Javascript | Easy | O(n) | O(n) |
| 18 | Binary trees | Binary Tree Level Order Traversal | Javascript | Medium | O(n) | O(n) |
| 19 | Binary trees | Binary Tree Right Side View | Javascript | Medium | O(n) | O(n) |
| 20 | Binary trees | Count Complete Tree Nodes | Javascript | Medium | O(log n) | O(1) |
| 21 | Binary trees | Validate Binary Search Tree | Javascript | Medium | O(n) | O(n) |
| 22 | 2D arrays | Number of Islands | Javascript | Medium | O(n * m) | O(max (n, m)) |
| 23 | 2D arrays | Rotting Oranges | Javascript | Medium | O(n * m) | O(n * m) |
| 24 | 2D arrays | Walls and Gates | Javascript | Medium | O(n * m) | O(n * m) |
| 25 | 2D arrays | Transpose Matrix | Javascript | Easy | O(n * m) | O(n * m) |
| 26 | 2D arrays | Set Matrix Zeroes | Javascript | Medium | O(n * m) | O(1) |
| 27 | 2D arrays | Search a 2D Matrix | Javascript | Medium | O(n + log(m)) | O(1) |
| 28 | Graphs | Time Needed to Inform All Employees | Javascript | Medium | O(n) | O(n) |
| 29 | Graphs | Course Schedule | Javascript | Medium | O(v + e) | O(v + e) |
| 30 | Graphs | Network Delay Time | Javascript | Medium | O(e + log v) | O(v + e) |
| 31 | Dynamic Programming | Min Cost Climbing Stairs | Javascript | Easy | O(n) | O(1) |
| 32 | Dynamic Programming | Knight Probability in Chessboard | Javascript | Medium | O(k * n ^ 2) | O(k * n ^ 2) |
| 33 | Dynamic Programming | Best Time to Buy and Sell Stock | Javascript | Easy | O(n) | O(1) |
| 34 | Dynamic Programming | Coin Change | Javascript | Medium | O(n * amount) | O(amount) |
| 35 | Dynamic Programming | House Robber | Javascript | Medium | O(n) | O(1) |
| 36 | Dynamic Programming | 0-1 Knapsack Problem | Javascript | Medium | O(n * w) | O(n) |
| 37 | Dynamic Programming | Longest Common Subsequence | Javascript | Medium | O(n * m) | O(n * m) |
| 38 | Dynamic Programming | Longest Increasing Subsequence | Javascript | Medium | O(n log n) | O(n) |
| 39 | Dynamic Programming | Longest Palindromic Subsequence | Javascript | Medium | O(n ^ 2) | O(n ^ 2) |
| 40 | Dynamic Programming | Longest Palindromic Substring | Javascript | Medium | O(n ^ 2) | O(1) |
| 41 | Dynamic Programming | Maximum Subarray | Javascript | Medium | O(n) | O(1) |
| 42 | Dynamic Programming | Partition a set into two subsets such that the difference of subset sums is minimum | Javascript | Hard | O(n * m) | O(n * m) |
| 43 | Dynamic Programming | Minimum Path Sum | Javascript | Medium | O(n * m) | O(1) |
| 44 | Dynamic Programming | Palindromic Substrings | Javascript | Medium | O(n * 2) | O(1) |
| 45 | Dynamic Programming | Partition Equal Subset Sum | Javascript | Medium | O(n * m) | O(n * m) |
| 46 | Dynamic Programming | Subset Sum | Javascript | Medium | O(n * m) | O(n * m) |
| 47 | Backtracking | N-Queens | Javascript | Hard | O(n!) | O(n ^ 2) |
| 48 | Backtracking | Palindrome Partitioning | Javascript | Medium | O(n * 2 ^ n) | O(n) |
| 49 | Backtracking | Partition to K Equal Sum Subsets | Javascript | Medium | O(k * 2 ^ n) | O(n) |
| 50 | Backtracking | Sudoku Solver | Javascript | Hard | O(9! ^ 9) | O(9 ^ 2) |
| # | Category | Title | Solution |
|---|---|---|---|
| 1 | Queue | Implementing queues using stacks | Typescript |
| 2 | Naray tree / dfs traversal | Manager employee problem | Typescript |
| 3 | Naray tree / dfs and bfs traversal | Manager employee II problem | Typescript |
| 4 | Naray tree / dfs traversal | Monarchy problem | Typescript |
| 5 | Naray tree / dfs and bfs traversal | Monarchy II problem | Typescript |