Given an array of integers of size N. For each ith element in the array, calculate the absolute difference between the count of numbers that are to the left of i and are strictly greater than ith element, and the count of numbers that are to the right of i and are strictly lesser than ith element.
Example 1:
Input:
N = 5
A[] = {5, 4, 3, 2, 1}
Output: 4 2 0 2 4 
Explanation: We can see that the 
required number for the 
1st element is |0-4| = 4
Example 2:
Input:
N = 5
A[] = {1, 2, 3, 4, 5}
Output: 0 0 0 0 0
Explanation: There is no greater 
element on the left for any element 
and no lesser element on the right.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function greaterLesser() which takes the array arr[], its size Nas input parameters and returns the required array.
Expected Time Complexity: O(N log N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
-10^{9}^{ }≤ arr[i] ≤ 10^{9}
Array can contain duplicate elements.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Range queries

Segment trees revisited

Starter code: #User function Template for python3



class Solution:

    def greaterLesser (self, A, N):

        # code here 

Solutions:
from bisect import bisect, bisect_left

class Solution:

	def greaterLesser(self, A, N):
		output = []
		left = []
		for item in A:
			i = bisect(left, item)
			output.append(len(left) - i)
			left.insert(i, item)
		right = []
		for (i, item) in enumerate(A[::-1]):
			j = bisect_left(right, item)
			right.insert(j, item)
			output[-i - 1] = abs(output[-i - 1] - j)
		return output


class Solution:

	class Seg_Tree:

		def __init__(self, n, arr):
			self.n = n
			self.arr = arr
			self.tree = [0] * (n * 4 + 4)

		def build(self, s, e, idx):
			if s == e:
				self.tree[idx] = self.arr[s]
				return
			mid = s + (e - s) // 2
			self.build(s, mid, 2 * idx)
			self.build(mid + 1, e, 2 * idx + 1)
			self.tree[idx] = self.tree[2 * idx] + self.tree[2 * idx + 1]

		def update(self, pos, v, s, e, idx):
			if pos < s or pos > e:
				return
			if s == e:
				self.tree[idx] += 1
				return
			mid = s + (e - s) // 2
			self.update(pos, v, s, mid, 2 * idx)
			self.update(pos, v, mid + 1, e, 2 * idx + 1)
			self.tree[idx] = self.tree[2 * idx] + self.tree[2 * idx + 1]

		def query(self, qs, qe, s, e, idx):
			if qs <= s and qe >= e:
				return self.tree[idx]
			if qs > e or qe < s:
				return 0
			mid = s + (e - s) // 2
			return self.query(qs, qe, s, mid, 2 * idx) + self.query(qs, qe, mid + 1, e, 2 * idx + 1)

	def solve(self, arr, n):
		A = [0] * (n + 1)
		mp = dict()
		for i in range(n):
			mp[arr[i]] = 0
		c = 0
		for i in sorted(mp):
			c += 1
			mp[i] = c
		for i in range(1, n + 1):
			A[i] = mp[arr[i - 1]]
		res = []
		obj = self.Seg_Tree(n, arr)
		for i in range(1, n + 1):
			obj.update(A[i], 1, 1, n, 1)
			res.append(obj.query(A[i] + 1, n, 1, n, 1))
		return res

	def greaterLesser(self, A, N):
		left = []
		right = []
		ans = []
		left = self.solve(A, N)
		temp = []
		for i in range(N):
			temp.append(-A[N - i - 1])
		right = self.solve(temp, N)
		for i in range(N):
			ans.append(abs(left[i] - right[N - i - 1]))
		return ans


from bisect import bisect_left, bisect_right

class Solution:

	def greaterLesser(self, A, N):
		right = [0] * N
		res = []
		for i in range(N - 1, -1, -1):
			j = bisect_left(res, A[i])
			right[i] = j
			res.insert(j, A[i])
		left = [0] * N
		res = []
		for i in range(N):
			j = bisect_right(res, A[i])
			left[i] = abs(len(res) - j - right[i])
			res.insert(j, A[i])
		return left