NeetCode

?? Trees Cheat Sheet - BFS Breadth First Search (BFS) is a traversal algorithm that allows us to traverse nodes level-by-level, using a queue. ???????????????????????????? 1. Enqueue the starting node (the root node). 2. Dequeue and visit the node. 3. Enqueue the node’s children. 4. Repeat until the queue is empty. ?????? ?????????? 1. Binary Tree Level Order Traversal ?? https://lnkd.in/gWH7nMYH 2. Binary Tree Right Side View ?? https://lnkd.in/gfPTsqQc ???????? ?????? ?????????? Time: O(n) Space: O(n) These animations are taken from the Algorithms & Data Structures course from neetcode.io and edited to fit on LinkedIn. #dsa #leetcode #codinginterview

Arrays Cheat Sheet - Two Pointers There are many variations of the two pointers algorithm, but a common one involves initializing two pointers are the ends of an array. And then gradually shifting one of them until some condition has been met. The below animation shows how two pointers could be used to find the target sum within a sorted array. ???????????????????????????? 1. Initialize left and right pointers 2. Compute sum of left and right nums 3. If sum greater than target, shift right pointer 4. If sum less than target, shift left pointer 5. Continue until target sum found ?????? ?????????? 1. Palindrome String ?? https://lnkd.in/g4Ev6UAW 2. Target Sum in Sorted Array ?? https://lnkd.in/gF6mJj6C 3. Trapping Rain Water ?? https://lnkd.in/gFDydjqT ???????? ?????? ?????????? Time: O(n) Space: O(1)

Linked List Cheat Sheet - Cycle Detection To determine if a linked list contains a cycle, we can use the two pointer technique. One of the pointers will move twice as fast as the other. There are two possiblities: 1. The fast pointer reaches the end of the list (no cycle) 2. The two pointers reach the same position (cycle detected) ???????????????????????????? 1. Initialize slow and fast pointer at different positions. 2. Shift pointers while they are non null. 3. Shift slow pointer by one and fast pointer by two. 4. If pointers reach same position, cycle detected. ?????? ?????????? 1. Linked List Cycle ?? https://lnkd.in/gEN6PSBm 2. Find the Duplicate Integer ?? https://lnkd.in/gwKb7enz ???????? ?????? ?????????? Time: O(n) Space: O(1) These animations are taken from the Algorithms & Data Structures course from neetcode.io and edited to fit on LinkedIn. #dsa #leetcode #codinginterview

Tree Cheat Sheet - Tries Tries are a special tree data structure. I prefer calling them Prefix Trees, because they store strings together if they have the same prefix. Tries can be useful for auto-completion suggestions and other features. Each node in the tree represents a single character. This way if two words have the same prefix, we can save space on nodes. For example, "Apple" and "Ape" share the prefix "Ap". ?????? ?????????? 1. Implement a Prefix Tree https://lnkd.in/gi2NfNgj 2. Design Word Search Data Structure https://lnkd.in/gz4XP52K 3. Search for Word https://lnkd.in/gWy7sHnZ ???????? ?????? ?????????? Insertion: O(m), where m is the length of the word. Search: O(m) for both exact matches and prefix queries. Space: O(n * m), where n is the number of words and m is the average length of the words. This animation is from the Advanced Algorithms course on neetcode.io and has been edited to fit on linkedin. #dsa #leetcode #codinginterview

?? Tree Cheat Sheet - Segment Trees Segment Trees are an advanced data structure used for efficient range queries and updates. Structurally, they are similar to Binary Trees, but the value of each node represents a range rather than a single value. A segment tree is basically another way to represent an array. The below animation shows how a Segment Tree could be used to compute the sum of values from index = 2 through index = 4. ???????????????????????????? 1. Recursively find lower bound of range, e.g. 2 from [2, 4] 2. Recursively find upper bound of range, e.g. 4 from [2, 4] 3. Combine segments, which in this case means compute the sum. ?????? ?????????? 1. Range Sum Queries in an Array 2. Range Minimum/Maximum Queries 3. Range Updates with Lazy Propagation ???????? ?????? ?????????? Time: O(n) for building and O(log n) for both range queries and updates Space: O(n) This animation is from the Advanced Algorithms course on neetcode.io and has been edited to fit on linkedin. #dsa #leetcode #codinginterview

