Absolute Beginner's Guide to Algorithms

Kirupa Chinnathambi has spent most of his life teaching others to love web development as much as he does. He founded KIRUPA, one of the Web's most popular free web development education resources, serving 210,000+ registered members. Now a product manager at Google, he has authored several books, including Learning React (2017). He holds a B.S. in computer science from MIT.

• Part I: Data Structures  Chapter 1. Introduction to Data Structures .................................................................. 1Right Tool for the Right Job .................................................................................... 2Back to Data Structures ........................................................................................... 5Conclusion ................................................................................................................. 6  Chapter 2. Big-O Notation and Complexity Analysis ................................................... 7It's Example Time ...................................................................................................... 8It's Big-O Notation Time! .......................................................................................11Conclusion ...............................................................................................................15  Chapter 3. Arrays ....................................................................................................... 17What Is an Array? ....................................................................................................18Array Implementation / Use Cases .......................................................................24Arrays and Memory ................................................................................................26Performance Considerations .................................................................................30Conclusion ...............................................................................................................32  Chapter 4. Linked Lists ............................................................................................... 35Meet the Linked List ...............................................................................................36Linked List: Time and Space Complexity .............................................................40Linked List Variations ..............................................................................................41Implementation .......................................................................................................44Conclusion ...............................................................................................................52  Chapter 5. Stacks ........................................................................................................ 53Meet the Stack ........................................................................................................54A JavaScript Implementation ................................................................................56Stacks: Time and Space Complexity ....................................................................58Conclusion ...............................................................................................................59  Chapter 6. Queues ..................................................................................................... 61Meet the Queue .....................................................................................................62A JavaScript Implementation ................................................................................64Queues: Time and Space Complexity ..................................................................66Conclusion ...............................................................................................................67  Chapter 7. Trees ......................................................................................................... 69Trees 101 .................................................................................................................70Height and Depth ...................................................................................................75Conclusion ...............................................................................................................77  Chapter 8. Binary Trees .............................................................................................. 79Meet the Binary Tree ..............................................................................................80A Simple Binary Tree Implementation ..................................................................86Conclusion ...............................................................................................................89  Chapter 9. Binary Search Trees ................................................................................... 91It's Just a Data Structure ........................................................................................93Implementing a Binary Search Tree ....................................................................103Performance and Memory Characteristics .........................................................110Conclusion .............................................................................................................112  Chapter 10. Heaps ...................................................................................................... 113Meet the Heap ......................................................................................................114Heap Implementation ..........................................................................................126Performance Characteristics ................................................................................132Conclusion .............................................................................................................134  Chapter 11. Hashtable (aka Hashmap or Dictionary) .................................................. 137A Very Efficient Robot ..........................................................................................138From Robots to Hashing Functions ....................................................................142From Hashing Functions to Hashtables .............................................................145JavaScript Implementation/Usage ......................................................................148Dealing with Collisions .........................................................................................150Performance and Memory ...................................................................................151Conclusion .............................................................................................................153  Chapter 12. Trie (aka Prefix Tree) ............................................................................... 155What Is a Trie? ......................................................................................................156Diving Deeper into Tries ......................................................................................167Many More Examples Abound! ..........................................................................172Implementation Time ...........................................................................................173Performance ..........................................................................................................179Conclusion .............................................................................................................181  Chapter 13. Graphs .................................................................................................... 183What Is a Graph? ..................................................................................................184Graph Implementation .........................................................................................190Conclusion .............................................................................................................196  Part II: Algorithms  Chapter 14. Introduction to Recursion ....................................................................... 199Our Giant Cookie Problem ..................................................................................200Recursion in Programming ..................................................................................202Conclusion .............................................................................................................206  Chapter 15. Fibonacci and Going Beyond Recursion ................................................. 207Recursively Solving the Fibonacci Sequence ....................................................209Recursion with Memoization ...............................................................................213Taking an Iteration-Based Approach ..................................................................215Going Deeper on the Speed ..............................................................................217Conclusion .............................................................................................................218  Chapter 16. Towers of Hanoi ...................................................................................... 221How Towers of Hanoi Is Played ..........................................................................222The Single Disk Case ...........................................................................................223It's Two Disk Time .................................................................................................224Three Disks ............................................................................................................225The Algorithm .......................................................................................................228The Code Solution ...............................................................................................229Check Out the Recursiveness! ............................................................................231It's Math Time ........................................................................................................232Conclusion .............................................................................................................234  Chapter 17. Search Algorithms and Linear Search ..................................................... 235Linear Search .........................................................................................................236Conclusion .............................................................................................................241  Chapter 18. Faster Searching with Binary Search ....................................................... 243Binary Search in Action ........................................................................................243The JavaScript Implementation ..........................................................................250Runtime Performance ...........................................................................................254Conclusion .............................................................................................................257  Chapter 19. Binary Tree Traversal ............................................................................... 259Breadth-First Traversal ..........................................................................................260Depth-First Traversal ............................................................................................265Implementing Our Traversal Approaches ..........................................................270Performance of Our Traversal Approaches ........................................................278Conclusion .............................................................................................................279  Chapter 20. Depth-First Search (DFS) and Breadth-First Search (BFS) ....................... 281A Tale of Two Exploration Approaches ..............................................................282It's Example Time ..................................................................................................285When to Use DFS? When to Use BFS? ..............................................................298A JavaScript Implementation ..............................................................................300Performance Details .............................................................................................307Conclusion .............................................................................................................308  Chapter 21. Quicksort ................................................................................................ 309A Look at How Quicksort Works .........................................................................310Another Simple Look ...........................................................................................314It's Implementation Time .....................................................................................319Performance Characteristics ................................................................................322Conclusion .............................................................................................................323  Chapter 22. Bubblesort .............................................................................................. 325How Bubblesort Works ........................................................................................326Walkthrough ..........................................................................................................329The Code ...............................................................................................................333Conclusion .............................................................................................................333  Chapter 23. Insertion Sort .......................................................................................... 335How Insertion Sort Works ....................................................................................336One More Example ..............................................................................................347Algorithm Overview and Implementation .........................................................349Performance Analysis ...........................................................................................351Conclusion .............................................................................................................353  Chapter 24. Selection Sort ......................................................................................... 355Selection Sort Walkthrough .................................................................................356Algorithm Deep Dive ...........................................................................................364The JavaScript Implementation ..........................................................................366Conclusion .............................................................................................................369  Chapter 25. Mergesort ............................................................................................... 371How Mergesort Works .........................................................................................372Mergesort: The Algorithm Details ......................................................................379Looking at the Code ............................................................................................380Conclusion .............................................................................................................381  Conclusion .................................................................................................................383  Index ............................................................................................................................ 387