Given an unsorted array arr of size n. The task is to find all the star and super star elements in the array. Star are those elements which are strictly greater than all the elements on its right side. Super star are those elements which are strictly greater than all the elements on its left and right side.
Note: Assume first element (arr[0]) is greater than all the elements on its left side, And last element (arr[n-1]) is greater than all the elements on its right side.
Example 1:
Input:
n = 10
arr[] = {1, 6, 5, 4, 7, 8, 4, 3, 2, 1}
Output: 
8 4 3 2 1 
8
Explanation: Star elements are 8, 4, 3, 2 and 1.
Super star element is 8.
Example 2:
Input:
a = 9
arr[] = {1, 2, 10, 3, 4, 5, 8, 10, 4}
Output: 
10 4 
-1
Explanation: Star elements are 10 and 4.
No super star element present here.
Your Task:
You don't need to read input or print anything. Your task is to complete the function getStarAndSuperStar() which takes the array of integers arr and n as parameters and returns an array of integers denoting the answer where first element is the super star element and rest are star elements. Return -1 in first element of the array if no super star element is present. The driver code itself prints the star elements in first line and super star element in second line.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 <= n <= 10^{6}
0 <= |arr[i]| <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3









def getStarAndSuperStar(arr, n):

    # code here

Solutions:
def getStarAndSuperStar(arr, n):
	star = [arr[-1]]
	super_star = []
	for i in arr[-2:-len(arr) - 1:-1]:
		if i > star[-1]:
			star.append(i)
	max_ele = max(star)
	count = 0
	for i in arr:
		if i == max_ele:
			count += 1
		if count > 1:
			max_ele = -1
	return [max_ele, ' '.join((str(x) for x in star[::-1]))]


def getStarAndSuperStar(arr, n):
	if n == 1:
		return [arr[n - 1], arr[n - 1]]
	a = []
	a.append(arr[n - 1])
	max_value = arr[n - 1]
	for i in range(n - 1, -1, -1):
		if arr[i] > max_value:
			a.append(arr[i])
			max_value = arr[i]
	arr.sort()
	if arr[n - 1] == arr[n - 2]:
		a.append(-1)
	else:
		a.append(arr[n - 1])
	a.reverse()
	return a


def getStarAndSuperStar(arr, n):
	mx = arr[-1]
	l = [arr[-1]]
	for i in range(n - 2, -1, -1):
		if arr[i] > mx:
			mx = arr[i]
			l.append(arr[i])
	c = arr.count(mx)
	l = l[::-1]
	if c > 1:
		l = [-1] + l
	else:
		l = [mx] + l
	return l


import heapq

def getStarAndSuperStar(arr, n):
	max_heap = []
	(star, superstar) = ({n - 1: 1}, {})
	for i in range(n - 1, -1, -1):
		if bool(max_heap):
			if arr[i] > -1 * max_heap[0]:
				star[i] = 1
		heapq.heappush(max_heap, -1 * arr[i])
	max_heap.clear()
	for i in range(n):
		if bool(max_heap):
			if arr[i] > -1 * max_heap[0]:
				if star.get(i, -1) != -1:
					superstar[arr[i]] = 1
		if bool(max_heap) == False:
			if star.get(i, -1) != -1:
				superstar[arr[i]] = 1
		heapq.heappush(max_heap, -1 * arr[i])
	super_ = list(superstar.keys())
	sub_ = list(star.keys())
	sub_ = [arr[i] for i in sub_]
	sub_.sort(reverse=True)
	if len(super_) == 0:
		sub_.insert(0, -1)
	else:
		sub_ = super_ + sub_
	return sub_


def getStarAndSuperStar(arr, n):
	star = [arr[-1]]
	for i in range(n - 1, -1, -1):
		if arr[i] > star[0]:
			star.insert(0, arr[i])
	if star[0] == max(arr) and arr.count(max(arr)) == 1:
		star.insert(0, star[0])
	else:
		star.insert(0, -1)
	return star


