CareerCup

You can do it using two queues.
Q = input queue
minQ = min queue.

Algo can be as follows,

Push the element in Q,
simultaneously, push the element in minQ if
if minQ.front < current element then
push element in minQ
else if minQ.front > current element
delete minQ.rear and push current element in minQ.


now
For the operation getMin()
return minQ front.
For the operation delete_front() on Q (original queue)
if (Q.front == minQ.front)
delete front from both the queue
else
delete front from only Q (original queue)

...........................................

E.g.
12 4 8 7 10 25

Q.push(12),
minQ.push(12)
Q - 12
minQ - 12

Q.push(4),
minQ.push(4)
Q - 12 4
minQ - 4

Q.push(8),
minQ.push(8)
Q - 12 4 8
minQ - 4 8

Q.push(7),
minQ.push(7)
Q - 12 4 8 7
minQ - 4 7

Q.push(10),
minQ.push(10)
Q - 12 4 8 7 10
minQ - 4 7 10

Q.push(25),
minQ.push(25)
Q - 12 4 8 7 10 25
minQ - 4 7 25

please correct me if I am wrong.

how about queue using 2 stacks Sol, with every item in stack maintaining minimum value in stack till itself

bg is right. excellent alg.

if minQ.rear < current element then
push element in minQ


Can we directly access the rear of a queue? queue.rear is not implemented usually, right?

@bg, Anonymous, xyz0410...
bg's algo is right with small modification as Anonymous corrected.

Rather than using queue to maintain minimum elements we can use double ended queue, so that we can enqueue and dequeue from both sides (front and rear).
For each element, we need to enqueue and dequeue in minQ(double ended queue) only once, hence even there is while loop , maximum number of operations will not cross 2n for n elements. Hence enque, deque and findmin operation will be constant time.

How this is correct for sequence 8,9,11,14,1,5
even if all the elements are pushed before doing getMin(), state of minQ is
minQ : 8, 9, 11, 1, 5

calling getMin() will return 8.

use one queue and two min queues:

Queue q, minq1, minq2;
isMinq1Current=true;

void push(int a)
{
  q.push(a);
  if(isMinq1Current)
  {
    if(minq1.empty) minq1.push(a);
    else
    {
      while(!minq1.empty && minq1.top<=a) minq2.push(minq1.pop());
      minq2.push(a);
      while(!minq1.empty) minq1.pop();
      isMinq1Current=false;
    }
  }
  else
  {
    //mirror if(isMinq1Current) branch. 
  }
}

int pop()
{ 
  int a = q.pop();
  if(isMinq1Current)
  {
    if(a==minq1.top) minq1.pop();
  }
  else
  {
    //mirror if(isMinq1Current) branch.    
  }

  return a;
}

Anonymous, I also ended up with similar solution like urs have globalmin variable define and set its value no need to keep seperate stack for it

@Anonymous :
In your delete function :
globalMin = front.previousMin; I think this logic is wrong. Since for every element, element.previousMin is an element which lies before the present element in the queue. So when current element is deleted its previousMin would have already been deleted according to your insert code logic.

Also in your insert function : If a sample input is 3 5 4 .. what is the minimum element once 3 is deleted ?

@Anonymous : Sorry for multiple postings

Hey, I might be wrong on this and refining my concepts but I have been thinking about this problem :

For getMin() , how about if we use Fibonaaci Heap.
getMin() and Insert is 0(1).
The only caveat to it is if we pop that element which is currently minimum, we will have to delete it and the amortized complexity for delete operation is log n.

In my humble opinion, this is simply not possible. The only scenario where this might be somehow feasible would be one where the keys could only have a relatively low number of different values. In this case, the algorithm would maintain an array of buckets (one per possible value) with nonempty buckets also forming a sorted search tree. Then there would be a log(V) factor in the complexities, where V is the number of diferent values (hopefully much lesser than N)