Graph Cheat Sheet - Union-Find Union-Find (Disjoint Set Union) is a very elegant data structure used in many graph algorithms. The below animation shows how it can be used to detect cycles within a graph. ???????????????????????????? 1. Initialize each element as its own parent. 2. Find the root parent of a given node. 3. Union two sets of nodes by connecting their root parents 4. (Optional) Use Path Compression and Union by Rank to optimize performance. ?????? ?????????? 1. Cycle Detection in a Graph https://lnkd.in/e4we3nyY 2. Kruskal’s Algorithm for Minimum Spanning Tree https://lnkd.in/eBKeGNGz 3. Count Connected Components in a Graph https://lnkd.in/eTX36jpC ???????? ?????? ?????????? Time: Near O(1) for both find and union operations due to path compression and union by rank. Space: O(n) where n is the number of elements. This animation is from the Advanced Algorithms course on neetcode.io and have been edited to fit on linkedin. #dsa #unionfind #codinginterview

Arrays Cheat Sheet - Sliding Window We can use the sliding window algorithm to find the longest subarray without duplicates. ???????????????????????????? 1. Initialize left and right pointers at index 0 2. Increment right pointer 3. If element is non-duplicate, assign left pointer to right 4. Update max length of subarray without duplicates 5. Repeat steps 2 through 4 ?????? ?????????? 1. Best Time to Buy & Sell Stock ?? https://lnkd.in/gTUpiJyg 2. Longest Substring Without Duplicates ?? https://lnkd.in/ghNE7hCj 3. Minimum Window Substring ?? https://lnkd.in/gsFR_C6w ???????? ?????? ?????????? Time: O(n) where n is the size of the input array. Space: O(1) in most cases. These animations are taken from the Algorithms & Data Structures course from neetcode.io and edited to fit on LinkedIn. #dsa #leetcode #codinginterview

Arrays Cheat Sheet - Binary Search Binary search can be applied to sorted data. We search for a target value by eliminating half of the search space at each step. ???????????????????????????? 1. Initialize left and right pointers. 2. Compute mid pointer as floor((left + right) / 2). 3. If target > nums[mid], search to right of mid. 4. If target < nums[mid], search to left of mid. 5. Repeat steps 2 through 4 until target is found, or search space is empty. ?????? ?????????? 1. Search Sorted Array ?? https://lnkd.in/g3-AcTnH 2. Search Rotated Sorted Array ?? https://lnkd.in/gZYjmEuR 3. Find Median of Two Sorted Arrays ?? https://lnkd.in/gsEXxV3Q ???????? ?????? ?????????? Time: O(logn) where n is the size of the input array. Space: O(1) These animations are taken from the Algorithms & Data Structures course from neetcode.io and edited to fit on LinkedIn. #dsa #leetcode #codinginterview

Arrays Cheat Sheet - Prefix Sums We compute the sum of every subarray that contains the first element. This simple preprocessing allows us to solve many array problems more efficiently. ???????????????????????????? 1. Initialize a pointer at index 0 2. Add the current element to the sum 3. Assign the sum to prefix sums array at pointer 4. Increment the pointer 5. Repeat ?????? ?????????? 1. Range Sum Queries 2. Find Equilibrium Index (left sum == right sum) 3. Product of Array not Including Self (prefix products) ???????? ?????? ?????????? Time: O(n) where n is the size of the input array. Space: O(n) These animations are taken from the Algorithms & Data Structures course from neetcode.io and edited to fit on LinkedIn. #dsa #leetcode #codinginterview

Graph Cheat Sheet - Breadth-First Search Breadth-first search is one of the core algorithms that come up in coding interviews, and many other areas of computer science. ???????????????????????????? 1. Start at source 2. Add neighbors to queue 3. Mark positions visited to avoid infinite loop 4. Continue until target is reached ?????? ?????????? 1. Shortest Path in an unweighted graph - https://lnkd.in/g_AykKqr 2. Kahn's algorithm for topological sort - https://lnkd.in/gM4iZkVa 3. Connected components - https://lnkd.in/gKhM7EgG ???????? ?????? ?????????? Time: O(n*m) where n and m are the dimensions of the grid. Space: O(n*m) These animations are taken from the Algorithms & Data Structures course from neetcode.io and edited to fit on LinkedIn. #dsa #leetcode #codinginterview