Using Objects to Count Frequency

I've been doing a course on data structures and algorithms and I've noticed a pattern of using objects in JavaScript to count the frequency of values in strings and arrays.

Why use an Object

When talking about algorithms or data structures it is important to understand Big-O notation. I won't go to into detail on what that entails, but for this article we will briefly look at objects and how fast it is to add/access a key-value pair. It is important to note that while objects and maps in JavaScript are similar enough for our purposes, there are some subtle differences relevant stackoverflow article. I will just refer to these types of data structures as objects in this article.

Object Time Complexity

Action	Time Complexity
Insert	O(1) : Constant
Remove	O(1) : Constant
Access	O(1) : Constant
Search	O(N) : Linear

As we can see from our table, objects are very fast at inserting, removing, and accessing key-value pairs. Note: It is is important to note that accessing an element in an array takes constant time ex. names[0] is just as fast as names.sam. The difference is that we can immediately see if there is a key called "sam" in our names object as opposed to something like names.indexOf("sam") which loops over the entire array (linear time). If this doesn't make sense, check out this video Introduction to Big O Notation and Time Complexity.

The Problem

So now that we know that objects are faster than arrays to check if a certain value(the key) exists, let's look at a problem.

Determine if two words are anagrams of each other

Note: an anagram is a word or phrase formed by rearranging the letters of another word or phrase.

The Solution

While there are almost always multiple ways to solve a problem in computer science, let's go ahead and use an object to count the frequency of each character in our strings.

const isAnagram = (str1, str2) => {
  if (str1.length !== str2.length) {
    return false;
  }

  let freqCounter1 = {};
  let freqCounter2 = {};

  for (let char of str1) {
    freqCounter1[char] = (freqCounter1[char] || 0) + 1;
  }
  for (let char of str2) {
    freqCounter2[char] = (freqCounter2[char] || 0) + 1;
  }

  for (let key in freqCounter1) {
    if (freqCounter1[key] !== freqCounter2[key]) {
      return false;
    }
  }
  return true;
};

Let's go over the code line by line.

1. if (str1.length !== str2.length) {

Here we are just short-circuiting our function to return false if the lengths of the strings don't match up.

2. let freqCounter1 = {};

Declaring our frequency counting objects.

3. for (let char of str1) {

Looping through each character of our first string. (Time complexity is linear)

4. freqCounter1[char] = (freqCounter1[char] || 0) + 1;

This is where we are actually adding each character to the frequency counter object and initially setting the value to 0+1. If our character key already exists then its value is added to 1 (incremented). We do the same for our second string.

5. for (let key in freqCounter1) {

Looping through the keys in our frequency counter object. (Read more about the difference between of and in when looping through arrays and objects at stackoverflow)

6. if (freqCounter1[key] !== freqCounter2[key]) {

Here we are checking the frequencies for each character and returning false if they don't match.

Conclusion

Using objects, maps, hashes, dictionaries, or whatever your favorite language calls these data structures as a frequency counter should always be an option you are aware of. It doesn't work for every problem, but it can sometime provide the most optimal solution (2 sum problem, I'm looking at you). Review some problems and see where you can use key-value pairs.