To watch the youtube video on this topic, please click here.
Introduction: Matrices
A matrix is a 2dimensional 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 1Bits (Leetcode)
This Leetcode problem is a great example of custom sorting. It asks you to sort an array of integers by the number of 1bits each number has in its bitrepresentation.
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 [Interview Question] Find The Lowest Common Ancestor In Binary (Search) Tree (Both BT and BST)3/1/2020
To watch the youtube video on this topic where I explain everything, please click here.
Introduction
This series of problems asks to find the "lowest common ancestor" for two types of binary trees.
A "common ancestor" for two nodes is a node that has those two nodes as descendants (and a node can be a descendants of itself). The "lowest" common ancestor is the node that's closest to the two nodes that satisfies the common ancestor condition. [Easy] Find Lowest Common Ancestor In Binary Search Tree
Given the root of a binary search tree and two nodes in the tree, p and q, find the lowest common ancestor of p and q. (Problem on Leetcode.)
For example, in the following diagram if p is node 3 and q is node 1, then the LCA(p,q) is node 2. Solution (Iterative)
We'll recognize that the node that's the LCA node of p and q must be one of the following:
For this solution, we'll take advantage of the "search" property of Binary Search Trees. In a BST, a node's left children have values that are less than the node's value, and the node's right children have values that are greater than the node's value. Because of this, we'll know if the p is on the left and q is on the right without having to search those subtrees. The C++ solution to the problem is as follows:
The time complexity is O(N). (Specifically O(H) where H is the height of the tree.)
The space complexity is O(1) because we're not using any extra space.
Note: We choose the iterative solution here because the recursive solution has a space complexity of O(N). However, he code itself is basically the same as the iterative approach.
[Medium] Find Lowest Common Ancestor In Binary Tree
Given the root of a binary tree and two nodes in the tree, p and q, find the lowest common ancestor of p and q. (Problem on Leetcode.)
For example, in the following diagram if p is node 2 and q is node 9, then the LCA(p,q) is node 7. Solution (Recursive)
Like the previous solution, we'll recognize that the node that's the LCA node of p and q must be one of the following:
However, this time we have a regular binary tree, and so we're forced to look through the entire tree until we find p and q. Our strategy is, for each node, recursively check the left and right subtrees to determine if either subtree has p or q in it. The node that satisfies one of these conditions is the lowest common ancestor.
The time complexity is O(N), because our recursion visits each node exactly once.
The space complexity is O(N) because we potentially hold the entire tree in memory at the same time.
Note: We choose the recursive solution here because the code/algorithm is simpler. The iterative solution's code is harder and requires a stack.
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. Protip: 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.
