You are given N elements and your task is to Implement a Stack in which you can get a minimum element in O(1) time.
Example 1:
Input:
push(2)
push(3)
pop()
getMin()
push(1)
getMin()
Output: 2 1
Explanation: In the first test case for
query 
push(2)  Insert 2 into the stack.
         The stack will be {2}
push(3)  Insert 3 into the stack.
         The stack will be {2 3}
pop()    Remove top element from stack 
         Poped element will be 3 the
         stack will be {2}
getMin() Return the minimum element
         min element will be 2 
push(1)  Insert 1 into the stack.
         The stack will be {2 1}
getMin() Return the minimum element
         min element will be 1
Your Task:
You are required to complete the three methods push() which takes one argument an integer 'x' to be pushed into the stack, pop() which returns an integer popped out from the stack, and getMin() which returns the min element from the stack. (-1 will be returned if for pop() and getMin() the stack is empty.)
Expected Time Complexity: O(1) for all the 3 methods.
Expected Auxiliary Space: O(1) for all the 3 methods.
Constraints:
1 <= Number of queries <= 100
1 <= values of the stack <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class stack:

    def __init__(self):

        self.s=[]

        self.minEle=None



    def push(self,x):

        #CODE HERE



    def pop(self):

        #CODE HERE

        



    def getMin(self):

        #CODE HERE

Solutions:
class stack:

	def __init__(self):
		self.s = []
		self.minEle = -1
		self.length = 0

	def push(self, x):
		if len(self.s) == 0:
			self.s.append(x)
			self.minEle = x
			self.length += 1
		elif x > self.minEle:
			self.s.append(x)
			self.length += 1
		else:
			topel = 2 * x - self.minEle
			self.s.append(topel)
			self.length += 1
			self.minEle = x

	def pop(self):
		if len(self.s) != 0:
			if self.s[-1] < self.minEle:
				a = self.minEle
				self.minEle = 2 * self.minEle - self.s[-1]
				if len(self.s) == 1:
					self.minEle = -1
				self.length -= 1
				self.s.pop()
				return a
			else:
				if len(self.s) == 1:
					self.minEle = -1
				self.length -= 1
				return self.s.pop()
		else:
			return -1

	def getMin(self):
		return self.minEle


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		self.s.append(x)

	def pop(self):
		if len(self.s) != 0:
			k = self.s.pop(-1)
		else:
			k = -1
		return k

	def getMin(self):
		if len(self.s) == 0:
			return -1
		return min(self.s)


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		if len(self.s) == 0:
			self.s.append(x)
			self.minEle = x
			return
		if x >= self.minEle:
			self.s.append(x)
		else:
			self.s.append(2 * x - self.minEle)
			self.minEle = x

	def pop(self):
		if len(self.s) == 0:
			return -1
		y = self.s.pop()
		if y < self.minEle:
			min = self.minEle
			self.minEle = 2 * self.minEle - y
			return min
		return y

	def getMin(self):
		if not self.s:
			return -1
		return self.minEle


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		if len(self.s) == 0:
			self.minEle = x
			self.s.append(x)
		elif self.minEle > x:
			temp = self.minEle
			self.minEle = x
			self.s.append(2 * x - temp)
		else:
			self.s.append(x)
		return

	def pop(self):
		if len(self.s) == 0:
			return -1
		if self.s[-1] < self.minEle:
			temp = self.minEle
			oldmin = 2 * temp - self.s[-1]
			self.minEle = oldmin
			self.s.pop()
			return temp
		ans = self.s[-1]
		self.s.pop()
		return ans

	def getMin(self):
		if len(self.s) == 0:
			return -1
		return self.minEle


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		self.s.append(x)

	def pop(self):
		if len(self.s) == 0:
			return -1
		return self.s.pop()

	def getMin(self):
		if len(self.s) == 0:
			min = -1
			return min
		min = self.s[0]
		for i in self.s:
			if i < min:
				min = i
		return min


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		if not self.s:
			self.s.append(x)
			self.minEle = x
		elif x < self.minEle:
			self.s.append(2 * x - self.minEle)
			self.minEle = x
		else:
			self.s.append(x)

	def pop(self):
		if not self.s:
			return -1
		top = self.s.pop()
		if top < self.minEle:
			poppedEle = self.minEle
			self.minEle = 2 * self.minEle - top
			return poppedEle
		else:
			return top

	def getMin(self):
		if not self.s:
			return -1
		return self.minEle


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		if len(self.s) == 0:
			self.s.append(x)
			self.minEle = x
		else:
			if x > self.minEle:
				self.s.append(x)
			if x <= self.minEle:
				temp = 2 * x - self.minEle
				self.minEle = x
				self.s.append(temp)

	def pop(self):
		if len(self.s) == 0:
			return -1
		el = self.s.pop()
		if el <= self.minEle:
			val = self.minEle
			self.minEle = 2 * self.minEle - el
			return val
		if el > self.minEle:
			val = el
			return val

	def getMin(self):
		if len(self.s) == 0:
			return -1
		if self.minEle:
			return self.minEle


