CareerCup

<pre lang="java" line="1" title="CodeMonkey634" class="run-this">public class MinStack<T extends Comparable<T>>
{
private Node<T>[] table;
private int size;

public T pop() {
if (this.isEmpty()) {
return null;
}

return table[--size].item;
}

public T min() {
if (this.isEmpty()) {
return null;
}

return table[--size].min;
}

public void push(T item) {
if (size == table.length) {
this.resize();
}

if (this.isEmpty()) {
table[size++] = new Node(item, item);
} else {
Node<T> top = table[size - 1];
T min = top.min.compareTo(item) < 0 ?
top.min : item;

table[size++] = new Node(item, min);
}
}

public boolean isEmpty() {
return this.size == 0;
}

private void resize() {
int newCapacity = 2 * this.table.length;
if (newCapacit < 0)
newCapacity = Integer.MAX_VALUE;

Node<T> newTable = (Node<T>) new Node[newCapacity];
System.arraycopy(table, newTable, size);

this.table = newTable;
}

private static class Node<T>
{
public final T item;
public final T min;

public Node(T item, T min) {
this.item = item;
this.min = min;
}
}
} </pre>

In the min() function, the last line should be

return table[size - 1].min;

Basically you just need another stack S for storing the minimums. S.top() gives you the current min. When inserting a new item, call S.push(min(S.top(), item)). When popping an item, you just call S.pop().

All 3 operations in O(1)? I dont think that's possible.

If we just keep a track of the new elements that are being pushed into the stack and comparing it with the existing min value , ( and hence updating as necessary ) , we can complete the task in O(1) time . And as for the push and pop things , they require O (1) in the first place , so no hassle there .

I do second Sayak.

Basically all_ele_stack shall push all elements into it. Whereas min_ele_stack shall only push only the "running minimum" elements.

Push
-----
all_ele_stack.push(newElement)
if (newElement < min_ele_stack.peep())
min_ele_stack.push(newElement)

Pop
---
data = all_ele_stack.pop();
if (data == min_ele_stack.peep())
min_ele_stack.pop()
return data;

Min
---
return min_ele_stack.peep();


So it solves the problem with extra space complexity of O(n).

It assumes no duplication of the input data.

class LinkStack
{
static void Main(string[] args)
{
LinkStackX theStack = new LinkStackX(); //make stack

theStack.push(1, 20); //push items
theStack.push(2, 40);

theStack.displayStack(); //display stack (40, 20)

theStack.push(3, 60); //push items
theStack.push(4, 80);

theStack.displayStack(); //display (80, 60, 40, 20,)

theStack.pop(); //pop items (80, 60)
theStack.pop();

theStack.displayStack(); //display stack (40, 20)
}

class LinkStackX
{
private LinkedListX.LinkListX_ pList; //pointer to linked list

public LinkStackX() //constructor
{
pList = new LinkedListX.LinkListX_();
} //make a linked list

//--------------------------------------------------------------
public void push(int id, double j) //put item on top of stack
{
pList.insertFirst(id, j);
}

//--------------------------------------------------------------
public double pop() //take item from top of stack
{
return pList.removeFirst();
}

//--------------------------------------------------------------
public bool isEmpty() //true if stack is empty
{
return (pList.isEmpty());
}

//--------------------------------------------------------------
public void displayStack()
{
Console.WriteLine("Stack (top-->bottom): ");
pList.displayList();
}
}
}

class LinkedListX
{
public class Link
{
public int iData; //data item
public double dData; //data item
public Link pNext; //ptr to next link in list

//-------------------------------------------------------------
public Link(int id, double dd)
{
iData = id;
dData = dd;
pNext = null;
}

//-------------------------------------------------------------
public void displayLink() //display ourself {22, 2.99}
{
Console.WriteLine("iData = " + dData);
}
//-------------------------------------------------------------
}

public class LinkListX_
{
private Link pFirst; //ptr to first link on list

public LinkListX_() //constructor
{
pFirst = null;
} //(no links on list yet)

//-------------------------------------------------------------
public bool isEmpty() //true if list is empty
{
return pFirst == null;
}

//-------------------------------------------------------------
//insert at start of list
public void insertFirst(int id, double dd)
{ //make new link
Link pNewLink = new Link(id, dd);
pNewLink.pNext = pFirst; //newLink-->old first
pFirst = pNewLink; //first-->newLink
}

//-------------------------------------------------------------

public Link getFirst() //return first link
{
return pFirst;
}

//-------------------------------------------------------------
public double removeFirst() //delete first link
{ //(assumes list not empty)
Link pTemp = pFirst; //save first
pFirst = pFirst.pNext; //unlink it: first-->old next
double key = pTemp.dData;
pTemp = null; //delete old first
return key;
}

//-------------------------------------------------------------
public Link find(int key) //find link with given key
{ //(assumes non-empty list)
Link pCurrent = pFirst; //start at ‘first’
while (pCurrent.pNext != null &&
pCurrent.iData != key) //while no match,
{
pCurrent = pCurrent.pNext; //go to next link
}
return pCurrent; //found it
}

//-------------------------------------------------------------
public bool remove(int key) //remove link with given key
{ //(assumes non-empty list)
Link pCurrent = pFirst; //search for link
Link pPrevious = pFirst;
while (pCurrent.pNext != null &&
pCurrent.iData != key)
{
pPrevious = pCurrent; //go to next link
pCurrent = pCurrent.pNext;
} //found it
if (pCurrent == pFirst) //if first link,
pFirst = pFirst.pNext; //change first
else //otherwise,
pPrevious.pNext = pCurrent.pNext; //bypass it
pCurrent = null; //delete link
return true; //successful removal
}

//-------------------------------------------------------------
public void displayList()
{
Console.WriteLine("List (first-->last): ");
Link pCurrent = pFirst; //start at beginning of list
while (pCurrent != null) //until end of list,
{
pCurrent.displayLink(); //print data
pCurrent = pCurrent.pNext; //move to next link
}
}
}
}

