The hiring team aims to find 3 candidates who are great collectively. Each candidate has his or her ability expressed as an integer. 3 candidates are great collectively if product of their abilities is maximum. Given abilities of N candidates in an array arr[], find the maximum collective ability from the given pool of candidates.
Example 1:
Input:
N = 5
Arr[] = {10, 3, 5, 6, 20}
Output: 1200
Explanation:
Multiplication of 10, 6 and 20 is 1200.
Example 2:
Input:
N = 5
Arr[] = {-10, -3, -5, -6, -20}
Output: -90
Explanation:
Multiplication of -3, -5 and -6 is -90.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxProduct() which takes the array of integers arr[] and n as input parameters and returns the maximum product.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
3 ≤ N ≤ 10^{7}
-10^{5} ≤ Arr[i] ≤ 10^{5}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def maxProduct(self, arr, n):

        # code here

Solutions:
class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		return max(arr[-1] * arr[-2] * arr[-3], arr[0] * arr[1] * arr[-1])


class Solution:

	def maxProduct(self, arr, n):
		arr.sort(reverse=True)
		return max(arr[0] * arr[1] * arr[2], arr[0] * arr[n - 1] * arr[n - 2])


class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		(a, b, c, d, e) = (arr[0], arr[1], arr[n - 3], arr[n - 2], arr[n - 1])
		return max(a * b * e, c * d * e)


class Solution:

	def maxProduct(self, arr, n):
		temp = sorted(arr)
		return max(temp[0] * temp[1] * temp[2], temp[0] * temp[1] * temp[-1], temp[-1] * temp[-2] * temp[-3])


class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		for i in range(len(arr)):
			a = arr[-3] * arr[-2] * arr[-1]
			b = arr[0] * arr[1] * arr[-1]
			return max(a, b)


class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		if arr[0] < 0 and arr[1] < 0 and (arr[-1] > 0):
			return max(arr[0] * arr[1] * arr[-1], arr[-3] * arr[-2] * arr[-1])
		else:
			return arr[-3] * arr[-2] * arr[-1]


class Solution:

	def maxProduct(self, nums, n):
		nums.sort(reverse=True)
		return max(nums[0] * nums[1] * nums[2], nums[len(nums) - 1] * nums[len(nums) - 2] * nums[0])


class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		a1 = arr[0]
		a2 = arr[1]
		b = arr[n - 3]
		c = arr[n - 2]
		d = arr[n - 1]
		return max(a1 * a2 * d, b * c * d)


import heapq

class Solution:

	def maxProduct(self, arr, n):
		if n == 3:
			return arr[0] * arr[1] * arr[2]
		heapq.heapify(arr)
		mini1 = heapq.heappop(arr)
		mini2 = arr[0]
		heapq._heapify_max(arr)
		maxi1 = heapq._heappop_max(arr)
		maxi2 = heapq._heappop_max(arr)
		maxi3 = arr[0]
		return max(maxi1 * maxi2 * maxi3, maxi1 * mini1 * mini2)


import numpy as np

class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		aa = np.prod(arr[-3:])
		bb = np.prod(arr[:3])
		cc = np.product(arr[:2] + [arr[-1]])
		return max([aa, bb, cc])


class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		l = []
		a = arr[n - 1] * arr[n - 2] * arr[n - 3]
		l.append(a)
		b = arr[0] * arr[1] * arr[2]
		l.append(b)
		c = arr[n - 1] * arr[0] * arr[1]
		l.append(c)
		return max(l)


class Solution:

	def maxProduct(self, arr, n):
		a = sorted(arr)
		res = a[-1] * a[-2] * a[-3]
		res2 = a[0] * a[1] * a[-1]
		if res > res2:
			return res
		else:
			return res2


class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		n1 = arr[0]
		n2 = arr[1]
		p1 = arr[-1]
		p2 = arr[-2]
		p3 = arr[-3]
		if arr[-1] <= 0:
			return p1 * p2 * p3
		elif arr[0] >= 0:
			return p1 * p2 * p3
		t1 = n1 * n2 * p1
		t2 = p1 * p2 * p3
		return max(t1, t2)


class Solution:

	def maxProduct(self, arr, n):
		if len(arr) == 2:
			return arr[0] * arr[1]
		if len(arr) == 1:
			return arr[0]
		arr.sort()
		ans = max(arr[-1] * arr[-2] * arr[-3], arr[0] * arr[1] * arr[-1])
		return ans


