design a stack such that getMinimum should be O 1

Question

This is one of an interview question  You need to design a stack which holds an integer value such that getMinimum   function should return the minimum element in the stack   For example  consider the below example   case  1  5  --  TOP 1 4 6 2  When getMinimum   is called it should return 1  which is the minimum element  in the stack    case  2  stack pop   stack pop    Note  Both 5 and 1 are poped out of the stack  So after this  the stack looks like   4  --  TOP 6 2  When getMinimum   is called is should return 2 which is the minimum in the  stack     Constriants    getMinimum should return the minimum value in O 1  Space constraint also has to be considered while designing it and if you use extra space  it should be of constant space

User · Answer

I found this solution here  struct StackGetMin     void push int x        elements push x       if  minStack empty      x  lt   minStack top          minStack push x         bool pop         if  elements empty    return false      if  elements top      minStack top          minStack pop        elements pop        return true        bool getMin int  amp min        if  minStack empty            return false        else         min   minStack top          return true              stack lt int gt  elements    stack lt int gt  minStack

User · Answer

Add a field to hold the minimum value and update it during Pop   and Push    That way getMinimum   will be O 1   but Pop   and Push   will have to do a little more work    If minimum value is popped  Pop   will be O n   otherwise they will still both be O 1   When resizing Push   becomes O n  as per the Stack implementation   Here s a quick implementation  public sealed class MinStack       private int MinimumValue      private readonly Stack lt int gt  Stack   new Stack lt int gt          public int GetMinimum             if  IsEmpty                throw new InvalidOperationException  Stack is empty                      return MinimumValue             public int Pop             var value   Stack Pop            if  value    MinimumValue                MinimumValue   Stack Min                      return value             public void Push int value            if  IsEmpty    value  lt  MinimumValue                MinimumValue   value                    Stack Push value              private bool IsEmpty   get   return Stack Count      0

User · Answer

Here is my solution in java using liked list   class Stack      int min      Node top      static class Node          private int data          private Node next          private int min           Node int data  int min              this data   data             this min   min             this next   null              void push int data           Node temp          if top    null               temp   new Node data data               top   temp              top min   data                    if top min  gt  data               temp   new Node data data               temp next   top              top   temp            else               temp   new Node data  top min               temp next   top              top   temp                   void pop        if top    null           top   top next               int min        return top min

User · Answer

public interface IMinStack lt T extends Comparable lt T gt  gt      public void push T val     public T pop      public T minValue      public int size          import java util Stack   public class MinStack lt T extends Comparable lt T gt  gt  implements IMinStack lt T gt      private Stack lt T gt  stack   new Stack lt T gt       private Stack lt T gt  minStack   new Stack lt T gt         Override   public void push T val        stack push val       if  minStack isEmpty      val compareTo minStack peek     lt  0          minStack push val           Override   public T pop         T val   stack pop        if   false    minStack isEmpty                 amp  amp  val compareTo minStack peek       0          minStack pop        return val          Override   public T minValue         return minStack peek            Override   public int size         return stack size

User · Answer

public class StackWithMin       int min      int size      int   data   new int 1024        public void push   int val             if   size    0                 data size    val              min   val            else if   val  lt  min                data size    2   val - min              min   val               assert  data size   lt  min              else               data size    val                       size              check size and grow array            public int getMin              return min             public int pop              --size           int val   data size            if     size  gt  0    amp  amp    val  lt  min                   int prevMin   min              min    min - val              return prevMin            else               return val                       public boolean isEmpty              return size    0             public static void main  String   args            StackWithMin stack   new StackWithMin             for   String arg  args                stack push  Integer parseInt  arg               while     stack isEmpty                   int min   stack getMin                int val   stack pop                 System out println  val         min                       System out println               It stores the current minimum explicitly  and if the minimum changes  instead of pushing the value  it pushes a value the same difference the other side of the new minimum   if min   7 and you push 5  it pushes 3 instead   5- 7-5    3  and sets min to 5  if you then pop 3 when min is 5 it sees that the popped value is less than min  so reverses the procedure to get 7 for the new min  then returns the previous min   As any value which doesn t cause a change the current minimum is greater than the current minimum  you have something that can be used to differentiate between values which change the minimum and ones which don t   In languages which use fixed size integers  you re borrowing a bit of space from the representation of the values  so it may underflow and the assert will fail  But otherwise  it s constant extra space and all operations are still O 1    Stacks which are based instead on linked lists have other places you can borrow a bit from  for example in C the least significant bit of the next pointer  or in Java the type of the objects in the linked list  For Java this does mean there s more space used compared to a contiguous stack  as you have the object overhead per link   public class LinkedStackWithMin       private static class Link           final int value          final Link next           Link   int value  Link next                 this value   value              this next   next                     int pop   LinkedStackWithMin stack                 stack top   next              return value                       private static class MinLink extends Link           MinLink   int value  Link next                 super  value  next                       int pop   LinkedStackWithMin stack                 stack top   next              int prevMin   stack min              stack min   value              return prevMin                       Link top      int min       public LinkedStackWithMin                 public void push   int val             if     top    null        val  lt  min                   top   new MinLink min  top               min   val            else               top   new Link val  top                        public int pop              return top pop this              public int getMin              return min             public boolean isEmpty              return top    null          In C  the overhead isn t there  and you can borrow the lsb of the next pointer   typedef struct  stack link stack with min   typedef struct  stack link stack link   struct  stack link       size t  next      int     value      stack link  get next   stack link  link          return   stack link      link - gt  next  amp      size t   1       bool is min   stack link  link         return   link - gt  next  amp  1       0     void push   stack with min  stack  int value         stack link  link   malloc   sizeof  stack link           link - gt  next     size t   stack - gt  next       if    stack - gt  next    0       value    stack - gt  value               link - gt  value   stack - gt  value          link - gt  next    1     mark as min       else           link - gt  value   value             stack - gt  next   link     etc     However  none of these are truly O 1   They don t require any more space in practice  because they exploit holes in the representations of numbers  objects or pointers in these languages  But a theoretical machine which used a more compact representation would require an extra bit to be added to that representation in each case

User · Answer

