Reduce memory of graph traversal by marking spot as visited instead of using a set[Technique Tuesdays]
This will help you a lot when it comes to optimizing your code.
To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
Another day, another post dedicated to graphs huh,
There’s just something about this annoying Data Structure. For some reason, some of the hardest algorithms and questions you will have to solve involve Graphs.
This also means more information to break down graph problems. And more avenues for you to stand out in your interviews. And today, I’ve got one of my favorite optimization techniques available. Anytime you have to code up a graph traversal algorithm, this will be very helpful. And it’s super duper simple. No tricky coding required.
This trick is so effective that it will help you go from O(n) space complexity to O(1) complexity. Just by making a few easy changes. Don’t believe me? We can go from this-
To-
That.
Talk about a massive improvement. If you want a shot at this question, you can find it here, [Solution]Problem 37: Word Search[Amazon]. Without further ado, let’s jump right into it-
The technique- In graph traversal algorithms, you will have to have a visited set to keep track of all the nodes you have already visited. One clever workaround is to simply ‘mark’ the node we’re currently at with a unique value that will tell us whether we’ve already come here. For example, we change the values in the visited cell from a character to ‘.’ in the aforementioned word search problem. Pure Computer Science nerds are probably screeching and pulling their hair out reading this, but we’re all Giga Chads here. So go change away, my beautiful, optimization-obsessed reader.
Why this is so awesome- Adding a visited set takes O(n) extra space. This approach takes no extra space, since all changes are being made in place. This is also super simple to implement.
Something to consider- Be careful when choosing a value for the visited cells. If your nodes might have their values be strings, then you want something distinctive like -1 or ‘_’. Always ask your interviewer about the domain of your input before you start making changes.
How to get good at this- Go through all the Graph Traversal algorithms you have solved so far, and start implementing these changes. It’s just about building muscle memory with this technique.
Extra Cherry on top- In my post on the Bloom Filter for Systems Design, I covered why sets can become extremely expensive with very large datasets. This kind of approach can help you keep costs low when building solutions.
To implement this super awesome technique, you will first need to be able to have a baseline understanding of Graphs, Recursion, and Graph Traversal Algorithms. Lucky for you, I have covered these topics in depth, with in-depth tutorials, explanations and demo questions. Where can you access them? The newsletter has an amazing option, that lets you search through older posts. Take a look at the image below.
All you need to do is head to our archive section right here and put in whatever topic you’re interested in. Keep in mind, that the archive is accessible from our homepage and is available to everyone. So if you are struggling with any idea or concept, just head on over and read through the old posts. And if there is something you want me to cover, reach out to me by replying to this email/using one of the social media links below.
I created Technology Interviews Made Simple using new techniques discovered through tutoring multiple people into top tech firms. The newsletter is designed to help you succeed, saving you from hours wasted on the Leetcode grind. I have a 100% satisfaction policy, so you can try it out at no risk to you. You can read the FAQs and find out more here. Use the button below to get 50% off for upto a whole year.
This is a limited-time offer, that I’m running to celebrate my almost 50 questions completed. Take advantage of it by clicking the button above.
Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.
***Special Request***
This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.
There is a simple form in Substack that you can fill up for it. Here it is. Thank you.
https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform
To get your Substack URL, follow the following steps-
Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.
You will be redirected to your URL. Please put that in to the survey. Appreciate your help.
In the comments below, share what topic you want to focus on. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
I see you living the dream.
Go kill all and Stay Woke,
Devansh <3
To make sure you get the most out of Technique Tuesdays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75