class Solution:

	def maxProduct(self, arr, n):
		arr = sorted(arr)
		ans1 = arr[n - 1] * arr[n - 2] * arr[n - 3]
		ans2 = arr[0] * arr[1] * arr[n - 1]
		return max(ans1, ans2)


class Solution:

	def maxProduct(self, arr, n):
		a = sorted(arr)
		r = (a[-1] * a[-2] * a[-3], a[0] * a[-1] * a[1])
		return max(r)


import numpy as np
import math

class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		value1 = arr[-1] * arr[-2] * arr[-3]
		value2 = arr[0] * arr[1] * arr[2]
		value3 = -math.inf
		if arr[0] < 0 and arr[1] < 0:
			value3 = arr[0] * arr[1] * arr[-1]
		return max(value1, value2, value3)


class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		case1 = arr[-1] * arr[-2] * arr[-3]
		case2 = arr[0] * arr[1] * arr[-1]
		res = max(case1, case2)
		return res


class Solution:

	def maxProduct(self, arr, n):
		arr.sort(reverse=True)
		if n >= 3:
			product = arr[0] * arr[1] * arr[2]
			min_product = arr[0] * arr[-2] * arr[-1]
			if product > min_product:
				return product
			else:
				return min_product


class Solution:

	def maxProduct(self, arr, n):
		maxA = maxB = maxC = -float('inf')
		minA = minB = float('inf')
		for e in arr:
			if e >= maxA:
				(maxB, maxC) = (maxA, maxB)
				maxA = e
			elif e >= maxB:
				maxC = maxB
				maxB = e
			elif e > maxC:
				maxC = e
			if e < minA:
				minB = minA
				minA = e
			elif e < minB:
				minB = e
		return max(maxA * maxB * maxC, maxA * minA * minB)


class Solution:

	def maxProduct(self, arr, n):
		arr = sorted(arr)
		if arr[0] > 0:
			p = 1
			for i in range(0, 3):
				p = p * arr[i]
			return p
		elif arr[0] < 0 and arr[n - 1] > 0:
			return max(arr[0] * arr[1] * arr[n - 1], arr[n - 3] * arr[n - 2] * arr[n - 1])
		else:
			return arr[n - 3] * arr[n - 2] * arr[n - 1]


class Solution:

	def maxProduct(self, arr, n):
		maxms = [float('-inf')] * 3
		minms = [float('inf')] * 3
		for x in arr:
			if x > maxms[0]:
				maxms[2] = maxms[1]
				maxms[1] = maxms[0]
				maxms[0] = x
			elif x > maxms[1]:
				maxms[2] = maxms[1]
				maxms[1] = x
			elif x > maxms[2]:
				maxms[2] = x
			if x < minms[0]:
				minms[2] = minms[1]
				minms[1] = minms[0]
				minms[0] = x
			elif x < minms[1]:
				minms[2] = minms[1]
				minms[1] = x
			elif x < minms[2]:
				minms[2] = x
		return max(maxms[0] * maxms[1] * maxms[2], maxms[0] * minms[1] * minms[0])


class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		n = len(arr)
		x = arr[0] * arr[1] * arr[n - 1]
		y = arr[n - 1] * arr[n - 2] * arr[n - 3]
		if x >= y:
			return x
		else:
			return y


class Solution:

	def maxProduct(self, arr, n):
		max1 = float('-inf')
		max2 = float('-inf')
		max3 = float('-inf')
		min1 = float('inf')
		min2 = float('inf')
		for u in arr:
			if u >= max1:
				max3 = max2
				max2 = max1
				max1 = u
			elif u >= max2:
				max3 = max2
				max2 = u
			elif u > max3:
				max3 = u
			if u <= min1:
				min2 = min1
				min1 = u
			elif u < min2:
				min2 = u
		return max(max1 * max2 * max3, min1 * min2 * max1)


class Solution:

	def maxProduct(self, arr, n):
		arr.sort()
		p1 = arr[n - 1] * arr[n - 2] * arr[n - 3]
		p2 = arr[0] * arr[1] * arr[n - 1]
		if p1 < p2:
			return p2
		else:
			return p1