Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in JavaScript

Problem: All O`one Data Structure

Explore how to build an efficient AllOne data structure that stores string keys and tracks their frequencies. Learn to implement operations for incrementing, decrementing counts, and retrieving max or min frequency keys, all running in constant time using a doubly linked list and hash maps.

We'll cover the following...

Statement

Design a data structure that stores string keys along with their frequencies and supports efficient updates and queries.

Implement the AllOne class:

  • AllOne() → Initializes the data structure.

  • inc(key) → Increases the count of key by 1. If the key does not exist, insert it with count 1.

  • dec(key) → Decreases the count of key by 1. If the count becomes 0, remove the key. It is guaranteed the key exists when dec is called.

  • getMaxKey() → Returns any key with the highest count. If empty, return "".

  • getMinKey() → Returns any key with the lowest count. If empty, return "".

All operations must run in average O(1)O(1) time.

Examples

canvasAnimation-image
1 / 8

Try it yourself

Implement your solution in the following coding playground.

JavaScript
usercode > AllOne.js
class AllOne {
    constructor() {
        // Initialize your data structure here
    }
    inc(key) {
        // Implement logic to increment the count of `key`
    }
    dec(key) {
        // Implement logic to decrement the count of `key`
    }
    getMaxKey() {
        // Return one of the keys with maximal value
        return "";
    }
    getMinKey() {
        // Return one of the keys with minimal value
        return "";
    }
}
export default AllOne;
All O`one Data Structure

Solution

The solution uses a doubly linked list combined with two hash maps to support efficient retrieval of the highest- and lowest-frequency keys in constant time. The linked list keeps nodes arranged by frequency in ascending order, where each node stores a specific frequency count and a set of keys that all share that count. One hash map called ...