Knowing What to Track: Introduction

Let’s go over the Knowing What to Track pattern, its real-world applications, and some problems we can solve with it.

Overview

The knowing what to track pattern is mostly used to find the frequency count of the data. It’s able to avoid the O(n2)O(n^2) time by simplifying the problem and identifying certain key numeric properties in the given data.

This pattern is often used with an array and strings, and helps solve problems that require counting data frequencies or returning boolean values (TRUE/FALSE). More often than not, the problems that can be solved using this pattern include comparison and checks, such as the examples given below:

  • Check if the values of the first array have corresponding squared values in the second array
  • Check if two strings are anagrams
  • Check if the player wins the game

Hashmaps can store the frequency count of the given data while allowing search and retrieval of data in constant O(1)O(1) time.

There might be a chance to solve some problems without using hash maps. We can use separate arrays or variables to store the frequency counts in those cases.

Let’s look at the following illustration to understand how we can use hash maps to keep the counts of given data:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.