def reverse(ar, s, e):
	if len(ar) < 2:
		return
	else:
		while s < e:
			temp = ar[s]
			ar[s] = ar[e]
			ar[e] = temp
			s += 1
			e -= 1

def getStarAndSuperStar(arr, n):
	maxx = arr[-1]
	li = []
	if arr.count(max(arr)) > 1:
		li.append(-1)
	else:
		li.append(max(arr))
	li.append(arr[-1])
	for i in range(n - 2, -1, -1):
		if arr[i] > maxx:
			li.append(arr[i])
			maxx = arr[i]
	reverse(li, 1, len(li) - 1)
	return li


def getStarAndSuperStar(arr, n):
	lst = []
	mx = -9999999
	cnt = 0
	lst.append(arr[-1])
	for i in range(n - 2, -1, -1):
		mx = max(lst[-1], mx)
		if arr[i] > mx:
			lst.append(arr[i])
	mx1 = max(arr)
	if arr[0] == mx1 and arr[0] not in arr[1:]:
		lst.append(mx1)
		return lst[::-1]
	for i in range(n):
		if mx1 > arr[i]:
			cnt = cnt + 1
		else:
			break
	for j in range(n - 1, -1, -1):
		if mx1 > arr[j]:
			cnt = cnt + 1
		else:
			break
	if cnt + 1 == n:
		lst.append(mx1)
	else:
		lst.append(-1)
	return lst[::-1]


def getStarAndSuperStar(arr, n):
	(left_max, right_max) = (float('-inf'), float('-inf'))
	(left_max_arr, right_max_arr) = ([], [])
	for index in range(n):
		if arr[index] > left_max:
			left_max = arr[index]
		if arr[-index - 1] > right_max:
			right_max = arr[-index - 1]
		right_max_arr.append(right_max)
		left_max_arr.append(left_max)
	right_max_arr = right_max_arr[::-1]
	right_max_arr.append(float('-inf'))
	left_max_arr.append(float('-inf'))
	(star_elem, super_star_elem) = ('', '')
	for index in range(n):
		if right_max_arr[index + 1] < arr[index]:
			star_elem += str(arr[index]) + ' '
		if right_max_arr[index + 1] < arr[index] and left_max_arr[index - 1] < arr[index]:
			super_star_elem += str(arr[index]) + ' '
	super_star_elem = super_star_elem if super_star_elem else '-1'
	return (super_star_elem.strip(), star_elem.strip())


def getStarAndSuperStar(arr, n):
	maximum = max(arr)
	indexx = [i for i in range(n) if arr[i] == maximum]
	if len(indexx) > 1:
		superstar = [-1]
	else:
		superstar = [maximum]
	start_index = indexx[-1]
	star = []
	for i in range(-1, start_index - n - 1, -1):
		if i == -1:
			star.append(arr[i])
		elif arr[i] > star[-1]:
			star.append(arr[i])
	return superstar + star[::-1]


def getStarAndSuperStar(arr, n):
	if n == 1:
		return [arr[0], arr[0]]
	left = [0] * n
	left[0] = arr[0]
	for i in range(1, n):
		left[i] = max(left[i - 1], arr[i])
	right = [0] * n
	right[-1] = arr[-1]
	for i in range(n - 2, -1, -1):
		right[i] = max(right[i + 1], arr[i])
	star = []
	superstar = []
	if right[1] < right[0]:
		star.append(arr[i])
		superstar.append(arr[i])
	for i in range(1, n - 1):
		if right[i + 1] < arr[i] and arr[i] > left[i - 1]:
			star.append(arr[i])
			superstar.append(arr[i])
		elif right[i + 1] < arr[i]:
			star.append(arr[i])
	star.append(arr[-1])
	if left[-2] < arr[-1]:
		superstar.append(arr[-1])
	if superstar == []:
		star.insert(0, -1)
	else:
		star.insert(0, superstar[0])
	return star