/* struct to hold the actual data */
typedef struct node
{
int data;
struct node *next;
struct node *nextMin;

}Node;

/* Queue head */
typedef struct
{
Node *head;
Node *tail;
Node *min;

}Queue;


/* Initialize the queue */
inline void initQueue(Queue *q)
{
q->tail = q->head = q->min = NULL;
}

/*check for queue empty */
inline int isEmpty(Queue *q)
{
return !q || q->head == NULL;
}

/* Deallocates the queue */
void endQueue(Queue *q)
{
if(isEmpty(q))
return;

Node *h = q->head;
Node *tmp;

while(h)
{
tmp = h;
h = h->next;
free(tmp);
}
}

/* inserts element at the end */
void enqueue(Queue *q, int el)
{
if(!q)
return;

Node *node = calloc(sizeof(Node), 1);
assert(node != NULL);
node->data = el;

if(!q->head) /* if Q empty */
{
q->min = q->head = q->tail = node;
}
else
{

if(q->min->data >= el) /*Update current min */
{
q->min = node;
}
else
{
Node *min = q->min;

while(min)
{
if(!min->nextMin || min->nextMin->data >= el)
{
min->nextMin = node;
break;
}
min = min->nextMin;
}
}

q->tail->nextMin = q->tail->next = node; /* attach at the end */
q->tail = node; /* move tail */

}

}

/*pops the element at the beginning */
int dequeue(Queue *q, int *el)
{
if(isEmpty(q))
return -1;

*el = q->head->data;

Node *tmp = q->head;

q->head = q->head->next; /* move head */

if(q->min == tmp) /* if head is the min, move the min */
{
q->min = tmp->nextMin;
}

free(tmp);

return 0;
}

/* Returns the minimum element in Q */
inline int findMin(Queue *q, int *el)
{
if(isEmpty(q))
return -1;

*el = q->min->data;

return 0;
}

/* prints the queue to stdout */

Here is my Code

include <string.h>
struct  node_s  {
                        int             minNext;
                        int             minPrev;
                        int             value;
                };


typedef struct{
        struct  node_s  *pBase;
        unsigned        int     rd;
        unsigned        int     wr;
        unsigned        int     len;

        unsigned        int     minHdr;
        unsigned        int     minTail;

        unsigned        int     counts; /*Debug Usage*/
} minQueueList;
void    initQueue(minQueueList  *pList, unsigned        int depth)
{
        if(NULL==pList||1>depth)
                return;
        memset((void*)pList, 0, sizeof(minQueueList));
        pList->pBase=malloc(sizeof(struct node_s)*(depth+1));
        if(NULL==pList->pBase)
                return;

        pList->len=depth+1;
        /*Following means that the list is empty*/
        pList->rd=0;
        pList->wr=0;
        pList->minHdr=depth+1;
        pList->minTail=pList->minHdr;
}

int     pushRearQueue(minQueueList *pList, int value)
{
        unsigned        int     nextWr;
        unsigned        int     curWr;
        unsigned        int     count;
        if(NULL==pList)
                return -1;
        curWr=pList->wr;
        nextWr=(pList->wr+1)%pList->len;
        if(nextWr==pList->rd)
        {
                // the queue is FULL
                return -1;
        }else
        {
                memset(pList->pBase+curWr, 0, sizeof(pList->pBase[curWr]));
                pList->pBase[curWr].value=value;
                pList->pBase[curWr].minNext=pList->len;/*NO NEXT FOR LATEST ONE ITEM*/
                if(pList->minHdr==pList->len)
                {
                        //no hdr at all before
                        pList->minHdr=curWr;
                        pList->minTail=curWr;
                        pList->pBase[curWr].minPrev=pList->len;/*NO PREV FOR  FIRST ITEM*/
                        pList->counts++;
                }else
                {
                        /*here we need to add new element*/
                        for(count=pList->minTail;1;)
                        {
                                pList->counts++;
                                if(pList->pBase[count].value>value)
                                {
                                        if(count==pList->minHdr)
                                        {
                                                pList->minHdr=curWr;
                                                pList->pBase[curWr].minPrev=pList->len;
                                                break;
                                        }else
                                        {
                                                count=pList->pBase[count].minPrev;
                                        }
                                }else
                                {
                                        pList->pBase[count].minNext=curWr;
                                        pList->pBase[curWr].minPrev=count;
                                        break;
                                }
                        }
                        pList->minTail=curWr;
                }
                pList->wr=nextWr;
        }
        return 0;
}

