Posts

To be or not to be? That is the Backtracking

Image
Backtracking is often introduced alongside the concepts of permutations and combinations. If you're familiar with Python's itertools , you might be wondering, "Why not just use those?" Well, fear not — backtracking has its own advantages. As the name suggests, think of backtracking like having regrets in life — if only you could go back and make a better choice! That’s exactly what this algorithm does: it explores one choice, checks if it leads to a valid solution, and if not, it backtracks and tries a different path. It’s a step beyond brute-force permutations because it allows pruning of unpromising paths early. The classic backtracking template involves maintaining an output (your current path of choices) and a position on a timeline (the index you're exploring). At each step, you make a decision — either to include an element or not — much like traversing a binary tree of "yes" and "no" decisions. Indeed "To be or not to be?" Th...
Post a Comment
Read more

Why the merge sort?

Image
If you're not a CS graduate like me and have been grinding endless LeetCode problems and studying DSA, you've probably found yourself wondering: Is there any real meaning to all this? That moment hit me when I was staring at the merge sort algorithm. I had a very valid question: Why use merge sort when its close cousin quicksort offers the same comforting time complexity of O(n log n)? That was until I met a different kind of beast: the Linked List . I like to describe a linked list as a prerequisite to trees—kind of like a one-child tree. And here's where merge sort truly shines: when you're dealing with linked lists instead of arrays. Merge sort’s divide-and-conquer philosophy involves splitting the structure (be it a list or linked list) into halves until there’s only one element left, and then merging them back together by comparing elements—essentially deciding “who's the parent of whom.” <photo credits: Lucas Films> Here’s a fun example of where mer...
Post a Comment
Read more