def getStarAndSuperStar(arr, n):
	A = []
	maxi = -10 ** 6
	for i in range(n - 1, -1, -1):
		if arr[i] > maxi:
			maxi = arr[i]
			A.append(arr[i])
	if arr.count(maxi) > 1:
		A.append(-1)
	else:
		A.append(maxi)
	return A[::-1]


def getStarAndSuperStar(arr, n):
	a = max(arr)
	if arr.count(a) > 1:
		superstar = -1
	else:
		superstar = a
	star = arr[-1]
	ans = [arr[-1]]
	if n > 1:
		for j in range(n - 2, -1, -1):
			if arr[j] > star:
				star = arr[j]
				ans.append(star)
	ans = ans[::-1]
	ans.insert(0, superstar)
	return ans


def getStarAndSuperStar(arr, n):
	maxi = max(arr)
	if arr.count(maxi) > 1:
		maxi = -1
	ans = [maxi]
	s = [arr[n - 1]]
	for i in range(n - 2, -1, -1):
		if s[-1] < arr[i]:
			s.append(arr[i])
	return ans + s[::-1]


def getStarAndSuperStar(arr, n):
	arr.reverse()
	result = [arr[0]]
	superstar = True
	for item in arr[1:]:
		if item > result[-1]:
			result.append(item)
			superstar = True
		elif item == result[-1]:
			superstar = False
	if superstar:
		result.append(result[-1])
	else:
		result.append(-1)
	return result[::-1]


def getStarAndSuperStar(arr, n):
	maxi = -float('inf')
	a = []
	for x in arr[::-1]:
		if x > maxi:
			maxi = x
			a.append(x)
	ss = -float('inf')
	for x in arr:
		if x > ss:
			ss = x
	if arr.count(ss) > 1:
		ss = -1
	a.append(ss)
	return a[::-1]


def getStarAndSuperStar(a, n):
	x = max(a)
	y = a[n - 1]
	count = 0
	li = []
	for i in range(n - 1, -1, -1):
		if a[i] >= y and a[i] <= x:
			y = max(a[i], y)
			if count == 0:
				if a[i] not in li:
					li.append(a[i])
			if a[i] == x:
				count += 1
	if count > 1:
		li.append(-1)
	elif count == 1:
		li.append(x)
	return list(reversed(li))


def getStarAndSuperStar(arr: list, n: int) -> list:
	star = [arr[-1]]
	super_star_index = maxIndex(arr)
	super_star = arr[super_star_index]
	maximum = arr[-1]
	for i in range(n - 2, -1, -1):
		if arr[i] > maximum:
			star.insert(0, arr[i])
			maximum = arr[i]
	for x in arr[:super_star_index] + arr[super_star_index + 1:]:
		if x == super_star:
			super_star = -1
			break
	return [super_star] + star

def maxIndex(arr: list) -> int:
	(max_index, max_value) = (None, float('-inf'))
	for (i, v) in enumerate(arr):
		if v > max_value:
			(max_index, max_value) = (i, v)
	return max_index


def getStarAndSuperStar(arr, n):
	ls = []
	mx = arr[n - 1]
	superStar = arr[n - 1]
	ls.append(mx)
	for i in range(1, n):
		if arr[n - i - 1] > mx:
			ls.insert(0, arr[n - i - 1])
			superStar = arr[n - i - 1]
			mx = arr[n - i - 1]
		elif arr[n - i - 1] == superStar:
			superStar = -1
	ls.insert(0, superStar)
	return ls


def freq(a, l):
	c = 0
	for i in l:
		if a == i:
			c += 1
		if c > 1:
			return True
	return False

def getStarAndSuperStar(arr, n):
	l = []
	h = -50000
	for i in range(n - 1, -1, -1):
		if h < arr[i]:
			h = arr[i]
			l.append(h)
	if freq(max(arr), arr):
		l.append(-1)
	else:
		l.append(max(arr))
	l.reverse()
	return l


