CODEWITHSUNDEEP
algorithmdata-structures
Nimrodshn
Nimrodshn

Reputation: 971

Design a data structure that supports min, getLast, append, deleteLast in O(1), memory bounded by n (not O(n)) + O(1)

I need to design a data structure that supports the following:

getMinElement, getLastElement, insertElement, deleteLastElement - in O(1) run time.

Memory is bounded by n (not O(n)) i.e. You can keep at most n elements at a given moment. plus O(1) memory.

(Important: pointers are regarded as 1 as well, so linked list, for instance, is out of the question).

Example:

insert(6)
min() -> 6
insert(10)
insert(5)
min() -> 5
insert(7)
delete()
min() -> 5
delete()
min() -> 6

Upvotes: 1

Views: 246

Answers (3)

rob mayoff
rob mayoff

Reputation: 386018

We'll store the most recent minimum directly. This is O(1) space.

We'll also use an array of integers, since that seems to be our only option for variable-length space. But we won't store the elements directly. Instead, when we insert an element, we'll store the difference between that element and the (prior) minimum. When we delete an element, we can use that difference to restore the prior minimum if necessary.

In Python:

class MinStorage:

    def __init__(self):
        self.offsets = []
        self.min = None

    def insertElement(self, element):
        offset = 0 if self.min is None else (element - self.min)
        self.offsets.append(offset)
        if self.min is None or offset < 0:
            self.min = element

    def getMinElement(self):
        return self.min

    def getLastElement(self):
        offset = self.offsets[-1]
        if offset < 0:
            # Last element defined a new minimum, so offset is an offset
            # from the prior minimum, not an offset from self.min.
            return self.min
        else:
            return self.min + offset

    def deleteLastElement(self):
        offset = self.offsets[-1]
        self.offsets.pop()
        if len(self.offsets) == 0:
            self.min = None
        if offset < 0:
            self.min -= offset

Here's a version that allows any unsigned 16-bit integer as an element, and only stores unsigned 16-bit integers in the array:

class MinStorage:

    Cap = 65536

    def __init__(self):
        self.offsets = []
        self.min = None

    def insertElement(self, element):
        assert 0 <= element < self.Cap
        offset = 0 if self.min is None else (element - self.min)
        if offset < 0: offset += self.Cap
        self.offsets.append(offset)
        if self.min is None or element < self.min:
            self.min = element

    def getMinElement(self):
        return self.min

    def getLastElement(self):
        element = self.__getLastElementUnchecked()
        if element < self.min:
            # Last element defined a new minimum, so offset is an offset
            # from the prior minimum, not an offset from self.min.
            return self.min
        else:
            return element

    def deleteLastElement(self):
        element = self.__getLastElementUnchecked()
        self.offsets.pop()
        if len(self.offsets) == 0:
            self.min = None
        elif element < self.min:
            # Popped element defined a new minimum.
            self.min = element

    def __getLastElementUnchecked(self):
        offset = self.offsets[-1]
        element = self.min + offset
        if element >= self.Cap:
            element -= self.Cap
        return element

Note that in a language with unsigned 16-bit arithmetic that wraps on overflow/underflow, you wouldn't need the checks and adjustments involving self.Cap. In C (§6.2.5/9) and C++ (§3.9.1/4), unsigned arithmetic is required to behave as needed. However, Python doesn't support unsigned 16-bit arithmetic.

Upvotes: 5

Jake Griffin
Jake Griffin

Reputation: 2074

If you can assume something like "data is in the range 0 to 255 (int8)", and you are allowed to store an integer of twice the precision (int16), then you could store the "cumulative minimum" in the upper byte and the data point in the lower byte. Other than something like this, I don't believe this is possible within the constraints you have given.

Upvotes: 0

gen-y-s
gen-y-s

Reputation: 881

Use a stack that stores both the inserted value and the current min. The current min is updated when inserting (push) a value, by comparing the value against the current min, and when deleting (pop) a value peeking the current min value from the top of the stack.

Upvotes: 1

Related Questions