How Pigeons can help us write Algorithms

Have you ever heard of the Pigeonhole Principle? It’s a simple concept that can be applied in many ways, including in computer science. In this article, we’ll explain the Pigeonhole Principle, show how it can be used in a sorting algorithm, and then provide an example of how it can solve a real-life problem.

Photo by sanjiv nayak on Unsplash

The Pigeonhole Principle

The Pigeonhole Principle is a basic idea that states: if you have more pigeons than pigeonholes, then at least one pigeonhole must have more than one pigeon. This may seem obvious, but it has important implications in mathematics and computer science and can be used in techniques such as data compression, error correction, and data analysis. It is a powerful tool that can help us solve complex problems in an elegant and efficient way.

The other day, I was sitting in my living room watching one of those ‘visualised sorting algorithms’ videos on YouTube (as one does) and as I was sitting there enthralled by the dancing lines and the 8-bit sounds, I noticed that one of the algorithms was called ‘Pigeon Sort’. The visualisation of it looked really interesting (to me at least) as it seemed to scan over the input once and then magically* had them all sorted. This prompted me to look into how it worked a bit more and I found it to be an elegant algorithm.

Pigeon Sort Algorithm

You may be familiar with well-known sorting algorithms such as Bubble Sort (O(n^2)) or Quick Sort (average case O(n log n), worst case O(n^2)), but for me, the Pigeon Sort algorithm is far more intriguing. It uses the pigeonhole principle and has a time complexity of O(n + m), where m is the range of key values in the input array.

While it may not always be the most efficient sorting algorithm, particularly for large ranges of integers, it’s a fascinating approach that I quickly appreciated. Additionally, its principle can align well with the flexibility of JavaScript arrays, which aren’t contiguous in memory; that is they can handle varied lengths dynamically, accommodating sparse data distributions without worrying about overflows.

The algorithm works by creating an auxiliary array of ‘pigeonholes’, each one designed to hold its corresponding ‘pigeon’. The algorithm iterates over the input array, placing each element (which we can think of as a pigeon) into the corresponding pigeonhole. It does this by looking at the value of the element (e.g 4 ) and then it places that into the index of the pigeonholes array. There are a few other numbers we need to calculate to get the correct indexes but we will see that shortly. Next up, it iterates over the auxiliary pigeonhole array, adding the elements back into the original input array in order. Finally we remove any ‘empty’ pigeonholes using the filter method.

Here’s an example implementation of the Pigeon Sort Algorithm in TypeScript:

function pigeonSort(nums: number[]) {
    let min = Math.min(...nums);
    let max = Math.max(...nums);
    let range = max - min + 1;
    let aux = new Array(range).fill(undefined);

    for (let i = 0; i < nums.length; i++) {
      aux[nums[i] - min] = nums[i];
    }

    for (let i = 0; i < aux.length; i++) {
      nums[i] = aux[i];
    }

    return nums.filter((n) => Number.isInteger(n));
  }

By calculating the minimum and maximum numbers in the input array, we can determine the size of the auxiliary array. To position the pigeon in its correct pigeonhole, we subtract the minimum value from the pigeon's value because the indices of the auxiliary array start from zero, and we want to map our input's minimum value to that zeroth index, thereby determining the correct index position (e.g if the minimum value is 5, we want to map value 5 to index 0 and value 6 to index 1 etc). The final line filters out all the empty values by filtering out undefined items, which we pre-filled into each pigeonhole when initialising the auxiliary array. In other words, we filter out the empty pigeonholes.

Applying the Pigeonhole Principle

The next day, I saw a coding challenge that went along the lines of:

Given an array of integers, find the first missing positive integer in linear time. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.

For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.

As I had just been playing around with Pigeon Sort, applying a similar strategy using the Pigeonhole principle seemed like a good place to start. We are essentially trying to put each “pigeon” (positive number) into its “pigeonhole” (index in the array). Once a number is in its corresponding index, we can easily check for missing positive integers by looking at each positive integer “pigeonhole” in turn and returning the first index where there was no “pigeon” so to speak. This was my initial solution:

function findMissingInt(nums: number[]): number {
  const aux = [];

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) {
      aux[nums[i]] = nums[i];
    }
  }

  for (let i = 1; i < aux.length; i++) {
    if (aux[i] == undefined) {
      return i;
    }
  }

  return auxArr.length;
}

This works in linear time and linear space as we needed to create an auxiliary array with a length proportional to the length of the input array. You may notice that I do not need to calculate the minimum value because in this case, when viewing the pigeonholes I do want to check from the first positive integer (1). And if that is empty then the first missing positive integer would indeed be 1.

The bonus follow up to this challenge was:

Find the first missing positive integer in linear time and constant space. You can modify the input array in-place.

I eventually arrived at a working solution which still uses a hint of the pigeonhole principle, but more closley resembles the Counting Sort algorithm. I won’t say anymore to allow you to tackle this yourself should you wish to!

Conclusion

The Pigeonhole Principle is a simple concept with many applications in mathematics and computer science. We’ve shown how it can be used in the Pigeon Sort Algorithm and to solve a specific problem. The next time you encounter a problem that involves distributing items into groups, remember the Pigeonhole Principle and see if it can help you find a solution.