Frequency Tracker - Practice Coding Problems

Frequency Tracker - Problem

Design a data structure that keeps track of the values in it and answers some queries regarding their frequencies.

Implement the FrequencyTracker class:

FrequencyTracker(): Initializes the FrequencyTracker object with an empty array initially.
void add(int number): Adds number to the data structure.
void deleteOne(int number): Deletes one occurrence of number from the data structure. The data structure may not contain number, and in this case nothing is deleted.
bool hasFrequency(int frequency): Returns true if there is a number in the data structure that occurs frequency number of times, otherwise, it returns false.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["FrequencyTracker", "add", "add", "hasFrequency"], values = [0, 3, 3, 2]

› Output: [null, null, null, true]

💡 Note: Create tracker, add 3 twice (frequency 2), hasFrequency(2) returns true since 3 appears 2 times

Example 2 — Delete Operations

$ Input: operations = ["FrequencyTracker", "add", "deleteOne", "hasFrequency"], values = [0, 1, 1, 1]

› Output: [null, null, null, false]

💡 Note: Add 1, delete 1, now no numbers exist so hasFrequency(1) returns false

Example 3 — Multiple Numbers

$ Input: operations = ["FrequencyTracker", "add", "add", "add", "hasFrequency", "hasFrequency"], values = [0, 1, 1, 2, 2, 1]

› Output: [null, null, null, null, true, true]

💡 Note: Add 1,1,2. Number 1 has frequency 2, number 2 has frequency 1. Both queries return true

Constraints

1 ≤ number ≤ 10⁵
1 ≤ frequency ≤ 10⁵
At most 2 × 10⁵ calls to add, deleteOne, and hasFrequency

Visualization

Tap to expand

Understanding the Visualization

Input

Sequence of add/delete/query operations

Process

Maintain frequency counts efficiently

Output

Return boolean results for hasFrequency queries

Key Takeaway

🎯 Key Insight: Using two hash maps allows instant frequency lookups while maintaining counts efficiently

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is to maintain two hash maps: one tracking the count of each number, and another tracking how many numbers have each frequency. This allows all operations to run in O(1) time. Best approach uses dual hash maps with Time: O(1), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Count Every Query	O(n)	O(n)	Store numbers in array, count frequencies by scanning entire array each time
Optimized - Dual Hash Maps	O(1)	O(n)	Use two hash maps: one for number counts, another for frequency counts

Brute Force - Count Every Query — Algorithm Steps

Store numbers in dynamic array
For add: append to array
For delete: find and remove first occurrence
For hasFrequency: scan array, count all numbers, check if any count equals target

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Numbers

Numbers are added to array

Scan Array

For hasFrequency, count all occurrences

Check Match

Return true if any count matches target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_SIZE 10000

typedef struct {
    int numbers[MAX_SIZE];
    int size;
} FrequencyTracker;

FrequencyTracker* frequencyTrackerCreate() {
    FrequencyTracker* ft = (FrequencyTracker*)malloc(sizeof(FrequencyTracker));
    ft->size = 0;
    return ft;
}

void frequencyTrackerAdd(FrequencyTracker* obj, int number) {
    if (obj->size < MAX_SIZE) {
        obj->numbers[obj->size++] = number;
    }
}

void frequencyTrackerDeleteOne(FrequencyTracker* obj, int number) {
    for (int i = 0; i < obj->size; i++) {
        if (obj->numbers[i] == number) {
            for (int j = i; j < obj->size - 1; j++) {
                obj->numbers[j] = obj->numbers[j + 1];
            }
            obj->size--;
            return;
        }
    }
}

bool frequencyTrackerHasFrequency(FrequencyTracker* obj, int frequency) {
    if (frequency == 0) return false;
    int counts[MAX_SIZE] = {0};
    int unique[MAX_SIZE];
    int uniqueCount = 0;
    
    // Count frequencies
    for (int i = 0; i < obj->size; i++) {
        int num = obj->numbers[i];
        int found = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (unique[j] == num) {
                counts[j]++;
                found = 1;
                break;
            }
        }
        if (!found) {
            unique[uniqueCount] = num;
            counts[uniqueCount] = 1;
            uniqueCount++;
        }
    }
    
    for (int i = 0; i < uniqueCount; i++) {
        if (counts[i] == frequency) return true;
    }
    return false;
}

int main() {
    // Simple implementation for demonstration
    printf("[null,null,null,true,null,false]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each hasFrequency query scans the entire array of n elements

✓ Linear Growth

Space Complexity

O(n)

Array stores all n numbers that were added

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Count Every Query — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler