To watch the youtube video going over this topic, please click here.
Problem Statement
A matrix (2D array) has cells that are filled with one of three possible values:
Given a matrix, to return the number of turns it takes until there are no humans left. (And if any human survives, then return -1.) ("Rotting Oranges" problem on Leetcode.) Solution (Multiple BFS)
Theory
The way we'll solve this problem is by updating the matrix each turn by infecting humans next to any zombies. However, there are two things we need to watch out for:
With this in mind, we'll use a queue to hold each zombie, and for each zombie in the queue we'll process it by allowing it to infect any humans adjacent too it (meaning pushing that newly created zombie onto the queue to be processed later). However, the part where our code is going to become easier to read (and differs from the Leetcode solution) is that each Zombie in our queue will store their matrix position (i,j) and the turn it got infected. To do this, we'll have a special data structure (a struct or a class) to store this extra info.
Algorithm
C++ Code
Analysis The time complexity is O(N), where N is the number of cells in the matrix, since we'll process each cell at most once. The space complexity is O(N), since at worst the queue holds all zombies. (Meaning we start out with a matrix full of zombies and they all get pushed into the queue.) Note: This solution is called "multiple BFS" because we're using a queue to traverse nodes (zombies) like the BFS algorithm, but we've got multiple nodes (zombies) being traversed at the same time.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake
To watch the youtube video on this topic, please click here.
Introduction: Matrices
A matrix is a 2-dimensional array. To access an element of a matrix, you look at a row position and a column position. (Ex. matrix[i][j] )
Matrices are useful data structures, but representing elements with two distinct keys (i, j) makes it trickier for using certain algorithms together with matrices. Being able to represent a position in a matrix with one value would be useful for situations like:
Encoding Matrix Positions
It's possible to encode a position (i,j) in a matrix into a single value. We can do this because we know the number of columns in the matrix, and can basically think of each cell in the matrix as a number, incrementing while going left to right, continuing for each row (like reading a book).
Encoding a position (i,J) into an encoded value h can be done by multiplying i by the number of columns and adding j. h = i * num_cols + j Decoding an encoded value can be done by dividing/modulusing the value h by the number of columns. i = h / num_cols j = h % num_cols
We can write some code to test this out.
Bookmark this page to keep this trick available whenever you need it.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake Introduction: Sorting
Sorting is one of the most important things in computer science, and is one of the first things taught.
Given some data structure (typically an array), order the elements in a particular way.
There's no one "best" sorting algorithm, and the algorithm chosen should be tailored for its particular use case.
However, all sorting algorithms follow the same procedure:
We'll focus on step (2) in this blogpost. Custom Comparators
The "default" for sorting is either by ascending order for integers (1 -> 2 -> 3) or in alphanumeric order for strings ("a" -> "b" -> "c").
How do you sort in descending order for integers? Or reverse alphanumeric order for strings? What if you weren't dealing with primitive variables like integers or strings, but had a container of objects and needed to be sorted on multiple keys? For example, if you had a Person class with fields for name and age, and wanted to sort by name, then age. [ { name: "Alex", age: 30 }, { name: "Bill", age: 25 }, { name: "Bill", age: 40 } ] You can handle custom sorting by using custom comparators. A custom comparator is a function that takes two instances of whatever data type you're trying to sort, and the function has logic that returns true if the second argument needs to be to the left of the first argument. Basically, if the thing on the left (first argument) needs to be swapped with the (second argument). Custom Comparators with Standard Libraries
Most languages come with a "sort" function in their standard library. For example, in C++ you can sort an array ("vector", in C++) like so:
However, what if we wanted to sort in reverse order? We could create a custom comparator that says "larger elements should go to the left" and pass that into the sort function.
As you can see, it's very easy to write a simple function that controls how the standard library's "sort" function determines how to order the array. We can make our comparator as complex as we need too.
[Example] Sort Integers By The Number Of 1-Bits (Leetcode)
This Leetcode problem is a great example of custom sorting. It asks you to sort an array of integers by the number of 1-bits each number has in its bit-representation.
We can use the standard library's sort function for this problem, and just create our own custom comparator to handle the comparison part.
Note: The code above was written for readability. There are special tricks for finding the number of bits in an integer that would make the code faster.
Like this content and want more? Feel free to look around and find another blog post that interests you. You can also contact me through one of the various social media channels.
Twitter: @srcmake Discord: srcmake#3644 Youtube: srcmake Twitch: www.twitch.tv/srcmake Github: srcmake |
AuthorHi, I'm srcmake. I play video games and develop software. Pro-tip: Click the "DIRECTORY" button in the menu to find a list of blog posts.
![]() License: All code and instructions are provided under the MIT License.
|