class stack:

	def __init__(self):
		self.st = []
		self.mini = None

	def push(self, x):
		if len(self.st) == 0:
			self.st.append(x)
			self.mini = x
		elif x > self.mini:
			self.st.append(x)
		elif x <= self.mini:
			val = 2 * x - self.mini
			self.mini = x
			self.st.append(val)

	def pop(self):
		if len(self.st) == 0:
			return -1
		top = self.st.pop()
		if top > self.mini:
			return top
		elif top <= self.mini:
			ans = self.mini
			val = 2 * self.mini - top
			self.mini = val
			return ans

	def getMin(self):
		if len(self.st) == 0:
			return -1
		if self.mini:
			return self.mini
		return -1


class stack:

	def __init__(self):
		self.stack = []
		self.mini = None

	def push(self, x):
		if self.stack == []:
			self.stack.append(x)
			self.mini = x
		elif x < self.mini:
			self.stack.append(2 * x - self.mini)
			self.mini = x
		else:
			self.stack.append(x)

	def pop(self):
		if self.stack == []:
			return -1
		else:
			top = self.stack.pop()
			if top < self.mini:
				value = self.mini
				self.mini = 2 * self.mini - top
				return value
			else:
				return top

	def getMin(self):
		if len(self.stack) > 0:
			return self.mini
		return -1


class stack:

	def __init__(self):
		self.s = []
		self.s1 = []
		self.minEle = None

	def push(self, x):
		if len(self.s) == 0 and len(self.s1) == 0:
			self.s1.append(x)
		elif len(self.s1) > 0 and self.s1[-1] >= x:
			self.s1.append(x)
		self.s.append(x)

	def pop(self):
		if len(self.s) == 0:
			return -1
		if len(self.s1) > 0 and self.s1[-1] == self.s[-1]:
			self.s1.pop()
		ans = self.s[-1]
		self.s.pop()
		return ans

	def getMin(self):
		if len(self.s1) == 0:
			return -1
		m = self.s1[-1]
		return m


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		self.s.append(x)

	def pop(self):
		if len(self.s) == 0:
			return -1
		ans = self.s[-1]
		self.s.pop()
		return ans

	def getMin(self):
		if len(self.s) == 0:
			return -1
		m = min(self.s)
		return m


class stack:

	def __init__(self):
		self.s = []
		self.m = None

	def push(self, x):
		if self.m is None or len(self.s) == 0:
			self.m = x
		self.s.append(x - self.m)
		if x < self.m:
			self.m = x

	def pop(self):
		if len(self.s) != 0:
			if self.s[-1] >= 0:
				return self.m + self.s.pop()
			else:
				temp = self.m
				self.m = temp - self.s[-1]
				self.s.pop()
				return temp
		else:
			return -1

	def getMin(self):
		if len(self.s) != 0:
			return self.m
		else:
			return -1


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		if not self.s:
			self.minEle = x
			self.s.append(x)
		elif x < self.minEle:
			self.s.append(2 * x - self.minEle)
			self.minEle = x
		else:
			self.s.append(x)

	def pop(self):
		if not self.s:
			return -1
		p = self.s.pop()
		k = self.minEle
		if p < k:
			self.minEle = 2 * k - p
			return k
		else:
			return p

	def getMin(self):
		if not self.s:
			return -1
		return self.minEle


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		self.s.append(x)

	def pop(self):
		if not self.s:
			return -1
		x = self.s.pop()
		return x

	def getMin(self):
		if not self.s:
			return -1
		return min(self.s)