Let s assume the stack which we will be working on is this    6   minvalue 2 2   minvalue 2 5   minvalue 3 3   minvalue 3 9   minvalue 7 7   minvalue 7 8   minvalue 8   In the above representation the stack is only built by left value s the right value s  minvalue  is written only for illustration purpose which will be stored in one variable   The actual Problem is when the value which is the minimun value get s removed at that point how can we know what is the next minimum element without iterating over the stack    Like for example in our stack when 6 get s popped we know that  this is not the minimum element because the minimum element is 2  so we can safely remove this without updating our min value   But when we pop 2  we can see that the minimum value is 2 right now and if this get s popped out then we need to update the minimum value to 3   Point1   Now if you observe carefully we need to generate minvalue 3 from this particular state  2   minvalue 2   or if you go depperin the stack we need to generate minvalue 7 from this particular state  3   minvalue 3   or if you go more depper in the stack then we need to generate minvalue 8  from this particular state 7   minvalue 7   Did you notice something in common in all of the above 3 cases the value which we need to generate depends upon two variable which are both equal  Correct  Why is this happening because when we push some element smaller then the current minvalue  then we basically push that element in the stack and updated the same number in minvalue also   Point2   So we are basically storing duplicate of the same number once in stack and once in minvalue variable  We need to focus on avoiding this duplication and store something useful data in the stack or the minvalue to generate the previous minimum as shown in CASES above   Let s focus on what should we store in stack when the value to store in push is less than the minmumvalue  Let s name this variable y   so now our stack will look something like this   6   minvalue 2 y1   minvalue 2 5   minvalue 3 y2   minvalue 3 9   minvalue 7 y3   minvalue 7 8   minvalue 8   I have renamed them as y1 y2 y3 to avoid confusion that all of them will have same value   Point3   Now Let s try to find some constraint s over y1 y2and y3  Do you remember when exactly we need to update the minvalue while doing pop    only when we have popped the element which is equal to the minvalue  If we pop something greater than the minvalue then we don t have to update minvalue  So to trigger the update of minvalue  y1 y2 amp y3 should be smaller than there corresponding minvalue   We are avoding equality to avoid duplicate Point2   so the constrain is   y  lt  minValue     Now let s come back to populate y  we need to generate some value and put y at the time of push  remember  Let s take the value which is coming for push to be x which is less that the prevMinvalue and the value which we will actually push in stack to be y  So one thing is obvious that the newMinValue x   and y  lt  newMinvalue   Now we need to calulate y remember y can be anynumber which is less than newMinValue x  so we need to find some number which can fulfill our constraint  with the help of prevMinvalue and x newMinvalue    Let s do the math      x  lt  prevMinvalue  Given      x - prevMinvalue  lt  0      x - prevMinValue   x  lt  0   x  Add x on both side      2 x - prevMinValue  lt  x       this is the y which we were looking for less than x newMinValue   y   2 x - prevMinValue   or  y   2 newMinValue - prevMinValue  or  y   2 curMinValue - prevMinValue  taking curMinValue newMinValue     So at the time of pushing x if it is less than prevMinvalue then we push y 2 x-prevMinValue  and update newMinValue   x    And at the time of pop if the stack contains something less than the minValue then that s our trigger to update the minVAlue  We have to calculate prevMinValue from the curMinValue and y      y   2 curMinValue - prevMinValue  Proved      prevMinVAlue   2 curMinvalue - y    2 curMinValue - y is the number which we need to update now to the prevMinValue   Code for the same logic is shared below with O 1  time and O 1  space complexity      C   program to implement a stack that supports     getMinimum   in O 1  time and O 1  extra space    include  lt bits stdc   h gt   using namespace std       A user defined stack that supports getMin   in     addition to push   and pop    struct MyStack         stack lt int gt  s       int minEle           Prints minimum element of MyStack      void getMin                   if  s empty                 cout  lt  lt   Stack is empty n                variable minEle stores the minimum element             in the stack           else             cout  lt  lt  Minimum Element in the stack is                      lt  lt  minEle  lt  lt    n                   Prints top element of MyStack      void peek                   if  s empty                            cout  lt  lt   Stack is empty                 return                       int t   s top       Top element            cout  lt  lt   Top Most Element is                  If t  lt  minEle means minEle stores             value of t            t  lt  minEle   cout  lt  lt  minEle  cout  lt  lt  t                  Remove the top element from MyStack      void pop                   if  s empty                            cout  lt  lt   Stack is empty n                return                       cout  lt  lt   Top Most Element Removed              int t   s top             s pop                 Minimum will change as the minimum element             of the stack is being removed           if  t  lt  minEle                          cout  lt  lt  minEle  lt  lt    n                minEle   2 minEle - t                       else             cout  lt  lt  t  lt  lt    n                   Removes top element from MyStack      void push int x                     Insert new number into the stack          if  s empty                            minEle   x               s push x                cout  lt  lt    Number Inserted     lt  lt  x  lt  lt    n                return                          If new number is less than minEle          if  x  lt  minEle                          s push 2 x - minEle                minEle   x                       else            s push x             cout  lt  lt    Number Inserted     lt  lt  x  lt  lt    n                   Driver Code  int main           MyStack s       s push 3        s push 5        s getMin         s push 2        s push 1        s getMin         s pop         s getMin         s pop         s peek          return 0

User · Answer