def getStarAndSuperStar(arr, n):
	star = []
	superstar = -1
	maxi = -float('inf')
	for i in range(n - 1, -1, -1):
		if arr[i] > maxi:
			star.append(arr[i])
			maxi = arr[i]
			superstar = arr[i]
		elif arr[i] == superstar:
			superstar = -1
	star.append(superstar)
	return star[::-1]


def getStarAndSuperStar(arr, n):
	result = []
	result.append(arr[-1])
	maxi = arr[-1]
	for i in range(n - 1, -1, -1):
		if arr[i] > maxi:
			result.append(arr[i])
			maxi = arr[i]
	count = 0
	for i in range(n):
		if arr[i] == maxi:
			count = count + 1
	if count > 1:
		result.append(-1)
	else:
		result.append(maxi)
	return result[::-1]


def getStarAndSuperStar(arr, n):
	l = []
	arr = arr[::-1]
	l.append(arr[0])
	for i in range(1, n):
		if arr[i] > l[len(l) - 1]:
			l.append(arr[i])
	if arr.count(max(arr)) > 1:
		l.append(-1)
	else:
		l.append(max(arr))
	l = l[::-1]
	return l


def getStarAndSuperStar(arr, n):
	if n == 1:
		return [arr[0], arr[0]]
	left = [0] * n
	right = [0] * n
	left[0] = arr[0]
	for i in range(1, n):
		left[i] = max(left[i - 1], arr[i])
	right[n - 1] = arr[n - 1]
	for i in range(n - 2, -1, -1):
		right[i] = max(right[i + 1], arr[i])
	ans = [-1]
	for j in range(1, n):
		if right[j] != right[j - 1]:
			ans.append(right[j - 1])
	ans.append(right[n - 1])
	if arr[0] > right[1]:
		ans[0] = arr[0]
	elif arr[n - 1] > left[n - 2]:
		ans[0] = arr[n - 1]
	for i in range(1, n - 1):
		if arr[i] > left[i - 1] and arr[i] > right[i + 1]:
			ans[0] = arr[i]
	return ans


def getStarAndSuperStar(arr, n):
	s = [arr[-1]]
	m = arr[-1]
	for i in range(n - 2, -1, -1):
		if arr[i] > m:
			m = arr[i]
			s.append(arr[i])
	res = s[::-1]
	if arr.count(m) >= 2:
		res.insert(0, -1)
	else:
		res.insert(0, m)
	return res


def getStarAndSuperStar(arr, n):
	a = []
	leader = arr[n - 1]
	a.append(leader)
	for i in range(n - 1, -1, -1):
		if arr[i] > leader:
			a.append(arr[i])
			leader = arr[i]
	a.sort(reverse=True)
	if arr.count(leader) > 1:
		a.insert(0, -1)
	else:
		a.insert(0, leader)
	return a


def getStarAndSuperStar(arr, n):
	S1 = []
	maxi = arr[n - 1]
	S1.append(arr[n - 1])
	for i in arr[::-1]:
		if i > maxi:
			S1.append(i)
			maxi = i
	f = max(arr)
	if arr.count(f) > 1:
		f = -1
	s2 = []
	s2.append(f)
	for y in S1[::-1]:
		s2.append(y)
	return s2


def getStarAndSuperStar(arr, n):
	if n == 1:
		return [arr[0], arr[0]]
	l = []
	lm = arr[0]
	for i in arr:
		if i > lm:
			lm = i
		l.append(lm)
	r = []
	rm = arr[-1]
	for i in arr[::-1]:
		if i > rm:
			rm = i
		r.append(rm)
	r = r[::-1]
	star = []
	for i in range(len(arr) - 1):
		if arr[i] > r[i + 1]:
			star.append(arr[i])
	star.append(arr[-1])
	super_star = []
	if arr[0] > r[1]:
		super_star.append(arr[0])
	for i in range(1, len(arr) - 1):
		if arr[i] > r[i + 1] and arr[i] > l[i - 1]:
			super_star.append(arr[i])
	if arr[-1] > l[-2]:
		super_star.append(arr[-1])
	x = []
	if len(super_star) == 0:
		x.append(-1)
	else:
		x.append(super_star[0])
	for i in star:
		x.append(i)
	return x


