MinStack

May 19, 2020

[ My apologies that this exercise is so long delayed. We have been rewriting all of our business practices in the light of the pandemic, and work has been madness. The biggest projects are now complete, and we have retreated to merely super-busy, so maybe I will have time to write some more exercises. I hope everyone is well; I am. ]

Today’s task is to implement a minstack data structure that provides the normal stack operations push, pop and top and also the operation least which returns the smallest item in the stack without altering the stack in any way. All four operations must operate in O(1) time and O(n) space, where n is the size of the stack.

Your task is to implement a minstack as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

4 Responses to “MinStack”

  1. chaw said

    Here’s a solution in R7RS Scheme. The main idea is the same as in the
    solution by @programmingpraxis, but the implementation is a bit more
    general in item-comparison predicates. As is often the case, the code
    for the demo and test took longer than the main code. Wishing good
    health to all…

    (import (scheme base)
            ;; The rest are only for demos and tests:
            (scheme write)
            (scheme char)
            (only (srfi 1) list-tabulate fold)
            (only (srfi 8) receive)
            (only (srfi 27) random-integer))
    
    (define (make-min-stack item<)
      ;; s = ((stack-item . min-item) ...), top-to-bottom stack order.
      (let ((s '()))
        (define (push item)
          (set! s (cons (cons item
                              (if (or (null? s)
                                      (item< item (cdar s)))
                                  item
                                  (cdar s)))
                        s)))
        (define (top)
          (if (null? s)
              (error "stack is empty")
              (caar s)))
        (define (pop)
          (let ((t (top)))
            (set! s (cdr s))
            t))
        (define (least)
          (if (null? s)
              (error "stack is empty")
              (cdar s)))
        (values push pop top least)))
    
    (define (demo item< items verbose?)
      (receive (push pop top least) (make-min-stack item<)
        (when verbose? (display items) (newline))
        (for-each push items)
        (let* ((rhistory (fold (lambda (i r)
                                 (let ((l (least)))
                                   (cons (cons l (pop))
                                         r)))
                               '()
                               items))
               (history (reverse rhistory)))
          (when verbose? (display (reverse rhistory)) (newline))
          (and (equal? (map cdr rhistory)
                       items)
               (equal? (map car history)
                       (fold (lambda (item min-trace)
                               (cons (if (or (null? min-trace)
                                             (item< item (car min-trace)))
                                         item
                                         (car min-trace))
                                     min-trace))
                             '()
                             items))))))
    
    (demo < '(3 1 4 1 5 9 2 5 9) #t)
    
    (demo > '(3 1 4 1 5 9 2 5 9) #t)
    
    (demo < (list-tabulate 20 (lambda (i) (random-integer 100))) #t)
    
    (demo > (list-tabulate 20 (lambda (i) (random-integer 100))) #t)
    
    (let ((words '("Hello, World!" "Namaste" "नमस्ते" "OK" "Hellooo" "Oh" "oh" "ok")))
      (demo string<? words #t)
      (demo string>? words #t)
      (demo string-ci>? words #t))
    
    (define (test)
      (let loop ((i 1000)
                 (ok #t))
        (and ok
             (or (<= i 0)
                 (loop (- i 1)
                       (demo <
                             (list-tabulate 100 (lambda (i) (random-integer 1000)))
                             #f))))))
    
    (display (test))
    (newline)
    

    (3 1 4 1 5 9 2 5 9)
    ((1 . 9) (1 . 5) (1 . 2) (1 . 9) (1 . 5) (1 . 1) (1 . 4) (1 . 1) (3 . 3))
    #t (3 1 4 1 5 9 2 5 9)
    ((9 . 9) (9 . 5) (9 . 2) (9 . 9) (5 . 5) (4 . 1) (4 . 4) (3 . 1) (3 . 3))
    #t (44 3 71 47 54 40 20 75 15 68 78 20 11 79 1 33 81 73 28 85)
    ((1 . 85) (1 . 28) (1 . 73) (1 . 81) (1 . 33) (1 . 1) (3 . 79) (3 . 11)
     (3 . 20) (3 . 78) (3 . 68) (3 . 15) (3 . 75) (3 . 20) (3 . 40) (3 . 54)
     (3 . 47) (3 . 71) (3 . 3) (44 . 44))
    #t (39 57 29 99 86 22 75 83 39 78 60 24 16 32 98 17 52 46 94 49)
    ((99 . 49) (99 . 94) (99 . 46) (99 . 52) (99 . 17) (99 . 98) (99 . 32)
     (99 . 16) (99 . 24) (99 . 60) (99 . 78) (99 . 39) (99 . 83) (99 . 75)
     (99 . 22) (99 . 86) (99 . 99) (57 . 29) (57 . 57) (39 . 39))
    #t (Hello, World! Namaste नमस्ते OK Hellooo Oh oh ok)
    ((Hello, World! . ok) (Hello, World! . oh) (Hello, World! . Oh)
     (Hello, World! . Hellooo) (Hello, World! . OK) (Hello, World! . नमस्ते)
     (Hello, World! . Namaste) (Hello, World! . Hello, World!))
    (Hello, World! Namaste नमस्ते OK Hellooo Oh oh ok)
    ((नमस्ते . ok) (नमस्ते . oh) (नमस्ते . Oh) (नमस्ते . Hellooo) (नमस्ते . OK)
     (नमस्ते . नमस्ते) (Namaste . Namaste) (Hello, World! . Hello, World!))
    (Hello, World! Namaste नमस्ते OK Hellooo Oh oh ok)
    ((नमस्ते . ok) (नमस्ते . oh) (नमस्ते . Oh) (नमस्ते . Hellooo) (नमस्ते . OK)
     (नमस्ते . नमस्ते) (Namaste . Namaste) (Hello, World! . Hello, World!))
    #t #t
    

  2. Daniel said

    Glad you’re back and well!

    Here’s a solution in Python.

    class MinStack(list):
        def push(self, x):
            least = x
            if self:
                least = min((self[-1][1], least))
            self.append((x, least))
    
        def pop_(self):
            return self.pop()[0]
    
        def top(self):
            return self[-1][0]
    
        def least(self):
            return self[-1][1]
    
    if __name__ == '__main__':
        stack = MinStack()
        l = [9, 8, 2, 3, 1, 7, 4, 0, 5, 6]
        print('push')
        for x in l:
            stack.push(x)
            print(f'  top: {stack.top()}, min: {stack.least()}')
        print('pop')
        while len(stack) > 0:
            print(f'  top: {stack.top()}, min: {stack.least()}')
            stack.pop()
    

    Output:

    push
      top: 9, min: 9
      top: 8, min: 8
      top: 2, min: 2
      top: 3, min: 2
      top: 1, min: 1
      top: 7, min: 1
      top: 4, min: 1
      top: 0, min: 0
      top: 5, min: 0
      top: 6, min: 0
    pop
      top: 6, min: 0
      top: 5, min: 0
      top: 0, min: 0
      top: 4, min: 1
      top: 7, min: 1
      top: 1, min: 1
      top: 3, min: 2
      top: 2, min: 2
      top: 8, min: 8
      top: 9, min: 9
    
  3. Daniel said

    The stack.pop() call in my example code was intended to be stack.pop_(), but it turns out to not matter in that example since the return value is not used. The former would return a pair, and the latter a single value.

  4. Xero said

    Hi, Here’s a closure based implementation in Commonlisp

    (defun make-minstack (&key (comparison-function #'<))
      (let ((stack nil))
        (labels ((compare (a b)
                   (funcall comparison-function a b))
                 (stack-empty-p ()
                   (null stack))
                 (stack-top ()
                   (caar stack))
                 (stack-pop ()
                   (pop stack))
                 (stack-least ()
                   (cadar stack))
                 (stack-push (x)
                   (let ((y (stack-least)))
                     (let ((z (or (and y (compare y x) y)
                                  x)))
                       (push (list x z) stack)))))
          (list
           (cons 'least #'stack-least)
           (cons 'pop  #'stack-pop)
           (cons 'top  #'stack-top)
           (cons 'push #'stack-push)
           (cons 'emptyp #'stack-empty-p)))))
    
    (defun minstack-push (minstack x)
      "push the element x on to the minstack"
      (funcall (cdr (assoc 'push minstack)) x))
    
    (defun minstack-pop (minstack)
      "pop the top of minstack"
      (funcall (cdr (assoc 'pop minstack))))
    
    (defun minstack-top (minstack)
      "return the top of minstack"
      (funcall (cdr (assoc 'top minstack))))
    
    (defun minstack-least (minstack)
      "return the least element of minstack"
      (funcall (cdr (assoc 'least minstack))))
    

    A simple demo:

    MINSTACK> (let ((ms (make-minstack)))                                                                                                                                                         
                (minstack-push ms 5)                                                                                                                                                              
                (minstack-push ms 2)                                                                                                                                                              
                (minstack-push ms -1)                                                                                                                                                             
                (minstack-push ms 500))
    
    ((500 -1) (-1 -1) (2 2) (5 5))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: