Create a customized data structure which evaluates functions in O(1)

Last Updated : 08 Sep, 2022

Create a customized data structure such that it has functions :-

GetLastElement();
RemoveLastElement();
AddElement()
GetMin()

All the functions should be of O(1)

Question Source : amazon interview questions

Approach :

create a custom stack of type structure with two elements, (element, min_till_now)
implement the functions on this custom data type

Implementation:

C++

// program to demonstrate customized data structure
// which supports functions in O(1)
#include <iostream>
#include <vector>
using namespace std;
const int MAXX = 1000;
 
// class stack
class stack {
    int minn;
    int size;
 
public:
    stack()
    {
        minn = 99999;
        size = -1;
    }
    vector<pair<int, int> > arr;
    int GetLastElement();
    int RemoveLastElement();
    int AddElement(int element);
    int GetMin();
};
 
// utility function for adding a new element
int stack::AddElement(int element)
{
    if (size > MAXX) {
        cout << "stack overflow, max size reached!\n";
        return 0;
    }
    if (element < minn)
        minn = element;
    arr.push_back(make_pair(element, minn));
    size++;
    return 1;
}
 
// utility function for returning last element of stack
int stack::GetLastElement()
{
    if (size == -1) {
        cout << "No elements in stack\n";
        return 0;
    }
    return arr[size].first;
}
 
// utility function for removing last element successfully;
int stack::RemoveLastElement()
{
    if (size == -1) {
        cout << "stack empty!!!\n";
        return 0;
    }
 
    // updating minimum element
    if (size > 0 && arr[size - 1].second > arr[size].second) {
        minn = arr[size - 1].second;
    }
    arr.pop_back();
    size -= 1;
    return 1;
}
 
// utility function for returning min element till now;
int stack::GetMin()
{
    if (size == -1) {
        cout << "stack empty!!\n";
        return 0;
    }
    return arr[size].second;
}
 
// Driver code
int main()
{
    stack s;
    int success = s.AddElement(5);
    if (success == 1)
        cout << "5 inserted successfully\n";
 
    success = s.AddElement(7);
    if (success == 1)
        cout << "7 inserted successfully\n";
 
    success = s.AddElement(3);
    if (success == 1)
        cout << "3 inserted successfully\n";
    int min1 = s.GetMin();
    cout << "min element  :: " << min1 << endl;
 
    success = s.RemoveLastElement();
    if (success == 1)
        cout << "removed successfully\n";
 
    success = s.AddElement(2);
    if (success == 1)
        cout << "2 inserted successfully\n";
 
    success = s.AddElement(9);
    if (success == 1)
        cout << "9 inserted successfully\n";
    int last = s.GetLastElement();
    cout << "Last element :: " << last << endl;
 
    success = s.AddElement(0);
    if (success == 1)
        cout << "0 inserted successfully\n";
    min1 = s.GetMin();
    cout << "min element  :: " << min1 << endl;
 
    success = s.RemoveLastElement();
    if (success == 1)
        cout << "removed successfully\n";
 
    success = s.AddElement(11);
    if (success == 1)
        cout << "11 inserted successfully\n";
    min1 = s.GetMin();
    cout << "min element  :: " << min1 << endl;
 
    return 0;
}

Java

// program to demonstrate customized data structure
// which supports functions in O(1)
import java.util.ArrayList;
public class Gfg 
{
   
  // class Pair 
  static class Pair{
    int element;
    int minElement;
 
    public Pair(int element, int minElement) {
      this.element = element;
      this.minElement = minElement;
    }
  }
  int min;
  ArrayList<Pair> stack = new ArrayList<>();
 
  public Gfg() {
    this.min = Integer.MAX_VALUE;
  }
 
  // utility function for adding a new element 
  void addElement(int x)
  {
    if(stack.size() == 0 || x < min)
    {
      min=x;
    }
    Pair pair = new Pair(x,min);
    stack.add(pair);
    System.out.println(x + " inserted successfully");
  }
 
  // utility function for returning last element of stack 
  int getLastElement()
  {
    if (stack.size() == 0)
    {
      System.out.println("UnderFlow Error");
      return -1;
    }
    else
    {
      return stack.get(stack.size() - 1).element;
    }
  }
 
  // utility function for removing last element successfully; 
  void removeLastElement()
  {
 
    if (stack.size() == 0)
    {
      System.out.println("UnderFlow Error");
    }
    else if (stack.size() > 1)
    {
      min=stack.get(stack.size() - 2).minElement;
    }
    else
    {
      min=Integer.MAX_VALUE;
    }
    stack.remove(stack.size() - 1);
    System.out.println("removed successfully");
  }
 
  // utility function for returning min element till now; 
  int getMin()
  {
    if (stack.size() == 0)
    {
      System.out.println("UnderFlow Error");
      return -1;
    }
    return stack.get(stack.size() - 1).minElement;
  }
 
  // Driver Code
  public static void main(String[] args) {
    Gfg newStack = new Gfg();
    newStack.addElement(5);
    newStack.addElement(7);
    newStack.addElement(3);
    System.out.println("min element :: "+newStack.getMin());
    newStack.removeLastElement();
    newStack.addElement(2);
    newStack.addElement(9);
    System.out.println("last element :: "+newStack.getLastElement());
    newStack.addElement(0);
    System.out.println("min element :: "+newStack.getMin());
    newStack.removeLastElement();
    newStack.addElement(11);
    System.out.println("min element :: "+newStack.getMin());
  }
}
 
// This code is contributed by AkashYadav4.

Python3

# Program to demonstrate customized data structure
# which supports functions in O(1)
import sys
 
stack = []
Min = sys.maxsize
 
