• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Get Minimum element in O(1) from input numbers or Stack

August 16, 2014 by Dhaval Dave

Question : Get Minimum element in O(1) from Input Numbers or Stack

– With any traditional way we can’t get minimum element in O(1)
– so we need to come up with different data structure.
– As its very old and famous question We are directly explaining logic

Logic 1)
Keep Two Stacks A and B.
A will contain all numbers which are input by users.
B will contain only minimum number from all input numbers.
ex. Input 10,20,5,30,2

Consider the following input
A                        B  (minimum elements)
2  --> TOP               2   ...
30                       5   ...
5                        5  (smallest in 10,20,5 input)
20                       10 (smallest in 10,20 input)
10                       10 (smallest at beginning)
so as shown in figure B (minimum element stack will keep all smallest numbers wrt input)

Pros
– storing minimum element for each input.
– if current minimum element is popped , we still have minimum element in present stack

Cons
– O(n) Extra Space.

Code :

#include<iostream>
#include<stdlib.h>
using namespace std;
class Stack
{
private:
    static const int max = 100;
    int arr[max];
    int top;
public:
    Stack() { top = -1; }
    bool isEmpty();
    bool isFull();
    int pop();
    void push(int x);
};
bool Stack::isEmpty()
{
    if(top == -1)
        return true;
    return false;
}
bool Stack::isFull()
{
    if(top == max - 1)
        return true;
    return false;
}
int Stack::pop()
{
    if(isEmpty())
    {
        cout<<"Stack Underflow";
        abort();
    }
    int x = arr[top];
    top--;
    return x;
}
void Stack::push(int x)
{
    if(isFull())
    {
        cout<<"Stack Overflow";
        abort();
    }
    top++;
    arr[top] = x;
}
//Stack

class SpecialStack: public Stack
{
    Stack min;
public:
    int pop();
    void push(int x);
    int getMin();
};
 
void SpecialStack::push(int x)
{
    if(isEmpty()==true)
    {
        Stack::push(x);
        min.push(x);
    }
    else
    {
        Stack::push(x);
        int y = min.pop();
        min.push(y);
        if( x < y )
          min.push(x);
        else
          min.push(y);
    }
}
int SpecialStack::pop()
{
    int x = Stack::pop();
    min.pop();
    return x;
}
int SpecialStack::getMin()
{
    int x = min.pop();
    min.push(x);
    return x;
}
int main()
{
    SpecialStack s;
    s.push(10);
    s.push(5);
    s.push(20);
    s.push(30);
    cout<<s.getMin()<<endl;
    s.push(1);
    cout<<s.getMin();
    return 0;
}

C Working Code : Find here : http://ideone.com/qOtFoG
C++ Working code : Find here : http://ideone.com/mgtTQY

Logic 2)

To Get Minimum element in O(1) from Input or Stack,  Instead of keeping a stack of minimum elements in B, we can optimism the space complexity for above solution with single minimum number.

Consider the following input
A                        B  (minimum elements)
2  --> TOP               
30                       
5                        2  
20                       5 
10                       10 (smallest at beginning)

If You pop from A, Pop from B (min elem stack as well) and both’s data is not matching, Push B’s top element to B.
Consider sequence
Pop A. So popped element from A is 2, and B’s popped element is 2. so now min element is for now on is 5.
Pop A, So popped element from A is 30 and B’s popped element is 5, both are not matching, so push 5 to B again. so in B elements are 5,10 and will be min element.

Code :

In above C++ code, change these two methods Push and Pop

void SpecialStack::push(int x)
{
    if(isEmpty()==true){
        Stack::push(x);
        min.push(x);
    }
    else {
        Stack::push(x);
        int y = min.pop();
        min.push(y);
  
        if( x <= y )
            min.push(x);
    }
}
 
int SpecialStack::pop()
{
    int x = Stack::pop();
    int y = min.pop(); 
    if ( y != x )
        min.push(y);
    return x;
}

Similar Articles

Filed Under: Adobe Interview Questions, Amazon Interview Question, Flipkart Interview Questions, Interview Questions, Microsoft Interview Questions, problem Tagged With: Array, Stack

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Longest Increasing Subsequence

Reverse a Linked List in groups of given size

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

Edit Distance ( Dynamic Programming )

Singly linked list

Urban Ladder Written Test.

Sequence Finder Dynamic Programming

C Program for TAIL command of UNIX

Count number of ways to reach a given score in a game

Adobe Interview Questions 8 month Exp

Find Percentage of Words matching in Two Strings

Hackerearth : Counting Subarrays

Stock Buy Sell to Maximize Profit

Implement LRU Cache

SAP Off Campus Hiring_ March 2015 Verbal Skills

Get K Max and Delete K Max in stream of incoming integers

Diagonal Traversal of Binary Tree

Practo Hiring Experience

Spanning Tree

ADOBE Aptitude C Language Test

Binary Tree Isomorphic to each other

Find the smallest window in a string containing all characters of another string

Naurki.com Security Breach

Length of the longest substring without repeating characters

Find if a binary tree is height balanced ?

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Find loop in Singly linked list

25 horses 5 tracks Find 3 fastest puzzle

VMWare Openings

Level order traversal in Spiral form

Copyright © 2025 · Genesis Framework · WordPress · Log in