public class MinStack lt E gt        private final LinkedList lt E gt  mainStack   new LinkedList lt E gt         private final LinkedList lt E gt  minStack   new LinkedList lt E gt         private final Comparator lt E gt  comparator       public MinStack Comparator lt E gt  comparator                 this comparator   comparator                        Pushes an element onto the stack                        param e the element to push             public void push E e            mainStack push e           if minStack isEmpty                          minStack push e                     else if comparator compare e  minStack peek    lt  0                        minStack push e                     else                       minStack push minStack peek                                     Pops an element from the stack                        throws NoSuchElementException if this stack is empty             public E pop            minStack pop           return  mainStack pop                          Returns but not remove smallest element from the stack  Return null if stack is empty                     public E getMinimum                 return minStack peek                Override     public String toString             StringBuilder sb   new StringBuilder            sb append  Main stack             for  E e   mainStack                         sb append e toString    append                         sb append                sb append   Min stack             for  E e   minStack                          sb append e toString    append                         sb append                sb append   Minimum      append getMinimum             return sb toString               public static void main String   args            MinStack lt Integer gt  st   new MinStack lt Integer gt  Comparators INTEGERS            st push 2           Assert assertTrue  2 is min in stack  2    st getMinimum   equals 2            System out println st            st push 6           Assert assertTrue  2 is min in stack  2 6    st getMinimum   equals 2            System out println st            st push 4           Assert assertTrue  2 is min in stack  2 6 4    st getMinimum   equals 2            System out println st            st push 1           Assert assertTrue  1 is min in stack  2 6 4 1    st getMinimum   equals 1            System out println st            st push 5           Assert assertTrue  1 is min in stack  2 6 4 1 5    st getMinimum   equals 1            System out println st            st pop            Assert assertTrue  1 is min in stack  2 6 4 1    st getMinimum   equals 1            System out println st            st pop            Assert assertTrue  2 is min in stack  2 6 4    st getMinimum   equals 2            System out println st            st pop            Assert assertTrue  2 is min in stack  2 6    st getMinimum   equals 2            System out println st            st pop            Assert assertTrue  2 is min in stack  2    st getMinimum   equals 2            System out println st            st pop            Assert assertTrue  null is min in stack      st getMinimum    null           System out println st

User · Answer

I think you can simply use a LinkedList in your stack implementation   First time you push a value  you put this value as the linkedlist head   then each time you push a value  if the new value  lt  head data  make a prepand operation   which means the head becomes the new value    if not  then make an append operation   When you make a pop    you check if min    linkedlist head data  if yes  then head head next   Here is my code   public class Stack    int   elements  int top  Linkedlists min   public Stack int n        elements   new int n       top   0      min   new Linkedlists       public void realloc int n        int   tab   new int n       for  int i   0  i  lt  top  i              tab i    elements i              elements   tab     public void push int x        if  top    elements length            realloc elements length   2             if  top    0            min pre x         else if  x  lt  min head data            min pre x         else           min app x             elements top      x     public int pop          int x   elements --top       if  top    0               if  this getMin      x            min head   min head next            elements top    0      if  4   top  lt  elements length            realloc  elements length   1    2              return x     public void display         for  Object x   elements            System out print x                   public int getMin         if  top    0            return 0            return this min head data     public static void main String   args        Stack stack   new Stack 4       stack push 2       stack push 3       stack push 1       stack push 4       stack push 5       stack pop        stack pop        stack pop        stack push 1       stack pop        stack pop        stack pop        stack push 2       System out println stack getMin         stack display

User · Answer

Here is my Code which runs with O 1   The previous code which I posted had problem when the minimum element gets popped  I modified my code  This one uses another Stack that maintains minimum element present in stack above the current pushed element     class StackDemo       int   stk   new int 100       int top      public StackDemo                 top   -1            public void Push int value                if  top    100              Console WriteLine  Stack Overflow            else             stk   top    value            public bool IsEmpty                 if  top    -1              return true          else             return false            public int Pop                 if  IsEmpty                          Console WriteLine  Stack Underflow                return 0                    else             return stk top--             public void Display                 for  int i   top  i  gt   0  i--              Console WriteLine stk i            class MinStack   StackDemo       int top      int   stack   new int 100       StackDemo s1  int min      public MinStack                 top   -1          s1   new StackDemo              public void PushElement int value                s1 Push value           if  top    100              Console WriteLine  Stack Overflow            if  top    -1                        stack   top    value              stack   top    value                       else                           stack   top  value              int ele   PopElement                stack   top    ele              int a   MininmumElement min  value                 stack   top    min                   stack   top    value                  stack   top    a                        public int PopElement                  if  top    -1              return 1000          else                       min   stack top--               return stack top--                        public int PopfromStack                 if  top    -1              return 1000          else                       s1 Pop                return PopElement                        public int MininmumElement int a int b                if  a  gt  b              return b          else             return a            public int StackTop                 return stack top             public void DisplayMinStack                 for  int i   top  i  gt   0  i--              Console WriteLine stack i            class Program       static void Main string   args                MinStack ms   new MinStack            ms PushElement 15           ms PushElement 2           ms PushElement 1           ms PushElement 13           ms PushElement 5           ms PushElement 21           Console WriteLine  Min Stack            ms DisplayMinStack            Console WriteLine  Minimum Element   ms StackTop             ms PopfromStack            ms PopfromStack            ms PopfromStack            ms PopfromStack             Console WriteLine  Min Stack            ms DisplayMinStack            Console WriteLine  Minimum Element     ms StackTop             Thread Sleep 1000000

User · Answer

Here is the C   implementation of Jon Skeets Answer  It might not be the most optimal way of implementing it  but it does exactly what it s supposed to   class Stack   private      struct stack node           int val          stack node  next             stack node  top      stack node  min top  public      Stack             top   nullptr          min top   nullptr                void push int num            stack node  new node   nullptr          new node   new stack node          new node- gt val   num           if  is empty                  top   new node              new node- gt next   nullptr               min top   new node              new node- gt next   nullptr            else               new node- gt next   top              top   new node               if  new node- gt val  lt   min top- gt val                    new node- gt next   min top                  min top   new node                                     void pop int  amp num            stack node  tmp node   nullptr          stack node  min tmp   nullptr           if  is empty                  std  cout  lt  lt   It s empty n             else               num   top- gt val              if  top- gt val    min top- gt val                    min tmp   min top- gt next                  delete min top                  min top   min tmp                            tmp node   top- gt next              delete top              top   tmp node                       bool is empty   const           return  top             void get min int  amp item            item   min top- gt val             And here is the driver for the class  int main         int pop  min el      Stack my stack       my stack push 4       my stack push 6       my stack push 88       my stack push 1       my stack push 234       my stack push 2        my stack get min min el       cout  lt  lt   Min     lt  lt  min el  lt  lt  endl       my stack pop pop       cout  lt  lt   Popped stock element     lt  lt  pop  lt  lt  endl       my stack pop pop       cout  lt  lt   Popped stock element     lt  lt  pop  lt  lt  endl       my stack pop pop       cout  lt  lt   Popped stock element     lt  lt  pop  lt  lt  endl       my stack get min min el       cout  lt  lt   Min     lt  lt  min el  lt  lt  endl       return 0      Output   Min  1 Popped stock element  2 Popped stock element  234 Popped stock element  1 Min  4