Easy enough. Use a stack subclass, with an inner stack just for tracking min values.

When pushing, peek into the min stack and compare. If it's less than the min, push the min stack.
When popping, compare to the top of the min stack, and pop the min stack if it's the same object.

Thanks Inverse.Falcon.

For others as slow as I, indeed you only push the mins onto the min stack as they are smaller than the top of the min stack. Say you push (total) 1, 2, 3. 1 is at the bottom of the main, internal stack, then 2, top 3. 1 is the /only/ contents of the min stack. Popping the 1 would require you first to pop 3, then 2, so 1 is throughout, correctly, the min (until you pop it). You don't need to store all numbers on the min stack in min order; the top min on the min stack serves as the min for all numbers above where it (also) is on the main, internal stack.

The idea of using binary representation to keep track of whether the element is included in the main stack or min stack is good. But it will limit this algorithm to 32 items on a 32 bit machine and 64 items on a 64 bit machine. So its better we use the main stack to push and pop all the elements and in addition we will have min stack to update the min element.

one of the possible solution can be-
1.suppose we have stack(can be implemented through class),and top(indicates top position of the stack and min which indicates minimum element in stack
2.pop(),push() can be implemented O(1) as usually(since push and pop takes place on top) and for min
whenever we are inserting an element in to stack we update min as
if(element<min)
min=element
else
min=min

I dont know what the fuss is about ...
1. if arr[i]<min
min=arr[i]
2. push
3 pop

Inverse.Falcon, nice approach.
I would like to add one more thing to take care of multiple instance of same value.
As min is popped u will pop it from minStack as well, but if there is one more element down in the stack then min will return wrong value.
So if new element is same as min push min again to both the stacks.

@ramukumar as soon as min is popped out "min" will be out of sync.

@ysjaitawat
actually min indicates min element in stack which is updated accordingly whenever we insert element in to stack whenevr we calll minimun() just return min

1. Create 2 stacks named RegularStack and MinStack.
2. RegularStack: Implement normal push(), pop() and top() functions.
3 MinStack: Maintain the minimum element in RegularStack as its top.

1) Push:
While pushing an element into RegularStack, Compare this element with the top element in MinStack.
If it is smaller, then push that element into MinStack at the same time.
Else do nothing.

2) Pop:
While popping an element out from RegularStack, Compare this element with the top element in MinStack.
If they are equal, we pop out the top element from MinStack at the same time. Otherwise, we do nothing.

3. Get:
Peek element from MinStack and Return.

class StackOperations
{
    Stack<int> RegularStack = new Stack<int>();
    Stack<int> MinStack = new Stack<int>();
    StringBuilder StringBuilderObj = new StringBuilder(); 

    public void PushPopGetMinWithConstantTime()
    {
        Push(3);
        Push(4);
        Push(5);
        Push(1);
        Push(2);
        StringBuilderObj.Append("\nElements Pushed into Stack:\n 3,   4,  5,  1,  2");
            
        int minElement = GetMinElement();
        StringBuilderObj.Append("\n\nMin Element in Stack:\t" + minElement.ToString());
        
        int poppedElement = Pop();
        poppedElement = Pop();
        StringBuilderObj.Append("\n\nElements 1,  2 popped out from Stack.\t");

        StringBuilderObj.Append("\n\nRemaining Elements in Stack:\n 3,   4,  5");

        minElement = GetMinElement();
        StringBuilderObj.Append("\n\nMin Element in Stack:\t" + minElement.ToString());

        MessageBox.Show(StringBuilderObj.ToString());
    }

    public void Push(int elementToPush)
    {
        //Push element to RegularStack
        RegularStack.Push(elementToPush);

        //If the elementToPush is less than the currentMinElement in MinStack then insert elementToPush to MinStack
        //Else do nothing.
        int? currentMinElement = null;

        if (MinStack.Count > 0)
        {
            currentMinElement = MinStack.Peek();
        }

        if (currentMinElement == null || elementToPush < currentMinElement)
        {
            MinStack.Push(elementToPush);
        }
    }
    public int Pop()
    {
        if (RegularStack.Count == 0)
        {
            throw new Exception("No elements in stack to pop");
        }

        //Pop element from RegularStack.
        int elementPopped = RegularStack.Pop();

        //Get element from MinStack and check if it is same as elementPopped, then pop out it from the MinStack as well.
        int currentMinElement = MinStack.Peek();
        if (elementPopped == currentMinElement)
        {
            MinStack.Pop();
        }

        return elementPopped;

    }
    public int GetMinElement()
    {
        if (MinStack.Count == 0)
        {
            throw new Exception("No elements in stack to pop");
        }

        //Get element from MinStack and return.
        int currentMinElement = MinStack.Peek();
        return currentMinElement;
    }
}