3
\$\begingroup\$

I got the original problem from Leetcode for top k frequent elements, But I decide to simplify the problem just top 2 elements to make it simpler to solve.

// Given an array, return an array of the top 2 most elements.
// Input: [1, 2, 3, 4, 5, 3, 4] | Output: [3, 4]
// Input: [2, 2, 3, 2, 4, 3, 4] | Output: [2,4]

const topTwoElement = nums => {
  const arr = [];
  nums.forEach(num => {
    arr[num] ? arr[num][1]++ : arr[num] = [num, 1];
  }); 

  arr.sort((a, b) => b[1] - a[1]);
  return [arr[0][0], arr[1][0]];
};

console.log(topTwoElement([3, 2, 3, 4, 5, 3, 4])); //[3,4]
console.log(topTwoElement([2, 2, 3, 2, 4, 3, 4])); //[2,4]
\$\endgroup\$
3
\$\begingroup\$

Avoid the sort

You are almost there. But there is room for some improvements

Sparse array

Using an array to store number frequency works. Javascript will know to create a sparse array, and will sort such arrays using only the elements in it.

A spare array is an array that is not continuous. This is done to reduce the memory use. However there is a penalty for the memory saved, and that is it takes longer to access each item, as the index is used to find the real index, which then can get the item.

For a standard array, the index is used directly to get the item.

Sort is complex

The sort is an expensive operation and as you are only needing the top two you can store the top two results as you count the frequency of numbers.

This also means you don't need to store the number you are counting with each count, just how many there are.

The logic goes like this, see rewrite for implmentation

if frequency greater than second place
   if frequency greater than first place
      if first place the same value
          set the new first place frequency
      else
          move first place to second
          set first place to the new first 
   else
       set the new second place 

When done just return the first and second values.

It could also be done using a Map, but you would do that if the items to count were not able to be indexes (eg words).

More than one correct answer

The is a possibility that all values have the same frequency. That means that any two will be correct. Or as your second test [2, 2, 3, 2, 4, 3, 4] there are two correct answers [2,3] or [2,4]. As there are no rules for this any of the correct answers will do.

for loops are better than Array.forEach

Using a for loop to iterate over the array is more performant than using the array.forEach function.

A rewrite.

The rewrite avoids the sort

const topTwoElement = nums => {
    const arr = [];

    const first = {count : 0, value : null};
    const second = {count : 0, value : null};
    for (const num of nums) {

        if (arr[num]) { arr[num] += 1 }
        else { arr[num] = 1 }
        
        // to avoid having to index into the sparse array in the 
        // code to test for top two
        const count = arr[num];

        if (count > second.count) {
            if (count > first.count) {
                if (first.value === num) {
                    first.count = count
                } else {
                    second.count = first.count;
                    second.value = first.value;
                    first.count = count;
                    first.value = num;
                }
            } else {
                second.count = count;
                second.value = num;
            }
        }
    }
    return [first.value, second.value];
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.