## Amazon Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Written Test

but if the stack say an array is given as input... how can u find the min element from it in O(1)

@debajyothi

sorry i didn't get ur doubt clearly, but implementation of stack via array or link list doesn't change anything here. stack is stack ie LIFO.

Solution given by mr is to update a second stack to keep track of the minimum element while building the first stack.

The same can be done if we just keep a variable (say,min) and update its value every time we push a smaller element in the stack (compared to the element at the top).A second stack is not needed.

However, what is required is to find the minimum element in an already build stack, without losing it, in O(1) time complexity and the minimum possible space complexity.

@sp: what i think is u missed the point of finding min multiple times. with just 1 variable to track the min you won't be able to track the other min(as in 2nd min, 3rd min...so on ) when the 1st min has been popped out of the stack.

Keeping a second stack would solve that problem too and would return successive min also in o(1) time.

I hope i am not missing anything here, depending on what you mention.

Slight Modification.. Not only less then.. you have to push element less then and equal to.

@HunterCpp

Achieving what we want to find here can be done using this approach in o(1).

Regarding the complexity it would depend on the worst case or best case scenario and on an average the second stack wouldn't contain those many elements for a uniformly distributed data. But overall the space complexity will be o(n) != n (exactly).

Worst case: push order 4 3 2 1

in this case both stacks will contain 4 elements each

Best case: push order 1 2 3 4

in this case 1 stack will have 4 and other will have 1 only

but since you are checking top element every time, that means you are doing a primitive operation 'n' times. So the time complexity is O(n).

To understand this concept of finding minimum, maximum or range of stack in O(1) time watch this wonderful solution

youtube.com/watch?v=BOxJvXGNHys

You really like describing your own videos as "wonderful", etc. They're not that wonderful. They're handwritten solutions on a virtual blackboard.

That said, they're usually correct solutions, which is much, much more than can be said for most of the solutions on this site. So just for that I would say keep posting links to them. It would be better if you promoted with a disclaimer that they are your videos, though, and if you let others decide for themselves if they are "wonderful" or not.

This is more of a question about picking the best data structure, under different circumstances. You need to structure the data in such a way as to *find* the minimum element in O(1). Space is O(n), which could be 2n,etc, suggesting we could use another data structure inside the Stack abstraction. A couple possible options:

1) Maintain a min-heap upon push/pop, O(nlogn) add/remove. Finding the min is simply a matter of peeking at the top of the min-heap. The advantage here over push/pop, is you don't need to shift all the elements in memory.

2) Maintain another array, but use Select Sort O(nlogn), which has an advantage over quicksort, in that it does not need to sort the entire array, but stops when it finds the element at rank n.

package amazon;

import java.util.Stack;

class MyStack{

public Stack<Integer> basic;

public Stack<Integer> hold_min;

public MyStack(){

this.basic=new Stack<Integer>();

this.hold_min=new Stack<Integer>();

}

public void push(int newItem){

if(newItem<=this.getmin()){

this.hold_min.push(newItem);

}

this.basic.push(newItem);

}

public int pop(){

if(this.basic.isEmpty()){

return Integer.MIN_VALUE;

}

int value=this.basic.pop();

if(value==this.getmin()){

this.hold_min.pop();

}

return value;

}

public int getmin(){

if(this.hold_min.isEmpty()){

return Integer.MAX_VALUE;

}

else{

return this.hold_min.peek();

}

}

}

public class pop_push_min_in_stack{

public static void main(String[] args) {

MyStack test=new MyStack();

test.push(6);

test.push(3);

test.push(7);

System.out.println(test.getmin());

System.out.println(test.pop());

}

}

If you can find the minimum of a stack in O(1) won't you be able to sort n numbers in O(n)?

Didn't see anything that said there are no duplicates in the stack, so simply tracking the minimum followed by the next minimum in another stack won't work in that case. But it seems like its on the right track in that every time someone pushes a new element that equals the previous min, you have to push it again onto the tracking stack. So if your stack contains 2, 1, 3 (top to bottom) then the tracking stack should contain 1, 3. If someone pushes another 1 your stack will have 1,2,1,3 and the tracking stack will contain 1,1,3. Then if someone pops the first 1, you tracking stack will change to 1,3 and you will still know the minimum is 1. Popping the 2 keeps tracking stack as 1,3 and then popping the other 1 changes the tracking stack to 3, the new minimum.

1) Start with an array m of size k

2) m[0]=first element

3) merge each additional element in O(n) running time after each push

4) Find smallest element in O(1) time, m[0]

If the smallest element K is popped, m[0] == K, pop m[0] from m. Then, the next smallest element will be m[0]=m[1], and so on.

@Jack : I didnt get you exactly. However I guess we wont be able to find the min value in O(1) time complexity.

@mr:

The problem statement is find the minimum value in a stack .. no that how to maintain a min value while creating a stack. For that matter with every structure you can keep track of the min values .. need not be stack.

@Victor:

even if you encapsulate the things running times wont change from the perspective of algorithmics.. so I guess thats not going to help us.

Algo:

Have a custom stack object and always have minimum value along with actual value on the stack top

package com.santosh.career;

import java.util.ArrayList;

import java.util.List;

import java.util.Stack;

public class Career14462745 {

public static void main(String[] args) {

Stack<CustomStack> stack = new Stack<CustomStack>();

CustomStack s1 = new CustomStack();

CustomStack s2 = new CustomStack();

CustomStack s3 = new CustomStack();

s1.currentValue = 5;

s2.currentValue = 3;

s3.currentValue = 1;

List<CustomStack> stacks = new ArrayList<CustomStack>();

stacks.add(s1);

stacks.add(s2);

stacks.add(s3);

for (CustomStack customStack : stacks) {

if (stack.isEmpty()) {

customStack.minimumValue = customStack.currentValue;

stack.push(customStack);

} else {

CustomStack temp = stack.pop();

if (temp.minimumValue < customStack.currentValue) {

customStack.minimumValue = temp.minimumValue;

} else {

customStack.minimumValue = customStack.currentValue;

}

stack.push(temp);

stack.push(customStack);

}

}

System.out.println(stack.pop().minimumValue);

}

}

class CustomStack {

int currentValue;

int minimumValue = Integer.MAX_VALUE;

}

simple solution:

use two stacks both of same size and intially empty.

say a and b

start pushing elements in them.how?

say 18,19,89,11,42have to be pushed

a will contain all elements in normal way but b will contain only minimum elements encountered.(how b will contain minimum elements?by comparing them with first element pushed,here 18)

step1:

18 in a and 18 in b

step2:

19 in a and nothing to be done with b.

step3:

89 in a and nothing to be done with b.

step4:

11 in a and 11 in b(why?beacause 11 is less than 18)

step5:

42 in a and nothing to be done with b.

YOU ARE DONE

Now pop top element from b, you get the answer.

explaination of O(1) :

we are using push and pop only, which have O(1) time complexity.

push/pop has O(1) time complexity.Why?we deal with only one element i.e top element in push/pop.

Hope this helps.

Cheers

:)

```
package com.pocketlab.practice.ds;
import java.util.ArrayList;
import java.util.List;
public class MinStack {
List<Node> items;
public void push(int num) {
if (items == null) {
items = new ArrayList<Node>();
}
Node node = new Node(num);
if (items.size() > 0) {
node.min = Math.min(items.get(items.size() - 1).min, num);
node.max = Math.max(items.get(items.size() - 1).max, num);
} else {
node.min = num;
node.max = num;
}
// System.out.println("Pushed > " + node.data);
items.add(node);
printStack();
}
public Node pop() {
Node popThis = null;
if (items != null && items.size() > 0) {
popThis = this.items.get(items.size() - 1);
items.remove(items.size() - 1);
// System.out.println("Popped > " + popThis.data);
}
printStack();
return popThis;
}
public int getMin() {
if (items != null && items.size() > 0) {
int min = this.items.get(items.size() - 1).min;
System.out.println("Minimum Element > " + min);
return min;
}
return -1;
}
public int getMax() {
if (items != null && items.size() > 0) {
int max = this.items.get(items.size() - 1).max;
System.out.println("Maximum Element > " + max);
return max;
}
return -1;
}
public void printStack() {
int i = 0;
for (Node n : items) {
System.out.print(n.data + " > ");
if (i == items.size() - 1) {
System.out.print(" | Min = " + n.min + " |");
System.out.print(" | Max = " + n.max + " |");
}
i++;
}
System.out.println();
}
public static void main(String args[]) {
MinStack stack = new MinStack();
stack.push(10);
stack.push(13);
stack.push(19);
stack.push(3);
stack.push(2);
stack.push(2);
stack.printStack();
stack.pop();
//stack.getMin();
stack.printStack();
}
}
class Node {
int data;
int min;
int max;
public Node(int data) {
super();
this.data = data;
}
public Node() {
super();
}
}
```

