Leetcode Daily Question 29/09/2024 - 432. All O`one Data Structure

Problem Description:

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts. |--| Implement the AllOne class: |--| AllOne() Initializes the object of the data structure. |--| inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1. |--| dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement. |--| getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "". |--| getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "". |--| Note that each function must run in O(1) average time complexity.

class AllOne:
  def __init__(self):
    self.d = {}
    self.isMinMax = 0
    self.minMax = ""
    
    
  def inc(self, key: str) -> None:
    self.isMinMax = 0
    if key not in self.d:
      self.d[key] = 1
    else:
      self.d[key] += 1
      
      
  def dec(self, key: str) -> None:
    self.isMinMax = 0
    if self.d[key] == 1:
      del self.d[key]
    else:
      self.d[key] -= 1
      
      
  def getMaxKey(self) -> str:
    if not self.d:
      return ""
    if self.isMinMax == 1:
      return self.minMax
    
    self.isMinMax = 1
    
    max_val = list(self.d.values())[0]
    self.minMax = list(self.d.keys())[0]
    
    for key, val in self.d.items():
      if val > max_val:
        max_val = val
        self.minMax = key
        
    return self.minMax
  
  
  def getMinKey(self) -> str:
    if not self.d:
      return ""
    if self.isMinMax == 2:
      return self.minMax
    
    self.minMax = 2
    
    min_val = list(self.d.values())[0]
    self.minMax = list(self.d.keys())[0]
    
    for key, val in self.d.items():
      if val < min_val:
        min_val = val
        self.minMax = key
     
    return self.minMax

Explanation:

The difficult part about this question is the constraint that every operation must be performed on average in O(1) time.

We utilise a dictionary to do this. Naturally, update and insertion are O(1) operations for a dictionary.

To deal with getting the minimum and maximum key, we need create custom memorisation. We can do this using a isMinMax delimiter that will save the state of the current min or max. This way, we do not need to iterate through the items everytime to find min / max. If we repeatedly call the min / max, we retrieve the cached value in memory.

def __init__(self):
  self.d = {}
  self.isMinMax = 0
  self.minMax = ""
  

def inc(self, key: str) -> None:
  self.isMinMax = 0 # Everytime we update the min max may change.
  if key not in self.d:
    self.d[key] = 1
  else:
    self.d[key] += 1
    

def dec(self, key: str) -> None:
  self.isMinMax = 0
  if self.d[key] == 1: # We are guaranteed that this key exists in the dictionary.
    del self.d[key] 
  else:
    self.d[key] -= 1

We shall use 0 to signify undefined, 1 to signify max, and 2 to signify min.

We also use self.minMax to store the current max/min key.

def getMaxKey(self) -> str:
  if not self.d:
    return ""
  if self.isMinMax == 1: # When we repeatedly call this function, the max does not change.
    return self.minMax
  
  self.isMinMax = 1
  
  max_val = list(self.d.values())[0] # Since Python 3.7 the values() method retains insertion order.
  max_key = list(self.d.keys())[0] # So, we use the first set of key/value as our base case for max.
  
  for key, val in self.d.items():
    if val > max_val:
      max_val = val
      max_key = key
      
  return self.minMax


def getMinKey(self) -> str:
  if not self.d:
    return ""
  if self.isMinMax == 2:
    return self.minMax
  
  self.isMinMax = 2
  
  min_val = list(self.d.values())[0]
  min_key = list(self.d.keys())[0]
  
  for key, val in self.d.items():
    if val < max_val:
      min_val = val
      min_key = key
      
  return self.minMax

The time complexity is O(1) as prescribed.

The space complexity is O(n) as we need to potentially store n unique elements given n operations.

The full solution can be found near the top of the page.