Given an array of positive integers, replace every element with the least greater element to its right.
 If there is no greater element to its right, replace it with -1. For instance, given the array 
 
 `[8, 58, 71, 18, 31, 32, 63, 92, 43, 3, 91, 93, 25, 80, 28]`,
 
 the desired output is 
 
 `[18, 63, 80, 25, 32, 43, 80, 93, 80, 25, 93, -1, 28, -1, -1]`.

Your task is to create a function "arrayManip()" that takes in an array as its argument, manipulates the array as described above, then return the resulting array.

Note: Return a new array, rather than modifying the passed array.

Source: codewars | Difficulty: EASY
Tags: Data structures

Range queries

Starter code: def array_manip(array):
	

Solutions:
def array_manip(array):
	return [min([a for a in array[i + 1:] if a > array[i]], default=-1) for i in range(len(array))]


def array_manip(array):
	return [min((r for r in array[i:] if r > n), default=-1) for (i, n) in enumerate(array, 1)]


def array_manip(array):
	return [min(filter(lambda y: y > x, array[i + 1:]), default=-1) for (i, x) in enumerate(array)]


def array_manip(array):
	res = []
	for (i, n) in enumerate(array):
		try:
			res.append(min([x for x in array[i + 1:] if x > n]))
		except ValueError:
			res.append(-1)
	return res


array_manip = lambda a: [min([m for m in a[i + 1:] if m > n] or [-1]) for (i, n) in enumerate(a)]


def array_manip(array):
	result = []
	for i in range(len(array)):
		try:
			cr = array[i]
			mm = sorted((x for x in array[i + 1:] if x > cr))[0]
			result.append(mm)
		except:
			result.append(-1)
	return result


def array_manip(array):
	return [min(filter(lambda a: a > array[i], array[i + 1:]), default=-1) for i in range(len(array))]


class BinaryTree:

	def __init__(self, value, left=None, right=None, parent=None):
		self.value = value
		self.left = left
		self.right = right
		self.parent = parent

	def __str__(self):
		if self.left or self.right:
			s = '(' + str(self.value)
			sl = self.left or '#'
			sr = self.right or '#'
			for l in str(sl).split('\n'):
				s += '\n  ' + l
			for l in str(sr).split('\n'):
				s += '\n  ' + l
			return s + ')'
		else:
			return f'{self.value}'

	def add(self, val):
		if val < self.value:
			if self.left:
				return self.left.add(val)
			else:
				self.left = BinaryTree(val, parent=self)
				return self.left
		elif val > self.value:
			if self.right:
				return self.right.add(val)
			else:
				self.right = BinaryTree(val, parent=self)
				return self.right
		elif val == self.value:
			return self

	def leftmost(self):
		x = self
		while x.left:
			x = x.left
		return x

	def nxt(self):
		if self.right:
			return self.right.leftmost().value
		else:
			x = self.parent
			while x and x.value < self.value:
				x = x.parent
			if x:
				return x.value
		return -1

def array_manip(array):
	if not array:
		return []
	result = []
	b = BinaryTree(array[-1])
	for item in reversed(array):
		result.append(b.add(item).nxt())
	return result[::-1]