DEV Community

Samantha Diaz
Samantha Diaz

Posted on

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 = {};
Enter fullscreen mode Exit fullscreen mode

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
   }
}
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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];
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)