# Thoroughly explaining what's going on, a very concise solution accepted as best submission in C

• Before we really get started, let's first make some points clear about this problem and also there are some complaints about the specification of the problem -> so misleading! Here is the detailed specification of the problem:

• push will push the value to the stack - as a new top value;
• pop will delete the top value of the stack - the only removing operation;
• top will just return he top value of the stack - no removing;
• getMin will just get the minimal value among the values in stack - no removing;

The true question comes around now, how can we just get the minimal of the stack in constant time? First we need to think about this -> it's a stack -> values comes and goes at the rear of an array -> so we can just use another array <font color="#0000ff">mins</font> to store the so-far minimals which exactly means that when we are pushing values to the stack from the very beginning, we need to check whether the so-far minimal will be changed, if it's changed for the incoming new value, we need to push this value to the <font color="#0000ff">mins</font> array and so on and so on.

the other array <font color="#0000ff">mins</font> will store the so-far minimals and should be updated in each push and pop operation to maintain this feature

• so-far minimals means the minimals among values from the bottom till the top of the stack

Bang! End of Story!

Another typical example using space to reduce time cost:

• space cost O(n)
• time cost O(1)

``````typedef struct
{
int *arr;
int count;
int *mins;
int minCount;
} MinStack;

void minStackCreate(MinStack *stack, int maxSize)
{
stack->arr = (int*)malloc(sizeof(int)*maxSize);
stack->mins = (int*)malloc(sizeof(int)*maxSize); //record the mins till the top of the arr;
stack->count = 0;
stack->minCount = 0;
}

void minStackPush(MinStack *stack, int element) //push it to arr normally, but meantime check whether we should push it to mins;
{
stack->arr[stack->count++] = element;
if(stack->minCount==0 || element<=stack->mins[stack->minCount-1])
stack->mins[stack->minCount++] = element;
}

void minStackPop(MinStack *stack) //pop will always pop the top -> the top of mins and arr;
{
int top = stack->arr[stack->count-1];
if(stack->mins[stack->minCount-1] == top)
stack->minCount--;
stack->count--;
}

int minStackTop(MinStack *stack) //just return the top, needless to remove it;
{
return stack->arr[stack->count-1];
}

int minStackGetMin(MinStack *stack) //just return the min, needless to remove it;
{
return stack->mins[stack->minCount-1];
}

void minStackDestroy(MinStack *stack)
{
free(stack->arr);
free(stack->mins);
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.