def getStarAndSuperStar(arr, n):
	stars = []
	maxiR = -float('inf')
	leftValuesMinor = True
	for index in range(n - 1, -1, -1):
		value = arr[index]
		if maxiR < value:
			stars.insert(0, value)
			maxiR = value
			leftValuesMinor = True
		elif maxiR == value:
			leftValuesMinor = False
	if leftValuesMinor:
		stars.insert(0, maxiR)
	else:
		stars.insert(0, -1)
	return stars


def getStarAndSuperStar(arr, n):
	largest = None
	isSuperStar = False
	star = list()
	for i in reversed(range(n)):
		if largest == None or arr[i] > largest:
			star.append(arr[i])
			largest = arr[i]
			isSuperStar = True
		elif arr[i] == largest:
			isSuperStar = False
	if isSuperStar:
		star.append(largest)
	else:
		star.append(-1)
	return star[::-1]


def getStarAndSuperStar(arr, n):
	mx = -float('inf')
	mxcnt = 1
	right = []
	for x in arr[::-1]:
		if x == mx:
			mxcnt = 0
		elif x > mx:
			mx = x
			right.append(mx)
			mxcnt = 1
	if mxcnt:
		right = [mx] + right[::-1]
	else:
		right = [-1] + right[::-1]
	return right


import sys

def getStarAndSuperStar(a, n):
	res = []
	maxi = -sys.maxsize
	for i in range(n - 1, -1, -1):
		if a[i] > maxi:
			res.append(a[i])
			maxi = a[i]
			flag = 1
		elif a[i] == maxi:
			flag = 0
	if flag == 0:
		maxi = -1
	res.append(maxi)
	return res[::-1]


def getStarAndSuperStar(a, n):
	s = [a[-1]]
	m = len(a) - 1
	i = len(a) - 2
	while i >= 0:
		if a[i] > a[m]:
			m = i
			s.insert(0, a[i])
		i -= 1
	j = m - 1
	while j >= 0 and a[j] < a[m]:
		j -= 1
	if j == -1:
		s.insert(0, a[m])
	else:
		s.insert(0, -1)
	return s


import sys

def getStarAndSuperStar(arr, n):
	left_max = [-1 for i in range(n)]
	left_max[0] = -sys.maxsize
	right_max = [-1 for i in range(n)]
	right_max[n - 1] = -sys.maxsize
	for i in range(1, n):
		left_max[i] = max(left_max[i - 1], arr[i - 1])
	for i in range(n - 2, -1, -1):
		right_max[i] = max(right_max[i + 1], arr[i + 1])
	stars = []
	index = []
	for i in range(n):
		if arr[i] > right_max[i]:
			stars.append(arr[i])
			index.append(i)
	super_star = []
	for i in index:
		if arr[i] > left_max[i]:
			super_star.append(arr[i])
			break
	if len(super_star) == 0:
		super_star = [-1]
	super_star.extend(stars)
	return super_star


def getStarAndSuperStar(arr, n):
	a = []
	maxi = -100000000000000000
	b = max(arr)
	if arr.count(b) == 1:
		a.append(b)
	else:
		a.append(-1)
	for i in range(n - 1, -1, -1):
		if arr[i] > maxi:
			a.append(arr[i])
			maxi = arr[i]
	return list(a[0:1] + a[1:][::-1])


def getStarAndSuperStar(arr, n):
	l = []
	x = -10 ** 9
	for i in range(n - 1, -1, -1):
		if arr[i] > x:
			l.append(arr[i])
			x = arr[i]
	m = max(arr)
	c = 0
	for i in arr:
		if m == i:
			c += 1
	if c != 1:
		l.append(-1)
	else:
		l.append(x)
	l.reverse()
	return l