User · Answer

A practical implementation for finding minimum in a Stack of User Designed Object  named  School  The Stack is going to store the Schools in Stack based on the rank assigned to a school in specific region  say  findMin   gives the School where we get the maximum number of applications for Admissions  which in turn is to be defined by the comparator which uses rank associated with the schools in previous season    The Code for same is below       package com practical   import java util Collections  import java util Iterator  import java util LinkedList  import java util List  import java util Stack   public class CognitaStack        public School findMin Stack lt School gt  stack  Stack lt School gt  minStack             if   stack empty    amp  amp   minStack isEmpty                return  School  minStack peek            return null             public School removeSchool Stack lt School gt  stack  Stack lt School gt  minStack             if  stack isEmpty                return null          School temp   stack peek            if  temp    null                   if temp compare stack peek    minStack peek    lt 0               stack pop                minStack pop                                     stack pop                      return stack peek               public static void main String args               Stack lt School gt  stack   new Stack lt School gt             Stack lt School gt  minStack   new Stack lt School gt              List lt School gt  lst   new LinkedList lt School gt              School s1   new School  Polam School    London   3           School s2   new School  AKELEY WOOD SENIOR SCHOOL    BUCKINGHAM   4           School s3   new School  QUINTON HOUSE SCHOOL    NORTHAMPTON   2           School s4   new School  OAKLEIGH HOUSE SCHOOL     SWANSEA   5           School s5   new School  OAKLEIGH-OAK HIGH SCHOOL    Devon   1           School s6   new School  BritishInter2    Devon   7            lst add s1           lst add s2           lst add s3           lst add s4           lst add s5           lst add s6            Iterator lt School gt  itr   lst iterator            while  itr hasNext                  School temp   itr next                if   minStack isEmpty        temp compare temp  minStack peek     lt  0        minStack peek   equals temp                  stack push temp                   minStack push temp                 else                   minStack push minStack peek                     stack push temp                                     CognitaStack cogStack   new CognitaStack            System out println   Minimum in Stack is     cogStack findMin stack  minStack  name           cogStack removeSchool stack  minStack           cogStack removeSchool stack  minStack            System out println   Minimum in Stack is                       cogStack findMin stack  minStack     null    cogStack findMin stack  minStack  name    Empty                Also the School Object is as follows   package com practical   import java util Comparator   public class School implements Comparator lt School gt         String name      String location      int rank       public School String name  String location  int rank            super            this name   name          this location   location          this rank   rank              Override     public int hashCode             final int prime   31          int result   1          result   prime   result     location    null    0   location hashCode             result   prime   result     name    null    0   name hashCode             result   prime   result   rank          return result              Override     public boolean equals Object obj            if  this    obj              return true          if  obj    null              return false          if  getClass      obj getClass                return false          School other    School  obj          if  location    null                if  other location    null                  return false            else if   location equals other location               return false          if  name    null                if  other name    null                  return false            else if   name equals other name               return false          if  rank    other rank              return false          return true             public String getName             return name             public void setName String name            this name   name             public String getLocation             return location             public void setLocation String location            this location   location             public int getRank             return rank             public void setRank int rank            this rank   rank             public int compare School o1  School o2               TODO Auto-generated method stub         return o1 rank - o2 rank            class SchoolComparator implements Comparator lt School gt         public int compare School o1  School o2            return o1 rank - o2 rank             This Example covers the following  1  Implementation of Stack for User defined Objects  here  School 2  Implementation for the hashcode   and equals   method using all fields of Objects to be compared  3  A practical implementation for the scenario where we rqeuire to get the Stack contains operation to be in order of O 1

User · Answer

I found a solution that satisfies all the constraints mentioned  constant time operations  and constant extra space   The idea is to store the difference between min value and the input number  and update the min value if it is no longer the minimum   The code is as follows   public class MinStack       long min      Stack lt Long gt  stack       public MinStack            stack   new Stack lt  gt                public void push int x            if  stack isEmpty                  stack push 0L               min   x            else               stack push x - min     Could be negative if min value needs to change             if  x  lt  min  min   x                       public int pop             if  stack isEmpty    return           long pop   stack pop             if  pop  lt  0                long ret   min             min   min - pop    If negative  increase the min value             return  int ret                    return  int  pop   min               public int top             long top   stack peek            if  top  lt  0                return  int min            else              return  int  top   min                        public int getMin             return  int min            Credit goes to  https   leetcode com discuss 15679 share-my-java-solution-with-only-one-stack

User · Answer

Saw a brilliant solution here  https   www geeksforgeeks org design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space   Bellow is the python code I wrote by following the algorithm   class Node      def   init   self  value           self value   value         self next   None  class MinStack      def   init   self           self head   None         self min   float  inf           param x  an integer     def push self  x           if self head    None              self head   Node x              self min   x         else              if x  gt   self min                  n   Node x                  n next   self head                 self head   n             else                  v   2   x - self min                 n   Node v                  n next   self head                 self head   n                 self min   x         return nothing     def pop self           if self head              if self head value  lt  self min                  self min   self min   2 - self head value             self head   self head next         return an integer     def top self           if self head              if self head value  lt  self min                  self min   self min   2 - self head value                 return self min             else                  return self head value         else              return -1         return an integer     def getMin self           if self head              return self min         else              return -1

User · Answer

class FastStack        private static class StackNode           private Integer data          private StackNode nextMin           public StackNode Integer data                this data   data                     public Integer getData                 return data                     public void setData Integer data                this data   data                     public StackNode getNextMin                 return nextMin                     public void setNextMin StackNode nextMin                this nextMin   nextMin                        private LinkedList lt StackNode gt  stack   new LinkedList lt  gt          private StackNode currentMin   null       public void push Integer item            StackNode node   new StackNode item           if  currentMin    null                currentMin   node              node setNextMin null             else if  item  lt  currentMin getData                  StackNode oldMinNode   currentMin              node setNextMin oldMinNode               currentMin   node                     stack addFirst node              public Integer pop             if  stack isEmpty                  throw new EmptyStackException                      StackNode node   stack peek            if  currentMin    node                currentMin   node getNextMin                      stack removeFirst            return node getData               public Integer getMinimum             if  stack isEmpty                  throw new NoSuchElementException  Stack is empty                      return currentMin getData

