Algorithms: Common edge cases in JS

Algorithms are the bedrock of computer programming. Algorithms are built to handle specific data structures with a range of accepted parameters. An edge case is a problem or situation that occurs only at an extreme (maximum or minimum) operating parameter. As programmers, how can we predict these cases in order to protect our app from breaking?

I will demonstrate some common edge cases in a basic bubble sort algorithm:

// bubbleSort.js
function bubbleSort(array) {
  var swapped;
  do {
    swapped = false;
    for(var i = 0; i < array.length; i++) {
      if(array[i] > array[i + 1]) {
        swap(array, i, i + 1);
        swapped = true;
      }
    }
  } while(swapped);
  return array;
}
function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

1. Accepted data structure

The first major edge case is the unaccepted data structure. My bubble sort algorithm only works predictably for arrays. Javascript will not prevent you from inputting other data structures in the function, such as normal objects. For example, what happens if I input this object:

var obj = {0: 0, 
           1: 1, 
           2: 2, 
           3: 3}

This will do some very strange things inside the for loop, but ultimately, our algorithm will return the original object.

--> obj

That may not be what we want! If the algorithm is going to be truly fool proof, we should test that our data structure is an array, and handle it somehow. Here I will return false so that we can handle unwanted data structures as an error in our program:

if (!Array.isArray(arr)) {
 
    return false 
    }

This will also return false for falsey values like null or undefined.

2. Emptiness

An empty array would not break this specific sorting algorithm, but empty values are something important to look out for:

bubbleSort([]) 
--> []

In the context of many programs, we want to handle an empty array differently so that it doesn’t break something in our program further down the line:

if (!arr[0]) {
    return false
} 
or 
if (arr.length === 0) {
    return false 
}

For algorithms that accept different data structures and types, we should also look out for emptiness. Here are some common ones:

var str = ''
var obj = {}
var arr = []
var num = 0

If our algorithm iterates through nested data structures, we may also want to check for nested emptiness like this:

[[],[],[],[[]],[[[]]]]

3. Accepted types

The next big case to test for is accepted types inside our array. Our bubbleSort algorithm sorts strings based on their Unicode values. That means that capital letters will go before lowercase:

bubbleSort([a,A,b,B])
---> [A,B,a,b]

If we want the algorithm to sort strings independent of capitalization, we may want to handle that:

if (arr[j-1].toLowerCase > arr[j].toLowerCase) {            
                var temp = arr[j-1];            
                arr[j-1] = arr[j];            
                arr[j] = temp;         
           }

Another case you may want to handle are string numbers vs normal numerical values. Here is one strange example of this:

2 > '2' ---> false 
2 < '2' ---> false 
2 === '2' ---> false 
2 == '2' ---> true 

In the case of two equal numbers, where one is a string, the only operator that evaluates to true is == . It gets even more tricky if there is a letter in the numerical string.

1 > '1a' ---> false 
1 < '1a' ---> false 
1 === '1a' ---> false 
1 == '1a' ---> false 
2 > '1a' ---> false 
2 < '1a' ---> false 

This could lead to some strange results in our sorting algorithm. Therefore, we may want to only accept numbers and not strings, or handle the different types separately.

Another type to be aware of is the boolean value. true is loosely equal to 1 while false is loosely equal to 0 .

true == 1 ---> true 
false == 0 ---> true 
true > false ---> true 
true < 2 ---> true 
true < 'a' ---> false
false < 'a' ---> false

We may not want to allow boolean values in our algorithm, especially if we are sorting an array of strings. This includes falsey values like null, undefined and NaN , which will all act strange when passed into a comparison operator.

The falsey data types all act differently in the comparison operators:

null < 0.0000000001 ---> true
null >= 0 ---> true
null > 0 ---> false
null == 0 ---> false
null === null ---> true
null == undefined ---> true
undefined < 2 ---> false 
undefined > 0 ---> false 
undefined == 1 --> false
undefined === undefined ---> true
NaN == undefined ---> false
NaN === NaN ---> false 
NaN >= 0 ---> false 
NaN <= 2 ---> false 
NaN == null ---> false

You may want to exclude these from your sorting algorithm. null is probably the strangest, where it approaches zero but does not equal 0 and is not greater than 0, but it can be coerced by == to be equal to undefined.

Luckily, Javascript has a way of forcefully making falsey data types become equal to each other and false. Simply append double exclamation points onto any of them.

!!null == 0 ---> true
!!undefined == 0 ---> true
!!NaN == 0 --> true

This has to do with the coercion algorithms in Javascript and how different falsey values are stored in memory. More on this here: http://www.ecma-international.org/ecma-262/5.1/#sec-11.9.3. and here: http://www.ecma-international.org/ecma-262/5.1/#sec-11.8.5

4. Large Values

In our case, we should be looking out for extremely large arrays. What happens if our function is given an array with length greater than 1 x 10¹⁰⁰?

Here is where Big O notation comes in.

Big O complexity

Big O complexity is a measure of algorithm efficiency. It makes a big difference when we are dealing with large data sets. Big O has two variables — time and memory space. Memory is important because it can be break our algorithm if large amounts of data are passed as parameters. Every computer program stores data in stack and heap memory. Stack memory is much faster to access but there’s less of it. How does this relate to algorithms?

Let’s answer this with two versions of bubble sort, recursive and iterative —

// bubbleSort.js
function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}
/// Bubble Sort using for loops 
function bubbleSort(array) {
  var swapped;
  do {
    swapped = false;
    for(var i = 0; i < array.length; i++) {
      if(array[i] > array[i + 1]) {
        swap(array, i, i + 1);
        swapped = true;
      }
    }
  } while(swapped);
  return array;
}
// Bubble sort using recursion
var swapped = true
function recursiveSwapping(arr, i = 0) {
  var len = arr.length;
  if (i >= len) {
    return arr
  }
    if (arr[i] > arr[i + 1]) {
      swap(arr, i, i + 1);
      swapped = true
    }
    return recursiveSwapping(arr, i + 1)
}

function recursiveBubbleSort(arr) {
    if (!swapped) {
      return arr
    }
        swapped = false
        recursiveSwapping(arr, i = 0)
        return recursiveBubbleSort(arr)
}

These two examples use the same exact algorithm, but the memory is handled differently. The recursive version of the algorithm uses stack memory, and will therefore break with a stack overflow error if the length of the array is very large. This is because the stack keeps track of every call of recursiveSwappinguntil the original call resolves. The iterative version of the function doesn’t face stack overflow issues.

In theory, the recursive version shouldn’t face memory issues either. Many lower level languages allow something called tail-call optimization, which makes it possible to to write recursive functions with 0(1) memory complexity. Until recently, JS did not allow tail call optimization, but in ECMAScript 6 you can enable it in strict mode. Simply type 'use strict’ at the top of the file, and you will be able to write recursively without running into stack overflow errors.

'use strict'

Just make sure that your recursive function calls are written in the last line, or tail, of your function like in the function below.

function recursiveSwapping(arr, i = 0) {
  var len = arr.length;
  if (i >= len) {
    return arr
  }
    if (arr[i] > arr[i + 1]) {
      swap(arr, i, i + 1);
      swapped = true
    }
// tail call below 
    return recursiveSwapping(arr, i + 1)
}

5. Some other edge cases to keep in mind

1. Odd/even — numbers and string length
2. Negative numbers
3. Special characters
4. Duplicate elements
5. Length of 1
6. Long string or large number
7. Null or Falsey values