Imagine you’re walking along a path that has treasure chests and traps. Some chests have gold coins, and some traps take away coins. You want to find the part of the path where you can get the most coins. The key idea: It is a dynamic programming algorithm for finding the maximum contiguous sum subarray in a given array. It is a simple and efficient algorithm that works by maintaining two variables:...
Preface Facing the Dynamic Programming Challenge Like many others, I initially found Dynamic Programming (DP) on LeetCode daunting and perplexing. However, this challenging journey led to profound insights. My initial misconception was that DP was all about complexity, but I learned it’s fundamentally about simplifying complex problems into manageable segments. Here’s my journey into understanding DP and why it’s a crucial tool in a programmer’s toolkit. Unraveling Dynamic Programming The Essence of DP...
Overview Recursion is a way of solving a problem by breaking it down into smaller problems of the same type. The smaller problems are then solved recursively, until a base case is reached. The base case is a simple problem that can be solved without recursion. Imagine you have a big box of toy blocks, and each block represents a problem you need to solve. Some blocks are big (complex problems), and some are tiny (simple problems)....
Overview The union-find algorithm is a data structure and algorithm that maintains a collection of disjoint sets. A disjoint set is a set of elements that are not connected to each other. The union-find algorithm can be used to perform the following operations: Find: Find the set that an element belongs to. Union: Merge two sets together. The union-find algorithm is often used to solve problems that involve graph connectivity. For example, the union-find algorithm can be used to determine whether two nodes in a graph are connected, or to find all of the connected components in a graph....
Overview It is not easy to summarize the pattern of Two Pointers, but most likely it is used for list and linked list and the required time complexity is O(N) - the underlying pattern allows us to use Two Pointers to go through the list once to get the results. Common usage: Linear Structure: Typically applied to a sorted array or linked list. Two pointers might move in the same direction or in opposite directions....
Overview The Divide-n-Conquer strategy often employs recursion, as it relies on applying the same method to reduce the problem size by half and subsequently combining the outcomes for the ultimate solution. I view Divide-n-Conquer in a light similar to MapReduce, particularly when the task involves transformation. MapReduce breaks down a large problem into more manageable, independent sub-problems. Since each of these sub-problems operates autonomously, we can address them sequentially and still integrate their solutions....
Overview In one word, binary search is to search for a target in a sorted array. The idea is to shrink the search space to empty. It must be sorted because we can be sure how to shrink the search space and we normally reduce the search space by half so the time complexity is O(logN) where N is the size of entire search space. One common problem to understand Binary Search is how to identify the boundary of the search space....