LeetCode 432: All O`one Data Structure Solution

Master LeetCode problem 432 (All O`one Data Structure), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

432. All O`one Data Structure

Hard

Hash Table Linked List Design Doubly-Linked List

Problem Explanation

Explanation

To solve this problem, we can use a combination of a hashmap and a doubly linked list. The hashmap will store the key along with its corresponding count node in the linked list. The linked list will maintain the counts in ascending order.

Algorithm:

Define two classes: Node to represent a count node in the linked list and AllOne to implement the data structure.
In the Node class, store the count, maintain a set of keys with that count, and pointers to the previous and next nodes.
In the AllOne class, maintain a hashmap to map keys to their corresponding count nodes and maintain pointers to the head and tail of the linked list.
Implement the inc method to increment the count of a key by 1. If the key does not exist, insert it with count 1.
Implement the dec method to decrement the count of a key by 1. If the count becomes 0, remove the key from the data structure.
Implement the getMaxKey method to return a key with the maximal count (from the tail of the linked list).
Implement the getMinKey method to return a key with the minimum count (from the head of the linked list).

Time Complexity:

All operations run in O(1) time complexity on average.

Space Complexity:

O(n) where n is the number of keys.

Solution Code

class AllOne {
    private static class Node {
        int count;
        Set<String> keys;
        Node prev;
        Node next;
        
        Node(int count) {
            this.count = count;
            keys = new HashSet<>();
        }
    }
    
    private Map<String, Node> keyToNode;
    private Node head;
    private Node tail;
    
    public AllOne() {
        keyToNode = new HashMap<>();
        head = new Node(Integer.MIN_VALUE);
        tail = new Node(Integer.MAX_VALUE);
        head.next = tail;
        tail.prev = head;
    }
    
    public void inc(String key) {
        Node node = keyToNode.get(key);
        if (node == null) {
            Node nextNode = head.next;
            if (nextNode.count != 1) {
                nextNode = addNodeAfter(new Node(1), head);
            }
            nextNode.keys.add(key);
            keyToNode.put(key, nextNode);
        } else {
            Node nextNode = node.next;
            if (nextNode.count != node.count + 1) {
                nextNode = addNodeAfter(new Node(node.count + 1), node);
            }
            nextNode.keys.add(key);
            keyToNode.put(key, nextNode);
            node.keys.remove(key);
            if (node.keys.isEmpty()) {
                removeNode(node);
            }
        }
    }
    
    public void dec(String key) {
        Node node = keyToNode.get(key);
        if (node != null) {
            if (node.count == 1) {
                node.keys.remove(key);
                keyToNode.remove(key);
                if (node.keys.isEmpty()) {
                    removeNode(node);
                }
            } else {
                Node prevNode = node.prev;
                if (prevNode.count != node.count - 1) {
                    prevNode = addNodeAfter(new Node(node.count - 1), prevNode);
                }
                prevNode.keys.add(key);
                keyToNode.put(key, prevNode);
                node.keys.remove(key);
                if (node.keys.isEmpty()) {
                    removeNode(node);
                }
            }
        }
    }
    
    public String getMaxKey() {
        return tail.prev == head ? "" : tail.prev.keys.iterator().next();
    }
    
    public String getMinKey() {
        return head.next == tail ? "" : head.next.keys.iterator().next();
    }
    
    private Node addNodeAfter(Node newNode, Node prevNode) {
        newNode.prev = prevNode;
        newNode.next = prevNode.next;
        prevNode.next.prev = newNode;
        prevNode.next = newNode;
        return newNode;
    }
    
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 432 (All O`one Data Structure)?

This page provides optimized solutions for LeetCode problem 432 (All O`one Data Structure) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 432 (All O`one Data Structure)?

The time complexity for LeetCode 432 (All O`one Data Structure) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 432 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 432 in Java, C++, or Python.

Back to LeetCode Solutions