«
»
▶
Lecture Copilot
Lectures
Ask
Exam prep
Help
Sign in
← Data Structures & Algorithms
L1
DSA Interview Prep
Ask the lectures
Every answer cites the moment it comes from. Click a citation to jump there.
Your question
Ask
00:00
Arrays and Strings Basics
05:11
Sets and Time Complexity
10:00
Hash Maps and Two Sum
18:33
Two-Pointers Technique
25:18
Sliding Window Pattern
37:22
Binary Search Fundamentals
49:03
Breadth-First Search
58:01
Depth-First Search
1:05:11
Backtracking
1:10:25
Priority Queues and Heaps
Transcript
00:00
Welcome to this comprehensive course on data structures and algorithms. Whether you're
00:06
preparing for coding interviews, or looking to strengthen your foundational programming skills,
00:13
this is a great course for you. Sheldon Chai developed this course. Sheldon will break down
00:19
the most essential data structures, like arrays, strings, sets, hash maps, and heaps. And he'll
00:25
show you exactly how and when to use them. You also master core algorithmic patterns,
00:30
such as two pointers, sliding windows, binary search, breadth first search, depth first search,
00:37
and backtracking, all explained with clear examples and real interview problems.
00:43
This course will help you build your intuition for efficiency and help you recognize which
00:48
patterns to apply and how to avoid brute force solutions. And each concept is taught step by
00:55
step with practical code walkthroughs and tips for common pitfalls. Let's start with the absolute
01:02
foundation. Arrays. Arrays are the default data structure for basically everything. Whether it's
01:10
list of numbers, characters, coordinates, or even object, if it's linear and ordered, it's probably
01:17
going to be stored as an array. Now here's the important part. Arrays give you constant time
01:23
access by index. So if I say ARR at index 4, we can go straight there. That's O of one time.
01:34
And the reason this is possible is because arrays are stored in contiguous memory.
01:38
It's like having a row of houses all next to each other. You know exactly how far to walk
01:44
to get to house number 5. That's what makes arrays fast for reading and indexing.
01:50
Where arrays start to break down is when you want to insert elements or delete elements in the middle.
01:57
So let's say we have 1, 2, 3, 4, 5, and we want to insert a 0 at the beginning.
02:04
What happens?
02:05
Well, you have to shift everything one position to the right to make room for it.
02:11
That is an O of N operation.
02:13
And the same goes for deleting something in the middle.
02:16
We have to shift everything left to fill the gap.
02:19
So the trade-off is pretty simple with arrays.
02:22
If you accessing by index super fast Appending at the end also usually fast However if it inserting or deleting from the middle or front that is when it gets expensive So how do you use arrays in interviews
02:39
Honestly, you will use them constantly. In particular, in problems where you need to
02:44
traverse a structure in order, access specific indices, compare elements from both ends,
02:51
or even for doing tricks like sliding windows or prefix sums.
02:56
A lot of people think of arrays as basics they don't need to spend much time on,
03:01
but almost every single clever interview problem comes down to how well you can leverage the array structure
03:06
to avoid unnecessary work or build into other data structures.
03:12
Strings are just arrays of characters, but with a few catches.
03:18
First, in most languages, strings are immutable.
03:21
That means if you change a string, even slightly, you're not really modifying the original.
03:28
You're creating an entirely new one under the hood.
03:31
This has big implications for code efficiency.
03:35
Let's say you're solving a problem where you're building a result string for multiple steps.
03:40
A common beginner mistake is doing something like this.
03:44
It looks clean, but under the hood, that's creating a new string on every iteration.
03:51
Concatenating strings in a loop like this can lead to an O of N squared time complexity.
03:57
Instead, you should be building a list of characters and joining them at the end.
04:02
What you want is something like this.
04:05
That gets you back to O of N.
04:08
Aside from this, strings work largely very similarly to arrays, and you can almost think of them in the same way.
04:16
Strings also show up a ton, especially in interview problems.
04:20
You'll see tons of questions like, find the longest substring without repeating characters,
04:26
check if two strings are anagrams, or return all the substrings that match a pattern.
04:32
Here's the thing, most of these are actually hidden as sliding window problems,
04:37
a pattern we're going to get to later in the video, or another pattern called two pointer.
04:42
We'll actually cover both of these patterns in detail, but the key insight for now is,
04:47
string problems are almost never about brute force character checking.
04:50
They about smart windowing fast lookups and efficient traversal Sets are one of the simplest data structures and one of the most useful for time efficiency A set is just a collection of unique values
05:05
No duplicates, no particular order, just a group of things where each one only appears once.
05:11
Let's say you're given a list of numbers, and you want to quickly check whether a certain number is in it.
05:16
If you store that list as a set instead, you can check for existence in constant time on average.
05:24
In Python, for example, you can write this.
05:28
This check, once you convert it to a set, actually runs in O of one time, which is much faster than looping through the entire list.
05:38
So when do you want to use sets?
05:40
You should always use a set instead of a list when you care about uniqueness, like checking for duplicates.
05:48
Existence, where you're saying, have I seen this before?
05:51
Fast membership checks, saying, is this value in the current group?
05:57
For example, in a problem where you're scanning in a array to find the first repeated element,
06:01
using a set is usually the cleanest and fastest solution.
06:04
Sets also come up in problems where you're maintaining a sliding window.
06:08
And you want to make sure that all elements in the window are unique.
06:12
In that case, the set becomes a quick way to track what's currently in play and what needs to be removed.
06:18
But we'll get to that a bit later.
06:20
So just to sum it up, sets are not for storing key value pairs, which is a mistake people often make.
06:26
They're for tracking whether something exists.
06:29
They do it quickly and cleanly, and you'll use them in place of lists a lot more than you think.
06:35
This might sound obvious, but it's worth saying.
06:39
You need to be extremely comfortable with basic loops and control flow.
06:44
Almost all interview problems boil down to three things.
06:48
a loop, some condition, and a few variables being updated. And that's it. Here are the basics you
06:57
should know like the back of your hand. Now, these might sound basic, but it's where a ton of people
07:03
stumble. They forget to update the loop pointer correctly, or they don't think through what the
07:08
loop they're making should be doing. One of the best habits you can build early is walking through
07:13
your code with an actual example input. Mentally run it. Where do the pointers move? What changes
07:20
on each iteration This one habit will save you dozens of bugs especially once you start working with more complicated data structures and algorithms You absolutely need to know these basics It time to talk about efficiency Big O notation is how we measure how a program performance scales with input size
07:40
Now, I'll be honest, you don't need to memorize 20 different Big O classes,
07:45
and that's a misconception that puts people off of learning this concept.
07:49
You really just need to learn the few basic ones, and from then, it will just be intuition to you.
07:54
You should be able to look at a nested loop and think, oh, that's O of n squared, that's probably too slow.
08:00
Or see a binary search and know instantly, O of log n, that's fast.
08:06
So let's go through the most common ones you'll see.
08:10
The fastest one is O of 1, constant time.
08:14
In this case, it doesn't matter how big the input is, the time complexity never changes.
08:20
Some good examples are accessing a specific index in an array, or checking if x exists in a set.
08:27
The next fastest is O of log n, which is logarithmic time.
08:33
This is where you divide the problem in half each time.
08:36
Think of binary search, which we'll get to in a bit.
08:41
Next is O of n, linear time.
08:44
In this case, you're going through each item once.
08:48
This is probably the most common time complexity and is often associated with loops and traversing through lists.
08:55
Next, we have O of n log n.
08:58
This is almost always related to sorting, and that includes the default sort methods built into each programming language.
09:06
The last one of importance is O of n squared.
09:10
This is almost always associated with nested loops, so a for loop within a for loop.
09:17
Often, this is when you're doing brute force comparisons, and just as a hint, this is usually too slow for large inputs and will not be accepted as a viable solution for interview problems.
09:28
Now, here's the basic rule of thumb.
09:31
For inputs up to 10 to the power of 5, you probably need O of n log n or better.
09:38
For inputs up to 10 to the power of 4, you can maybe get away with O of n squared.
09:43
And anything higher than that, you absolutely need to optimize.
09:47
That about covers the introductory concepts you need to know before moving on and learning
09:53
these patterns. Now, if you feel comfortable, let's get started with learning the patterns
09:58
and getting ready to ace these interviews.
10:00
Hash maps are the first data structure we'll be covering, and they're arguably the most useful pattern you'll learn in this entire video.
10:08
At the most basic level, a hash map is a way to store data using a key to find a value.
10:15
It's a key value pair system. Think of how arrays work, but instead you use custom indices instead of the default numbers.
10:24
Now it's more complex than that, but that's a good way to start thinking about them.
10:29
What makes HashMap so powerful is how it does this in constant time.
10:34
O of 1 on average for both lookup and insertion.
10:38
Now, how does this actually work?
10:41
Imagine you have a huge row of mailboxes.
10:45
Each mailbox has a unique number.
10:48
And instead of looking through every mailbox for someone's letter,
10:51
you can just run their name through a formula known as a hash function,
10:55
and it tells you exactly which mailbox to open.
10:59
So if I gave you a key, like the string banana, the hash function will take banana and spit out a number, like 243.
11:09
That number points to a slot in memory, and that's where your value is stored.
11:15
You don't need to scan all keys. You don't need to sort anything.
11:20
You just ask, where does this key go? And the hash function gives you an immediate answer.
11:26
And this is why hash maps are so fast and so powerful.
11:29
They don't depend on the size of the data.
11:32
Whether you have 10 elements or a million, getting or setting a value takes the same amount of time.
11:39
Now, in practice, two keys might sometimes get the same hash.
11:44
This is called a collision.
11:46
For example, maybe both banana and peach hash to 243.
11:52
Fortunately, we don't have to worry about that.
11:55
Most languages have built-in hash map implementations that handle these collisions for us.
12:00
I'm just mentioning it here so that you understand a bit more about how hashing actually works.
12:05
And if you're interested, I recommend spending some free time and really digging into it because it's quite fascinating.
12:11
Now, there's one really big rules about keys for hash maps.
12:15
They must be what's called hashable.
12:18
What that means depends on the specific language.
12:21
but in general numbers strings and tuples are all hashable whereas lists and dictionaries which is just another name for hash maps are not hashable So if you try to use a list or another hash map slash dictionary as a key it throw
12:38
an error, because their contents can change, and hash maps need keys that stay the same.
12:45
This comes up more often than you'd think.
12:48
For example, if you're grouping elements by their structure, like sorting strings and
12:52
using them as keys, you'll need to convert them into a format that's hashable first.
12:58
So why are hash maps so common in interviews? Because they're your go-to structure when brute
13:04
force is too slow. Let's say you need to find a value that already exists. Without a hash map,
13:12
you're looping through everything you've seen so far, and that's O of N. But with a hash map,
13:17
you just need to check once, O of 1. In a lot of interview problems, the real trick isn't some
13:25
clever algorithm. It's just storing information in a smarter way, and a hash map gives you that
13:30
for free. Here's the mindset shift you need to make. When you solve problems with brute force,
13:37
you're asking the same questions over and over. When you solve problems with a hash map,
13:43
You're remembering the answers as you go.
13:46
It's a small shift, but it saves you tons of time and unlocks O of N solutions where others get stuck at O of N squared.
13:55
Now let's take a second to look at how hash maps actually look in code.
14:00
The syntax might vary by language, but the pattern stays the same.
14:05
You're essentially doing three things.
14:07
First, you're storing something.
14:10
Then you're looking something up.
14:12
and optionally you might update or initialize more values as you go.
14:17
Here's a basic sketch of the code structure you'll use again and again.
14:24
This structure is often referred to as a frequency map and it's one of the most common patterns
14:29
you'll see. As you can see we're basically going through all of the items in some data list and if
14:36
an item doesn't already exist in our map we're setting its count to one and if it does exist
14:42
we're updating its count by plus one.
14:45
There are language specific helpers
14:47
that help clean up this code,
14:49
such as default dict in Python,
14:51
or map dot get or default in Java.
14:54
But the underlying logic is always the same You storing something under a key and either retrieving it or updating it later Also HashMaps are often used while you loop not just after
15:08
So you're building and using the map in real time, which is what lets you write a one-pass
15:13
solution instead of having to loop twice.
15:16
We'll come back to this idea when we look at real problems in a moment or two.
15:20
For now, just keep this shape in your head.
15:23
a map, use it while looping, and it gives you fast lookup and storage. Hash maps are the most
15:30
flexible structure in your toolbox. You'll use them in string problems, array problems, recursion,
15:37
dynamic programming, graph traversal, literally everything. If you're ever stuck and don't know
15:42
how to avoid brute force, just ask, what could I store to avoid doing extra work later? And if you
15:50
If you can answer that, you're already halfway to a half-map solution.
15:54
Alright, let's solve one of the most iconic interview problems, 2sum.
16:00
The setup is simple.
16:02
You are given an array of integers and a target number.
16:06
You need to return the indices of two numbers that add up to the target.
16:11
This problem is deceptively simple, and a perfect example of how using the right data
16:15
structure makes all the difference.
16:19
So we start by identifying the pattern.
16:22
For this one, I'm going to choose the HashMap pattern.
16:26
How did I know that?
16:27
Well, because we know that we want to track which numbers we've seen before and be able
16:32
to look them up instantly.
16:35
HashMaps are often great for questions like this where you need to ask, have I seen the
16:39
corresponding value that completes this pair?
16:43
In this case, it's the number that adds to the current number we're looking at to create
16:48
the target. Now, let's see how the code works. We start by creating an empty hash map called
16:55
num2index. This is going to store each number we see along with its index so we can quickly
17:02
look it up later. Then, we loop through the array using enumerate, which gives us both the index i
17:09
and the current number num. At each step, we calculate the complement. That is the number
17:17
we'd need to pair with the num to hit the target. And then we check our hash map. Have we already
17:24
seen this complement If we have it means the current number and that earlier complement add up to the target so we should return their indices
17:35
If we haven't seen it yet, we store the current number in the map with its index.
17:40
That way, it'll be available for future numbers to match against.
17:45
So doing this, we're only looping through the array once, and in each step we're doing constant-time lookups and inserts, making the whole thing super efficient.
17:54
efficient. Now, analyzing the time and space complexity of this is quite easy once we just
18:00
trace through what we're doing. So let's start with the time complexity. Well, we know that in
18:06
a worst case scenario, we might have to go through each element in nums exactly once.
18:12
So that is going to be O of n time complexity, because we might have to see all n elements.
18:18
Now, what about space complexity?
18:21
Well, let's look at what we're doing.
18:23
We're creating a new hash map, and again, in worst case scenario, we might need to add
18:29
every single number with its index to that hash map.
18:33
So the hash map could be n elements long, meaning that our space complexity is also O
18:39
of n.
18:40
And that's it.
18:41
Just like that, we solved a super popular interview problem using skills you didn't
18:46
even know 10 minutes ago.
18:48
Now, let's talk about another very common interview pattern, two-pointers.
18:54
This is one of the most foundational patterns for solving problems that involve linear structures,
19:00
like arrays, strings, and even sometimes linked lists.
19:06
You'll see it constantly in coding interviews, and the key is recognizing when to use it
19:11
and how to adapt it to the shape of the problem.
19:14
At a high level, two-pointers is exactly what it sounds like.
19:17
You use two indices, or pointers, to move through a structure, usually in a way that helps you avoid nested loops or repeated scanning.
19:27
You can think of it as reading a book with two fingers.
19:31
One tracks the start of something, the other tracks the end.
19:35
The trick is in how they move, and why.
19:39
There are two major types of the two-pointer technique.
19:42
Both pointers move in the same direction, and pointers move towards each other from opposite ends.
19:49
Let's break each one down.
19:51
The same direction pattern usually shows up when you're doing a single pass over the data,
19:57
but you need to track a range.
20:00
not just one element at a time. A classic example is the fast and slow two-pointer setup.
20:07
You'll often see one pointer moving one step at a time, which is the slow pointer,
20:12
and another one moving faster, two steps at a time. Now, why would you ever do that?
20:18
Well, it lets you detect patterns in a single pass. For example, if the fast pointer reaches
20:26
the end while one is halfway, you've found the middle. Or if the fast pointer ever lapsed the
20:34
slow pointer, you've detected a cycle. The ability to find the middle of something or detect cycles
20:41
are not only incredibly useful for a variety of reasons, but as you can see, extremely simple.
20:47
Now, the opposite direction pattern is the more classic two-pointers implementation,
20:52
where one pointer starts at the beginning and the other starts at the end and they move inward.
20:59
You'll see this pattern used when the array is sorted and you're trying to find a pair or
21:03
combination, you're comparing symmetric parts of a structure like checking for palindromes,
21:08
or you want to avoid nested loops when looking at all pairs. Now here's the mental model for this.
21:14
Your left pointer starts at zero, your right pointer starts at the last index,
21:20
Then you check the current pair.
21:22
And based on some condition, which is problem dependent,
21:26
so it could be their sum or checking if the two characters match,
21:30
you move one of the pointers inward.
21:33
The condition is always problem specific, but this pattern is consistent.
21:38
Opposite direction two pointers are especially powerful in sorted arrays.
21:42
Because each time you move a pointer, you can eliminate an entire range of possibilities.
21:48
Instead of checking all combinations, which would be O of n squared, you're solving it in O of n.
21:55
The reason two-pointers are so powerful is because they let you reduce the number of iterations you need,
22:01
track a relationship between two places in a structure, and avoid extra space by not needing sets or maps.
22:08
This is one of the few techniques that can actually optimize both time and space complexity at once.
22:14
It's also extremely intuitive once you practice it.
22:18
You don't really need to memorize much at all.
22:20
You just need to recognize the shape of the problem.
22:23
In particular two come up a lot in problems involving the following Often the problem won say use two but if the brute force solution is checking all pairs or scanning
22:38
repeatedly, it's usually a sign there's a more efficient way. So you should always ask yourself,
22:45
can I do this by just walking the array once from both sides or in one pass? And if the answer is
22:53
yes, two pointers is probably the most efficient way to go.
22:58
Valid palindrome. The problem is simple in concept. We're given a string, and we need to
23:05
check if it reads the same forwards and backwards. But we're only supposed to consider letters and
23:10
numbers, and we have to ignore casing. So this isn't just a straight-up mirror check.
23:16
We have to skip over punctuation, spaces, and special characters. Let's look at how this
23:22
solution handles that using two pointers. We start by setting up our left and right pointers.
23:28
L starts at the beginning of the string, and R starts at the end. Classic setup for this pattern.
23:35
Now, while the two pointers haven't crossed each other, that is, while left is still less than
23:41
right, we enter a loop. Inside the loop, the first thing we do is skip over non-alphanumeric
23:49
characters. We do that by moving the left pointer forward until it's pointing at a valid character.
23:55
And we do the same thing with the right pointer, moving it backward.
23:59
This is important because we're only supposed to compare letters and numbers.
24:04
Everything else just gets ignored. Once both pointers are on valid characters,
24:10
we compare them. But we don't compare them directly, because remember, we're supposed to
24:15
ignore case. So we lowercase both characters and then check if they're equal. If they're not equal,
24:23
we can immediately return false, because that means the string isn't a palindrome.
24:29
If they are equal, we're good, so we move both pointers inward, one step from the left,
24:35
one step from the right, and keep going. This loop keeps repeating until the pointers meet in the
24:42
And if we never hit a mismatch, we return true because the string passed all our checks.
24:49
So the beauty of this solution is that it only scans each character at most once.
24:54
No extra space no reversing strings Just two pointers doing a clean pass through the input And that why the two pattern is so powerful for problems like this
25:05
Let's move on to the next one. All right, now let's look at another super common interview
25:11
problem. It uses the same direction, two-pointers technique, finding the middle of a linked list.
25:18
The problem is simple on the surface. Given a linked list, return the middle node,
25:23
And, if the list has an even number of nodes, you return the second middle one.
25:29
So for something like 0 points to 1, 1 to 2, 2 to 3, and 3 to 4, the middle is clearly 2.
25:37
But how do we find that efficiently, in just one pass?
25:42
Let's walk through the code and break it down.
25:44
We start by creating two pointers, slow and fast, and we set both of them to the head of the list.
25:49
Now here comes the magic. We enter a loop. And while fast and fast.next are still valid,
25:57
we do two things. We move fast two steps forward, and we move slow just one step forward.
26:03
So fast races ahead, while slow walks at a steady pace. Eventually, fast will hit the end of the
26:09
list. And when that happens, slow will be sitting at the middle. We return slow.val, which gives us
26:15
value of the middle node. Why does that work? Because for every two steps fast takes, slow only
26:21
takes one. So by the time fast reaches the end, slow has only gone halfway. That's the beauty of
26:28
this pattern. One traversal, no extra space, and it works for both odd and even length lists.
26:35
In the even case, the slow pointer lands right on the second middle, which is exactly what we want.
26:41
So that's it, the fast and slow pointer in action. Simple, elegant, and interview approved.
26:48
The sliding window pattern is one of the most versatile techniques in coding interviews.
26:54
It is a natural extension of the two-pointers pattern we just talked about,
26:58
but with a tighter focus. Instead of tracking just two positions, you're managing an entire
27:04
range of values. This range is what we call your window, and as the name suggests,
27:10
you'll be sliding it across your data structure to inspect or process different segments of it,
27:16
without re-traversing the same data over and over.
27:19
If a problem is asking about contiguous segments,
27:22
like a substring subarray or a group of consecutive elements a sliding window is almost always the right answer Now imagine you have a scanner and you dragging it across a line of text
27:35
The scanner starts small and grows as you move forward, or maybe shrinks depending on what you're
27:42
looking for. At any given moment, you're only interested in what's inside the window. You don't
27:49
care about anything before or after it. This is what makes sliding window efficient. You're looking
27:56
at a subset of the data, adjusting the window as needed, and never revisiting the same element
28:02
twice. And that last part is key. Just like two-pointers, this gives us a clean way to reduce
28:09
time complexity to O of N, even when the problem feels like it should require nested loops.
28:14
Just like with two pointers, there are two main types of sliding window patterns.
28:21
The first is fixed size, where the size of the window is predetermined and stays the same throughout.
28:27
And the second is dynamic, where the window can shrink and expand as necessary.
28:32
Now, let's break each one down.
28:34
A fixed size sliding window is used when the problem gives you a specific window size,
28:40
usually with language like
28:41
find the maximum average of any subarray of size k,
28:46
return the sum of every k-length block,
28:49
or find the subarray of length k with the largest or smallest x.
28:54
In these problems, the window's length never changes.
28:58
It always includes exactly k elements,
29:01
and as you slide the window over the data,
29:03
you add one new element from the right and remove one old element from the left,
29:08
keeping the window's size constant.
29:10
The key is that you're maintaining a running window, and at every step you're updating your result based on the current contents of the window.
29:18
Now let's walk through the code template you'll see over and over.
29:24
This is the template. Now let's break it down a bit.
29:28
We start by grabbing the first window size elements as our initial window.
29:34
This gives us a valid starting point to build from.
29:37
Then, we loop from window size till the end of the input.
29:43
On each step, we're calculating left as right minus window size to give us the index of the
29:49
element that just fell out of the window.
29:53
Then we remove that old element from the window, we add the new input, right, to the end, and
30:00
And then we update our answer based on whatever the problem is asking.
30:04
Max, min, sum, average, etc.
30:08
Now let's move to the more flexible and more powerful version, the dynamic sized sliding window.
30:15
This is used when the window size is not fixed, and you're trying to find the largest, smallest, or optimal range that satisfies some condition.
30:25
You'll usually see problems that sound like,
30:28
find the length of the longest substring with at most k unique characters,
30:33
what's the smallest subarray with a sum greater than a target,
30:36
or return the longest window where a certain rule is valid.
30:40
In these problems, the window grows and shrinks depending on the data.
30:45
You expand the window to include more elements,
30:48
and once the condition is violated, you start shrinking it from the left until it becomes valid again.
30:54
This gives you complete control. You're not just sliding the window across, you're
31:00
adjusting it in real time to maintain the right conditions. Here is the core
31:05
pattern. Again, let's break this down so we understand it. You start with an empty
31:12
window and grow it one element at a time from the right. Every time you add a new
31:18
element, you check if the window is still valid. Once the window is valid, you update your answer.
31:26
This usually means something like tracking the characters in the window to see if they
31:29
meet some condition. If the window is invalid, you start removing elements from the left,
31:37
shrinking the window until it becomes valid again. Now let's see these two templates in action.
31:44
Let's put the fixed size sliding window pattern into action with this problem.
31:49
Maximum subarray of length k. We're given an array of non-negative numbers and a number k,
31:55
and we need to find the largest possible sum of any subarray of length k. Since the subarrays must
32:03
be exactly length k and consecutive, this is a perfect case for a fixed size sliding window.
32:08
So here's how we solve it.
32:10
First, we build the initial window by summing up the first k elements of the array.
32:16
That gives us a starting point to compare against.
32:19
We store that in a variable called window sum then we copy that into a largest variable since this is our first and currently best subarray sum Next we slide the window forward through the rest of the array We do this by looping from index k all the way to the end of the list
32:39
Each step forward means one number falls out of the window on the left, and one new number
32:45
enters on the right.
32:47
So first we figure out the index of the element that's now outside the window.
32:51
That's right minus k, which we call left.
32:54
Then, we subtract nums at index left from our window sum, since that value is no longer
32:59
in the window.
33:00
Next, we add in the new number at nums at index right, which just entered the window.
33:06
Now that our window is updated, we check if this new sum is larger than what we've seen
33:10
before, and update largest if so.
33:13
We repeat that process until we've scanned the entire array.
33:17
Finally, we return largest, which will hold the maximum sum we've found across all k-length
33:23
windows.
33:24
This is a classic example of how sliding window avoids extra work.
33:28
We're not resumming each subarray from scratch.
33:30
Instead, we're just adjusting the total by removing one number and adding another.
33:36
Time complexity stays linear big O, which is exactly what we want in an interview.
33:40
And that's it.
33:41
Smooth and efficient.
33:44
Alright, let's try another real coding problem.
33:47
And this one's a textbook example of when to use a dynamic sliding window.
33:52
the length of the longest substring without repeating characters. We're given a string,
33:58
and we need to find the length of the longest substring that doesn't have any repeated characters.
34:04
This kind of problem is perfect for the sliding window pattern, because we're working with
34:09
contiguous characters, and we need to grow and shrink the range based on some rule,
34:14
in this case, uniqueness. Let's look at a quick example to build some intuition before diving
34:20
into the code. We'll use the input string ABCDBEA and walk through how the sliding window works.
34:27
We'll start with both pointers, red on the right and blue on the left. Add the first character.
34:35
That gives us the substring A, which is valid, and its length is 1. Now we move the right pointer to
34:43
Our window is now AB. No repeats, so we update our longest to 2.
34:49
Add C to the window Now it ABC still all unique and we bump the longest up to 3 Add D We got ABCD all unique longest becomes 4 Now we hit a repeat We add B and that gives us A B C D B But B is already inside the window so this window is
35:10
invalid. To fix that, we slide the left pointer, the blue one forward, one step at a time, until B
35:17
is no longer duplicated. We remove A, then remove the first B. Now we're left with CDB,
35:25
which is valid again. Next, we add E. The window becomes BCDE. No repeats, but the length is still
35:34
4, so longest doesn't change. Add A. Now it's BCDEA. All unique again, and now we have a new
35:43
longest of 5. At this point, we've scanned through the whole string, and we're done. The final answer
35:50
is 5. Now let's walk through how the code captures that exact logic. We start by setting up two
35:56
variables, longest, which will track the maximum substring length we've seen so far, and L, which
36:02
marks the start of our sliding window. We also set up a dictionary called counter, which keeps track
36:08
how many times each character appears in the current window. We use default dict so that every
36:14
character automatically starts with a count of zero. Then we loop through the string using a
36:19
write pointer, r. For each character at index r, we add it to our window by incrementing its count
36:26
in counter. Now here's the important part. If the character we just added appears more than once,
36:31
that means we have a duplicate, and we need to fix the window. So we use a while loop to shrink
36:37
the window from the left. We subtract 1 from the character at the left pointer and move L forward
36:42
by 1. We repeat this until the character count goes back to 1, meaning the window is valid again.
36:48
Once the window is valid, we calculate its size using R minus L plus 1, and if that's larger than
36:54
our current longest, we update it. This process continues as we scan through the whole string,
37:00
always expanding the window from the right and shrinking from the left as needed to maintain
37:05
At the end, we return the value of longest,
37:08
which gives us the length of the longest substring,
37:11
without repeating characters.
37:13
This is a great example of a dynamic sliding window in action.
37:16
You're not just moving across the string,
37:18
you're constantly adjusting the window to match the rule you're enforcing.
37:22
It's efficient.
37:23
The time complexity is linear big O since every character is visited at most twice And the pattern is super reusable Once you get comfortable tracking conditions like no repeats inside the window
37:37
you'll start to see this technique everywhere.
37:40
Binary search is one of the most efficient algorithms in all of computer science.
37:46
At its core, it's a way to take a big problem and cut it in half over and over again
37:51
until you land on the answer.
37:54
And that's the key idea.
37:56
Cut the problem in half at every step.
37:59
Instead of scanning the array from start to finish, which would take O of n time,
38:06
binary search lets you find the answer in O log n time.
38:11
But here's the thing.
38:13
Binary search is so much more powerful than just searching for a number, and most people don't even realize it.
38:18
So let's start with the basics and then we'll generalize it to see how truly powerful it is.
38:25
But first, the intuition.
38:27
Imagine you're playing a number guessing game.
38:30
I pick a number between 1 and 80 and you have to guess it in the least amount of moves.
38:36
Each time you guess, I tell you if it's too high or too low.
38:41
What should your first guess be?
38:43
Well, you would probably guess 40 because it's right in the middle and you can automatically eliminate half the answers.
38:50
Now, based on this answer, you would then make another guess and cut the range in half again and again and so on until you find your answer.
38:59
That's essentially what binary search is.
39:02
Each guess lets you eliminate half the remaining options.
39:06
And that's what gives you logarithmic time.
39:08
You can even go from 1 million down to 1 in just about 20 steps.
39:15
Far more efficient than scanning all 1 million values, which would take at worst a million steps.
39:22
Now, let's take a look at starting with the binary search template that you might recognize.
39:28
Let's start by taking a look at the vanilla binary search template, which is what most people may recognize.
39:33
Now, let's break down how this vanilla binary search algorithm works line by line.
39:38
This is our function definition.
39:39
We're given a sorted list of integers AR and a target number that we want to find the index of.
39:45
We set two pointers.
39:46
Left starts at the beginning of the array and right starts at the end.
39:51
These define the current search range we're looking at.
39:54
This loop runs as long as there's something to search,
39:57
meaning our left pointer hasn't passed the right one.
40:00
Once they cross, we know we've exhausted the search space.
40:04
We calculate the middle index of the current range.
40:07
Python's double slash is integer division, so this gives us a whole number.
40:11
If you're using another language that handles division differently, check out documentation online.
40:17
This is the ideal case, we found the target.
40:20
So we return the index where it lives.
40:22
If the middle value is less than our target, that means the target must be to the right of mid.
40:27
So we discard the left half, including mid, and shift our left pointer to mid plus 1.
40:33
And if the middle value is greater than the target, then the target has to be on the left side.
40:38
So we move the right pointer to mid minus 1, cutting off the right half.
40:43
If we exit the loop without finding the target, we return negative 1, meaning the element wasn't found in the array.
40:50
And there we have it.
40:51
This version of binary search is what you'll use anytime you're directly looking for a number in a sorted array.
40:58
Here's where binary search gets really powerful.
41:01
Remember how in the vanilla version, we needed a sorted array to cut our search space in half?
41:07
Turns out, we don't actually need a sorted array.
41:10
All we really need is a monotonic condition.
41:13
A monotonic condition is one that only changes in one direction.
41:17
If it's increasing, it won't ever decrease.
41:19
and if it's decreasing, it won't ever increase. The reason this is powerful is because we can
41:26
make definitive claims about what happens past a certain point. For example, take a look at the
41:32
graph on screen, at the point where x equals 5, y equals 100. What if I asked you, will all the y
41:41
values to the left of this be smaller than 100? On the monotonic slope, we can definitively say
41:47
yes. So we know that every value left of this is smaller and every value right of this is larger.
41:54
But on the non-monotonic slope, we can't say that for certain because some values to the left are
41:59
higher while some are lower. Doesn't this sound familiar? This is the exact premise that our
42:04
vanilla binary search is based on. We look at a middle value and because we know everything to the
42:10
left is smaller and everything to the right is larger, we can cut out half of the list immediately.
42:16
So having a sorted array is a type of monotonic condition, but there are other types that don't appear as sorted arrays.
42:24
Let say we have a function fx that returns either true or false If we plot the values of fx over a range it might look like this Once the function turns true it stays true
42:36
That's what makes it monotonic.
42:38
It only transitions once and in one direction.
42:41
Binary search can help us find that first true, the boundary, in logarithmic time,
42:48
as long as we can write a feasible function that answers, is this index valid?
42:53
This comes up a lot in problems such as ones where you're not given a sorted array,
42:59
but you're trying to minimize or maximize something, and you can check whether a solution
43:03
is valid for a given guess. Sort of makes sense? Let's take a look at the template line by line,
43:11
and I'm sure it will make more sense. We're still using two pointers to define our search space.
43:18
Nothing new yet. We keep track of the best candidate we've seen so far,
43:23
If we find a position that returns true, we store it here, but keep searching left to see if there's an even earlier one.
43:30
Classic binary search loop. We keep going until we've narrowed down the search space, grab the midpoint as usual.
43:37
Here's where things get different.
43:39
We're not comparing values directly. Instead, we check if this index satisfies some condition.
43:46
Think of this as asking, is this index good enough?
43:49
If it is good enough, we store it as a possible answer, and then move left in case there's an earlier index that also works.
43:59
This is the key move when you're trying to find the first valid solution.
44:03
If mid is not feasible, we discard it and move right.
44:07
Finally, we return the best answer we found, or negative one, if nothing was ever feasible.
44:13
This template might feel abstract at first, but once you plug it into a real problem, it clicks.
44:19
Now let's plug that pattern into a real problem to see it in action.
44:23
We're given a sorted array of booleans.
44:25
All the falses come first, followed by a bunch of trues, and our job is to find the first index where the value is true.
44:33
This setup is a classic monotonic condition.
44:36
Once the array turns true, it stays true. It never flips back.
44:40
So the array might not look traditionally sorted, but it still has that one directional property we need.
44:46
So how do we find that first true efficiently?
44:49
Binary search.
44:51
We start by setting our usual left and right pointers to cover the full array and we keep track of the best candidate we seen so far the earliest index that returned true Inside the loop we grab the midpoint and ask
45:07
is this index good enough? If the value at that index is true, that means it could be our answer,
45:15
but we're greedy here. We want the first true, so we update our boundary and keep searching to the
45:20
left. If it's false, then this index and everything before it is invalid. So we shift our search to the
45:27
right. This is the core idea of binary search on a feasibility function. We're not comparing values
45:34
in the usual way. We're asking yes-no questions about whether the index satisfies the condition.
45:41
That lets us confidently shrink the search space in the right direction.
45:44
Once the loop ends, we return the best index we found.
45:49
If the array was all false, that fallback value of negative 1 gets returned.
45:54
This approach lets us find the boundary, the first true, in logarithmic time, no matter how big the
45:59
array is. Pretty slick, right? Let's tackle a classic interview problem. Find the minimum in
46:06
a rotated sorted array. We're given a sorted array that's been rotated at some unknown pivot.
46:12
So something like 10, 20, 30, 40, 50 might become 30, 40, 50, 10, 20.
46:19
Our goal is to find the index of the smallest number in that array.
46:24
At first, it might seem like binary search won't help here. The array isn't fully sorted anymore.
46:30
But if you look closely, there's still structure we can use.
46:35
Before the rotation point, the numbers are increasing. Then suddenly, they drop.
46:39
That drop is the pivot. And the smallest number sits right at that turning point.
46:44
What's cool is that this creates a kind of split in the array. Every number before the minimum is
46:51
greater than the last number in the array, and every number starting from the minimum is less
46:56
than or equal to the last number. That's a one-way transition. We've got a yes or no condition that
47:03
only flips once, in other words, a monotonic pattern.
47:07
So for each index we can ask a question like, is this number less than or equal to the last
47:14
number in the array?
47:16
This gives us a series of false values, followed by trues.
47:21
And now the problem becomes find the first index where the answer is true If you already seen the pattern for finding the first true in a boolean array this should feel familiar We going to apply that same boundary binary search here
47:37
Let's walk through the code logic. We start with two pointers, left and right, covering the whole
47:43
array. We also track the best candidate index we've seen so far. Each loop, we find the midpoint
47:50
and ask our condition. Is this number less than or equal to the last number?
47:56
If the answer is yes, we store that index and move left, looking for an earlier one.
48:02
If the answer is no, we know we're still in the too big part of the array, so we shift right.
48:08
Eventually, the pointers converge. And at that point, we found the boundary,
48:13
the index of the smallest number. Even though the array looks unsorted,
48:18
the key is that the condition we're testing is monotonic, which makes binary search possible.
48:23
It's a clever way to turn a tricky looking array into something we can solve in logarithmic time.
48:28
BFS, breadth-first search, is one of the most common and powerful patterns
48:34
for traversing non-linear structures like trees and graphs.
48:38
The core idea is this. You explore the structure level by level, start at the root or source node,
48:45
then visit all its neighbors, then all their neighbors, and so on, before going deeper.
48:50
This pattern is useful because it naturally gives you the shortest number of steps to reach something,
48:56
a clean level order traversal, and a guaranteed way to explore everything evenly and fairly.
49:03
At the heart of BFS is a simple tool, a queue. This queue ensures we always explore nodes
49:09
in the exact order we discovered them. First in, first out. But how we apply this differs slightly
49:16
depending on whether we're working with a tree or a graph. Let's break down both cases. Trees are a
49:21
special kind of graph that don't have cycles, meaning you can't loop back to a node you've
49:25
already visited. That makes BFS on trees simpler. You don't need a visited set because the structure
49:32
itself guarantees no repeats.
49:34
Here's the exact template for running BFS on a tree.
49:38
Let's break it down.
49:40
We start with the root node and place it into a queue.
49:43
While the queue isn't empty, we remove the first node, FIFO.
49:47
We look at all of its children.
49:50
If any child meets the goal, we return it.
49:53
Otherwise, we add the children to the queue and keep going.
49:56
The queue ensures that we always finish one level before moving to the next.
50:00
This is what makes BFS so great for things like finding the shortest path in a tree, or processing level by level.
50:07
And because trees are acyclic by definition, we don't need to worry about visiting the same node twice, which simplifies the logic a lot.
50:14
Use this pattern when you're traversing a tree from top to bottom or root to leaves.
50:19
Or when you care about depth, distance, or level-based logic.
50:23
Or if you're looking for the first match, or the closest node to the root.
50:27
to the root. As long as you're working with a true tree, this version is clean and efficient.
50:32
But once cycles are possible, we need something more.
50:36
Graphs are more general than trees. They can have cycles, loops, and multiple connections
50:40
between nodes, which means you can revisit the same node more than once if you're not
50:44
careful. To prevent this, BFS on a graph must track visited nodes. Otherwise, you'll either
50:49
do redundant work, or worse, get stuck in an infinite loop.
50:52
Here's the template for Graph BFS.
50:55
Let's break it down.
50:56
Start with the root node in the queue and in the visited set.
50:59
While the queue isn't empty, pop the next node from the front.
51:03
Look at all of its neighbors.
51:04
If a neighbor has already been visited, skip it.
51:06
Otherwise, mark it as visited and enqueue it.
51:09
This version guarantees two things.
51:11
Every node is visited once you never enter a cycle or revisit paths unnecessarily.
51:15
The key move here is when we mark nodes as visited, we do it when we enqueue them, not
51:19
when we process them.
51:21
That way we avoid adding the same node more than once.
51:23
Use this version when you're working with grids, adjacency lists, or networks.
51:28
The structure can contain cycles or duplicate paths.
51:31
You need to find the shortest number of steps or minimum moves.
51:35
You're exploring possible states in puzzles, games, or logic problems BFS on graphs is
51:39
especially useful when all edges or moves have the same cost, because it will always
51:44
find the shortest path first.
51:46
Both versions for trees and graphs follow the same fundamental structure.
51:49
a queue for the current layer of exploration, a loop to process each node, and a branching
51:54
step where neighbors or children are added to the queue.
51:57
You'll see this structure everywhere, from tree traversals to maze solving to social networks
52:01
to shortest path problems.
52:03
Once you know the pattern, you can recognize it immediately and fill in the details.
52:07
And on that note, let's take a look at applying these patterns to some real-life interview
52:12
problems.
52:13
Alright, let's walk through a classic BFS problem.
52:17
The idea is simple We given the root of a binary tree and we want to return a list of values level by level so the root level comes first then the next layer of nodes then the next and so on always from left to right This is a perfect use case for BFS because BFS is all about exploring one layer at a
52:39
time.
52:40
Let's jump into the code. We start off by importing Decay from Python's Collections
52:45
module. This gives us a super-efficient queue that we'll use for our level by level traversal.
52:51
Now into the main logic, the level order traversal function.
52:56
We first create an empty list called res, short for result, which will store all the
53:00
levels of the tree as we go.
53:02
Next, we initialize our queue with the root node already inside.
53:07
Even if the tree has only one node, this is enough to kick off the traversal.
53:12
We now enter a while loop, and this is key.
53:16
The loop keeps running as long as there are nodes left in the queue.
53:19
In other words, as long as there's something to process at any level of the tree.
53:25
Inside the loop, we grab the current size of the queue that tells us how many nodes are
53:29
in this level.
53:31
Think of it like freezing the queue at this moment in time, we're going to process only
53:35
those nodes before moving on.
53:38
We make a new level list to collect the values from this level.
53:41
Now comes the core BFS step, a for loop that runs exactly n times, where n is the number
53:47
of nodes in the current level.
53:49
For each node, we pop it from the front of the queue, classic FIFO behavior, and we add
53:55
its value to the new level list.
53:58
Then we look at its children.
53:59
If the node has a left child or a right child, we append them to the queue so they'll be
54:04
processed in the next round.
54:06
That's it.
54:07
We just rinse and repeat.
54:08
After we've finished processing all nodes at this level, we append the new level list
54:12
to our result list.
54:14
And when the queue finally runs out, meaning we've hit the bottom of the tree, we return
54:19
res which now holds all the levels in order. So to recap, we use a queue to control the order of
54:26
traversal. At each level we process the current set of nodes. For each node we add its children
54:34
to the queue and we repeat until there's nothing left. This structure gives us a clean left to
54:41
right level order traversal of the tree. Exactly what the problem is asking for.
54:46
Let walk through another real interview problem the flood fill problem which is basically like simulating the paint bucket tool in MS Paint You given an image as a 2D grid where each number represents a color Starting from a given pixel at row R column C you want to change the
55:07
color of that pixel and every connected pixel with the same color to a new one.
55:11
The key here is connected pixels, meaning all the ones that are directly
55:16
touching up, down, left, or right, and have the same original color. Not
55:22
diagonally, just the four cardinal directions. This is a perfect place to use BFS on a grid,
55:29
since we want to explore all the connected regions evenly without going too deep too fast.
55:34
Let's work through the code. We're starting off by grabbing the number of rows and columns from
55:39
the image, just some prep to help with boundary checks later. Then we define a helper function
55:44
called getNeighbors. This is where we figure out which adjacent pixels are part of the same region.
55:52
We take a coordinate, which is just a row call pair, and for each of the four directions, we calculate the neighbor's row and column.
56:00
We make sure the neighbor is still inside the bounds of the grid, and then we check if that neighbor has the same color as the one we started with.
56:06
If it does, we yield it. That just means we found another connected pixel to explore later.
56:12
Now comes the main part, BFS.
56:15
We define a BFS function that takes in the starting coordinate, or root.
56:19
We initialize a Q with that starting pixel. Remember, BFS always starts with a Q.
56:26
We also create a visited grid, same size as the image, to track which pixels we've already handled,
56:32
because unlike trees, grids can loop back, and we don't want to visit the same pixel more than once.
56:39
Then we extract the row and column from our starting point, get the color we're trying to replace,
56:43
and immediately update that pixel to the new replacement color.
56:47
And of course, we mark it as visited.
56:49
Now we start the actual BFS loop.
56:51
As long as the queue isn't empty, we keep pulling out the next pixel to process.
56:56
For each pixel, we use the Get Neighbors helper to find all its same color neighbors.
57:01
If we find one we haven't visited yet, we update its color, add it to the queue so it
57:06
can spread to its neighbors later, and mark it as visited.
57:10
So this is where the flood fill effect happens, one level at a time, expanding outward like
57:15
like ripples in water.
57:17
Finally, once BFS is done, we return the updated image,
57:21
now with the connected region filled in with the new color.
57:24
And that it A clean BFS on a grid with visited tracking to avoid cycles Depth search or DFS is one of the most common ways to explore tree or graph structures
57:37
If BFS is about going wide, layer by layer, then DFS is about going deep. You pick a path and follow
57:43
it as far as it can go. Only when you reach the end of that path do you back up and explore other
57:48
options. The key idea behind DFS is this. Fully explore one branch before moving on to the next.
57:54
DFS is used in problems where you need to explore every possibility. You want to visit all nodes, possibly in a specific order.
58:01
You care about structure, not distance, like whether something exists, not how close it is.
58:06
DFS is often implemented recursively, using the call stack to manage where you are in the structure.
58:11
In some cases, it can also be done iteratively with an explicit stack, but recursion is more common in interviews and easier to read.
58:18
Let's look at how it plays out, starting with trees.
58:20
Trees are acyclic, by definition. They branch downward, and you can't loop back. That makes them a perfect fit for DFS.
58:26
Here's the clean recursive DFS template for a tree.
58:29
How it works. We first check if the current node is none. If it is, there's nothing to search, return.
58:34
Then, we check if the current node matches the target. If not, we go left and search down that entire subtree.
58:39
If we find something there, we return it. If not, we backtrack and go right.
58:42
This is classic DFS. Go deep into the left subtree first, then back up and try the right.
58:47
The recursive call stack handles everything.
58:49
It keeps track of where we are and automatically returns us to the previous node after exploring each path.
58:54
And because trees don't have cycles, we don't need a visited set.
58:57
DFS is what you'll use in many recursive tree problems such as flattening trees,
59:01
building or checking structures, searching for nodes based on custom logic.
59:05
The structure is simple and surprisingly powerful.
59:07
When we move to graphs, the challenge changes.
59:10
Now you can have cycles and it's possible to revisit the same node multiple times unless you're careful.
59:14
To handle that, DFS on graphs must track visited nodes, just like BFS.
59:19
Here's the template for recursive DFS on a graph.
59:22
Breaking it down, you start at a root node, and for each neighbor, if the neighbor has already been visited, skip it.
59:27
Otherwise, mark it as visited and explore it recursively.
59:30
This is where the graph DFS differs from tree DFS.
59:33
There's no parent-child assumption.
59:35
You must manually avoid cycles, and you might visit the same node from multiple paths unless blocked.
59:40
The visited set is what guarantees each node gets visited exactly once, and that you don't enter infinite recursion.
59:46
DFS is especially powerful for problems involving puzzles and state exploration.
59:50
Graph coloring, recursive traversal, backtracking, which we'll cover later.
59:54
Just remember, the presence of cycles is what separates trees from graphs in DFS logic. That's why visit is not a good idea.
1:00:00
is required here. As we can see, like the other strategies we've covered, DFS follows a reusable
1:00:04
structure. You start at a node, mark it, and recursively explore neighbors or children. That's
1:00:09
it. The variations come from when you return values, when you check conditions, how you track
1:00:14
state across recursive calls. But the overall shape stays the same. Once you've seen this pattern a
1:00:19
few times, it becomes second nature. So let's start now and practice a few problems. All right,
1:00:24
let's walk through a classic recursive DFS problem, maximum depth of binary tree.
1:00:29
So the idea here is simple. Given the root of a binary tree, we want to find the maximum depth.
1:00:35
In other words, how far down does this tree go? What's the longest path from the root to a leaf?
1:00:41
We're going to use DFS to solve this because, well, it's perfect for problems where we want
1:00:49
to go all the way down each path. Now the helper function here is called DFS, and it follows that
1:00:56
clean recursive template we looked at earlier. First up, we check if the current node is none.
1:01:02
If it is, that means we've hit the end of a path, so we just return zero. There's no more depth to
1:01:08
add here. Otherwise, we're at a real node, so we want to explore both its left and right subtrees.
1:01:14
We do that by recursively calling DFS on both sides.
1:01:18
We're asking, hey, what's the max depth of the left side?
1:01:22
And what's the max depth of the right side?
1:01:25
Once we have those two numbers, we take the bigger one, because we care about the longest path.
1:01:31
And then we add one for the current node we're on.
1:01:35
So it's like, the depth of this subtree is the max of my left and right, plus one for myself.
1:01:41
That's the recursive part building upward as we return from the calls.
1:01:46
Now at the very end, we return dfs root minus 1.
1:01:50
Why minus 1?
1:01:52
It depends on how you're counting depth.
1:01:54
In this solution, the author treats the root level as depth 0, not 1.
1:02:00
So we subtract 1 to match that definition.
1:02:03
If the root is none, we just return 0 directly.
1:02:07
And that's it.
1:02:08
clean, recursive DFS to find the depth of a tree.
1:02:11
No visited set, no loops, no fancy tricks, just classic recursion going all the way down
1:02:17
and bubbling the answers back up.
1:02:20
Alright, let's tackle the number of islands problem.
1:02:23
So here the setup You given a two grid of ones and zeros Think of ones as land and zeros as water Your job is to count how many separate islands there are
1:02:35
and an island is just a group of land tiles connected vertically or horizontally, not diagonally.
1:02:41
This problem can be solved in a few different ways, but we're using DFS here.
1:02:46
We're exploring connected land, and we want to mark it all once we've visited it.
1:02:52
Let's break down how the solution works.
1:02:54
We start by getting the number of rows and columns in the grid.
1:02:59
Nothing fancy here, just setting up some variables so we know our bounds.
1:03:03
Next up is a helper function called getNeighbors.
1:03:06
This gives us all the valid adjacent tiles, up, right, down, and left, for a given cell.
1:03:13
We use two arrays, deltaRow and deltaColumn, to represent the movement in each direction.
1:03:18
For each one, we calculate the new row and column and check that we're still inside the grid.
1:03:23
If we are, we add that coordinate to the result. So this function just returns the four connected
1:03:29
neighbors for any given tile. Super useful for traversal. Now comes the core of the logic,
1:03:36
the df's function. Here's what it does. It takes in a coordinate, a tile on the grid,
1:03:42
and checks. Is this tile water? If it is, we just return. Nothing to explore. If it's land,
1:03:49
we mark it as visited by setting it to zero. In other words, we're sinking this part of the island
1:03:55
so we don't come back to it again. Then we loop through each of its neighbors. If any neighbor is
1:04:01
also land, meaning it's a one, we recursively call DFS on that neighbor. So we keep exploring outward,
1:04:09
marking every connected land tile as visited. This is depth-first search in action. We pick a
1:04:15
direction and go deep until there's nothing left to explore. Once we've defined those helper
1:04:21
functions, we move on to the main part of the code. We loop through every cell in the grid,
1:04:26
row by row, column by column. If we find a one, that means we've discovered an unvisited island.
1:04:33
We call DFS to sync that entire island, to mark all of its land as visited, and then we increment
1:04:39
our island count. We keep going until we've checked every tile, and by the end, count tells
1:04:44
how many islands we found. And that's it. Each DFS call handles one full island. And because we
1:04:51
mark every part of it as visited we don double count anything It clean efficient and a great example of how DFS shines in grid problems Backtracking is a recursive problem technique that explores all possible configurations
1:05:07
of a solution, but efficiently backs up when it realizes a path won't work.
1:05:11
Think of it like this.
1:05:12
You're trying to solve a puzzle by filling in decisions step by step.
1:05:16
At every step, you try all possible options.
1:05:18
If one leads to a dead end, you undo the last move and try something else.
1:05:22
undo part, that's what makes it backtracking. It's basically DFS with the ability to reverse a choice.
1:05:27
You use backtracking when the solution involves combinations, permutations, partitions, or paths.
1:05:33
You're building up a partial solution, one step at a time. You want all possible solutions,
1:05:37
or the first valid one, and you need a way to discard bad paths early instead of exploring
1:05:42
them fully. It's commonly used in Sudoku solvers, word searches, subset and permutation problems,
1:05:48
constraint-based problems like n queens. Now let's look at the core pattern. We'll be storing
1:05:52
our final results in this list. It could be valid permutations, combinations, solutions to a puzzle,
1:05:58
etc. The core of backtracking is a recursive DFS function. Start index keeps track of where we are
1:06:04
in the input. Path is the current in-progress solution. The additional states are optional.
1:06:08
Things like counters, visited arrays, frequency maps, etc. that track constraints or states outside
1:06:14
of the path. This is the base case. A leaf means we've reached a complete solution. Notice that we
1:06:19
store a copy of path, not the path itself, because the path will keep changing as we backtrack. If we
1:06:23
didn't copy it, we'd overwrite all of our answers. At each step, we try all valid next choices, or
1:06:29
edges, from the current state. In the case of permutations, this could be choosing the next
1:06:32
available number. In word break problems, this could be slicing the next substring. In subset
1:06:37
generation, it could be whether to include or exclude the next element. This is a critical
1:06:41
performance step, prune early. If an option breaks a constraint, skip it. This keeps your algorithm
1:06:46
from going down paths that can never lead to valid solutions. The earlier you can prune,
1:06:51
the faster your backtracking runs. We commit to a decision. Add the current edge choice to our path.
1:06:56
This is like choosing a number, a character, a tile, or a subset. This is where you update things
1:07:01
like marking a number as used, decrementing a counter, flipping a value, tracking sum, product,
1:07:06
frequency, etc. This lets you encode complex rules, like you can only use this letter once,
1:07:11
or you can't exceed a sum.
1:07:13
We move to the next step and repeat the process.
1:07:15
This is where the search continues deeper
1:07:17
and where all paths are explored.
1:07:18
After we return from the recursive call,
1:07:20
we undo the decision we just made.
1:07:22
This is the back in backtracking.
1:07:24
Without this we be stuck on our first path forever We also revert any state changes if needed to make sure the next iteration starts fresh Here are some signs you looking at a backtracking problem The question wants you to generate all possible combinations or find all valid arrangements
1:07:39
You're making a series of choices, each of which affects the remaining options.
1:07:43
The solution space is exponential, but you can prune it with smart rules. You're given a grid,
1:07:48
board, set of digits, or string, and asked to form, build, place, or explore. If a problem sounds like
1:07:54
Try all the ways to do x, but only return the valid ones. It's probably a backtracking problem.
1:08:00
Once you've written backtracking a few times, you'll see that. The structure is always the same,
1:08:04
only the details of pruning, edge generation, and state tracking change. And those details are what
1:08:09
you get good at over time. Let's get started now by applying it to a few practice problems.
1:08:14
All right, let's break down the solution to word search, which is a classic example of
1:08:19
backtracking on a 2D grid. The goal here is to find whether a given word can be traced through
1:08:24
adjacent letters on the board, moving up, down, left, or right, without reusing the same cell.
1:08:30
So we're using backtracking to explore all possible paths through the board that could
1:08:34
spell out the word. Inside the DFS function, the first thing we check is, does the current board
1:08:41
cell match the letter we're looking for at this position in the word? If it doesn't match,
1:08:46
we return false right away. That's pruning. No need to go further if the current path is already
1:08:53
invalid. Then we check the base case. Are we on the last letter of the word and it matches?
1:09:00
If yes, we've successfully found the entire word, so we return true. Now, to avoid reusing the same
1:09:07
cell, we mark the current one with a special character. Here, it's an asterisk. This is our
1:09:14
way of saying, hey, this cell is already used in this path. Next, we define the four directions we
1:09:21
we can move in up, down, left, and right.
1:09:26
For each of these directions, we check if the next cell is still inside the board boundaries.
1:09:32
If it is, we recursively call DFS to explore that cell as the next character in the word.
1:09:38
If any of those recursive calls return true, that means we've found a valid path.
1:09:42
So we bubble up that result and return true.
1:09:45
And here comes the backtracking part.
1:09:47
After exploring, we reset the current cell back to its original letter.
1:09:52
This is the undo step, so the board is clean for the next path we want to try.
1:09:57
Outside the DFS, we loop over
1:10:00
cell on the board. We treat each one as a potential starting point for the word. If DFS from any of
1:10:05
them returns true, we're done. The word exists in the grid. And if we finish checking every cell and
1:10:12
none of the paths worked out, we return false. So again, this is classic backtracking. We're
1:10:19
exploring all paths, pruning ones that can't work, and carefully restoring state after each step.
1:10:25
Lastly, but not least, we have priority queues, also known as heaps. A priority queue is a special
1:10:32
kind of queue where elements are removed in order of priority, not just in the order they were added.
1:10:36
Under the hood, priority queues are usually implemented as binary heaps, which are just
1:10:41
binary trees stored in arrays. There are two main kinds. For a min heap, every parent is smaller
1:10:46
than its children. For a max heap, every parent is larger than its children. In Python, the default
1:10:52
is a min heap, meaning the smallest element comes out first. But we can easily simulate a max heap
1:10:57
by negating the values. That means insertion and removal both take O of log n time, which is fast
1:11:02
enough for most real-time scheduling or selection problems. Priority cues show up in a ton of
1:11:07
interview problems especially when you want to repeatedly extract the smallest or largest item efficiently You maintaining a top K or bottom K set of values You need real ranking greedy selection or Dijkstra pathfinding You need to sort on
1:11:20
the fly, but don't want to pay the full big O of N log N cost for sorting the entire array.
1:11:26
Priority queues are one of the easiest implementations, often utilizing simple
1:11:30
libraries, so the best way to learn these is to get right into it now with some practice problems.
1:11:35
Alright, let's put that heap knowledge to work with this classic problem, finding the
1:11:40
k closest points to the origin.
1:11:42
We're given a bunch of points on a 2d plane, and we want to return the k points that are
1:11:47
closest to 0, 0, using regular Euclidean distance.
1:11:52
Now remember, since we only care about which points are closest, not the actual distances,
1:11:56
we can just compare the squared distances.
1:11:59
That saves us from doing a square root for every point.
1:12:02
Let's walk through the code.
1:12:04
First, we import heap pop and heap push from Python's heap eq module.
1:12:09
This gives us a nice way to use a min heap, where the smallest elements come out first.
1:12:14
Next, we create an empty heap.
1:12:17
We'll use this to keep track of all the points sorted by their distance to the origin.
1:12:23
Now we loop through each point in the input list.
1:12:26
For every point we calculate its squared distance from the origin That just x squared plus y squared Then we push a tuple into the heap
1:12:37
The distance first, and the point itself second.
1:12:41
Why do we put the distance first?
1:12:43
Because heaps in Python use the first item in the tuple to figure out the priority,
1:12:47
so this makes sure the point with the smallest distance will bubble up to the top.
1:12:52
Alright.
1:12:53
Once we've pushed all the points into the heap, we're ready to grab the top k.
1:12:57
We create a result list, and for k times we pop the smallest element off the heap.
1:13:02
That gives us the point with the next closest distance each time.
1:13:05
We don't care about the distance anymore, so we just extract the point and add it to our result
1:13:11
list. And finally, return the result. So overall, we're using a priority queue to help us efficiently
1:13:18
pull out the k closest points without having to sort the entire list.
1:13:24
The heap makes this fast.
1:13:25
Each insertion and removal is logarithmic.
1:13:29
And the code stays simple and readable.
1:13:31
Alright, let's dive into a classic selection problem using heaps, finding the Keith largest
1:13:37
element in an array.
1:13:39
So what are we trying to do here?
1:13:41
We given an unsorted list of numbers and we need to find the Keith largest Not just the keith item but the one that would sit in the keith spot from the end if we sorted it
1:13:52
Now, since we just learned about heaps, and especially how fast they are at pulling out
1:13:57
the largest or smallest values, this is a great chance to use them in action.
1:14:03
Here's what we're doing.
1:14:05
First up, we take all the numbers and negate them.
1:14:08
Why?
1:14:09
Python's heap implementation is a min heap by default, meaning it always pops out the smallest
1:14:14
value, but we want the largest ones to come out first. So, by flipping the signs, we turn it into
1:14:21
a max heap. Once we have our max heap, we call heapify, which rearranges the list so it satisfies
1:14:27
the heap structure. This step only takes linear time, which is a nice bonus. Now, the Keith largest
1:14:35
element will be the one that comes out after we've removed the largest one, k-a minus 1 times.
1:14:42
So we pop from the heap k minus 1 times. Each pop gives us the current largest number.
1:14:48
And finally, we return the number at the top of the heap.
1:14:51
But don't forget to flip the sign back to get the original value.
1:14:55
That's it. Fast, efficient, and no need to sort the entire array. Just a smart use of a heap.