User · Answer

The task can be acheived by creating two stacks       import java util Stack                        Find min in stack using O n  Space Complexity             public class DeleteMinFromStack            void createStack Stack lt Integer gt  primary  Stack lt Integer gt  minStack  int   arr           Create main Stack and in parallel create the stack which contains the minimum seen so far while creating main Stack                primary push arr 0                minStack push arr 0                 for  int i   1  i  lt  arr length  i                      primary push arr i                    if  arr i   lt   minStack peek      Condition to check to push the value in minimum stack only when this urrent value is less than value seen at top of this stack                        minStack push arr i                                      int findMin Stack lt Integer gt  secStack                return secStack peek                       public static void main String args                   Stack lt Integer gt  primaryStack   new Stack lt Integer gt                 Stack lt Integer gt  minStack   new Stack lt Integer gt                  DeleteMinFromStack deleteMinFromStack   new DeleteMinFromStack                 int   arr     5  5  6  8  13  1  11  6  12                deleteMinFromStack createStack primaryStack  minStack  arr               int mimElement   deleteMinFromStack findMin primaryStack  minStack           This check for algorithm when the main Stack Shrinks by size say i as in loop below                for  int i   0  i  lt  2  i                      primaryStack pop                               System out println   Minimum element is     mimElement                       here in have tried to add for loop wherin the main tack can be shrinked expaned so we can check the algorithm

User · Answer

class MyStackImplementation  private final int capacity   4  int min  int arr     new int capacity   int top   -1   public void push   int val     top    if top  lt   capacity-1       if top    0   min   val  arr top    val    else if val  lt  min   arr top    arr top  min  min   arr top -min  arr top    arr top -min    else   arr top    val    System out println  element is pushed      else System out println  stack is full         public void pop      top--     if top  gt  -1        min   arr top     else  min 0  System out println  stack is under flow        public int min    return min      public boolean isEmpty          return top    0     public static void main String   s   MyStackImplementation msi   new MyStackImplementation    msi push 1   msi push 4   msi push 2   msi push 10   System out println msi min   msi pop    msi pop    msi pop    msi pop    msi pop    System out println msi min

User · Answer

include lt stdio h gt  struct stack       int data      int mindata   a 100    void push int  tos int input        if   tos  gt  100                printf  overflow            return              tos         a   tos   data input      if  0     tos          a  tos  mindata input      else if  a  tos -1  mindata  lt  input          a  tos  mindata a  tos -1  mindata      else         a  tos  mindata input     int pop int   tos        if   tos  lt   -1                printf  underflow            return -1            return a   tos --  data     void display int tos        while  tos  gt  -1                printf   d  d t  a tos  data a tos  mindata           tos--               int min int tos       return a tos  mindata     int main     int tos -1 x choice  while 1        printf  press 1-push 2-pop 3-mindata 4-display 5-exit         scanf   d   amp choice       switch choice            case 1  printf  enter data to push                scanf   d   amp x               push  amp tos x               break      case 2  printf  the poped out data  d   pop  amp tos                break      case 3  printf  The min peeped data  d  min tos                break      case 4  printf  The elements of stack  n                display tos               break      default  exit 0

User · Answer

EDIT  This fails the  constant space  constraint - it basically doubles the space required  I very much doubt that there s a solution which doesn t do that though  without wrecking the runtime complexity somewhere  e g  making push pop O n    Note that this doesn t change the complexity of the space required  e g  if you ve got a stack with O n  space requirements  this will still be O n  just with a different constant factor   Non-constant-space solution  Keep a  duplicate  stack of  minimum of all values lower in the stack   When you pop the main stack  pop the min stack too  When you push the main stack  push either the new element or the current min  whichever is lower  getMinimum   is then implemented as just minStack peek     So using your example  we d have   Real stack        Min stack  5  -- gt  TOP        1 1                 1 4                 2 6                 2 2                 2   After popping twice you get   Real stack        Min stack  4                 2 6                 2 2                 2   Please let me know if this isn t enough information  It s simple when you grok it  but it might take a bit of head-scratching at first      The downside of course is that it doubles the space requirement  Execution time doesn t suffer significantly though - i e  it s still the same complexity    EDIT  There s a variation which is slightly more fiddly  but has better space in general  We still have the min stack  but we only pop from it when the value we pop from the main stack is equal to the one on the min stack  We only push to the min stack when the value being pushed onto the main stack is less than or equal to the current min value  This allows duplicate min values  getMinimum   is still just a peek operation  For example  taking the original version and pushing 1 again  we d get   Real stack        Min stack  1  -- gt  TOP        1 5                 1 1                 2 4                  6                  2                    Popping from the above pops from both stacks because 1    1  leaving   Real stack        Min stack  5  -- gt  TOP        1 1                 2 4                  6                  2                    Popping again only pops from the main stack  because 5   1   Real stack        Min stack  1                 1 4                 2 6                  2                    Popping again pops both stacks because 1    1   Real stack        Min stack  4                 2 6                  2                    This ends up with the same worst case space complexity  double the original stack  but much better space usage if we rarely get a  new minimum or equal    EDIT  Here s an implementation of Pete s evil scheme  I haven t tested it thoroughly  but I think it s okay     using System Collections Generic   public class FastMinStack lt T gt        private readonly Stack lt T gt  stack   new Stack lt T gt            Could pass this in to the constructor     private readonly IComparer lt T gt  comparer   Comparer lt T gt  Default       private T currentMin       public T Minimum               get   return currentMin               public void Push T element                if  stack Count    0                comparer Compare element  currentMin   lt   0                        stack Push currentMin               stack Push element               currentMin   element                    else                       stack Push element                        public T Pop                 T ret   stack Pop            if  comparer Compare ret  currentMin     0                        currentMin   stack Pop                      return ret

User · Answer

