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

Question

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

Linked list ought to do it, although you'll need to continually keep track of the smallest element after each operation (which will incidentally cause `delete` to be O(n) since you'll have to do a full rescan to find the minimum again) — Kevin, Aug 18 '15 at 17:14
The "important" part doesn't make sense, as the existence of `delete` method is suggesting that the structure has to have *at least* N elements. And if adding some overhead for the structuring itself - we are doomed given that note. I think you have misunderstood that part. — Eugene Sh., Aug 18 '15 at 17:19
Well, array + index of the last + index of the min is N+2. But if you consider an extensible vector of N elements as of size N... — Michel Billaud, Aug 18 '15 at 17:19
@ozangds Existence of such a bound will make the memory and any operation O(1). — Eugene Sh., Aug 18 '15 at 17:25
@Eugene Sh. -- that's one way of looking at it, but I don't think that's the interpretation the OP's school assignment is seeking. — Ozan Bellik, Aug 18 '15 at 17:57
The example uses `delete`, but it's not in the list of supported functions. Can you please clarify? And if it should be there, what is its required complexity? — Petr, Aug 18 '15 at 18:05
Your question still doesn't match. You say `deleteElement` which sounds like you specify an element to delete. But your example just says `delete` (and without indicating *what* gets deleted). What exactly is your requirement? — , Aug 18 '15 at 18:26
(note I'm not trying to be pedantic; the details of your requirements are *actually important*. They usually are, but I think especially so in this case: that "delete any element it doesn't matter which" allows for easy solutions, whereas letting the caller specify a particular element to delete is impossible, because your constraints would allow for an `O(n)` comparison-based sort) — , Aug 18 '15 at 18:43
@Nimrodshn is there a restriction on the elements? Are they nonnegative integers bounded above by some maximum M, for example? — Edward Doolittle, Aug 18 '15 at 18:43
What does `getLastElement` do? Does this mean the data structure keeps track of insertion order? Or do you mean `getMaxElement`? Does the data structure treat elements as unique, or is it set-like (ignoring duplicates, structural equality)? Also - as others commented - the behaviour of `delete` is just as unclear (min? max? last inserted? by value?). — Bergi, Aug 18 '15 at 19:59
Again sorry for the confustion - delete means delete laste inserted elements and as implied the assumption is (as I myself understand it) that the elements are inserted in a given order which is know to the user, as shown in the example. Thanks for the help everyone. — Nimrodshn, Aug 18 '15 at 20:09
And there are no restrictions on the the elements themselfves. — Nimrodshn, Aug 18 '15 at 20:10
"Memory is bounded by n (not `O(n)`)" – that doesn't even make sense. n what? bytes? words? elements? it's these arbitrary constant factors that make it **necessary** to talk about orders instead of just "n". — The Paramagnetic Croissant, Aug 18 '15 at 20:13
n elements, it just means u cant have an array/stack with 2n/3n/4n... elements which you were ablle to have with O(n). — Nimrodshn, Aug 18 '15 at 20:13
@Nimrodshn why? doesn't an array of n element have at most… n elements? — The Paramagnetic Croissant, Aug 18 '15 at 20:14
yes but an array of O(n) can have 2n or 3n elements but this is not the case. — Nimrodshn, Aug 18 '15 at 20:15
@Nimrodshn, does this mean that if one element consumes K bytes than the data structure should consume K * N + O(1) bytes? In this case you are pretty much limited to arrays. — Aivean, Aug 18 '15 at 20:18
@Aivean I think the remark is correct but to simplify things i would prefer (and that is how the problem was presented to me) there would be no regards to the representation of the elements just the elements themselves - you are allowed to consume/keep at most n elements + O(1) memory. — Nimrodshn, Aug 18 '15 at 20:22
@Nimrodshn what do you mean by **"keep"**? You have only two options: have references to your N entities, in this case **your data structure** will consume N * P memory (P is the memory consumed by each reference), or you can have some collection that contains elements by value, in the simplest case of array it will consume N * K, where K is the amount of memory consumed by each element. — Aivean, Aug 18 '15 at 20:39
again, as the question is posed there is no regards to the representation of the elemnts(bits, byts, etc..) just the elements themselves - you have n elements and your memory is restrictes to n elemens (not bits, byts or refrences) - maybe integeres would be easier comceptually altough you are not boumded to them. forget about the machine for a sec and try to solve it with pen an paper. — Nimrodshn, Aug 18 '15 at 20:52
Maybe i should note that I myself do not know the solution i've just copied it from a question set given to a student I am tutoring. — Nimrodshn, Aug 18 '15 at 20:57

rob mayoff · Accepted Answer · 2015-08-19T14:57:36.813

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.

Wow. I'm amazed. This approach works, except for minor mistake: in `insertElement` self.min is `None` for the first step, so you can't subtract it. — Aivean, Aug 19 '15 at 05:31
This seems correct i need some time to check hopfully this is the answer and ill mark it. Thanks a lot! — Nimrodshn, Aug 19 '15 at 05:43
Suppose the numeric values are unsigned 16-bit integers. So a valid sequence might be 65000,0, 64000, etc.... In your solution the list of differences would include -65000, +64000 which can't be stored in a 16-bit integer. You would need 17 bits..... or otherwise limit the input to be unsigned 15-bit numbers (instead of 16 bit). The same problem exist for 32/64 bit (signed or unsigned) input. This is because you are actually using (=wasting) 1-bit in each number.... — gen-y-s, Aug 19 '15 at 09:15
@gen-y-s I recognized this as probably being a classic type of puzzle where someone came up with a “clever” (but probably useless) algorithm, and tried to design a puzzle that can only be solved using the algorithm. So I looked for a solution along those lines. Nevertheless, it's not hard to modify my solution to meet your “unsigned 16-bit integers” requirement. I've added that to my answer. — rob mayoff, Aug 19 '15 at 14:39

score 1 · Answer 2 · answered Aug 18 '15 at 18:33

1

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.

answered Aug 18 '15 at 18:33

gen-y-s

871
6
12

This will require additional O(N) memory to store previous min values. This violates OP's requirements. – Aivean Aug 19 '15 at 05:07
@Aivean thats a bs requirement, the OP got many things wrong. This solution is O(N) which is optimal in space complexity, as well as time complexity (O(1) for all operations). – gen-y-s Aug 19 '15 at 06:37
I agree, but apparently there is a solution that satisfies OP's requirements (however suitable only for numeric elements). Check the accepted answer. – Aivean Aug 19 '15 at 06:42

score 0 · Answer 3 · answered Aug 18 '15 at 22:00

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.

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

3 Answers3