CODEWITHSUNDEEP
javascriptarraysfrequency
Asher
Asher

Reputation: 317

Finding the second lowest frequent element from an array of integers?

I'm looking to answer a coding challenge in JavaScript that I'm stuck on, here's the question:

Write a function which accepts an array of integers and returns an element of that array.

The function should determine the frequency of each element (how many times the element appears in the array) and whenever possible should return the element with the second-lowest frequency. Otherwise it should return the integer with the lowest frequency.

If there is more than one element satisfying the requirements then the second smallest one (according to value) should be returned.

Example outputs:

secondLowest( [4, 3, 1, 1, 2] ) === 1

secondLowest( [4, 3, 1, 1, 2, 2] ) === 2

secondLowest( [4, 3, 1, 2] ) === 2

This is what I've got so far although don't know how best to go about answering it after this:


    function mode(array) {
  if (array.length == 0) return null;
  let modeMap = {};
  let maxEl = array[0],
    maxCount = 1;
  for (let i = 0; i < array.length; i++) {
    var el = array[i];
    if (modeMap[el] == null) modeMap[el] = 1;
    else modeMap[el]++;
    if (modeMap[el] > maxCount) {
      maxEl = el;
      maxCount = modeMap[el];
    }
  }
  return maxEl;
}

Upvotes: 1

Views: 578

Answers (1)

Gershom Maes
Gershom Maes

Reputation: 8140

I was determined to give a generic, parameterized function, where no number is hardcoded.

Your example involved two hardcoded values:

  • The second least frequency should be selected
  • In cases of ties, the second least value should be selected

The following code works like this:

  • Get the frequency of each input value
  • Group together all values with the same frequency.
  • Sort these grouped pairs by frequency and select the nth-lowest (in your case, n=2)
  • If the nth-lowest frequency has multiple pairs, sort these pairs by value, and select the mth-lowest pair (in your case, m=2)
  • Return the value of this final pair

The m and n parameters I refer to here are called freqInd and valInd in the code. Note that in order to select the second-lowest frequency, freqInd should be 1, not 2 (since 0 would select the lowest, and therefore 1 selects the second-lowest).

let lowestFreqVal = (freqInd, valInd, values) => {
  
  // Calculate frequencies in a map
  let f = new Map();
  for (let v of values) f.set(v, (f.get(v) || 0) + 1);
  
  // Group together all val/freq pairs with the same frequency
  let ff = new Map();
  for (let [ val, freq ] of f) ff.set(freq, (ff.get(freq) || []).concat([ val ]));
  
  // Sort these groups by frequency
  let byFreq = [ ...ff ].sort(([ freq1 ], [ freq2 ]) => freq1 - freq2);  
  
  // Here are all the items of the `freqInd`-th lowest frequency, sorted by value
  // Note that `[1]` returns an array of integers at the frequency, whereas `[0]` would return the frequency itself
  let lowestItems = byFreq[ Math.min(byFreq.length - 1, freqInd) ][1]
    .sort((v1, v2) => v1 - v2);
  
  // Return the `valInd`-th lowest value
  return lowestItems[ Math.min(lowestItems.length - 1, valInd) ];
  
};

console.log('Some random examples:');
for (let i = 0; i < 10; i++) {
  // An array of random length, full of random integers
  let arr = [ ...new Array(3 + Math.floor(Math.random() * 5)) ]
    .map(v => Math.floor(Math.random() * 4));
  
  // Show the result of `lowestFreqVal` on this random Array
  console.log(`lowestFreqVal(1, 1, ${JSON.stringify(arr)}) = ${lowestFreqVal(1, 1, arr)}`);
}

This is not an optimal solution, since it resorts to using sort. It's known that the problem of finding some nth-maximal value in a list can be implemented to have a better runtime than sort (and a significantly better runtime when n is a small value - we can see this intuitively because if n=0, a single pass (O(n)) does the trick).

Upvotes: 2

Related Questions