CareerCup

Maintain another stack and keep pushing the min element on the stack as in when found.
Before 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.

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

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)?

In addition to stack, maintain a min-heap and encapsulate both in a class. The idea of encapsulating both in a class is to hide from the user of the class that there is a min-heap in it. That should solve the problem.

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.

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;
}

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

cn u tel us a way to get minimum element of the stack in <o(n) with only push and pop operations?

if there are n comparisons! how could it be O(1)????

pop stack, store the value in a variable say min
again pop and compare with min, if it is less than min, replace it with the min
but in this case also we are iterating the n elements, so it will be O(n)

pop stack, store the value in a variable say min
again pop and compare with min, if it is less than min, replace it with the min
but in this case also we are iterating the n elements, so it will be O(n)

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;
}
}

We can take two stacks and push all the elements one by one in stack 1. stack 2 stores the current minimum element present in stack 1 ,at the end print the top of the element of stack 2.

Logic::Create own stack class using link list and add extra variable min_elem in stack ,which will contain the minimun of stack.While pushing the data also check if new data is less than minmum_element else set new data as minimum elem.A function get_minmum will return the minimum element in stack at any time i.e O(1) complexity



C++ prog::

#include <iostream>
#include <cstdlib>


using namespace std;
struct node
{
int data;
int min_elem;

struct node *next;

};


class stack
{
public:
int min_elem;

int get_min()
{
return min_elem;
}

void push( int );
int pop();

int count;
int capacity;
node *root;

stack(int stack_size)
{
std::cout << "\n Stack Consructior";

root = NULL;
count = 0;
min_elem=0;
capacity = stack_size;

}

~stack()
{

std::cout << "\n Stack Desrtuctor";
}

};

void display(struct node *);


int main()
{

std::cout <<"\n func===" << __func__;

struct node *root=NULL ;
stack own_stack(10);
own_stack.push(109);
own_stack.push(2);
own_stack.push(8);
own_stack.push(9);
own_stack.push(5);
own_stack.push(6);
own_stack.push(7);

std::cout <<"\n min value in stack" << own_stack.get_min();

}


void stack::push (int data)
{


std::cout <<"\n we are in push";

if(count == capacity)
{
std::cout <<"\n stack full completely";
return;

}

struct node *tmp = (struct node *) malloc(sizeof(struct node));

tmp->data = data;
tmp->next =NULL;


if(root ==NULL)
{
root=tmp;
min_elem= root->data;
count++;
return ;
}

if(min_elem > tmp->data)
{
min_elem = tmp->data;
}


tmp->next =root;
root=tmp;

count++;

}

Logic::Create own stack using link list and add extra element min_elem in stack class .
Before pushing the data check whether the new data is less than min_elem, if its not than set min_elem value as new_data and also push the new data into stack

{
#include <iostream>
#include <cstdlib>


using namespace std;
struct node
{
   int data;
   int min_elem;

   struct node *next;

};// *root;


class stack
{
  public:
  int min_elem;
 // node stack_node;
 /* void set_min(int data ) 
  {
   stack_node.min_elem = data;

  }
 */ 
  int get_min()
  {
    return min_elem;
  }
 
  void push( int );
  int pop();
  
  int count;
  int capacity;
  node *root;
 
  stack(int stack_size)
  {
    std::cout << "\n Stack Consructior";
   // stack_node.data = 0;
    //stack_node.min_elem = 0;
   // stack_node.next=NULL;
    root = NULL;
    count = 0;
    min_elem=0;
    capacity =  stack_size; 

  }
  
 ~stack()
  {

    std::cout << "\n Stack Desrtuctor";
  }   
  
};

void display(struct node *);


int main()
{
  
 std::cout <<"\n func===" << __func__;
 int vertex = 5;
 int option;
 int data;

 struct node *root=NULL ;//= (struct node *  start) malloc ( sizeof(struct node) );
 stack own_stack(10); 
 own_stack.push(109);
 own_stack.push(2);
 own_stack.push(8);
 own_stack.push(9);
 own_stack.push(5);
 own_stack.push(6);
 own_stack.push(7);
  
 std::cout <<"\n min value in stack" << own_stack.get_min(); 

}


void stack::push (int data)
{


 std::cout <<"\n we are in push";

 if(count == capacity)
 {
   std::cout <<"\n stack full completely";
   return;

 }

 struct node *tmp = (struct node *) malloc(sizeof(struct node));

 tmp->data = data;
 tmp->next =NULL;


 if(root ==NULL)
  {
    root=tmp;
    min_elem= root->data;
    count++;
    return ;
  }

 if(min_elem > tmp->data)
  {
    min_elem = tmp->data;
  }
 
   
  tmp->next =root;
  root=tmp;  
  
  count++;
 

}

}

#include <stack>
#include <iostream>

class MinStack {
 public:
  void push(int n) {
    stack_.push(n);
    // track all multiple min values
    if (min_stack_.empty() || n <= min_stack_.top())
      min_stack_.push(n);
  }

  void pop() {
    if (stack_.empty())
      return;

    auto n = stack_.top();
    stack_.pop();
    if (n == min_stack_.top())
      min_stack_.pop();
  }

  int top() {
    return stack_.top();
  }

  int min() {
    return min_stack_.top();
  }

  bool empty() {
    return stack_.empty();
  }

private:
  std::stack<int> stack_;
  std::stack<int> min_stack_;
};

int main() {
  MinStack stack;
  for (auto n : {10, 9, 20, 8, 8, 30, 8, 7}) {
    stack.push(n);
    std::cout << "stack.top() is " << stack.top() << ", stack.min() is " << stack.min() << std::endl;
  }
  std::cout << std::endl;
  while (!stack.empty())
  {
    std::cout << "stack.top() is " << stack.top() << ", stack.min() is " << stack.min() << std::endl;
    stack.pop();
  }
}

O(1) solution? Kidding huh?
You have to go through all elemnts of stack to find minimum..that will make it O(n) for sure..

abcd