struct Node       let data  Int     init   d Int           data   d          struct Stack       private var backingStore    Node        private var minArray    Int         mutating func push n Node            backingStore append n          minArray append n data          minArray sort  gt           minArray            mutating func pop   - gt  Node            if backingStore isEmpty               return nil                    let n   backingStore removeLast            var found   false         minArray   minArray filter              if   found  amp  amp   0    n data                    found   true                 return false                           return true                   return n            func min   - gt  Int            return minArray last

User · Answer

using System  using System Collections Generic  using System IO  using System Linq   namespace Solution        public class MinStack               public MinStack                         MainStack new Stack lt int gt                 Min new Stack lt int gt                        static Stack lt int gt  MainStack          static Stack lt int gt  Min           public void Push int item                        MainStack Push item                if Min Count  0    item lt Min Peek                    Min Push item                      public void Pop                         if Min Peek    MainStack Peek                    Min Pop                MainStack Pop                      public int Peek                         return MainStack Peek                       public int GetMin                         if Min Count  0                  throw new System InvalidOperationException  Stack Empty                 return Min Peek

User · Answer

Here is my version of implementation      struct MyStack       int element      int  CurrentMiniAddress        void Push int value            Create you structure and populate the value     MyStack S   new MyStack        S- element   value       if Stack Empty                         Since the stack is empty  point CurrentMiniAddress to itself         S- CurrentMiniAddress   S             else                   Stack is not empty              Retrieve the top element  No Pop            MyStack  TopElement   Stack Top                 Remember Always the TOP element points to the             minimum element in ths whole stack          if  S- element CurrentMiniAddress- element                            If the current value is the minimum in the whole stack                then S points to itself             S- CurrentMiniAddress   S                          else                                    So this is not the minimum in the whole stack                     No worries  TOP is holding the minimum element                  S- CurrentMiniAddress   TopElement- CurrentMiniAddress                                Stack Add S        void Pop           if  Stack Empty                   Stack Pop                  int GetMinimum Stack  stack            if  stack Empty                         MyStack  Top    stack top                   Top always points to the minimumx             return  Top- CurrentMiniAddress- element

User · Answer

You could extend your original stack class and just add the min tracking to it  Let the original parent class handle everything else as usual   public class StackWithMin extends Stack lt Integer gt           private Stack lt Integer gt  min       public StackWithMin             min   new Stack lt  gt                public void push int num            if  super isEmpty                  min push num             else if  num  lt   min peek                  min push num                     super push num              public int min             return min peek               public Integer pop             if  super peek      min peek                  min pop                      return super pop

User · Answer

I think only push operation suffers  is enough  My implementation includes a stack of nodes  Each node contain the data item and also the minimum on that moment  This minimum is updated each time a push operation is done   Here are some points for understanding    I implemented the stack using Linked List  A pointer top always points to the last pushed item  When there is no item in that stack top is NULL  When an item is pushed a new node is allocated which has a next pointer that points to the previous stack and top is updated to point to this new node    Only difference with normal stack implementation is that during push it updates a member min for the new node   Please have a look at code which is implemented in C   for demonstration purpose          Implementation of Stack that can give minimum in O 1  time all the time     This solution uses same data structure for minimum variable  it could be implemented using pointers but that will be more space consuming       include  lt iostream gt  using namespace std   typedef struct stackLLNodeType stackLLNode   struct stackLLNodeType       int item      int min      stackLLNode  next      class DynamicStack   private      int stackSize      stackLLNode  top   public      DynamicStack         DynamicStack        void push int x       int pop        int getMin        int size     return stackSize        void pushOperation DynamicStack amp  p stackObj  int item   void popOperation DynamicStack amp  p stackObj    int main          DynamicStack stackObj       pushOperation stackObj  3       pushOperation stackObj  1       pushOperation stackObj  2       popOperation stackObj       popOperation stackObj       popOperation stackObj       popOperation stackObj       pushOperation stackObj  4       pushOperation stackObj  7       pushOperation stackObj  6       popOperation stackObj       popOperation stackObj       popOperation stackObj       popOperation stackObj        return 0     DynamicStack  DynamicStack            initialization     stackSize   0      top   NULL     DynamicStack   DynamicStack         stackLLNode  tmp         chain memory deallocation to avoid memory leak     while  top            tmp   top          top   top- gt next          delete tmp           void DynamicStack  push int x           allocate memory for new node assign to top     if  top  NULL            top   new stackLLNode          top- gt item   x          top- gt next   NULL          top- gt min   top- gt item            else              allocation of memory         stackLLNode  tmp   new stackLLNode             assign the new item         tmp- gt item   x          tmp- gt next   top              store the minimum so that it does not get lost after pop operation of later minimum         if  x  lt  top- gt min              tmp- gt min   x          else             tmp- gt min   top- gt min              update top to new node         top   tmp            stackSize       int DynamicStack  pop            check if stack is empty     if  top    NULL          return -1       stackLLNode  tmp   top      int curItem   top- gt item      top   top- gt next      delete tmp      stackSize--      return curItem     int DynamicStack  getMin         if  top    NULL          return -1      return top- gt min    void pushOperation DynamicStack amp  p stackObj  int item        cout lt  lt  Just pushed    lt  lt item lt  lt endl      p stackObj push item       cout lt  lt  Current stack min    lt  lt p stackObj getMin   lt  lt endl      cout lt  lt  Current stack size    lt  lt p stackObj size   lt  lt endl lt  lt endl     void popOperation DynamicStack amp  p stackObj        int popItem   -1      if   popItem   p stackObj pop       -1           cout lt  lt  Cannot pop  Stack is empty   lt  lt endl      else           cout lt  lt  Just popped    lt  lt popItem lt  lt endl          if  p stackObj getMin      -1              cout lt  lt  No minimum  Stack is empty   lt  lt endl          else             cout lt  lt  Current stack min    lt  lt p stackObj getMin   lt  lt endl          cout lt  lt  Current stack size    lt  lt p stackObj size   lt  lt endl lt  lt endl            And the output of the program looks like this   Just pushed  3 Current stack min  3 Current stack size  1  Just pushed  1 Current stack min  1 Current stack size  2  Just pushed  2 Current stack min  1 Current stack size  3  Just popped  2 Current stack min  1 Current stack size  2  Just popped  1 Current stack min  3 Current stack size  1  Just popped  3 No minimum  Stack is empty  Current stack size  0  Cannot pop  Stack is empty  Just pushed  4 Current stack min  4 Current stack size  1  Just pushed  7 Current stack min  4 Current stack size  2  Just pushed  6 Current stack min  4 Current stack size  3  Just popped  6 Current stack min  4 Current stack size  2  Just popped  7 Current stack min  4 Current stack size  1  Just popped  4 No minimum  Stack is empty  Current stack size  0  Cannot pop  Stack is empty