class stack:

	def __init__(self):
		self.stack = []
		self.min_stack = []

	def push(self, x):
		self.stack.append(x)
		if not self.min_stack or x <= self.min_stack[-1]:
			self.min_stack.append(x)

	def pop(self):
		if not self.stack:
			return -1
		popped_element = self.stack.pop()
		if popped_element == self.min_stack[-1]:
			self.min_stack.pop()
		return popped_element

	def getMin(self):
		if not self.min_stack:
			return -1
		return self.min_stack[-1]


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		if len(self.s) == 0:
			self.s.append(x)
			self.minEle = x
		elif x < self.minEle:
			self.s.append(2 * x - self.minEle)
			self.minEle = x
		else:
			self.s.append(x)

	def pop(self):
		k = 0
		if len(self.s) == 0:
			return -1
		else:
			z = self.s.pop()
			if z < self.minEle:
				k = self.minEle
				self.minEle = 2 * k - z
			else:
				k = z
			return k

	def getMin(self):
		if len(self.s) == 0:
			return -1
		else:
			return self.minEle


class stack:

	def __init__(self):
		self.s = []
		self.m = []

	def push(self, x):
		self.s.append(x)
		self.m.append(min(x, self.m[-1] if self.m else x))

	def pop(self):
		self.m.pop() if self.m else -1
		return self.s.pop() if self.s else -1

	def getMin(self):
		return self.m[-1] if self.m else -1


class stack:

	def __init__(self):
		self.s = []
		self.minEle = []

	def push(self, x):
		self.s.append(x)
		if len(self.minEle) != 0:
			top = self.minEle.pop()
			self.minEle.append(top)
			self.minEle.append(min(top, x))
		else:
			self.minEle.append(x)

	def pop(self):
		res = -1
		if len(self.s) != 0:
			res = self.s.pop()
			self.minEle.pop()
		return res

	def getMin(self):
		res = -1
		if len(self.minEle) != 0:
			res = self.minEle.pop()
			self.minEle.append(res)
		return res


class stack:

	def __init__(self):
		self.s = []

	class Node:

		def __init__(self, val, Min):
			self.val = val
			self.min = Min

	def push(self, x):
		if not self.s:
			self.s.append(self.Node(x, x))
		else:
			Min = min(self.s[-1].min, x)
			self.s.append(self.Node(x, Min))

	def pop(self):
		if self.s:
			return self.s.pop().val
		return -1

	def top(self):
		return self.s[-1].val

	def getMin(self):
		if self.s:
			return self.s[-1].min
		return -1


class stack:

	def __init__(self):
		self.stack = []
		self.mini = None

	def push(self, x):
		if len(self.stack) == 0:
			self.stack.append(x)
			self.mini = x
		elif x < self.mini:
			self.stack.append(2 * x - self.mini)
			self.mini = x
		else:
			self.stack.append(x)

	def pop(self):
		k = 0
		if len(self.stack) == 0:
			return -1
		else:
			z = self.stack.pop()
			if z < self.mini:
				k = self.mini
				self.mini = 2 * k - z
			else:
				k = z
			return k

	def getMin(self) -> int:
		if len(self.stack) == 0:
			return -1
		else:
			return self.mini


class stack:

	def __init__(self):
		self.s = []

	def push(self, x):
		self.s.append(x)

	def pop(self):
		if self.s:
			k = self.s.pop(-1)
		else:
			k = -1
		return k

	def getMin(self):
		if not self.s:
			return -1
		return min(self.s)


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		if not self.s:
			self.s.append(x)
			self.minEle = x
		elif x <= self.minEle:
			self.s.append(2 * x - self.minEle)
			self.minEle = x
		else:
			self.s.append(x)

	def pop(self):
		if not self.s:
			return -1
		else:
			y = self.s.pop()
			if y < self.minEle:
				temp = self.minEle
				self.minEle = 2 * self.minEle - y
				return temp
			else:
				return y

	def getMin(self):
		if not self.s:
			return -1
		else:
			return self.minEle


class stack:

	def __init__(self):
		self.s = []
		self.minEle = None

	def push(self, x):
		self.s.append(x)
		if self.minEle is None:
			self.minEle = [x]
		elif self.minEle[-1] >= x:
			self.minEle.append(x)

	def pop(self):
		if self.s == []:
			return -1
		else:
			x = self.s.pop()
			if len(self.s) == 0:
				self.minEle = None
				self.s = []
			elif x == self.minEle[-1]:
				self.minEle.pop()
			return x

	def getMin(self):
		if self.minEle is None:
			return -1
		return self.minEle[-1]


class stack:

	def __init__(self):
		self.s = []
		self.minEle = float('inf')

	def push(self, x):
		self.minEle = min(self.minEle, x)
		self.s.append([x, self.minEle])

	def pop(self):
		if self.s == []:
			return -1
		n = self.s.pop()
		if self.s != []:
			self.minEle = self.s[-1][1]
		else:
			self.minEle = float('inf')
		return n[0]

	def getMin(self):
		if self.s == []:
			return -1
		return self.s[-1][1]