Welcome to Subscribe On Youtube

2671. Frequency Tracker

Description

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 occurence 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.

 

Example 1:

Input
["FrequencyTracker", "add", "add", "hasFrequency"]
[[], [3], [3], [2]]
Output
[null, null, null, true]

Explanation
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(3); // The data structure now contains [3]
frequencyTracker.add(3); // The data structure now contains [3, 3]
frequencyTracker.hasFrequency(2); // Returns true, because 3 occurs twice

Example 2:

Input
["FrequencyTracker", "add", "deleteOne", "hasFrequency"]
[[], [1], [1], [1]]
Output
[null, null, null, false]

Explanation
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.add(1); // The data structure now contains [1]
frequencyTracker.deleteOne(1); // The data structure becomes empty []
frequencyTracker.hasFrequency(1); // Returns false, because the data structure is empty

Example 3:

Input
["FrequencyTracker", "hasFrequency", "add", "hasFrequency"]
[[], [2], [3], [1]]
Output
[null, false, null, true]

Explanation
FrequencyTracker frequencyTracker = new FrequencyTracker();
frequencyTracker.hasFrequency(2); // Returns false, because the data structure is empty
frequencyTracker.add(3); // The data structure now contains [3]
frequencyTracker.hasFrequency(1); // Returns true, because 3 occurs once

 

Constraints:

  • 1 <= number <= 105
  • 1 <= frequency <= 105
  • At most, 2 * 105 calls will be made to add, deleteOne, and hasFrequency in total.

Solutions

  • class FrequencyTracker {
        private Map<Integer, Integer> cnt = new HashMap<>();
        private Map<Integer, Integer> freq = new HashMap<>();
    
        public FrequencyTracker() {
        }
    
        public void add(int number) {
            int f = cnt.getOrDefault(number, 0);
            if (freq.getOrDefault(f, 0) > 0) {
                freq.merge(f, -1, Integer::sum);
            }
            cnt.merge(number, 1, Integer::sum);
            freq.merge(f + 1, 1, Integer::sum);
        }
    
        public void deleteOne(int number) {
            int f = cnt.getOrDefault(number, 0);
            if (f == 0) {
                return;
            }
            freq.merge(f, -1, Integer::sum);
            cnt.merge(number, -1, Integer::sum);
            freq.merge(f - 1, 1, Integer::sum);
        }
    
        public boolean hasFrequency(int frequency) {
            return freq.getOrDefault(frequency, 0) > 0;
        }
    }
    
    /**
     * Your FrequencyTracker object will be instantiated and called as such:
     * FrequencyTracker obj = new FrequencyTracker();
     * obj.add(number);
     * obj.deleteOne(number);
     * boolean param_3 = obj.hasFrequency(frequency);
     */
    
  • class FrequencyTracker {
    public:
        FrequencyTracker() {
        }
    
        void add(int number) {
            int f = cnt[number];
            if (f > 0) {
                freq[f]--;
            }
            cnt[number]++;
            freq[f + 1]++;
        }
    
        void deleteOne(int number) {
            int f = cnt[number];
            if (f == 0) {
                return;
            }
            freq[f]--;
            cnt[number]--;
            freq[f - 1]++;
        }
    
        bool hasFrequency(int frequency) {
            return freq[frequency] > 0;
        }
    
    private:
        unordered_map<int, int> cnt;
        unordered_map<int, int> freq;
    };
    
    /**
     * Your FrequencyTracker object will be instantiated and called as such:
     * FrequencyTracker* obj = new FrequencyTracker();
     * obj->add(number);
     * obj->deleteOne(number);
     * bool param_3 = obj->hasFrequency(frequency);
     */
    
  • class FrequencyTracker:
        def __init__(self):
            self.cnt = defaultdict(int)
            self.freq = defaultdict(int)
    
        def add(self, number: int) -> None:
            if self.freq[self.cnt[number]] > 0:
                self.freq[self.cnt[number]] -= 1
            self.cnt[number] += 1
            self.freq[self.cnt[number]] += 1
    
        def deleteOne(self, number: int) -> None:
            if self.cnt[number] == 0:
                return
            self.freq[self.cnt[number]] -= 1
            self.cnt[number] -= 1
            self.freq[self.cnt[number]] += 1
    
        def hasFrequency(self, frequency: int) -> bool:
            return self.freq[frequency] > 0
    
    
    # Your FrequencyTracker object will be instantiated and called as such:
    # obj = FrequencyTracker()
    # obj.add(number)
    # obj.deleteOne(number)
    # param_3 = obj.hasFrequency(frequency)
    
    
  • type FrequencyTracker struct {
    	cnt  map[int]int
    	freq map[int]int
    }
    
    func Constructor() FrequencyTracker {
    	return FrequencyTracker{map[int]int{}, map[int]int{} }
    }
    
    func (this *FrequencyTracker) Add(number int) {
    	f := this.cnt[number]
    	if f > 0 {
    		this.freq[f]--
    	}
    	this.cnt[number]++
    	this.freq[f+1]++
    }
    
    func (this *FrequencyTracker) DeleteOne(number int) {
    	f := this.cnt[number]
    	if f == 0 {
    		return
    	}
    	this.freq[f]--
    	this.cnt[number]--
    	this.freq[f-1]++
    }
    
    func (this *FrequencyTracker) HasFrequency(frequency int) bool {
    	return this.freq[frequency] > 0
    }
    
    /**
     * Your FrequencyTracker object will be instantiated and called as such:
     * obj := Constructor();
     * obj.Add(number);
     * obj.DeleteOne(number);
     * param_3 := obj.HasFrequency(frequency);
     */
    
  • class FrequencyTracker {
        private cnt: Map<number, number>;
        private freq: Map<number, number>;
    
        constructor() {
            this.cnt = new Map();
            this.freq = new Map();
        }
    
        add(number: number): void {
            const f = this.cnt.get(number) || 0;
            if (f > 0) {
                this.freq.set(f, (this.freq.get(f) || 0) - 1);
            }
            this.cnt.set(number, f + 1);
            this.freq.set(f + 1, (this.freq.get(f + 1) || 0) + 1);
        }
    
        deleteOne(number: number): void {
            const f = this.cnt.get(number) || 0;
            if (f === 0) {
                return;
            }
            this.freq.set(f, (this.freq.get(f) || 0) - 1);
            this.cnt.set(number, f - 1);
            this.freq.set(f - 1, (this.freq.get(f - 1) || 0) + 1);
        }
    
        hasFrequency(frequency: number): boolean {
            return (this.freq.get(frequency) || 0) > 0;
        }
    }
    
    /**
     * Your FrequencyTracker object will be instantiated and called as such:
     * var obj = new FrequencyTracker()
     * obj.add(number)
     * obj.deleteOne(number)
     * var param_3 = obj.hasFrequency(frequency)
     */
    
    

All Problems

All Solutions