Key-Value Store with Max Key Query

Problem

Implement a key value store, where keys and values are integers, with the following methods:

update(key, val): updates the value at key to val, or sets it if doesn’t exist
get(key): returns the value with key, or None if no such value exists
max_key(val): returns the largest key with value val, or None if no key with that value exists

For example, if we ran the following calls:

1
2


kv.update(1, 1)
kv.update(2, 1)

And then called kv.max_key(1), it should return 2, since it’s the largest key with value 1.

Examples

Example 1

1
2
3


Input: update(1, 1), update(2, 1), max_key(1)
Output: 2
Explanation: Both keys 1 and 2 have value 1, but key 2 is larger.

Example 2

1
2
3


Input: update(5, 10), update(3, 10), update(7, 10), max_key(10)
Output: 7
Explanation: Among keys with value 10, key 7 is the largest.

Example 3

1
2
3


Input: update(1, 5), get(1), get(2)
Output: 5, None
Explanation: Key 1 exists with value 5, key 2 doesn't exist.

Example 4

1
2
3


Input: update(1, 1), update(1, 2), max_key(1), max_key(2)
Output: None, 1
Explanation: After update, key 1 has value 2, no key has value 1.

Example 5

1
2
3


Input: update(3, 1), update(1, 1), update(2, 1), update(2, 2), max_key(1)
Output: 3
Explanation: Keys 1 and 3 have value 1, key 3 is larger (key 2 now has value 2).

Solution

Method 1 - Dual Hash Map with Ordered Set

Intuition

The key insight is to maintain two data structures: a hash map for key-to-value mapping (for efficient get and update) and a hash map of value-to-ordered-set-of-keys mapping (for efficient max_key). When updating a key, we need to remove it from the old value’s set and add it to the new value’s set. Using ordered sets allows us to quickly find the maximum key for any value.

Approach

Data Structures:
- keyToValue: HashMap to store key → value mapping
- valueToKeys: HashMap to store value → ordered set of keys mapping
Update Operation:
- If key exists, remove it from old value’s set in valueToKeys
- Add/update key in keyToValue
- Add key to new value’s set in valueToKeys
- Clean up empty sets to save memory
Get Operation:
- Simple lookup in keyToValue
Max Key Operation:
- Look up the ordered set for the given value
- Return the maximum element (last element in sorted order)
Edge Cases:
- Handle non-existent keys and values
- Clean up empty sets after removals

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


class Solution {
private:
    unordered_map<int, int> keyToValue;
    unordered_map<int, set<int>> valueToKeys;
    
public:
    void update(int key, int val) {
        // Remove from old value's set if key exists
        if (keyToValue.find(key) != keyToValue.end()) {
            int oldVal = keyToValue[key];
            valueToKeys[oldVal].erase(key);
            if (valueToKeys[oldVal].empty()) {
                valueToKeys.erase(oldVal);
            }
        }
        
        // Update key-value mapping
        keyToValue[key] = val;
        
        // Add to new value's set
        valueToKeys[val].insert(key);
    }
    
    optional<int> get(int key) {
        auto it = keyToValue.find(key);
        if (it != keyToValue.end()) {
            return it->second;
        }
        return nullopt;
    }
    
    optional<int> maxKey(int val) {
        auto it = valueToKeys.find(val);
        if (it != valueToKeys.end() && !it->second.empty()) {
            return *it->second.rbegin();
        }
        return nullopt;
    }
    
