Find the most common number in an array of numbers

Question

Exercise description:

Find the most common number in an array of numbers.

Create a software that takes an array of numbers as parameter. The return of the function shall be the most common number.

Example: Assume that the list is ... 1, 5, 1, 3, 5, 5, 2.

The program will output 5, because this is the most common number.

Note that if there is more than one most common number, the program will just print one of the most common numbers.

My solution (written in TypeScript):

let numbers: number[] = [1, 5, 1, 3, 5, 5, 2];

namespace Main {
  export function searchMostCommonNumber(arr: number[] = []): number {
    let current: number = 0;
    let max: number = 0;
    let mostCommonNumber: number = 0;
    let i: number;

    for (i = 0; i < arr.length - 1; i++) {
      let current: number = 1;
      let j: number;

      for (j = i + 1; j < arr.length; j++) {
        if (arr[i] === arr[j]) {
          current++;
        }
      }

      if (current > max) {
        max = current;
        mostCommonNumber = arr[i];
      }
    }

    return mostCommonNumber;
  }
}

console.log(Main.searchMostCommonNumber(numbers));

Live demo (with compiled code):

var numbers = [1, 5, 1, 3, 5, 5, 2];
var Main;
(function(Main) {
  function searchMostCommonNumber(arr) {
    if (arr === void 0) {
      arr = [];
    }
    var current = 0;
    var max = 0;
    var mostCommonNumber = 0;
    var i;
    for (i = 0; i < arr.length - 1; i++) {
      var current_1 = 1;
      var j = void 0;
      for (j = i + 1; j < arr.length; j++) {
        if (arr[i] === arr[j]) {
          current_1++;
        }
      }
      if (current_1 > max) {
        max = current_1;
        mostCommonNumber = arr[i];
      }
    }
    return mostCommonNumber;
  }
  Main.searchMostCommonNumber = searchMostCommonNumber;
})(Main || (Main = {}));
console.log('The most common number is :', Main.searchMostCommonNumber(numbers));

What do you think about my solution?

Is there a better way to accomplish the task? What would you have done differently?

Looking forward to reading your comments and answers.

Answer 1

For small arrays as input your script's performance is very good. Let me show you a different approach which might especially improve readability and might also increase performance for larger inputs and multiple runs.

.reduce()

Instead of iterating through the elements manually, I've used Array.prototype.reduce():

The reduce() method applies a function against an accumulator and each element in the array (from left to right) to reduce it to a single value.

The function has two steps now which both use reduce():

1. Reduce the input into an object that holds each number and its count as key/value-pairs.
2. Reduce this object to find the key with the highest value.

---

function findMode(numbers) {
    let counted = numbers.reduce((acc, curr) => { 
        if (curr in acc) {
            acc[curr]++;
        } else {
            acc[curr] = 1;
        }

        return acc;
    }, {});

    let mode = Object.keys(counted).reduce((a, b) => counted[a] > counted[b] ? a : b);

    return mode;
}

---

Performance

In the comments we had a lot of discussion about performance about this and other solutions.

One requested improvement was to calculate the mode directly in the first reduce call. It could look like this:

function findModeAlternative(numbers) {
    let max = 0;
    let mode = null;
    let counted = numbers.reduce((acc, curr) => { 
        if (curr in acc) {
            acc[curr]++;
        } else {
            acc[curr] = 1;
        }

        if (max < acc[curr]) {
            max = acc[curr];
            mode = curr;
        }

        return acc;
    }, {});

    return mode;
}

Unfortunately it didn't improve performance in Chrome and Firefox.

---

Then Blindman67 suggested the naive approach with this solution:

function findCommon(arr) {
    var max = 1,
        m = [],
        val = arr[0],
        i, x;

    for(i = 0; i < arr.length; i ++) {
        x = arr[i]
        if (m[x]) {
            ++m[x] > max && (max = m[i], val = x);
        } else {
            m[x] = 1;
        }
    } return val;    
}

Which will increase performance significantly in Firefox, but performs about the same in Chrome. Keep in mind, that functions like reduce, map etc. come with some overhead.

---

Finally the approach using map in Gerrit0's answer also increases the performance drastically opposed to the original.

---

Test

I've created a test, so you can check the performance of each variant yourself. The test uses two different arrays with ca. 500 elements each and runs every function 100000 times:

• test array A is kind of mixed
• test array B contains mostly one number with a few exceptions

These are the results from Chrome 61 on macOS:

• array A "findMode": 1000ms
• array B "findMode": 950ms
• array A "findModeAlternative": 1200 ms
• array B "findModeAlternative": 1100 ms
• array A "findCommon": 930 ms
• array B "findCommon": 960 ms
• array A "mostCommonNumber": 1700 ms
• array B "mostCommonNumber": 1300 ms
• array A "searchMostCommonNumber": 12697 ms
• array B "searchMostCommonNumber": 13400 ms

Try it yourself

Of course you can tweak the test and try different inputs etc.

The functions's name

As this is called mode in statistics, you could use a shorter function name like findMode()

^{Unfortunately this doesn't improve performance. This is just a personal preference}

---

^{I only included the ES6 version of the script in this answer. I didn't add the check whether the array is an array and not empty, as this will be added when compiling from TypeScript to JavaScript}

Answer 2

My approach would be slightly different.

1. Efficiency, though your current approach is memory efficient, it is O(n^2) which will make it rather slow for large arrays.

2. I don't see any reason to include a namespace. With module support, namespaces seem to add unnecessary complexity in most cases.

3. Scope variables properly. There's no reason to declare i and j outside of the loops.

4. Avoid adding types where they can be inferred. let n: number = 0 can be written as let n = 0 and Typescript can infer the type of n to be number without needing to explicitly type it (note that for complex types it is still sometimes a good idea to explicitly state the type).

5. Returning 0 for the empty array seems odd. There is no "most common number" if there are no numbers. Granted, returning NaN isn't much better (if it even is better).

Here's how I would implement this function.

function mostCommonNumber(numbers: number[]): number {
    let map = new Map<number, number>()
    for (let num of numbers) {
        map.set(num, (map.get(num) || 0) + 1)
    }

    let mostCommonNumber = NaN
    let maxCount = -1
    for (let [num, count] of map.entries()) {
        if (count > maxCount) {
            maxCount = count
            mostCommonNumber = num
        }
    }

    return mostCommonNumber
}

Demo:

function mostCommonNumber(numbers) {
    let map = new Map()
    for (let num of numbers) {
        map.set(num, (map.get(num) || 0) + 1)
    }

    let mostCommonNumber = NaN
    let maxCount = -1
    for (let [num, count] of map.entries()) {
        if (count > maxCount) {
            maxCount = count
            mostCommonNumber = num
        }
    }

    return mostCommonNumber
}

let tests = [
  [],
  [1, 2, 3, 4, 5],
  [1, 2, 3, 1, 2, 3, 1],
  [1, 5, 1, 3, 5, 5, 2]
]

for (let test of tests) {
  console.log(`[${test}] --> ${mostCommonNumber(test)}`)
}