Implementation of code in C with test cases and also finds max min and range:

overall time complexity : O(n)

overall space complexity : O(n)

time complexity for min max range operations:O(1)

```
#include<stdio.h>
#include<stdlib.h>
#define MAX 5
struct stack
{
int tos;
int array[MAX];
};
int is_empty(struct stack*st)
{
return (st->tos==-1)?1:0;
}
int is_full(struct stack*st)
{
return (st->tos==MAX-1)?1:0;
}
int top(struct stack*st)
{
return st->array[st->tos];
}
void printStack(struct stack*st)
{
int i;
for(i=0;i<=(st->tos);i++)
printf("%d ",st->array[i]);
printf("\n");
}
void simple_push(struct stack*st,int n)
{
if(!is_full(st))
st->array[++(st->tos)]=n;
}
void pushMinMax(struct stack*st,struct stack*maxst,struct stack*minst,int n)
{
if (!is_full(st))
{
simple_push(st,n);
if (is_empty(maxst))
simple_push(maxst,n);
else
{
if (n>=top(maxst))
simple_push(maxst,n);
else
simple_push(maxst,top(maxst));
}
if (is_empty(minst))
simple_push(minst,n);
else
{
if (n<=top(minst))
simple_push(minst,n);
else
simple_push(minst,top(minst));
}
}
}
int simple_pop(struct stack*st)
{
if(!is_empty(st))
return st->array[(st->tos)--];
}
int popMinMax(struct stack*st,struct stack*maxst,struct stack*minst)
{
int x=simple_pop(st);
simple_pop(maxst);
simple_pop(minst);
}
int getMin(struct stack*minst)
{
return top(minst);
}
int getMax(struct stack*maxst)
{
return top(maxst);
}
int getRange(struct stack*maxst,struct stack*minst)
{
return top(maxst)-top(minst);
}
int main()
{
struct stack st;
struct stack maxst;
struct stack minst;
int arr[]={2,4,4,1,3};
int i;
st.tos=-1;
maxst.tos=-1;
minst.tos=-1;
for(i=0;i<5;i++)
{
pushMinMax(&st,&maxst,&minst,arr[i]);
}
printStack(&st);
printStack(&maxst);
printStack(&minst);
printf("min:%d ",getMin(&minst));
printf("max:%d ",getMax(&maxst));
printf("range:%d \n",getRange(&maxst,&minst));
popMinMax(&st,&maxst,&minst);
popMinMax(&st,&maxst,&minst);
popMinMax(&st,&maxst,&minst);
printStack(&st);
printStack(&maxst);
printStack(&minst);
printf("min:%d ",getMin(&minst));
printf("max:%d ",getMax(&maxst));
printf("range:%d \n",getRange(&maxst,&minst));
}
```

public class MinStack {

Node top;

public void push(int x)

{

if(top == null)

{

top = new Node(x);

}

else

{

Node temp = new Node(x);

temp.next = top;

temp.min = Math.min(top.min, x);

top = temp;

}

}

public void pop()

{

if(top == null)

{

System.out.println("Stack empty!");

return;

}

top = top.next;

}

public int top()

{

if(top == null)

{

System.out.println("Stack empty!");

return Integer.MAX_VALUE;

}

return top.value;

}

public int min()

{

if(top == null)

{

System.out.println("Stack empty!");

return Integer.MAX_VALUE;

}

return top.min;

}

public static void main(String args[])

{

MinStack mStack = new MinStack();

mStack.push(7);

mStack.push(8);

System.out.println(mStack.min());

mStack.push(5);

mStack.push(9);

System.out.println(mStack.min());

mStack.push(5);

mStack.push(2);

System.out.println(mStack.min());

mStack.pop();

mStack.pop();

System.out.println(mStack.min());

}

}

class Node {

int value;

int min;

Node next;

Node(int x)

{

value = x;

next = null;

min = x;

}

}

Maintain another stack and keep pushing the min element on the stack as in when found.

- mr August 04, 2012Before each push on stack 1, just check if the current element is less than the top element of second stack if yes then push it on to stack 2.

While poping an element from stack1 check if the top of stack2 is same as the element in that case pop both the elements so that next min would show up on stack 2 for next min operation.

This would ensure that we pop out the min element in o(1) time.