LeetCode is the bane of many
wannabe software engineers, as these are the questions asked in
interviews for most tech companies. The truth is, you don’t need to
solve 1000+ LeetCode questions to ace your interviews. All you
need is a systematic approach, and you can solve any problem. Using this
approach, myself, along with many other engineers I know have landed jobs at FAANG
companies with less than 100 problems solved. Every LeetCode or interview question can be broken down into simple steps - no
matter how complicated it seems! Today, we’re going to go through those steps so
that you can tackle any problem you’re faced with, even if it seems impossible. I’ll
explain the exact steps you need to follow, how to figure out what data
structure/algorithm to use, and I’ll even solve a popular hard LeetCode question as
we go, showing you these steps in action. The first step is to simplify the problem. Most LeetCode questions have lots of fluff
that’s hiding what actually matters. The truth is, all LeetCode questions are
the same in nature: You’re given inputs, and you need to change them
into the expected outputs. After reading any question, you should be
able to repeat the problem to yourself, or out loud if it’s to an interviewer, in the
following structure: “The inputs are these”, “we do this to the inputs”, and
“we get this as the output”. If you’re struggling to understand
how the inputs become the outputs, manually walk through a test case - this often
makes it clear what exactly is happening. Also, if it’s a real interview, ask lots
of questions! You’re actually given bonus marks for asking clarifying questions,
so don’t be afraid to ask. In particular, make sure you catch the edge cases -
these are situations that might have a unique or unclear way of handling, and
interviewers expect you to catch these. --- Let’s put this step into action for
starting our LC problem, Word Ladder. - Simplify: The inputs are two strings,
beginWord and endWord. We change one letter at a time in the beginWord to
change it into a word in our wordList, until we reach our endWord.
Our output is an integer, representing how many words it took to get
from beginWord to endWord, unless this was impossible, in which case our output is 0.
- Test Case: For our test case, we have our starting word as hit, and our ending word as
cog. Let’s change one letter of our beginning word to get another word in the word list. Hit
becomes hot. Now let’s change it again - now hot becomes dot. As we keep doing this, you can
see we’re progressing through our wordList changing one letter at a time, and finally, we
get to the end word, cog, after 5 total words. - Questions: Now, here are
some clarifying questions we might ask an interviewer to get more insight.
- Is
endWord guaranteed to be in the word list? - Are the words case sensitive?
- Edge Cases: Lastly, these are some edge cases we should get clarification on.
- If
beginWord equals endWord, is the length 1, or do we return 0?
- If the word list is empty, do we return 0? Now that we know how what we’re solving,
let’s figure out how to solve it. LeetCode is just pattern recognition.
Most LeetCode problems can be solved using the same data structures
and algorithms. All you need to do is figure out which one you
should use for a given problem. Now, before you do this, you need to be
familiar with 2 concepts: Big O notation, and data structures & algorithms. I
have 3 great videos for these concepts, which I would check out
now if you’re not familiar. Step 1. If you’re a beginner, start out by
explaining the most straightforward solution. By this, I mean literally walk through the most
obvious answer, even if it’s not efficient. You don’t need to code it, but identify what the time
and space complexities would be. From doing this, you’ll often see places that can be simplified,
and a better solution may pop into your head. Step 2. Now, let’s find the optimal solution. We need to identify the data structure and
algorithm we should use for this problem. Firstly, check to see if the problem provides constraints
- often this can give away what you should use. - For example, if a problem has
a time complexity of O(log(n)), there is one specific algorithm that
accomplishes this: binary search. If there’s no obvious hints in the problem,
you’ll need to use the context of the problem to identify the pattern. Luckily, the sponsor of
today’s video, AlgoMonster, has a completely FREE flowchart you can use to identify what pattern
to use. You can use this while solving LeetCode problems to learn what to look for, and as you
get more familiar, you’ll have the entire thing committed to memory. AlgoMonster also offers
content for learning how to master every single pattern, which you can get for $7/month right now,
which will be more than covered in just an hour or two of work as a full-time software engineer!
Try AlgoMonster’s free flowchart today using the link in my description, and use code BAGEL for an
extra 10% off their full interview prep content. Let’s apply this to our LeetCode problem,
starting with the straightforward solution, and then finding the optimal solution. - Brute Force Approach:
- Starting from
beginWord, generate all possible single-letter transformations, and
recursively continue this for each new word, until we reach endWord.
- I’m not even going to type this approach out because it’s clearly
not efficient. How inefficient is it? Well, for starters, we know that each word can be
transformed 25 different ways, for each letter of the alphabet except itself. This means
each word has 25*L transformations. Then, we also know we have to do this for each word
in the
wordList, which we can represent as N. Therefore, our time and space complexities
for the straightforward approach are O(25L)^N. - Identify the Pattern:
- Now let’s move on to the optimal approach, and start by finding the right algorithm to use.
- Let’s use the flowchart. Firstly, is it a graph problem? Well, if a problem
can be represented as nodes and connections, or has some element of pathfinding, it is
likely a graph. So we can say YES to this. - Now, is it a tree? According to this
flowchart, if the problem mentions roots or leaves it’s a tree - otherwise, it’s
probably not. So we can say NO to this. - Now, is the problem related to directed
acyclic graphs? According to the flowchart, a directed graph has a clear sense of direction
implied. Well for our problem, do letters have any direction between them? No, they don’t.
We could easily change an A into a B, and vice versa. Therefore, we can say NO to this as well.
- Is the problem related to shortest paths? This one is pretty clear with our question -
we are looking for the shortest path to get from
beginWord to endWord. So, YES.
- Lastly, is the graph weighted? According to the flowchart, if the edges between words
have the same values, it is unweighted. In our case, every transformation of
a letter counts as 1 transformation, so it is unweighted. Now we can clearly
see what algorithm we should use: BFS. At this point, you’ve identified the
pattern you need to use. The hard part is done. All you need to do now is put this
pattern into action for this question. This is where practicing the various patterns
becomes useful; over time you’ll realize that 90% of the question is just the same
code you’ve used for other similar questions. This is best illustrated with
our problem, Word Ladder. We know now that we are using BFS
to solve this problem. If you’re not familiar with BFS, I’ve put the default
implementation on screen for you to see. For our use case, we only need to make
slight tweaks to this algorithm. Firstly, our starting node is just our starting word.
Also, on top of keeping track of each word, we also need to keep track of how many
transformations we’ve already made. As we go through each word in our queue, we
want to attempt to transform it. To do this, we need to go through each letter in our current
word, and replacing it with every possible letter. Now, this will mean we are
trying tons of new words, but we can actually rule out
almost all of them right away. We only care about a transformed
word if it fulfils three conditions: 1. If it is a different word than we
currently have, AKA not the exact same word 2. If it exists in our word list
- If we have not yet seen it If all of these are true, then we need to check -
is this new word our end word? If it is, we just add 1 to our current number of transformations
and boom, that’s our solution. If it’s not our end word, it must be a different word in our
word list, so we now want to add this word to our queue to go through next, and increase our
level by 1. Don’t forget to also add it to our visited set so we don’t try it again if another
word can be transformed into this one again. Now it’s time to code! at this point, you
should be done most of the hard work - just translate your implementation plan
to code and you’re good to go. If you forget some syntax, don’t
worry! In a real interview, interviewers are usually good about letting
you look at documentation or giving you some help. It’s getting the approach
that matters, not memorizing syntax. For our problem, I’ve actually mostly
done the coding as I’ve explained my implementation - which is great! Now we can run
it, and see that everything runs as expected. --- Optimally, after you’re done, your
code runs perfectly. But if not, don’t fret! Let’s take some time to debug next. “My code ran perfectly and every test
passed!” - said no programmer ever There are two types of errors that can
occur after you try to run your code. If your code doesn’t even
run - it’s a syntax error, which is easily fixable, just read
the error log and make the change. If your code runs, but tests
fail - it’s an implementation error, which requires a bit more digging. - Firstly, how many tests are
failing? if it’s only one or two, they’re likely edge cases you forgot about -
just make the fix to account for this edge case - If multiple tests are failing, then you’ve
made a mistake with your implementation - To fix this, the first thing to do is
manually walk the test case through your code. run through your code line by line, and walk
through what it’s actually doing to the input. Most of the time, you’ll catch the mistake here.
- If you still haven’t caught it, you need to figure out where something is going wrong.
Try adding print or logging statements to different parts of your code and seeing what
the inputs/outputs are at that point - this can show you what exactly is wrong,
and now all you need to do it figure out why it’s not what you’re expecting
- Debugging is probably the hardest part of solving any coding question - finding the
approach is easy once you’ve practiced enough, but inevitably, little errors always pop
up. the key is to practice lots - you’ll start to become familiar with
common mistakes that can be made That’s it! Press submit if you’re on
LeetCode, or run your code with your interviewer, and you’re done! If you
follow this step-by-step approach, combined with getting familiar with
data structures and algorithms, you will be able to solve any LeetCode
question and any interview question. Thanks so much for watching this video! If you
liked this, and want to see more content like it, make sure to hit the subscribe button and hit
the notification bell to stay up to date on the latest uploads. If you want to learn
more about data structures and algorithms, go check out these videos. I’ll
see you all in the next video!