Next Greater Element using Stack
Pradip Dharam
![Pradip Dharam]()
Pradip Dharam
Python Developer, Data Engineer, pySpark, ML (NLP) Product's Features Development & Refactoring, PR Reviews, git, MongoDB, Familiar with Airflow, Docker. Prototyping, Pandas, Numpy, SQL, sklearn. Novice to CICD.
Find next greater element for each element in given array. Check problem statement at https://www.geeksforgeeks.org/problems/next-larger-element-1587115620/1
Solved on my on machine pyCharm. Below the solution.
class Stack:
def __init__(self):
self.a = [None] * 1000000
self.top = -1
def pop(self):
if not self.empty:
p = self.a[self.top]
self.top = self.top - 1
return p
else:
return -1
def push(self, x):
if not self.full:
self.top = self.top + 1
self.a[self.top] = x
def top_element(self):
if not self.empty:
return self.a[self.top]
else:
raise RuntimeError("Stack is empty")
@property
def empty(self):
return self.top == -1
@property
def full(self):
return self.top == 1000000
def print(self):
print("stack:", self.a[:self.top + 1], "top:", self.top, )
stack = Stack()
arr = [1, 3, 2, 4]
# arr = [6, 8, 0, 1, 3]
# arr =[10, 20, 30, 50]
# arr =[50, 40, 30, 10]
n = len(arr)
ans = [None] * n
stack.push(0)
for i in range(1, n):
# print("i: ", i, "arr[i]: ", arr[i], "arr[top_ele: ",arr[stack.top_element()], "ans: ", ans)
# stack.print()
while not stack.empty and arr[i] > arr[stack.top_element()]:
ans[stack.pop()] = arr[i]
# stack.print()
stack.push(i)
# stack.print()
while not stack.empty:
ans[stack.pop()] = -1
# stack.print()
print(ans)