Solve a Frequency Counter Problem in JavaScript with an Empty Object

Creating an empty object in JavaScript can help to solve technical interview problems that ask you to find a value's frequency in an array.

Create an Empty Object

To create an empty object, set a variable equal to hashes. Note that unlike arrays, there is no order in an object and it uses key/value pairings instead of indexes.

let myObject = {};

Create Keys from an Array

Given an array, you can iterate and assign the array's values as the object's keys.

Code:

for (let i = 0; i < array.length; i++){ // A
   let key = array[i];                  // B
   if (myObject[key]){                  // C
        myObject[key] += 1;             // D
   } else {                             // E
        myObject[key] = 1;              // F
   }
}

Pseudocode:

• A) Iterate through the array
• B) Grab the value of each item in the array and set it to variable key
• C) If key exists as a key in myObject...
  • D) ... increment it by 1
• E) If not (key doesn't exist in myObject)...
  • F) ... create key in myObject and set it equal to 1

Refactored Code using Conditional (ternary) operator:

for (let i = 0; i < array.length; i++){
   let key = array[i];
   if myObject[key] ? myObject[key] += 1 : myObject[key] = 1
}

How to Access a Value in an Object

To access a key's value in an object is the same as accessing an index in an array:

myObject[value];

Solve a Frequency Counter Problem

Suppose you are solving to find the only number in an array that does not repeat. Assume there is only ever 1 answer.

To solve, you could:

• A) Create an empty object
• B) Iterate through the array to capture the array's values
• C) Set the values as keys and increment on each occurrence of the array
• D) Return the key in the hash with a count of 1 to find the non-repeating number

function findUniqueNumber(array) {  
  let myObject = {};                                          // A

  for (let i = 0; i < array.length; i++){                     // B
      let num = array[i];
      myObject[num] ? myObject[num] +=1 : myObject[num] = 1   // C
  }

  for (let key in myObject){
       if (myObject[key] === 1) return key;                   // D
  }
}

findUniqueNumber( [4, 6, 5, 17, 3, 5, 17, 88, 4, 88, 3] )     // 6

Big O of using an Object

Using brute force gives a Big O of quadratic O(n^2) because it requires two nested loops. As n inputs grows, it requires 2 sets of iterations to grab the first number and the next number to compare and repeats through the array's length.

By creating an object, we can reduce Big O to linear O(n). Here, we iterate twice through the array but on independent loops (2n can be simplified to n). So generally speaking, performance is only dependent on the size of the input array.