Foundational techniques that will come in handy when solving all sorts of different algorithm problems.
This is not an exhaustive list and I’m sure there are ways to improve upon them. So I look forward to feedback in the comments below.
When I first started solving algorithms, I didn’t know about these techniques and had to learn them the hard way. My hope is that this list will help those starting out or looking to improve their algorithm solving techniques by showing the stepping stones needed for building strong algorithm solving skills.
Creating a ‘counter’ variable
A ‘counter’ variable will allow you to store the state of a value, and increment it up or down, depending on the purposes of your algorithm.
A good place to use this technique is when the algorithm solution asks you to return the ‘count’ of a certain value, as in the case of an algorithm that asks you to return the count of how many times an integer appears in array of integers:
function countOfNums(array, num) {
var count = 0;for(var i = 0; i < array.length; i++) {
if(array[i] === num) {
count++;
}
}return count;
}var values = [1,2,3,4,3];
var num = 3;// returns 2
countOfNums(values, num);
As you can see, we can use the variable count and set it equal to 0. When we loop through the array of integers and encounter a value that is equal to num , we increment the variable count by 1 ( count++ ).
Another place where this technique is useful, is when an algorithm asks you to return the sum of some value. For example the sum of an array of values.
function sumOfArray(array) {
var sum = 0;for(var i = 0; i < array.length; i++) {
sum += array[i];
}return sum;
}var values = [1,2,3,4,5];// returns 15
sumOfArray(values);
In this case, we set sum = 0. Then, as we loop through the array, we add the value of array[i] to the current value of sum .
Creating a 'fast’ and 'slow’ pointer
In this technique, you initialise two pointers, one that increments by 1, and another that increments by 2. As you move through a list of values, you can update the position of each pointer and get valuable information, that can be used to do such things as find the midpoint of a list of values.
This technique is especially useful in sorting algorithms and in algorithms that ask you to find the middle element in a linked list. For example, a fast way to find the middle node in a linked list is to use this technique:
function getMiddleElement(linkedList) {
var node = getHead(linkedList); var slow = node;
var fast = node;while(fast!=null && fast.next!=null) {
fast = fast.next.next;
slow = slow.next;
} return slow.data;
}
Assuming we have a helper function getHead() , which will return the head node of a linked list, and our node has a property data which we can return, the fast and slow pointers are used to find the middle element of the linked list.
Since the fast pointer increments twice as fast as the slow pointer, by the time the fast pointer has reached the end of the list, the slow pointer should be at the midpoint of the list, and we can therefore return slow.data , which should be the middle element of the list. For a good visualization of this concept, please check out this coderbyte tutorial.
Loop through an array in reverse
We all know how to loop through an array from start to finish:
for(var i = 0; i < array.length; i++) {
console.log(array[i]);
}But you can also loop through an array going the opposite direction:
for(var i = array.length - 1; i >= 0; i--) {
console.log(array[i]);
}By setting the value of i = array.length we are starting at the end of the array. We then set a parameter that i >= 0 , which means that we won’t iterate past array[0] . Then we increment down using i-- . This allows us to start at the end of the array and loop back to front. Check the next technique for an example of this in action.
Use a Second Array
A second array can be really useful and the key to solving many algorithm problems very quickly. If, for example, you are asked to reverse the order of array, you can simply loop through array starting at the last value, and push each value into arrayTwo . Finally, return the value of arrayTwo , and you have just reversed the order of array.
function reverseArray(array) {
var arrayTwo = []; for(var i = array.length - 1; i >= 0; i--) {
arrayTwo.push(array[i]);
}array = arrayTwo;
return array;
}var values = [1,2,3];// [ 3, 2, 1 ]
reverseArray(values);
Some interviewers will set a condition that you can’t use a second array or that you need to modify the first array ‘in place’, which will require more steps usually.
However, if you are able to use a second array, it can save a lot of time and trouble, and make an otherwise tricky algorithm problem quite simple!
In other words, don’t forget to ask, “Uh, can I use a second array?”, because the answer might be “yes!”, and your life will get 100% easier!
Conclusion
I think the thing separating “good” algorithm solvers from “great” ones is simply more exposure to different techniques employed to solve different problems.
The more exposure you have to these techniques, the more diverse and dynamic your problem-solving abilities will become.
And the more algorithms you are able to think about and solve, the better you will become.
If you enjoyed this article, please check out Part 2:
