Frequency Counter Using JavaScript

There are many problem-solving patterns and approaches while solving a problem, But today I am going to talk about Frequency Counter Method only.

In Frequency counter we use an object to collect multiple inputs with their count. The advantage is it usually will have big O of O(n) time complexity compared to other approaches that will have big O of O(n2).

This article will explain the Frequency Counter using an example ;

Question.?Given a string S, count the frequency of characters in the string S i.e. which character 
          is present how many times in the string
          
          Input:
          
          hello world
          
          where:
          
          First line represents the input string
          
          Output:
          
          d 1
          e 1
          h 1
          l 3
          o 2
          r 1
          w 1
          
          Explanation: Print the count of each distinct letter present in string S.
          
          Assumptions:
          
          String contains only lower case letters
          
          Length of string S can be 0 to 10000g        

Solution Using Nested Loops :

          let s = "hello world

          s= s.split(" ").filter(a=>a).join("").split("").sort()

          let visited = []
          
          
          for (var i=0;i<s.length;i++){

          ? ? if(visited.indexOf(s[i]) == -1){

          ? ? ? ? visited.push(s[i])

          ? ? }

          }

          for (var k=0;k<visited.length;k++){

          ? ? var count = 0

          ? ? for(let j=0;j<s.length;j++){

          ? ? ? ? if(visited[k]==s[j]){

          ? ? ? ? ? ? count++ 
          ? ? ? ? }

          ? ? }

          ? ? console.log((visited[k]+ " "+count))

          }        

Here we see its just one loop but we are using indexOf so it will be big O of O(n2) time complexity while traversing through s to push all available element in s only once into visited array neglecting the element to duplicate inside visited. Also below that we are using nestedd loop whose tiime complexity will also be big O of O(n2). So, the overall time complecity for this solution using nested loop will be big O of O(n2). We can solve this problem in big O(n) using javascript object.

Solution using Frequency counter pattern

        let s = "hello world
        
        
        let obj = {}
        
        for(let i in s){
        
        ? ? if(s[i] == " ") {
        
        ? ? ? ? continue
        
        ? ? }
        
        ? ?if( obj[s[i]]){
        
        ? ? obj[s[i]]++
        
        ? ?}
        
        ? ?else{
        
        ? ? obj[s[i]] = 1
        
        ? ?}
        
        }
        
        for(let k in obj){
        
        ? ? console.log(k,obj[k])
        
        }
      
                

In above code if element of string is already pressent in object we are increasing the count of values of that object and if not we are assigning it with an initial value of one respectively, with its key being its elements and its value being frequency. And one thing to keep in mind is the key of an object is always unique. So we can clearly see the time complexity using this method will be big O of O(n), which is less than the time complexity we get through nested loop.

This is one among many problem-solving patterns, Practicing many patterns will help us become better at problem-solving.