int     popFrontQueue(minQueueList* pList, int *pValue)
{
        if(NULL==pList || NULL==pValue)
                return -1;
        if(pList->wr==pList->rd)
                return -1; /* Empty Here*/
        *pValue=pList->pBase[pList->rd].value;
        if(pList->rd==pList->minHdr)
        {
                pList->minHdr=pList->pBase[pList->minHdr].minNext;
                if(pList->minHdr==pList->len)
                        pList->minTail=pList->len; /*That is the case it is empty now*/
        }
        pList->rd=(pList->rd+1)%pList->len;
}

int     getMinQueue(minQueueList *pList, int *pValue)
{
        if(NULL==pList || NULL==pValue|| pList->minHdr==pList->len)
                return -1;
        *pValue=pList->pBase[pList->minHdr].value;
}


/*this api is used for the verification usage*/
int     getMinQueueDummy(minQueueList *pList, int *pValue)
{
        int     minValue;
        int     temp;
        if(NULL==pList || NULL==pValue || (pList->rd==pList->wr))
                return  -1;
        minValue=pList->pBase[pList->rd].value;
        temp=pList->rd;
        while(temp!=pList->wr)
        {
                if(minValue>pList->pBase[temp].value)
                        minValue=pList->pBase[temp].value;
                temp=(temp+1)%pList->len;
        }
        *pValue=minValue;
}

My Analyze is that the addRear operation will cost O(2) in average. Because you can find the number of min list operation + the left over in the min list after each addRear operation will not exceed the twice number of total addRear operations.

My metaphor for this is that you have a league of 1000 fighters or so, and they have constant fighting ability throughout their career. Fighting ability is transitive. Also, the most experienced fighter always retires first, but you have a variable influx of new fighters.

99.9% of fighters are not elite. They come into the league, try to fight the most elite fighter, and lose. Their record goes to 0 and 1. Severely embarrassed, they don't waste their time fighting other inferior fighters; they instead get on the waiting list to become the next most elite fighter after the most elite fighter retires.

Soon, a non-elite fighter retires with no hoopla, and he's not on active waiting lists either. Then another non-elite fighter retires again with no hoopla. And another. And another. All the non-elite fighters have lost to somebody younger in their career, and that younger fighter has already been crowned or similarly defeated.

Finally, an elite fighter retires. During his reign since the latest elite fighter retired, maybe 100 new fighters have come into the league, lost to him, and stayed on the waiting list. There are a whole bunch of fighters who have only lost to the retiring elite fighter, and they establish a fighting ladder to find the new successor. Losers who lose to older fighters get to stay on the waiting list, but if an older fighter loses, he is deemed to be a permanent loser, because the younger fighter will always be around to beat them. Only one fighter remains undefeated after the ladder works out, and he's the new elite guy. Fighter who lost to older fighters don't get elite status, but they stay on the waiting list.

My intuition says this system fairly keeps one fighter in the elite position, and it minimizes the need for unnecessary fights, but I'm not sure it's even amortized O(1) fights.

Here's the final solution:
q = queue
min = double-ended queue

void push(int x) {
 q.push(x);
 while(!min.empty() && min.rear() > x) {
  min.deleteRear(); 
 }
 min.push(x);
}

int pop() {
 int x = q.pop();
 if(x == min.front()) {
  min.pop(); //removes front element
 }
 return x;
}

int get_min() {
 return min.front();
}