User · Answer

We can do this in O n  time and O 1  space complexity  like so   class MinStackOptimized    def   init   self         self stack            self min   None    def push self  x          if not self stack              stack is empty therefore directly add           self stack append x            self min   x        else                          Directly add  x-self min  to the stack  This also ensures anytime we have a            negative number on the stack is when x was less than existing minimum           recorded thus far                          self stack append x-self min            if x  lt  self min                  Update x to new min               self min   x     def pop self         x   self stack pop         if x  lt  0                           if popped element was negative therefore this was the minimum           element  whose actual value is in self min but stored value is what           contributes to get the next min   this is one of the trick we use to ensure           we are able to get old minimum once current minimum gets popped proof is given           below in pop method   value stored during push was             x - self old min  and self min   x therefore we need to backtrack           these steps self min current  - stack value x  actually implies to               x  self min  -  x - self old min            which therefore gives old min back and therefore can now be set           back as current self min                          self min   self min - x     def top self         x   self stack -1        if x  lt  0                           As discussed above anytime there is a negative value on stack  this           is the min value so far and therefore actual value is in self min            current stack value is just for getting the next min at the time           this gets popped                          return self min       else                           if top element of the stack was positive then it s simple  it was           not the minimum at the time of pushing it and therefore what we did           was x actual  - self min min element at current stage  let s say  y            therefore we just need to reverse the process to get the actual           value  Therefore self min   y  which would translate to               self min   x actual  - self min  thereby giving x actual  back           as desired                          return x   self min    def getMin self           Always self min variable holds the minimum so for so easy peezy        return self min

User · Answer

To getMin elements from Stack  We have to use Two stack   i e Stack s1 and Stack s2    Initially  both stacks are empty  so add elements to both stacks   ---------------------Recursively call Step 2 to 4-----------------------   if New element added to stack s1 Then pop elements from stack s2 compare new elments with s2  which one is smaller   push to s2  pop from stack s2 which contains min element    Code looks like   package Stack  import java util Stack  public class  getMin               Stack lt Integer gt  s1  new Stack lt Integer gt             Stack lt Integer gt  s2   new Stack lt Integer gt              void push int x                        if s1 isEmpty      s2 isEmpty                                    s1 push x                    s2 push x                             else                               s1  push x                   int y    Integer  s2 pop                    s2 push y                   if x  lt  y                      s2 push x                                               public Integer pop                         int x              x  Integer  s1 pop                s2 pop                return x                 public  int getmin                         int x1              x1   Integer s2 pop                s2 push x1               return x1                 public static void main String   args            getMin s   new getMin                s push 10               s push 20               s push 30               System out println s getmin                 s push 1               System out println s getmin

User · Answer

Here s the PHP implementation of what explained in Jon Skeet s answer as the slightly better space complexity implementation to get the maximum of stack in O 1      lt  php         An ordinary stack implementation        In real life we could just extend the built-in  SplStack  class      class BaseIntegerStack                  Stack main storage                 var array             private  storage               ------------------------------------------------------------------------        Public API        ------------------------------------------------------------------------                 Pushes to stack                 param  int  value New item                 return bool             public function push  value                return is integer  value                 bool  array push  this- gt storage   value                false                        Pops an element off the stack                 return int             public function pop                 return array pop  this- gt storage                         See what s on top of the stack                 return int bool             public function top                 return empty  this- gt storage                false               end  this- gt storage                 ------------------------------------------------------------------------        Magic methods        ------------------------------------------------------------------------                 String representation of the stack                 return string             public function   toString                 return implode       this- gt storage              End of BaseIntegerStack class         The stack implementation with getMax   method in O 1       class Stack extends BaseIntegerStack                  Internal stack to keep track of main stack max values                 var BaseIntegerStack             private  maxStack                  Stack class constructor                Dependencies are injected                 param BaseIntegerStack  stack Internal stack                 return void             public function   construct BaseIntegerStack  stack                 this- gt maxStack    stack                ------------------------------------------------------------------------        Public API        ------------------------------------------------------------------------                 Prepends an item into the stack maintaining max values                 param  int  value New item to push to the stack                 return bool             public function push  value                if   this- gt isNewMax  value                  this- gt maxStack- gt push  value                      parent  push  value                         Pops an element off the stack maintaining max values                 return int             public function pop                  popped   parent  pop             if   popped     this- gt maxStack- gt top                   this- gt maxStack- gt pop                       return  popped                        Finds the maximum of stack in O 1                  return int         see push               public function getMax                 return  this- gt maxStack- gt top                  ------------------------------------------------------------------------        Internal helpers        ------------------------------------------------------------------------                 Checks that passing value is a new stack max or not                 param  int  new New integer to check                 return boolean             private function isNewMax  new                return empty  this- gt maxStack  OR  new  gt   this- gt maxStack- gt top                End of Stack class     ------------------------------------------------------------------------    Stack Consumption and Test    ------------------------------------------------------------------------  stack   new Stack      new BaseIntegerStack      stack- gt push 9    stack- gt push 4    stack- gt push 237    stack- gt push 5    stack- gt push 556    stack- gt push 15    print  Stack   stack n   print  Max    stack- gt getMax    n n    print  Pop    stack- gt pop    n   print  Pop    stack- gt pop    n n    print  Stack   stack n   print  Max    stack- gt getMax    n n    print  Pop    stack- gt pop    n   print  Pop    stack- gt pop    n n    print  Stack   stack n   print  Max    stack- gt getMax    n       Here s the sample output        Stack  9 4 237 5 556 15    Max  556       Pop  15    Pop  556       Stack  9 4 237 5    Max  237       Pop  5    Pop  237       Stack  9 4    Max  9

User · Answer

Well  what are the runtime constraints of push and pop  If they are not required to be constant  then just calculate the minimum value in those two operations  making them O n    Otherwise  I don t see how this can be done with constant additional space

