Algorithm Solving Techniques pt. 2

Part 2 of a series on algorithm solving techniques. Check out Part 1 if you missed it!

Use a “nested for-loop”

Nested for-loops, or a for-loop within a for-loop, are not so efficient. However, they give us an easy way to loop through data and perform actions. Perhaps the most famous example of a nested for-loop in action is the infamous ‘Bubble Sort’ algorithm:

function bubbleSort(array) {
  for (var i = 0; i < array.length; i++) {
    for(var j = 0; j < array.length; j++) {
      if(array[i]<array[j]) {
        // swap values
        var temp = array[j];
        array[j] = array[i];
        array[i] = temp;
      }
     }
  }
  return array;
}
var nums = [3,4,1];
// returns [1,3,4];
bubbleSort(nums);

A nested for loop will loop through an array once for each element in the array. So if you have an array [1, 2, 3], when i = 0 , the second for-loop will loop through each value of the array once more. and when i = 1 , the second for-loop will loop through each value in the array again.

As you can imagine, this is a very time consuming and exhaustive sort of process, which is why the run-time complexity for algorithms that use nested for-loops is typically O(n²). Check the bigocheatsheet for more information about evaluating time-complexity if you are interested.

Nested for-loops get a lot of slack because they are inefficient and break down with large data-sets (perhaps over 10,000).

Nevertheless, they are a tool that every developer should be aware of. It is a technique used in ‘brute-force’ approaches to solving algorithms. And using a brute-force approach for your “first pass solution” can give you valuable insights into the problem at hand. Those insights will allow you to evaluate your problem more clearly — and find a better solution.

Those insights will allow you to evaluate your problem more clearly — and find a better solution.

Plus, if you’re just starting out, it will also give you a way to actually create a working solution :). This will help you build the confidence you need to approach the problem from a different angle.

There is nothing worse than staring at a problem and having absolutely no way to even nudge the problem towards a possible solution.

So forget the haters, realizing that problem solving is about incremental steps, and add this technique to your tool belt. And don’t be ashamed of using it!

Talking Big O like the Pros

Swap values using “temp” variable

Another important technique in solving algorithms is knowing how to manipulate data in an array. There are at least three built-in methods in JavaScript for adding and removing elements to an array. Those are:

• array.push(value) // adds a value to end of array
• array.pop() // removes a value from end of array
• array.unshift() //adds a value to the beginning of an array
• array.splice(startIndex, deleteCount, itemToAdd) // adds or removes value from specific place in array

But how do you swap values manually? You can do this by creating a simple ‘swap’ operation:

var temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;

First, initialize a variable called temp and set it equal to the value you want to store temporarily. Second, set the array[i] equal to array[i+1] . Finally, set array[i+1] equal to temp .

This operation will allow you to swap two values, an operation that is especially useful in sorting algorithms.

Use a hash

In JavaScript, a hash is simply an object. You can create an empty hash with the following syntax:

var dictionary = {};

And you can add to this hash with this syntax:

dictionary['apples'] = 5;
dictionary['oranges'] = 7;

which will produce the following result:

{ 
  'apples': 5,
  'oranges': 7
}

Why is this useful, you may ask? It’s useful because you can construct hashes in order to keep track of information in a very simple way.

As in the example above, you could keep track of what words appeared in an array and the count of letters in each word (apple has 5 letters, oranges has 7).

Or you could use a hash to keep track of the number of times each integer appears in an array, and then use the hash to create a list of top 5 highest appearing integers.

An example of that looks like this:

function countOfElement(arr, N){
var encounteredNums = {};
  var num;
  for(var i = 0; i < arr.length; i++) {
    num = arr[i];
    if(encounteredNums[num]) {
      // value already encountered, count++
      encounteredNums[num]++;
    } else {
      // first encounter, initialize count
      encounteredNums[num] = 1;
    }
  }
  return encounteredNums[N] || 0;
}
// returns 6
countOfElement([3,4,2,3,2,2,2,2,3,2], 2);

Conclusion

If your goal is to get better at solving algorithms, don’t worry what people may say about nested for loops and the like. Snubbing these approaches is like shooting yourself in the foot. (As if it is possible to build anything perfectly with a perfect stroke of genius every time!)

No, problem solving is about creative use of proven methods. It requires stepping stones that lead you from brute-force approaches to promised-land of optimization and ideal solutions.

Keep on brushing up your skills with these simple techniques and give yourself a foundation that will help you solve more complex problems.

Did you enjoy this article? Please check out:

Algorithm Solving Techniques pt. 1

Algorithm Interview Questions and Answers (JS)