All O`one Data Structure

Hard Design Data Structures Linked Lists Original on LeetCode

All O`one Data Structure is a hard design data structures problem solved with the linked lists pattern. The best approach, optimal (linked list of count buckets), runs in O(1) for every operation time and O(k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (hash map, scan for the extremes) up.

Problem

Design a structure AllOne that counts how many times each string key has been added, and can report a key with the largest and the smallest count at any moment.

  • inc(key) adds one to the count of key (a new key starts at 1).
  • dec(key) subtracts one from the count of key; when the count reaches 0 the key disappears. The key is guaranteed to be present.
  • getMaxKey() returns any key with the highest count, or "" if nothing is stored.
  • getMinKey() returns any key with the lowest count, or "" if nothing is stored.

All four operations should take O(1) average time.

Examples

Example 1

Input
AllOne(), inc("cat"), inc("dog"), inc("cat"), getMaxKey(), getMinKey(), dec("cat"), dec("cat"), getMaxKey()
Output
null, null, null, null, "cat", "dog", null, null, "dog"
Why
After three increments cat has 2 and dog has 1. Two decrements remove cat entirely, leaving only dog.

Example 2

Input
AllOne(), getMaxKey(), inc("a"), getMinKey(), dec("a"), getMinKey()
Output
null, "", null, "a", null, ""
Why
With no keys stored, both queries return the empty string.

Constraints

  • 1 <= key.length <= 10, lowercase English letters.
  • dec is only called on a key that is currently stored.
  • At most 5 * 10^4 calls in total.
  • Every operation should run in O(1) average time.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (hash map, scan for the extremes)O(1) for inc and dec, O(k) for the queriesO(k)
Optimal (linked list of count buckets)O(1) for every operationO(k)

1Brute force (hash map, scan for the extremes)

TimeO(1) for inc and dec, O(k) for the queriesThe queries look at all k stored keys.
SpaceO(k)One map entry per stored key.

Keep a map from key to count. inc and dec update one entry; getMaxKey and getMinKey walk over every stored key.

  1. inc: counts[key] += 1 (starting from 0).
  2. dec: if counts[key] is 1 remove the key, otherwise subtract 1.
  3. getMaxKey / getMinKey: scan all entries and return the key with the largest / smallest count, or "" if empty.
class AllOne {
    private final Map<String, Integer> counts = new HashMap<>();

    public AllOne() {}

    public void inc(String key) {
        counts.merge(key, 1, Integer::sum);
    }

    public void dec(String key) {
        int c = counts.get(key);
        if (c == 1) counts.remove(key);
        else counts.put(key, c - 1);
    }

    public String getMaxKey() {
        String best = "";
        int bestCount = 0;
        for (Map.Entry<String, Integer> e : counts.entrySet()) {
            if (e.getValue() > bestCount) {
                bestCount = e.getValue();
                best = e.getKey();
            }
        }
        return best;
    }

    public String getMinKey() {
        String best = "";
        int bestCount = Integer.MAX_VALUE;
        for (Map.Entry<String, Integer> e : counts.entrySet()) {
            if (e.getValue() < bestCount) {
                bestCount = e.getValue();
                best = e.getKey();
            }
        }
        return best;
    }
}

2Optimal (linked list of count buckets)

TimeO(1) for every operationEach operation touches a constant number of buckets and hash-set entries.
SpaceO(k)Each key lives in one bucket and one map entry; there are at most k buckets.

Keep a doubly linked list of buckets sorted by count, between two sentinels. Each bucket stores one count and the set of keys that have exactly that count; a map sends each key to its bucket. Because a count changes by exactly one, a key only moves to the neighboring bucket, which is either already there (same count) or created right next to the current one. The first real bucket holds the minimum, the last holds the maximum.

  1. inc(key): let cur be its bucket (or the head sentinel if new) and c the new count. If cur.next has count c, use it; otherwise insert a new bucket with count c after cur. Move the key there, and delete cur if it became empty.
  2. dec(key): if its count is 1, just drop it from the map. Otherwise use cur.prev if its count is c - 1, or insert a new bucket before cur. Remove the key from cur and delete cur if empty.
  3. getMaxKey: any key of the bucket before the tail sentinel ("" if the list is empty).
  4. getMinKey: any key of the bucket after the head sentinel.
class AllOne {
    private static class Bucket {
        final int count;
        final Set<String> keys = new HashSet<>();
        Bucket prev, next;

        Bucket(int count) { this.count = count; }
    }

    private final Bucket head = new Bucket(0), tail = new Bucket(0);
    private final Map<String, Bucket> where = new HashMap<>();

    public AllOne() {
        head.next = tail;
        tail.prev = head;
    }

    private Bucket insertAfter(Bucket b, int count) {
        Bucket nb = new Bucket(count);
        nb.prev = b;
        nb.next = b.next;
        b.next.prev = nb;
        b.next = nb;
        return nb;
    }

    private void removeIfEmpty(Bucket b) {
        if (b.keys.isEmpty()) {
            b.prev.next = b.next;
            b.next.prev = b.prev;
        }
    }

    public void inc(String key) {
        Bucket cur = where.get(key);
        Bucket from = cur == null ? head : cur;
        int c = from.count + 1;
        Bucket target = from.next.count == c ? from.next : insertAfter(from, c);
        target.keys.add(key);
        where.put(key, target);
        if (cur != null) {
            cur.keys.remove(key);
            removeIfEmpty(cur);
        }
    }

    public void dec(String key) {
        Bucket cur = where.get(key);
        if (cur.count == 1) {
            where.remove(key);
        } else {
            int c = cur.count - 1;
            Bucket target = cur.prev.count == c ? cur.prev : insertAfter(cur.prev, c);
            target.keys.add(key);
            where.put(key, target);
        }
        cur.keys.remove(key);
        removeIfEmpty(cur);
    }

    public String getMaxKey() {
        return tail.prev == head ? "" : tail.prev.keys.iterator().next();
    }

    public String getMinKey() {
        return head.next == tail ? "" : head.next.keys.iterator().next();
    }
}

Edge cases to test

  • Querying an empty structure returns ""
  • Decrementing a key with count 1 removes it completely
  • Several keys share the maximum or minimum count: any of them is a valid answer
  • A key is incremented after it was removed: it starts again from 1

Hints

Hint 1

A hash map from key to count makes inc and dec easy. The hard part is finding the max and min without scanning.

Hint 2

Counts only ever change by one. Group keys into buckets by count and keep the buckets sorted by count.

Hint 3

Use a doubly linked list of buckets (each with a set of keys) plus a map from key to its bucket. Moving a key changes buckets only to a direct neighbor, which you can create or delete in O(1).

FAQ

What is the best time complexity for All O`one Data Structure?

Optimal (linked list of count buckets) runs in O(1) for every operation time and O(k) extra space. Each operation touches a constant number of buckets and hash-set entries.

Which pattern does All O`one Data Structure use?

It is a design data structures problem that uses the linked lists pattern. Other problems with the same pattern: Design Linked List, Design Front Middle Back Queue, LRU Cache.

Is there a brute force solution for All O`one Data Structure?

Yes. Brute force (hash map, scan for the extremes) takes O(1) for inc and dec, O(k) for the queries time and O(k) space. Keep a map from key to count.

Which edge cases should I test for All O`one Data Structure?

Querying an empty structure returns ""; Decrementing a key with count 1 removes it completely; Several keys share the maximum or minimum count: any of them is a valid answer; A key is incremented after it was removed: it starts again from 1.