def getStarAndSuperStar(arr, n):
	res = []
	maxi = float('-inf')
	flag = 0
	for i in range(n - 1, -1, -1):
		if arr[i] > maxi:
			res.append(arr[i])
			maxi = arr[i]
			flag = 1
		elif arr[i] == maxi:
			flag = 0
	if flag == 0:
		maxi = -1
	res.append(maxi)
	return res[::-1]


def getStarAndSuperStar(arr, n):
	r = []
	ss = True
	r.append(arr[-1])
	for i in range(n - 2, -1, -1):
		if arr[i] > r[0]:
			ss = True
			r.insert(0, arr[i])
		elif arr[i] == r[0]:
			ss = False
	if not ss:
		r.insert(0, -1)
	else:
		r.insert(0, r[0])
	return r


def getStarAndSuperStar(arr, n):
	l = []
	m = -float('inf')
	for i in range(n - 1, -1, -1):
		if arr[i] > m:
			l.append(arr[i])
			m = arr[i]
	d = {}
	for i in arr:
		d[i] = d.get(i, 0) + 1
	if d[m] > 1:
		l.append(-1)
	else:
		l.append(m)
	l.reverse()
	return l


def getStarAndSuperStar(arr, n):
	sa = [arr[-1]]
	d = dict()
	d1 = dict()
	for i in range(n - 1, -1, -1):
		if arr[i] > sa[0] and arr[i] not in d.keys():
			sa.insert(0, arr[i])
			d[arr[i]] = 1
		try:
			d1[arr[i]] = d1[arr[i]] + 1
		except:
			d1[arr[i]] = 1
	if sa[0] in d1.keys() and d1[sa[0]] > 1:
		sa.insert(0, -1)
	else:
		sa.insert(0, sa[0])
	return sa


def getStarAndSuperStar(arr, n):
	ans = []
	superstar = max(arr)
	if arr.count(superstar) == 1:
		ans.append(superstar)
	else:
		ans.append(-1)
	stack = [arr[-1]]
	for i in range(n - 2, -1, -1):
		temp = arr[i]
		if temp > stack[-1]:
			stack.append(temp)
	stack = stack[::-1]
	for ele in stack:
		ans.append(ele)
	return ans


def getStarAndSuperStar(arr, n):
	stack = []
	super_star = max(arr)
	for i in reversed(range(n)):
		if len(stack) == 0 or stack[-1] < arr[i]:
			stack.append(arr[i])
		elif super_star == arr[i]:
			super_star = -1
	stack.append(super_star)
	return stack[::-1]


def getStarAndSuperStar(arr, n):
	right = []
	left = []
	for i in arr:
		right.append(i)
		left.append(i)
	max_right = arr[n - 1]
	max_left = arr[0]
	star = []
	super_star = []
	right[n - 1] = -999
	left[0] = -999
	for i in range(n - 2, -1, -1):
		if arr[i + 1] > max_right:
			max_right = arr[i + 1]
		right[i] = max_right
	for i in range(1, n):
		if arr[i - 1] > max_left:
			max_left = arr[i - 1]
		left[i] = max_left
	for i in range(0, n):
		if arr[i] > right[i]:
			star.append(arr[i])
			if arr[i] > left[i]:
				super_star.append(arr[i])
	res = []
	if len(super_star) == 0:
		res.append(-1)
		res = res + star
	else:
		res = super_star + star
	return res


def getStarAndSuperStar(arr, n):
	ans = []
	ans.append(arr[n - 1])
	for i in range(n - 2, -1, -1):
		if arr[i] > ans[0]:
			ans.insert(0, arr[i])
	if arr.count(max(arr)) == 1:
		ans.insert(0, max(arr))
	else:
		ans.insert(0, -1)
	return ans