# Utility function for adding a new element
def addElement(x):
     
    global Min, stack
    if (len(stack) == 0 or x < Min):
        Min = x
    pair = [x, Min]
    stack.append(pair)
    print(x, "inserted successfully")
 
# Utility function for returning last
# element of stack
def getLastElement():
     
    global Min, stack
     
    if (len(stack) == 0):
        print("UnderFlow Error")
        return -1
    else:
        return stack[-1][0]
 
# Utility function for removing last
# element successfully;
def removeLastElement():
     
    global Min, stack
    if (len(stack) == 0):
        print("UnderFlow Error")
    elif (len(stack) > 1):
        Min = stack[-2][1]
    else:
        Min = sys.maxsize
    stack.pop()
     
    print("removed successfully")
 
# Utility function for returning min 
# element till now;
def getMin():
     
    global Min, stack
    if (len(stack) == 0):
        print("UnderFlow Error")
        return -1
         
    return stack[-1][1]
 
# Driver code
addElement(5)
addElement(7)
addElement(3)
print("min element ::", getMin())
removeLastElement()
addElement(2)
addElement(9)
print("Last element ::", getLastElement())
addElement(0)
print("min element ::", getMin())
removeLastElement()
addElement(11)
print("min element ::", getMin())
 
# This code is contributed by mukesh07

C#

// program to demonstrate customized data structure
// which supports functions in O(1)
using System;
using System.Collections.Generic;
class GFG {
 
  static List<Tuple<int,int>> stack = new List<Tuple<int,int>>();
  static int min = Int32.MaxValue;
  
  // utility function for adding a new element
  static void addElement(int x)
  {
    if(stack.Count == 0 || x < min)
    {
      min=x;
    }
    Tuple<int,int> pair = new Tuple<int,int>(x,min);
    stack.Add(pair);
    Console.WriteLine(x + " inserted successfully");
  }
  
  // utility function for returning last element of stack
  static int getLastElement()
  {
    if (stack.Count == 0)
    {
      Console.WriteLine("UnderFlow Error");
      return -1;
    }
    else
    {
      return stack[stack.Count - 1].Item1;
    }
  }
  
  // utility function for removing last element successfully;
  static void removeLastElement()
  {
  
    if (stack.Count == 0)
    {
      Console.WriteLine("UnderFlow Error");
    }
    else if (stack.Count > 1)
    {
      min=stack[stack.Count - 2].Item2;
    }
    else
    {
      min=Int32.MaxValue;
    }
    stack.RemoveAt(stack.Count - 1);
    Console.WriteLine("removed successfully");
  }
  
  // utility function for returning min element till now;
  static int getMin()
  {
    if (stack.Count == 0)
    {
      Console.WriteLine("UnderFlow Error");
      return -1;
    }
    return stack[stack.Count - 1].Item2;
  }
   
  static void Main() {
    addElement(5);
    addElement(7);
    addElement(3);
    Console.WriteLine("min element :: "+getMin());
    removeLastElement();
    addElement(2);
    addElement(9);
    Console.WriteLine("Last element :: "+getLastElement());
    addElement(0);
    Console.WriteLine("min element :: "+getMin());
    removeLastElement();
    addElement(11);
    Console.WriteLine("min element :: "+getMin());
  }
}
 
// This code is contributed by divyeshrabadiya07.

Javascript

<script>
    // program to demonstrate customized data structure
    // which supports functions in O(1)
     
    let min;
    let stack = [];
 
    min = Number.MAX_VALUE
 
    // utility function for adding a new element
    function addElement(x)
    {
      if(stack.length == 0 || x < min)
      {
        min=x;
      }
      let pair = [x,min];
      stack.push(pair);
      document.write(x + " inserted successfully" + "</br>");
    }
 
    // utility function for returning last element of stack
    function getLastElement()
    {
      if (stack.length == 0)
      {
        document.write("UnderFlow Error" + "</br>");
        return -1;
      }
      else
      {
        return stack[stack.length - 1][0];
      }
    }
 
    // utility function for removing last element successfully;
    function removeLastElement()
    {
 
      if (stack.length == 0)
      {
        document.write("UnderFlow Error" + "</br>");
      }
      else if (stack.length > 1)
      {
        min=stack[stack.length - 2][1];
      }
      else
      {
        min=Number.MAX_VALUE;
      }
      stack.pop();
      document.write("removed successfully" + "</br>");
    }
 
    // utility function for returning min element till now;
    function getMin()
    {
      if (stack.length == 0)
      {
        document.write("UnderFlow Error" + "</br>");
        return -1;
      }
      return stack[stack.length - 1][1];
    }
     
    addElement(5);
    addElement(7);
    addElement(3);
    document.write("min element :: "+getMin() + "</br>");
    removeLastElement();
    addElement(2);
    addElement(9);
    document.write("Last element :: "+getLastElement() + "</br>");
    addElement(0);
    document.write("min element :: "+getMin() + "</br>");
    removeLastElement();
    addElement(11);
    document.write("min element :: "+getMin() + "</br>");
     
    // This code is contributed by rameshtravel07.
</script>

Output

5 inserted successfully
7 inserted successfully
3 inserted successfully
min element  :: 3
removed successfully
2 inserted successfully
9 inserted successfully
Last element :: 9
0 inserted successfully
min element  :: 0
removed successfully
11 inserted successfully
min element  :: 2

Time complexity: Each function runs in O(1)

Auxiliary space: O(n) for stack

GeeksforGeeks

Improve

How to implement stack using priority queue or heap?

Implement Stack and Queue using Deque

Stack implementation in different language

Some questions related to Stack implementation

Easy problems on Stack

Intermediate problems on Stack

Hard problems on Stack

Create a customized data structure which evaluates functions in O(1)

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?