User · Answer

Here is my Code which runs with O 1   Here I used vector pair which contain the value which pushed and also contain the minimum value up to this pushed value   Here is my version of C   implementation   vector lt pair lt int int gt   gt A  int sz 0     to keep track of the size of vector  class MinStack   public      MinStack                 A clear            sz 0             void push int x                int mn  sz  0  x  min A sz-1  second x     find the minimum value upto this pushed value         A push back make pair x mn            sz       increment the size            void pop                 if sz  0  return          A pop back       pop the last inserted element         sz--      decrement size            int top                 if sz  0    return -1      if stack empty return -1         return A sz-1  first      return the top element            int getMin                 if sz  0  return -1          return A sz-1  second     return the minimum value at sz-1

User · Answer

I used a different kind of stack  Here is the implementation          main cpp     Eighth        Created by chaitanya on 4 11 13      Copyright  c  2013 cbilgika  All rights reserved       include  lt iostream gt   include  lt limits gt  using namespace std  struct stack       int num      int minnum   a 100    void push int n int m int  amp top         top        if  top gt  100            cout lt  lt  Stack Full           cout lt  lt endl            else          a top  num   n          a top  minnum   m             void pop int  amp top        if  top lt 0            cout lt  lt  Stack Empty           cout lt  lt endl            else         top--             void print int  amp top        cout lt  lt  Stack    lt  lt endl      for  int j   0  j lt  top   j              cout lt  lt     lt  lt a j  num lt  lt     lt  lt a j  minnum lt  lt     lt  lt endl            void get min int  amp top        if  top  lt  0                cout lt  lt  Empty Stack             else          cout lt  lt  Minimum element is    lt  lt a top  minnum            cout lt  lt endl     int main          int top   -1 min   numeric limits lt int gt   min   num      cout lt  lt  Enter the list to push  -1 to stop          cin gt  gt num      while  num  -1            if  top    -1                min   num              push num  min  top                     else              if  num  lt  min                    min   num                            push num  min  top                     cin gt  gt num            print top       get min top       return 0      Output   Enter the list to push  -1 to stop   5 1 4 6 2 -1 Stack    5 5   1 1   4 1   6 1   2 1  Minimum element is  1   Try it  I think it answers the question  The second element of every pair gives the minimum value seen when that element was inserted

User · Answer

I am posting the complete code here to find min and max in a given stack   Time complexity will be O 1     package com java util collection advance datastructure               author vsinha        public abstract interface Stack lt E gt                    Placing a data item on the top of the stack is called pushing it         param element                     public abstract void push E element                    Removing it from the top of the stack is called popping it         return the top element             public abstract E pop                    Get it top element from the stack and it         but the item is not removed from the stack  which remains unchanged         return the top element             public abstract E peek                    Get the current size of the stack          return             public abstract int size                     Check whether stack is empty of not          return true if stack is empty  false if stack is not empty             public abstract boolean empty            package com java util collection advance datastructure    SuppressWarnings  hiding   public abstract interface MinMaxStack lt Integer gt  extends Stack lt Integer gt         public abstract int min         public abstract int max         package com java util collection advance datastructure   import java util Arrays               author vsinha        param  lt E gt      public class MyStack lt E gt  implements Stack lt E gt         private E   elements  null      private int size   0      private int top   -1      private final static int DEFAULT INTIAL CAPACITY   10        public MyStack               If you don t specify the size of stack  By default  Stack size will be 10         this DEFAULT INTIAL CAPACITY               SuppressWarnings  unchecked       public MyStack int intialCapacity           if intialCapacity  lt  0               throw new IllegalArgumentException  initial capacity can t be negative or zero                         Can t create generic type array         elements   E    new Object intialCapacity               Override     public void push E element            ensureCapacity            elements   top    element            size              Override     public E pop             E element   null          if  empty                  element elements top                  Nullify the reference             elements top   null              --top              --size                    return element              Override     public E peek             E element   null          if  empty                  element elements top                     return element              Override     public int size             return size              Override     public boolean empty             return size    0                        Increases the capacity of this  lt tt gt Stack by double of its current length lt  tt gt  instance          if stack is full              private void ensureCapacity             if size    elements length                   Don t do anything  Stack has space            else              elements   Arrays copyOf elements  size  2                         Override     public String toString             return  MyStack  elements     Arrays toString elements       size                     size      top     top                    package com java util collection advance datastructure          Time complexity will be O 1  to find min and max in a given stack      author vsinha        public class MinMaxStackFinder extends MyStack lt Integer gt  implements MinMaxStack lt Integer gt         private MyStack lt Integer gt  minStack       private MyStack lt Integer gt  maxStack       public MinMaxStackFinder  int intialCapacity           super intialCapacity           minStack  new MyStack lt Integer gt             maxStack  new MyStack lt Integer gt                public void push Integer element               Current element is lesser or equal than min   value  Push the current element in min stack also          if  minStack empty                  if min    gt   element                    minStack push element                           else              minStack push element                        Current element is greater or equal than max   value  Push the current element in max stack also          if  maxStack empty                  if max    lt   element                    maxStack push element                           else              maxStack push element                     super push element               public Integer pop            Integer curr   super pop            if curr   null                if min      curr                    minStack pop                                if max      curr                   maxStack pop                                    return curr               Override     public int min             return minStack peek                Override     public int max             return maxStack peek                 Override     public String toString             return super toString     nMinMaxStackFinder  minStack     minStack     n maxStack                     maxStack                         You can use the below program to execute it   package com java util collection advance datastructure   import java util Random   public class MinMaxStackFinderApp        public static void main String   args            MinMaxStack lt Integer gt  stack  new MinMaxStackFinder 10           Random random  new Random            for int i  0  i lt  10  i                 stack push random nextInt 100                      System out println stack           System out println  MAX    stack max             System out println  MIN    stack min              stack pop            stack pop            stack pop            stack pop            stack pop             System out println stack           System out println  MAX    stack max             System out println  MIN    stack min               Let me know if you are facing any issue   Thanks  Vikash

[algorithm] design a stack such that getMinimum( ) should be O(1)

Examples related to algorithm

Examples related to language-agnostic

Examples related to data-structures

Examples related to stack