    void remove(int key) {
        auto it = keyToValue.find(key);
        if (it != keyToValue.end()) {
            int val = it->second;
            keyToValue.erase(it);
            
            valueToKeys[val].erase(key);
            if (valueToKeys[val].empty()) {
                valueToKeys.erase(val);
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


type KeyValueStore struct {
    keyToValue  map[int]int
    valueToKeys map[int]map[int]bool
}

func NewKeyValueStore() *KeyValueStore {
    return &KeyValueStore{
        keyToValue:  make(map[int]int),
        valueToKeys: make(map[int]map[int]bool),
    }
}

func (kv *KeyValueStore) Update(key, val int) {
    // Remove from old value's set if key exists
    if oldVal, exists := kv.keyToValue[key]; exists {
        delete(kv.valueToKeys[oldVal], key)
        if len(kv.valueToKeys[oldVal]) == 0 {
            delete(kv.valueToKeys, oldVal)
        }
    }
    
    // Update key-value mapping
    kv.keyToValue[key] = val
    
    // Add to new value's set
    if kv.valueToKeys[val] == nil {
        kv.valueToKeys[val] = make(map[int]bool)
    }
    kv.valueToKeys[val][key] = true
}

func (kv *KeyValueStore) Get(key int) *int {
    if val, exists := kv.keyToValue[key]; exists {
        return &val
    }
    return nil
}

func (kv *KeyValueStore) MaxKey(val int) *int {
    if keys, exists := kv.valueToKeys[val]; exists && len(keys) > 0 {
        maxKey := -2147483648 // INT_MIN
        for key := range keys {
            if key > maxKey {
                maxKey = key
            }
        }
        return &maxKey
    }
    return nil
}

func (kv *KeyValueStore) Remove(key int) {
    if val, exists := kv.keyToValue[key]; exists {
        delete(kv.keyToValue, key)
        
        delete(kv.valueToKeys[val], key)
        if len(kv.valueToKeys[val]) == 0 {
            delete(kv.valueToKeys, val)
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


class Solution {
    private Map<Integer, Integer> keyToValue;
    private Map<Integer, TreeSet<Integer>> valueToKeys;
    
    public Solution() {
        keyToValue = new HashMap<>();
        valueToKeys = new HashMap<>();
    }
    
    public void update(int key, int val) {
        // Remove from old value's set if key exists
        if (keyToValue.containsKey(key)) {
            int oldVal = keyToValue.get(key);
            valueToKeys.get(oldVal).remove(key);
            if (valueToKeys.get(oldVal).isEmpty()) {
                valueToKeys.remove(oldVal);
            }
        }
        
        // Update key-value mapping
        keyToValue.put(key, val);
        
        // Add to new value's set
        valueToKeys.computeIfAbsent(val, k -> new TreeSet<>()).add(key);
    }
    
    public Integer get(int key) {
        return keyToValue.get(key);
    }
    
    public Integer maxKey(int val) {
        TreeSet<Integer> keys = valueToKeys.get(val);
        if (keys != null && !keys.isEmpty()) {
            return keys.last();
        }
        return null;
    }
    
    public void remove(int key) {
        if (keyToValue.containsKey(key)) {
            int val = keyToValue.remove(key);
            
            valueToKeys.get(val).remove(key);
            if (valueToKeys.get(val).isEmpty()) {
                valueToKeys.remove(val);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution:
    def __init__(self):
        self.keyToValue: Dict[int, int] = {}
        self.valueToKeys: Dict[int, Set[int]] = {}
    
    def update(self, key: int, val: int) -> None:
        # Remove from old value's set if key exists
        if key in self.keyToValue:
            oldVal = self.keyToValue[key]
            self.valueToKeys[oldVal].remove(key)
            if not self.valueToKeys[oldVal]:
                del self.valueToKeys[oldVal]
        
        # Update key-value mapping
        self.keyToValue[key] = val
        
        # Add to new value's set
        if val not in self.valueToKeys:
            self.valueToKeys[val] = set()
        self.valueToKeys[val].add(key)
    
    def get(self, key: int) -> Optional[int]:
        return self.keyToValue.get(key)
    
    def maxKey(self, val: int) -> Optional[int]:
        if val in self.valueToKeys and self.valueToKeys[val]:
            return max(self.valueToKeys[val])
        return None
    
    def remove(self, key: int) -> None:
        if key in self.keyToValue:
            val = self.keyToValue.pop(key)
            
            self.valueToKeys[val].remove(key)
            if not self.valueToKeys[val]:
                del self.valueToKeys[val]

Complexity

⏰ Time complexity: O(log k) for all operations where k is the number of keys with the same value. Update and remove operations involve TreeSet/set operations which are O(log k), while get is O(1).
🧺 Space complexity: O(n) where n is the total number of key-value pairs stored, as we maintain two hash maps with the same data in different organizations.

Method 2 - Bucket-Based Approach with Lazy Cleanup

Intuition

We can optimize for cases where there are many keys with the same value by using a more sophisticated approach. Instead of maintaining ordered sets, we can use buckets and perform lazy cleanup. This approach trades some space for potentially better average-case performance, especially when dealing with frequent updates to the same keys.

Approach

Data Structures:
- keyToValue: HashMap for key → value mapping
- valueToKeys: HashMap for value → list of keys mapping
- maxKeyCache: Cache the maximum key for each value
Lazy Cleanup Strategy:
- Don’t immediately remove keys from valueToKeys on updates
- Mark stale entries and clean them up during max_key operations
- Use versioning to track valid entries
Update Operation:
- Update keyToValue immediately
- Invalidate cache for affected values
- Add new entry to valueToKeys
Max Key Operation:
- Check cache first
- If cache miss, scan the key list and compute maximum
- Clean up stale entries during scan
Memory Management:
- Periodic cleanup of stale entries
- Compact lists when they become too sparse

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82


class Solution {
private:
    unordered_map<int, int> keyToValue;
    unordered_map<int, vector<int>> valueToKeys;
    unordered_map<int, int> maxKeyCache;
    unordered_map<int, bool> cacheValid;
    
    void invalidateCache(int val) {
        cacheValid[val] = false;
    }
    
    int computeMaxKey(int val) {
        if (valueToKeys.find(val) == valueToKeys.end()) {
            return -1;
        }
        
        int maxKey = INT_MIN;
        bool found = false;
        vector<int>& keys = valueToKeys[val];
        
        // Clean up and find max in one pass
        vector<int> validKeys;
        for (int key : keys) {
            if (keyToValue.find(key) != keyToValue.end() && keyToValue[key] == val) {
                validKeys.push_back(key);
                maxKey = max(maxKey, key);
                found = true;
            }
        }
        
        // Update with cleaned list
        if (found) {
            valueToKeys[val] = validKeys;
            maxKeyCache[val] = maxKey;
            cacheValid[val] = true;
            return maxKey;
        } else {
            valueToKeys.erase(val);
            maxKeyCache.erase(val);
            cacheValid.erase(val);
            return -1;
        }
    }
    
public:
    void update(int key, int val) {
        // Invalidate cache for old value
        if (keyToValue.find(key) != keyToValue.end()) {
            invalidateCache(keyToValue[key]);
        }
        
        // Update key-value mapping
        keyToValue[key] = val;
        
        // Add to value's key list (lazy cleanup will handle duplicates)
        valueToKeys[val].push_back(key);
        
        // Invalidate cache for new value
        invalidateCache(val);
    }
    
    optional<int> get(int key) {
        auto it = keyToValue.find(key);
        if (it != keyToValue.end()) {
            return it->second;
        }
        return nullopt;
    }
    
    optional<int> maxKey(int val) {
        // Check cache first
        if (cacheValid[val] && maxKeyCache.find(val) != maxKeyCache.end()) {
            return maxKeyCache[val];
        }
        
        int result = computeMaxKey(val);
        if (result == -1) {
            return nullopt;
        }
        return result;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92


type LazyKeyValueStore struct {
    keyToValue   map[int]int
    valueToKeys  map[int][]int
    maxKeyCache  map[int]int
    cacheValid   map[int]bool
}

func NewLazyKeyValueStore() *LazyKeyValueStore {
    return &LazyKeyValueStore{
        keyToValue:  make(map[int]int),
        valueToKeys: make(map[int][]int),
        maxKeyCache: make(map[int]int),
        cacheValid:  make(map[int]bool),
    }
}

func (kv *LazyKeyValueStore) invalidateCache(val int) {
    kv.cacheValid[val] = false
}

func (kv *LazyKeyValueStore) computeMaxKey(val int) int {
    keys, exists := kv.valueToKeys[val]
    if !exists {
        return -1
    }
    
    maxKey := -2147483648 // INT_MIN
    found := false
    validKeys := make([]int, 0)
    
    // Clean up and find max in one pass
    for _, key := range keys {
        if currentVal, exists := kv.keyToValue[key]; exists && currentVal == val {
            validKeys = append(validKeys, key)
            if key > maxKey {
                maxKey = key
            }
            found = true
        }
    }
    
    // Update with cleaned list
    if found {
        kv.valueToKeys[val] = validKeys
        kv.maxKeyCache[val] = maxKey
        kv.cacheValid[val] = true
        return maxKey
    } else {
        delete(kv.valueToKeys, val)
        delete(kv.maxKeyCache, val)
        delete(kv.cacheValid, val)
        return -1
    }
}

func (kv *LazyKeyValueStore) Update(key, val int) {
    // Invalidate cache for old value
    if oldVal, exists := kv.keyToValue[key]; exists {
        kv.invalidateCache(oldVal)
    }
    
    // Update key-value mapping
    kv.keyToValue[key] = val
    
    // Add to value's key list
    kv.valueToKeys[val] = append(kv.valueToKeys[val], key)
    
    // Invalidate cache for new value
    kv.invalidateCache(val)
}

func (kv *LazyKeyValueStore) Get(key int) *int {
    if val, exists := kv.keyToValue[key]; exists {
        return &val
    }
    return nil
}

func (kv *LazyKeyValueStore) MaxKey(val int) *int {
    // Check cache first
    if kv.cacheValid[val] {
        if maxKey, exists := kv.maxKeyCache[val]; exists {
            return &maxKey
        }
    }
    
    result := kv.computeMaxKey(val)
    if result == -1 {
        return nil
    }
    return &result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80


class Solution {
    private Map<Integer, Integer> keyToValue;
    private Map<Integer, List<Integer>> valueToKeys;
    private Map<Integer, Integer> maxKeyCache;
    private Map<Integer, Boolean> cacheValid;
    
    public Solution() {
        keyToValue = new HashMap<>();
        valueToKeys = new HashMap<>();
        maxKeyCache = new HashMap<>();
        cacheValid = new HashMap<>();
    }
    
    private void invalidateCache(int val) {
        cacheValid.put(val, false);
    }
    
    private int computeMaxKey(int val) {
        if (!valueToKeys.containsKey(val)) {
            return -1;
        }
        
        List<Integer> keys = valueToKeys.get(val);
        int maxKey = Integer.MIN_VALUE;
        boolean found = false;
        List<Integer> validKeys = new ArrayList<>();
        
        // Clean up and find max in one pass
        for (int key : keys) {
            if (keyToValue.containsKey(key) && keyToValue.get(key).equals(val)) {
                validKeys.add(key);
                maxKey = Math.max(maxKey, key);
                found = true;
            }
        }
        
        // Update with cleaned list
        if (found) {
            valueToKeys.put(val, validKeys);
            maxKeyCache.put(val, maxKey);
            cacheValid.put(val, true);
            return maxKey;
        } else {
            valueToKeys.remove(val);
            maxKeyCache.remove(val);
            cacheValid.remove(val);
            return -1;
        }
    }
    
    public void update(int key, int val) {
        // Invalidate cache for old value
        if (keyToValue.containsKey(key)) {
            invalidateCache(keyToValue.get(key));
        }
        
        // Update key-value mapping
        keyToValue.put(key, val);
        
        // Add to value's key list
        valueToKeys.computeIfAbsent(val, k -> new ArrayList<>()).add(key);
        
        // Invalidate cache for new value
        invalidateCache(val);
    }
    
    public Integer get(int key) {
        return keyToValue.get(key);
    }
    
    public Integer maxKey(int val) {
        // Check cache first
        if (cacheValid.getOrDefault(val, false) && maxKeyCache.containsKey(val)) {
            return maxKeyCache.get(val);
        }
        
        int result = computeMaxKey(val);
        return result == -1 ? null : result;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


class Solution:
    def __init__(self):
        self.keyToValue: Dict[int, int] = {}
        self.valueToKeys: Dict[int, List[int]] = {}
        self.maxKeyCache: Dict[int, int] = {}
        self.cacheValid: Dict[int, bool] = {}
    
    def _invalidateCache(self, val: int) -> None:
        self.cacheValid[val] = False
    
    def _computeMaxKey(self, val: int) -> int:
        if val not in self.valueToKeys:
            return -1
        
        keys = self.valueToKeys[val]
        maxKey = float('-inf')
        found = False
        validKeys = []
        
        # Clean up and find max in one pass
        for key in keys:
            if key in self.keyToValue and self.keyToValue[key] == val:
                validKeys.append(key)
                maxKey = max(maxKey, key)
                found = True
        
        # Update with cleaned list
        if found:
            self.valueToKeys[val] = validKeys
            self.maxKeyCache[val] = maxKey
            self.cacheValid[val] = True
            return maxKey
        else:
            del self.valueToKeys[val]
            if val in self.maxKeyCache:
                del self.maxKeyCache[val]
            if val in self.cacheValid:
                del self.cacheValid[val]
            return -1
    
    def update(self, key: int, val: int) -> None:
        # Invalidate cache for old value
        if key in self.keyToValue:
            self._invalidateCache(self.keyToValue[key])
        
        # Update key-value mapping
        self.keyToValue[key] = val
        
        # Add to value's key list
        if val not in self.valueToKeys:
            self.valueToKeys[val] = []
        self.valueToKeys[val].append(key)
        
        # Invalidate cache for new value
        self._invalidateCache(val)
    
    def get(self, key: int) -> Optional[int]:
        return self.keyToValue.get(key)
    
    def maxKey(self, val: int) -> Optional[int]:
        # Check cache first
        if self.cacheValid.get(val, False) and val in self.maxKeyCache:
            return self.maxKeyCache[val]
        
        result = self._computeMaxKey(val)
        return result if result != -1 else None

Complexity

⏰ Time complexity: O(1) amortized for all operations. Update and get are O(1), while max_key is O(1) with cache hits and O(k) for cache misses where k is the number of keys with that value, but amortized to O(1) due to lazy cleanup.
🧺 Space complexity: O(n + m) where n is the number of key-value pairs and m is the additional space for lazy cleanup before garbage collection, but practically close to O(n) with periodic cleanup.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Example 5#

Solution#

Method 1 - Dual Hash Map with Ordered Set#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Bucket-Based Approach with Lazy Cleanup#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Method 1 - Dual Hash Map with Ordered Set

Intuition

Approach

Code

Complexity

Method 2 - Bucket-Based Approach with Lazy Cleanup

Intuition

Approach

Code

Complexity