Python O(1) Solution without using linkedlist, Sorry about the bad comments.


  • 1
    Z

    Sorry I don't have a lots of time recently to write a good explanation, will add more comments when I have time. And I think there are tons of optimizations can be done for this code. Please leave comments.

    class AllOne(object):
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            # key: index_to_rank_array
            self.keymap = {}
            # store the ranking for all keys
            # bigger key on the left, smaller key on the right for easy mantainance.
            # when remove key, just pop it in O(1)
            # [[key, value]]
            self.rank = []
            '''
            e.g.
            keymap = {k1: 0, k2: 1, k3: 2, k4: 3, k5: 4, k6: 5, k7: 6, k8: 7, k9: 8}
            [(k1, 3), (k2, 3), (k3, 2), (k4, 2), (k5, 2), (k6, 2), (k7, 1), (k8, 1), (k9, 1)]
                0        1        2        3        4        5        6        7        8
            for above example, the value_interval would be
            value_interval = {1: [6, 8], 2: [2, 5], 3: [0, 1]}
            The use case is when we are try to say increase/decrease the value "2" at position "3"
            if there are duplications value of 2, what we want to do is to swap 2 with right most index of 2
            it now becomes like this, map must be updated accordingly
            keymap = {k1: 0, k2: 1, k3: 2, k4: 5, k5: 4, k6: 3, k7: 6, k8: 7, k9: 8}
            [(k1, 3), (k2, 3), (k3, 2), (k6, 2), (k5, 2), (k4, 1), (k7, 1), (k8, 1), (k9, 1)]
                0        1        2        3        4        5        6        7        8
            should be very careful about updating value 1 and 2, don't forget to expand 1(or whatever smaller than x if we are
            updating bigger value, for example, if we are updating 3, 2 may not exist, we should take care of 1, just check when doing this)
            value_interval = {1: [5, 8], 2: [2, 4], 3: [0, 1]}
            ALL ABOVE OPERATIONS CAN BE ACHIEVE IN O(1), just need to be very careful
            '''
            self.value_interval = {}
    
        def fix_value_interval(self, idx, old_value=None):
            """
            This function is to fix all issues related to interval map
            merge/add/delete
    
            Implement these function separately could make the code more efficient
            but it will take a lot more time to do.
            """
            val = self.rank[idx][1]
            """
            The code here is to create/remove existing interval in certain condition.
            fix interval can be done later
            """
            if val not in self.value_interval:
                # create new interval for new value
                self.value_interval[val] = [idx, idx]
            # old_value can not be 0
            if old_value:
                # if the old_value is in his own group, remove that group
                old_interval = self.value_interval[old_value]
                if old_interval[0] == old_interval[1]:
                    # remove old group, since it is only contain one value
                    # and this value has been changed
                    del self.value_interval[old_value]
            if idx < len(self.rank) - 1:
                # checking right handside of the idx
                right_value = self.rank[idx + 1][1]
                right_interval = self.value_interval[right_value]
                assert val >= right_value
                if val == right_value:
                    # [3,2,2,[2],2]
                    # since [2] was covered within the interval range, don't change anything
                    if right_interval[0] > idx:
                        assert right_interval[0] == idx + 1
                        right_interval[0] = idx
                if val > right_value:
                    # leave the interval group if necessary
                    assert right_interval[0] in [idx, idx + 1]
                    right_interval[0] = idx + 1
            if idx > 0:
                # checking left hand side of the idx
                left_value = self.rank[idx - 1][1]
                left_interval = self.value_interval[left_value]
                assert val <= left_value
                if val == left_value:
                    # equal to idx, we updated it anyway, still O(1)
                    if left_interval[1] < idx:
                        assert left_interval[1] == idx - 1
                        left_interval[1] = idx
                if val < left_value:
                    assert left_interval[1] in [idx, idx - 1]
                    left_interval[1] = idx - 1
            # if the program get this far there are maximum one item in the list,
            # this case has been handled by the initial add/remove interval
            # operation
    
        def inc(self, key):
            # update existing key
            if key in self.keymap:
                idx = self.keymap[key]
                self.rank[idx][1] += 1
                new_rank = self.rank[idx]
                if idx != 0 and new_rank[1] > self.rank[idx - 1][1]:
                    swap_with_idx = self.value_interval[self.rank[idx - 1][1]][0]
                    # left most for idx - 1 value
                    self.keymap[new_rank[0]] = swap_with_idx
                    # get the index of the left most interval for previous value
                    self.keymap[self.rank[swap_with_idx][0]] = idx
                    self.rank[idx], self.rank[swap_with_idx] = self.rank[swap_with_idx], self.rank[idx]
                    # fix interval, swap won't create new interval group or cause group
                    # deletion, since we only swap for duplicates
                    self.fix_value_interval(swap_with_idx, old_value=None)
                    self.fix_value_interval(idx, old_value=None)
                else:
                    # for other case either there is no previous value or previous
                    # value >= new_value, no need to swap, just fix the interval
                    self.fix_value_interval(idx, old_value=new_rank[1] - 1)
            else:
                # key not in keymap, append a new one
                self.rank.append([key, 1])
                idx = len(self.rank) - 1
                self.keymap[key] = idx
                self.fix_value_interval(idx)
    
        def dec(self, key):
            # to pass the test cases
            if key not in self.keymap:
                return
            idx = self.keymap[key]
            old_rank = self.rank[idx]
            # if old_rank is 1, we should remove it
            if old_rank[1] == 1:
                del self.keymap[key]
                # manually handle interval here, since it is a special case
                # one_interval means value interval group for smallest value 1
                one_interval = self.value_interval[1]
                if one_interval[0] == one_interval[1]:
                    # now idx must be the last element, otherwise we got problems
                    assert one_interval[0] == idx == len(self.rank) - 1
                    del self.value_interval[1]
                    self.rank.pop()
                else:
                    # there are still more items has value 1
                    if idx != one_interval[1]:
                        # actually now the value we are expecting is self.rank[-1]
                        # but this is more readable
                        assert self.rank[one_interval[1]] is self.rank[-1]
                        right_most_rank = self.rank[one_interval[1]]
                        self.rank[idx] = right_most_rank
                        self.keymap[right_most_rank[0]] = idx
                    one_interval[1] -= 1
                    self.rank.pop()
            else:
                old_rank[1] -= 1
                if idx != len(self.rank) - 1 and old_rank[1] < self.rank[idx + 1][1]:
                    # get right most element to swap with
                    swap_with_idx = self.value_interval[self.rank[idx + 1][1]][1]
                    # left most for idx - 1 value
                    self.keymap[old_rank[0]] = swap_with_idx
                    # get the index of the left most interval
                    self.keymap[self.rank[swap_with_idx][0]] = idx
                    self.rank[idx], self.rank[swap_with_idx] = self.rank[swap_with_idx], self.rank[idx]
                    # fix interval, swap won't create new group or cause group
                    # deletion, since we only swap for duplicates
                    self.fix_value_interval(swap_with_idx, old_value=None)
                    self.fix_value_interval(idx, old_value=None)
                else:
                    # for other case either there is no previous value or previous
                    # value >= new_value, no need to swap, just fix the interval
                    self.fix_value_interval(idx, old_value=old_rank[1] + 1)
    
        def getMaxKey(self):
            """
            Returns one of the keys with maximal value.
            :rtype: str
            """
            # random return or all return can also be implemented with this data
            # structure
            return self.rank and self.rank[0][0] or ""
    
        def getMinKey(self):
            """
            Returns one of the keys with Minimal value.
            :rtype: str
            """
            return self.rank and self.rank[-1][0] or ""
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.