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

Problem: All O`one Data Structure

Understand how to design and implement an AllOne data structure that tracks string keys and their frequencies. This lesson guides you through using a doubly linked list combined with two hash maps to support constant-time insertions, deletions, and key frequency queries. You will learn how to maintain frequency nodes and retrieve keys with maximum and minimum counts efficiently.

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